问题
假设有一种29选7的彩票，每注由7个1~29的数字组成，而且这7个数字不能重复，编写程序输出所有的号码组合。
思路
还是用试探法解决问题的应用场景。组合嘛，只要不重复就行，所以这个问题就变成了输出7个不重复的1到29之间的数字就行。因为总共有7个位置嘛，每个位置有29种可能，所以你只需要尝试729次，每次判断是不是各个位的数组有相同的，如果都不同就说明找到了一个组合，但是这个方法太暴力了，也太费劲了，时间上伤不起啊。所以要换一种方法，你只要保证每次不同就行，这样首先把这7个位置上放上29~23这个七个数字，而且是顺序的。现在就一般的情况来谈谈，假设现在只有2个位置，也是这样顺序摆放，你会发现一开始相邻的两个位置上一开始就是不同的，然后再把较小的数字减一，这样相邻的2个位置的数字还是不同的，小的一边减到1，此时小的一边减无可减，于是把大的一边减一，此时小的一边再按此法不断减一直到1就得到一个组合，以此类推每一次变化就是一个组合，最后大的一边是2，于是所有情况就都被列举出来了。推而广之，这七个位置也是一样的，只要最大的那一边没有减到7算法就一直这样持续下去。这个算法的实现可以用循环来完成，也可以用递归来实现，本次我想用递归来实现。那么如何递归呢？这个实际上是个什么过程呢？这个就是减法的借位过程只不过每个位发生借位的上限不同，而且还是动态的。借位嘛，大家都知道最后一位的变化速度是最快的，并且每次下越界的时候就向前一位借位。现在考虑第i位，它每一次减都会促使i+1位从第i位当前值-1开始逐次减1。第i位减到什么时候就得借位了呢？假设总共有n位，那第i位的最小值就是n-i。但是如果你要是既考虑低位又考虑高位的事情，那就没法递归了，这个递归必须是单向的。所以你只需要考虑低位的事情，即，本位每减一次就让低位自己递减去，我姑且把本位的最大值称之为iMax，则本位的递减范围就是[iMax,n-i]，注意这里是闭区间。到最后其实是最低位每变化一次就输出一次整个数组，于是最初的输入就是最大的那个数即29，然后数组的元素个数也叫维度，只要检测到这是最后一位就打印呗，很简单这就是个判断，于是看代码就行了。由于这个打印结果太多太长，控制台缓冲区放不下，于是只能把打印结果输出到文件了，文件是我在桌面建立的叫做outPrinters.txt。
使用
package com.company;
public class Main {
public static void main(String[] args) {
// write your code here
Solution.lotteryCombination(29,7);
}
}
实现
package com.company;
import java.io.FileOutputStream;
import java.io.PrintWriter;
public class Solution {
/**
* 使用试探法解决29选7彩票问题
*/
static public void lotteryCombination(int maxNumber,int lotteryCounter) {
if (lotteryCounter <= 0 || maxNumber < lotteryCounter) {
System.out.println("输入错误");
return;
}
int[] combination = new int[lotteryCounter];
try {
PrintWriter out= new PrintWriter(new FileOutputStream(System.getProperties().getProperty("user.home") + "/Desktop/outPrinters.txt"));
Solution.calculation(combination,maxNumber,lotteryCounter,out);
out.close();
} catch (Exception e) {
System.out.println(e.toString());
}
}
/**
* 递归函数
* @param combination
* @param maxValue
* @param columnCounter
* @param printWriter
*/
static private void calculation(int[] combination,int maxValue,int columnCounter,PrintWriter printWriter) {
for (int counter = maxValue;counter >= columnCounter;counter--) {
combination[combination.length - columnCounter] = counter;
if (columnCounter == 1) {
for (int element:combination)printWriter.print(element + " ");
printWriter.println();
} else {
Solution.calculation(combination,counter - 1,columnCounter - 1,printWriter);
}
}
}
}
输出
