《试探法(回溯法)》由会员分享，可在线阅读，更多相关《试探法(回溯法)（6页珍藏版）》请在金锄头文库上搜索。
1、程序数据结构+算法软件程序+文档试探法（回溯法）是计算机解题中常用的算法，很多问题无法根据某种确定的计算法 则来解，可以利用试探的技术求解。试探法是搜索算法中的一种控制策略。它的基本思想 是：为了求得问题的解，先选择某一种可能情况进行试探，在试探过程中，一旦发现原来 的选择的假设情况是错误的，就退回一步重新选择，继续向前试探，如此反复进行，直至 得到解或证明无解。 试探算法一般也采用递归形式编写程序。一般的递归试探法算法结构如下：对解集合中的各解进行试探 if(满足条件) 保存结果 if(完成集合中所有解的试探) 输出解 else重复本过程进行下一步的试探(递归调用本函数) else恢复至上一
2、步保存结果之前的状态，进行另一步试探(递归调用本函数) 实例：生成彩票号码组合 常见的彩票号码都是由一些数字组成的，生成彩票号码其实就是将所有数字进行不同 的组合。例如，假设有一种彩票，每注由 7 个 1-29 的数字组成，且这 7 个数字不能相同， 编写程序生成所有的号码组合。 解法一（使用循环嵌套生成彩票组合）：#include #include void main() int i7,j; for(i0=1;i0 #include #define MAXN 3/设置每一注彩票的位数 #define NUM 5/设置组成彩票的数字 int numNUM; int lotteryMAXN;vo
3、id 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;iNUM;i+) numi=i+1; for(i=0;iMAXN;i+) lotteryi=0; combine(NUM,MAXN); getch(); return 0; 执
4、行结果：现在用 5 个数字产生 3 个数字的组合来演示程序执行的过程MAXN=3NUM=5i i5lottery2=num4=5 4lottery1=num3=4 in,m n,m 3 lottery0=lottery2=3543 combine(4,2)combine(3,1) 2 lottery0=lottery1=25421 lottery0=lottery0=1541i3 lottery1=num2=3 2 lottery0=lottery1=2532n,m 1 lottery0=lottery0=1531 combine(2,1)n,m combine(5,3) 2 lottery1
5、=num1=2 in,m 1 lottery0=lottery0=1521 combine(1,1) i4lottery2=num3=4 3 lottery1=num2=3 in,m n,m 2 lottery0=lottery1=2432 combine(3,2)combine(2,1) 1 lottery0=lottery0=14312 lottery1=num1=2 in,m 1 lottery0=lottery0=1421 combine(1,1) 3lottery2=num2=3 in,m 2 lottery1=num1=2 i combine(3,2) n,m 1 lottery0=lottery0=1321 combine(1,1)程序执行情况
