《试探法(回溯法).docx》由会员分享，可在线阅读，更多相关《试探法(回溯法).docx（6页珍藏版）》请在金锄头文库上搜索。
1、程序数据结构+算法软件程序+文档试探法（回溯法）是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来解，可以利用试探的技术求解。试探法是搜索算法中的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况进行试探，在试探过程中，一旦发现原来的选择的假设情况是错误的，就退回一步重新选择，继续向前试探，如此反复进行，直至得到解或证明无解。试探算法一般也采用递归形式编写程序。一般的递归试探法算法结构如下：对解集合中的各解进行试探if(满足条件)保存结果if(完成集合中所有解的试探)输出解else重复本过程进行下一步的试探(递归调用本函数)else恢复至上一步保存结果之前的状态，
2、进行另一步试探(递归调用本函数)实例：生成彩票号码组合常见的彩票号码都是由一些数字组成的，生成彩票号码其实就是将所有数字进行不同的组合。例如，假设有一种彩票，每注由7个1-29的数字组成，且这7个数字不能相同，编写程序生成所有的号码组合。解法一（使用循环嵌套生成彩票组合）：#include#include void main()int i7,j;for(i0=1;i0=29;i0+)for(i1=1;i1=29;i1+)if(i0=i1)continue;for(i2=1;i2=29;i2+)if(i0=i2|i1=i2)continue;for(i3=1;i3=29;i3+)if(i0=i3
3、|i1=i3|i2=i3)continue;for(i4=1;i4=29;i4+)if(i0=i4|i1=i4|i2=i4|i3=i4)continue;for(i5=1;i5=29;i5+)if(i0=i5|i1=i5|i2=i5|i3=i5|i4=i5)continue;for(i6=1;i6=29;i6+)if(i0=i6|i1=i6|i2=i6|i3=i6|i4=i6|i5=i6)continue;for(j=0;j7;j+)printf(%3d,ij);printf(n);getch();执行结果：从上例代码可看出，程序代码很繁琐，且程序不具有通用性。例如，要将程序改为生成5位数的不
4、同组合，就需要删除其中的两层循环。其实，解决这类问题更好的办法是使用试探法，逐步计算出所有可能的组合。首先分析可按如下顺序生成彩票号码：29 28 27 26 25 24 2329 28 27 26 25 24 2229 28 27 26 25 24 2129 28 27 26 25 24 2029 28 27 26 25 24 129 28 27 26 25 23 22从上面列出的顺序可看出，生成组合时，首先变化最后一位（第7位），当最后一位数为1时，将回溯计算倒数第二位（第6位），使该位（第6位）减少1，然后再变化最后一位数（第7位），通过这样的递归调用，即可生成所有的号码组合。解法二（使
5、用试探法生成彩票组合）：#include#include #define MAXN 3/设置每一注彩票的位数#define NUM 5/设置组成彩票的数字int numNUM;int lotteryMAXN;void combine(int n,int m)int i,j;for(i=n;i=m;i-)lotterym-1=numi-1;/保存一位数字if(m1)combine(i-1,m-1);else/若m=1,输出一注号码for(j=MAXN-1;j=0;j-)printf(%3d,lotteryj);getch();printf(n);int main()int i,j;for(i=0
6、;iNUM;i+)numi=i+1;for(i=0;iMAXN;i+)lotteryi=0;combine(NUM,MAXN);getch();return 0;执行结果：现在用5个数字产生3个数字的组合来演示程序执行的过程MAXN=3NUM=5 i i 5lottery2=num4=5 4lottery1=num3=4 i n,m n,m 3lottery0=lottery2=3543combine(4,2)combine(3,1) 2lottery0=lottery1=2542 1lottery0=lottery0=1541 i 3 lottery1=num2=3 2 lottery0=l
7、ottery1=2532 n,m 1 lottery0=lottery0=1531combine(2,1) n,mcombine(5,3) 2 lottery1=num1=2 i n,m 1 lottery0=lottery0=1521combine(1,1) i 4lottery2=num3=4 3 lottery1=num2=3 i n,m n,m 2 lottery0=lottery1=2432combine(3,2)combine(2,1) 1 lottery0=lottery0=1431 2 lottery1=num1=2 i n,m 1 lottery0=lottery0=1421combine(1,1) 3lottery2=num2=3 i n,m 2 lottery1=num1=2 icombine(3,2) n,m 1 lottery0=lottery0=1321combine(1,1)程序执行情况
