代码意识流——花朵数问题(二)

 

6.准备写qiongju()函数

     因为要解决的问题对时间的要求以及计算对象是21位数，所以不难想象这个函数可能比较复杂。不可能一蹴而就，所以在编写前首先要考虑测试。
     在测试用的main()内添加函数调用qiongju();作为测试驱动。

#ifdef CESHI //测试
   int main( void )
   {
      qiongju();
      system("PAUSE");
      return 0;
   }

#endif //CESHI

     把 0_问题.h 中的

#define QIUJIE

中的 QIUJIE 改成CESHI ,编译运行通过 。这表明文件包含及qiongju()函数原型等方面均没什么问题，也就是说完成了对qiongju()函数测试的环境搭建。
     下面转到 2_穷举.c 源文件中，填充那个空着的qiongju()函数定义。

 

7.对穷举方案的思考
  
    最容易想到的穷举方案是

    方案1.

    for(W_ws=最小W位数;W_ws<=最大W位数;W_ws++)
      {
         //验算
      }

    这种方案首先需要解决W位数的表示问题，即设计存储这种数据的数据类型的问题。
    此外还需要考虑这种数据如何赋值、加1及比较大小等问题。
    最主要的，还需要解决解的搜索空间过大的问题。
    一下子同时解决这几个问题总是让人有些生畏（但也并非不能解决），因此暂不考虑。

