试探算法

回溯算法(又叫试探算法)

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

 

实例:生成彩票号码组合.

     假设有一种彩票,每注由7个1-29的数字组成,且这7个数字不能相同,编写程序生成所有的号码组合.

 

Java代码描述:

public class Test {

	public static int MAXN = 7;		//设置每一组彩票的位数
	public static int NUM = 29;		//设置组成彩票的数字
	public static int[] num = new int[NUM]; 
	public static int[] lottery = new int[MAXN]; 
	
	public static void main(String[] args) {
		
		int i,j;
		for(i=0;i<NUM;i++){		//设置彩票各位数字
			num[i] = i+1;
		}
		for(j=0;j<MAXN;j++){
			lottery[j] = 0;
		}
		combine(NUM,MAXN);
		
	}
	public static void 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--){
					System.out.print(lottery[j]+"  ");
				}
				System.out.println();
			}
		}
	}
	
}

 运行结果:

 以上程序结束后,将会列出所有可能出现的点数.此情景也可通过穷举实现.