一个简单的24点程序
下面本文将通过两个题目实例，分别给出用递归方法和循环方法的解决方案以及解题思路，便于读者更好地掌握两种方法。首先是一个简单的计算24点的问题（为了简化问题，我们假设只使用求和计算方法）：
从1－9中任选四个数字（数字可以有重复），使四个数字的和刚好是24。
题目很简单，数字都是个位数，可以重复且之用加法，循环算法的核心就是使用四重循环穷举所有的数字组合，对每一个数字组合进行求和，判断是否是24。使用循环的版本可能是这个样子：
|
8 const unsigned int NUMBER_COUNT = 4; //9 9 const int NUM_MIN_VALUE = 1; 10 const int NUM_MAX_VALUE = 9; 11 const unsigned int FULL_NUMBER_VALUE = 24;//45; 40 void PrintAllSResult(void) 41 { 42 int i,j,k,l; 43 int numbers[NUMBER_COUNT] = { 0 }; 44 45 for(i = NUM_MIN_VALUE; i <= NUM_MAX_VALUE; i++) 46 { 47 numbers[0] = i; /*确定第一个数字*/ 48 for(j = NUM_MIN_VALUE; j <= NUM_MAX_VALUE; j++) 49 { 50 numbers[1] = j; /*确定第二个数字*/ 51 for(k = NUM_MIN_VALUE; k <= NUM_MAX_VALUE; k++) 52 { 53 numbers[2] = k; /*确定第三个数字*/ 54 for(l = NUM_MIN_VALUE; l <= NUM_MAX_VALUE; l++) 55 { 56 numbers[3] = l; /*确定第四个数字*/ 57 if(CalcNumbersSum(numbers, NUMBER_COUNT) ==FULL_NUMBER_VALUE) 58 { 59 PrintNumbers(numbers, NUMBER_COUNT); 60 } 61 } 62 } 63 } 64 } 65 } |
这个PrintAllSResult()函数看起来中规中矩，但是本人的编码习惯很少在一个函数中使用超过两重的循环，更何况，如果题目修改一下，改成9个数字求和是45的组合序列，就要使用9重循环，这将使PrintAllSResult()函数变成臭不可闻的垃圾代码。
现在看看如何用递归方法解决这个问题。递归方法的解题思路就是对题目规模进行分解，将四个数字的求和变成三个数字的求和，两个数字的求和，当最终变成一个数字时，就达到了递归终止条件。这个题目的递归解法非常优雅：
|
67 void EnumNumbers(int *numbers, int level, int total) 68 { 69 int i; 70 71 for(i = NUM_MIN_VALUE; i <= NUM_MAX_VALUE; i++) 72 { 73 numbers[level] = i; 74 if(level == (NUMBER_COUNT – 1)) 75 { 76 if(i == total) 77 { 78 PrintNumbers(numbers, NUMBER_COUNT); 79 } 80 } 81 else 82 { 83 EnumNumbers(numbers, level + 1, total – i); 84 } 85 } 86 } 87 88 void PrintAllSResult2(void) 89 { 90 int numbers[NUMBER_COUNT] = { 0 }; 91 92 EnumNumbers(numbers, 0, FULL_NUMBER_VALUE); 93 } |
如果题目改成“9个数字求和是45的组合序列”，只需将NUMBER_COUNT的值改成9，FULL_NUMBER_VALUE的值改成45即可，算法主体部分不需做任何修改。
转载请注明：尼古拉斯.赵四 » 数据结构和算法设计专题之—24点游戏(穷举法和递归法)