第二种方案用循环嵌套的方式进行穷举
   方案2.

   for(第1位数=1;第1位数     for(第2位数=0;第2位数        ……
       for(第W位数=0;第W位数       {
            //验算
       }

   这种方案在一开始不必考虑W位数的表示问题，但解的搜索空间依然很大。
   解空间巨大的原因是穷举给出的是各位数的排列，这是一个相当巨大的数目 （(JINZHI-1)

*JINZHI^(W-1)，对21位十进制数来说，这个值是9*10^20）。然而各种排列中有相当一部分，其各位数N次方的和是相同的(以3位数为例，110和101各位数的3次方之和都为2)，不应该重复计算这些数各位数N次方的和。
   为了避免重复计算这些值，应该只验算各位数字的各种组合而不是对各位数字的排列进行验算。

   为此，可将穷举的循环结构改良为

   方案2-1.
   for(第1位数=JINZHI-1;第1位数>0;第1位数--)
      for(第2位数=第1位数;第2位数>=0;第2位数--)
         ……
        for(第W位数=第W-1位数;第W位数>=0;第W位数--)
        {
           //验算
        }         
    这个结构由于保证了各位数字均不大于前面的各位数字，所以得到的是W位数的各种组合。解的搜索空间大大降低（对21位十进制数，只有14307149(30!/9!/21!-1)种可能）。
    此时验算的方法要稍微复杂一些。例如对于3位数情况，循环嵌套给出的数字组合可能为531，求出5、3、1这3个数字的3次方之和为153，由于153中各个数字出现个数与最初的数字组合531中各个数字出现的个数完全一致，因此即可判定153满足花朵数条件。 
    这种方案比较形象直观，容易理解。 

    既然第二种方案在本质上无非是给出各位数字的各种组合，那么也许不如索性更直接一些。第3种方案虽然略有些抽象但却更加直接。
    方案3.
　　    for( 数字(JINZHI-1)的个数=0 ; 数字(JINZHI-1)的个数<=总位数 ; 数字(JINZHI-1)的个数++)
       　　for( 数字(JINZHI-2)的个数=0 ;数字(JINZHI-2)的个数<=总位数-数字(JINZHI-1)的个数 ; 数字(JINZHI-2)的个数++ )
         　　 ……
         　　for( 数字1的个数=0 ; 数字1的个数<=总位数-前面各数字个数之和 ; 数字1的个数++)
        　　 {
              　　//数字0的个数= 总位数-前面各数字个数之和
              　　//<=>验算<=>记录结果
         　　}

    当JINZHI势。因此后面采用这种方案。 

      
8.测试方案可行性

　　对3进制5位数情况测试方案是否可行。因为是3进制，所以是两层循环嵌套，穷举的数字为2,1,0；因为是5位数，所以每种数字的个数可能为0~5个。
   

/*2_穷举.c*/
#include "2_穷举.h"

extern void qiongju( void )
{
   //<=>验算<=>记录结果
   #ifdef CESHI
   int n2; //n2:2的个数
   for( n2 = 0 ; n2 <= 5 ;n2++ ){ //5位数
      int n1;
      printf("%d个%d ",n2 ,3 - 1 ) ; //3进制
      for( n1 = 0 ; n1 <= 5-n2 ;n1 ++ ){ //n1:1的个数
         int n0;
         printf("%d个%d ",n1 ,3 - 2 );
         {
         n0 = 5 - n2 - n1 ; //n0:0的个数
         printf("%d个%d",n0 ,3 - 3 );
         putchar('\n');
         }
      }
   }
   #endif //CESHI
}

 　运行结果符合期待，表明方案可行。 
        
9.把嵌套改成递归         

　　 循环嵌套只能描述固定层数的嵌套结构，所以前面的方案只能写出某特定进制的情况（3进制2层循环……10进制9层循环）。如果希望代码对不同进制的问题都成立，需要把循环的嵌套改成函数的递归，即用函数描述每一层循环及最内层的循环体部分的运算。递归调用很容易利用变量控制嵌套的层数。
　　即使是只考虑十进制的情况，这样的修改也是必要的。因为循环嵌套的结构复杂、繁琐，不利于修改（后面应该还有许多内容需要添加）和维护。况且，写9层循环多少有些让人不寒而栗，至少对我来说是这样，不痛下决心是没勇气写9层循环嵌套的。
　　每一层循环（包括最内层的循环体）都需要两个参数确定:枚举的是哪个数字，这个数字的个数最多有几个（上限）。以第一层循环为例

   for( n2 = 0 ; n2 <= 5 ;n2++ ){  //5位数
      int n1; 
      printf("%d个%d ",n2 ,3 - 1 ) ; //3进制 
  　　　　 ……
   }
　　需要5、3-1 这两个参数。第二层循环和最内层的循环体同样需要这两个参数。 
　　对于函数的递归调用来说，获得这些参数的的途径可能有三种：函数调用的实参，外部变量，局部static变量。最常用的是第一种，外部变量的办法通常是写不出手的，局部static变量的办法写起来要稍微困难一点。

　　"2_穷举.c"的第二版为

/*2_穷举.c*/
#include "2_穷举.h"
#include "0_问题.h" //用到了WEISHU , JINZHI

static void xunhuan(const int ,const int ) ;

//改循环嵌套为函数递归
extern void qiongju( void )
{
  xunhuan( WEISHU , JINZHI-1 ) ;
}

static void xunhuan( const int gs_sx /*个数上限*/,
                     const int sz /*关于哪个数字*/)
{
   if( sz > 0 ){
      int i;
      for( i = 0 ; i <= gs_sx ; i++ ){
         #ifdef CESHI
          printf("%d个%d " , i , sz );
         #endif //CESHI
         xunhuan( gs_sx - i , sz - 1 );
      }
   }
   else{
      #ifdef CESHI
       printf("%d个%d " , gs_sx , sz );
       putchar('\n');
      #endif //CESHI
      //<=>验算<=>记录结果
   }
}

　　测试:对10进制3位数情况测试，输出正确。
　　到此，穷举部分基本完成。

 

10.去除递归调用的参数

 

　　考虑到函数传递参数比较慢，所以改用另一种方式实现递归——使用static 局部变量传递参量。修改之后的代码不再需要xunhuan()这个函数

/*2_穷举.c*/
#include "2_穷举.h"
#include "0_问题.h" //用到了QIUJIE、WEISHU

extern void qiongju( void )
{
  static int sz = JINZHI , gs_sx ; /*关于哪个数字 ,该数字个数的上限*/
  switch ( sz ) {
     case JINZHI :
         gs_sx = WEISHU ;
         sz -- ;
         qiongju();
         sz = JINZHI ;
         return ;
     default :
         {
            int i ;
            for( i = 0 ; i <= gs_sx ; i++ ){
               #ifdef CESHI
                 printf("%d个%d " , i , sz );
               #endif //CESHI
               sz -- ;
               gs_sx -= i ;
               qiongju ();
               gs_sx += i ;
               sz ++ ;
            }
            return ;
         }
     case 0 :
         #ifdef CESHI
          printf("%d个%d " , gs_sx , sz );
          putchar('\n');
         #endif //CESHI
         //<=>验算<=>记录结果
         return ;
  }
}