关注微信公众号:“编码美丽”技术干货实时推荐,欢迎访问我的github:点击进入

数据结构和算法设计专题之—24点游戏(穷举法和递归法)

数据结构和算法 jiangwei212 1312℃ 0评论

一个简单的24点程序

       下面本文将通过两个题目实例,分别给出用递归方法和循环方法的解决方案以及解题思路,便于读者更好地掌握两种方法。首先是一个简单的计算24点的问题(为了简化问题,我们假设只使用求和计算方法):

19中任选四个数字(数字可以有重复),使四个数字的和刚好是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(= NUM_MIN_VALUE; i <= NUM_MAX_VALUE; i++)

   46     {

   47         numbers[0] = i; /*确定第一个数字*/

   48         for(= NUM_MIN_VALUE; j <= NUM_MAX_VALUE; j++)

   49         {

   50             numbers[1] = j;  /*确定第二个数字*/

   51             for(= NUM_MIN_VALUE; k <= NUM_MAX_VALUE; k++)

   52             {

   53                 numbers[2] = k; /*确定第三个数字*/

   54                 for(= 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(= NUM_MIN_VALUE; i <= NUM_MAX_VALUE; i++)

   72     {

   73         numbers[level] = i;

   74         if(level == (NUMBER_COUNT  1))

   75         {

   76             if(== 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的值改成9FULL_NUMBER_VALUE的值改成45即可,算法主体部分不需做任何修改。

转载请注明:尼古拉斯.赵四 » 数据结构和算法设计专题之—24点游戏(穷举法和递归法)

喜欢 (1)or分享 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址