试探算法_生成彩票号码(C语言)

女爷i 2021-11-23 15:12 541阅读 0赞

试探算法(回溯法)的算法思路：为了求得问题的解，先选择某一种可能情况进行试探，在试探的过程中，一旦发现原来的选择的假设情况是错误的，就退回一步重新选择，继续向前试探，如此反复进行，直到得到解或证明无解。

实例：生成彩票号码组合  
假设有一种彩票，每注由7个1~29的数字组成，且这7个数字不能相同，编写程序生成所有的号码组合。

思想：为求解，先选择某一种情况试探，试探过程中，一旦发现原来的选择的假设情况是错误的，就退回一步重新选择，继续向前试探，如此反复进行，直至得到解或证明无解。  
如：迷宫探路  
算法结构：  
对解集合中的各解进行试探\{  
if（满足条件）\{  
保存结果  
if（完成集合中所有解的试探）  
输出解  
else  
重复本过程进行下一步的试探（递归调用本函数）  
\}  
else  
恢复上一步保存结果之前的状态，进行另一部试探（递归调用本函数）  
\}

C语言相关代码：

#include<stdio.h>
    #define MAXN 7 //设置每一注彩票的位数 
    #define  NUM 29 //设置够成彩票的数字
    int num[NUM];   //用来保存所有的彩票数字 
    int lottery[MAXN]; //用来保存每一注彩票对应的数字 
    int combine(int n,int m);
    int combine(int n,int m)
    {
     	int i,j;
    	 for(i=n;i>=m;i--)
    	 {
    	 	lottery[m-1]=num[i-1]; //保存一位数字 
    	 	if(m>1)
    	 		combine(i-1,m-1);
    	 	else               //若m=1，输出一注号码 
    	 	{
    	 		for(j=MAXN-1;j>=0;j--)
    	 			printf("%3d",lottery[j]);
    	 		//getchar();
    	 		printf("\n");
    		 }
    	 }
    }
    int main()
    {
    	int i,j;
    	for(i=0;i<NUM;i++) //将彩票中的数字分别保存进去 
    		num[i]=i+1;
    	for(i=0;i<MAXN;i++) //将彩票号码的数组，每一位都清零 
    		lottery[i]=0;
    	combine(NUM,MAXN);
    	return 0;
    }