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

11.完成qiongju()函数的框架
    除了对数字的各种组合进行穷举，qiongju()函数还需要完成计算各数字N次方之和并验算是否满足花朵数条件这两个功能。用伪代码表示就是

/*2_穷举.c*/
#include "2_穷举.h"
#include "0_问题.h" //用到了QIUJIE、WEISHU
extern void qiongju( void )
{
  static int sz = JINZHI , gs_sx ; /*关于哪个数字 ,该数字个数的上限*/
  //static 数据类型 各数字N次方和 ;
  switch ( sz ) {
     case JINZHI : //递归准备工作
         gs_sx = WEISHU ;
         sz -- ;
         //各数字N次方和 = 0 ;
         qiongju();
         sz = JINZHI ;
         return ;
     default : //递归过程
         {
            int i ;
            for( i = 0 ; i <= gs_sx ; i++ ){
               //求和
               //各数字N次方和 += i * sz^N ;
               sz -- ;
               gs_sx -= i ;
               qiongju ();
               //各数字N次方和 -= i * sz^N ;
               gs_sx += i ;
               sz ++ ;
            }
            return ;
         }
     case 0 : //递归终止
         //<=>验算<=>记录结果
         //验证是否满足花朵数条件：
         //判断 各数字N次方和 中的数字是否与构成组合的数字集一致
         return ;
  }
}

     //static 数据类型 各数字N次方和 ;
     由于“各数字N次方和”可能很大，通常的数据类型无法描述，所以必须建立新的数据类型来描述这种数据。这种类型用于表示并存储较大的整数，所以命名为DASHU_t(大数)。由于各次递归调用传递数据的需要，所以必须定义成static存储类别。
     之后为 各数字N次方和 取名为 he_szNf。
     //static 数据类型 各数字N次方和 ;
==》//static DASHU_t he_szNf ; //各数字N次方和 ;

12.进一步的分析   
     一种新的数据类型如何定义，不仅决定于这种类型存储什么样的数据，而且要受到这种数据将要进行的运算的约束。为此需要考察分析在qiongju()函数中he_szNf 都需要做哪些运算。
     //各数字N次方和 = 0 ;
     这里需要对  各数字N次方和 赋值，这里需要写一个函数完成赋值功能。

     //各数字N次方和 += i * sz^N ;
    这里要求计算 各数字N次方和 与 i * sz^N的和。i * sz^N 与 he_szNf一样可能是一个很大的非负整数，因此可考虑用同样的类型描述。

    由于在递归过程中i * sz^N这个值可能反复用到，每次都计算这个值势必徒增无谓的运行时间。所以应该在递归之前计算并存储起来，这就是所谓空间换时间。
    由于对每个数字需要 sz^N，2*sz^N……WEISHU*sz^N(0*sz^N不需要)这些值,且一共有JINZHI个数字,因而可以把这些数据组织成数组
    static DASHU_t N次幂倍数表[JINZHI-1][WEISHU]；
    数组的第一维尺寸为JINZHI-1是因为数字0计算时不用考虑。 定义为static 的原因同样是因为这些数据在各层递归中都要用到。

13.N次幂倍数表的定义和初始化
   在qiongju()给出数组定义 N次幂倍数表(Ncimi_bsb) 的定义之后需要考虑这个数组的初始化问题。这个数组显然应该在case JINZHI :部分初始化。伪代码如下

extern void qiongju( void )
{
  static int sz = JINZHI , gs_sx ; /*关于哪个数字 ,该数字个数的上限*/
  //static DASHU_t he_szNf ;//static 数据类型 he_szNf ; //各数字N次方和 ;
  //static DASHU_t Ncimi_bsb[JINZHI-1][WEISHU]；//N次幂倍数表[JINZHI-1][WEISHU]；
  switch ( sz ) {
     case JINZHI : //递归准备工作
         gs_sx = WEISHU ;
         sz -- ;
         // 各数字N次方和 = 0 ;
         // 初始化 ( Ncimi_bsb ) ;
         qiongju();
         sz = JINZHI ;
         return ;
     default : //递归过程
         {
            int i ;
            for( i = 0 ; i <= gs_sx ; i++ ){
               //求和
               //各数字N次方和 += i * sz^N ;
               sz -- ;
               gs_sx -= i ;
               qiongju ();
               //各数字N次方和 -= i * sz^N ;
               gs_sx += i ;
               sz ++ ;
            }
            return ;
         }
     case 0 : //递归终止
         //<=>验算<=>记录结果
         //验证是否满足花朵数条件：
         //判断 各数字N次方和 中的数字是否与构成组合的数字集一致
         return ;
  }
}

     不难想到，调用 初始化 (  N次幂倍数表 )过程中，各个数字的N次幂的倍数（最大为WEISHU）可能会超过 WEISHU 位，但由于花朵数的条件是 WEISHU 位，所以若某数字的N次幂的倍数超过 WEISHU 位只需能够表示而不必精确表示其值。这对DASHU_t类型的要求是能够表示溢出（超过WEISHU 位），但必须能精确表示WEISHU 位JINZHI进制非整数。
    此外如果这张表的各项是通过乘法完成的，那么DASHU_t类型应该保证乘的过程中不至于溢出，这样DASHU_t中存储的数据需要满足 (DASHU_t)(X)*WEISHU    如果这张表的各项是通过加法(用加法实现乘法)求得的，则这种类型的数据只需(DASHU_t)(X)

14.求和
    对一种新的数据类型做求和运算，在C语言中通常只能通过函数完成。qiongju()函数中的 //求和 部分可以写为
   //求和( & he_szNf , i * sz^N );
   亦即
   //求和( & he_szNf , & Ncimi_bsb[sz][i] );
   前一个参数使用指针的缘故是需要通过函数调用改变 he_szNf ，后一个是为了减少传递参数的时间消耗。
   求和对DASHU_t类型的要求不高，只要存储的内容不超过 UMANX 的一半就可以了。

15.减法
     //各数字N次方和 -= i * sz^N ;实际上可以通过增加变量的办法省略。亦即用一个auto局部变量记住最初的 各数字N次方和 ，待递归调用返回时再用这个auto局部变量恢复 各数字N次方和 原来的值。

    由于这里需要用到赋值运算，因此这种类型最好能直接赋值。很多数据类型都可以直接赋值，比如struct,所以可初步确定DASHU_t为某种struct类型。

/*2_穷举.c*/
#include "2_穷举.h"
#include "0_问题.h" //用到了QIUJIE、WEISHU
extern void qiongju( void )
{
  static int sz = JINZHI , gs_sx ; /*关于哪个数字 ,该数字个数的上限*/
  //static DASHU_t he_szNf ;//static 数据类型 he_szNf ; //各数字N次方和 ;
  //static DASHU_t N次幂倍数表[JINZHI-1][WEISHU]；
  switch ( sz ) {
     case JINZHI : //递归准备工作
         gs_sx = WEISHU ;
         sz -- ;
         // 各数字N次方和 = 0 ;
         // N次幂倍数表 初始化
         qiongju();
         sz = JINZHI ;
         return ;
     default : //递归过程
         {
            int i ;
            DASHU_t he_szNf_ = he_szNf ;//记录进入时的 he_szNf
            for( i = 0 ; i <= gs_sx ; i++ ){
               //求和
               //各数字N次方和 += i * sz^N ;
               //求和( & he_szNf , & Ncimi_bsb[sz][i] );
               sz -- ;
               gs_sx -= i ;
               qiongju ();
               //各数字N次方和 -= i * sz^N ;
               he_szNf = he_szNf_ ; //改回原来的he_szNf
               gs_sx += i ;
               sz ++ ;
            }
            return ;
         }
     case 0 : //递归终止
         //<=>验算<=>记录结果
         //验证是否满足花朵数条件：
         //判断 各数字N次方和 中的数字是否与构成组合的数字集一致
         return ;
  }
}

16.验算部分
    验算的基本原理是考察最终所得到的he_szNf的各个组成数字是否与最初提供数字组合中出现的数字一致。为此必须记录提供组合时的各个数字出现的次数。显然static数组就可以实现记录功能。     //static unsigned 各数字的次数[JINZHI];
    其中，各数字的次数[i]记录数字i在组合中的个数。伪代码如下：

/*2_穷举.c*/
#include "2_穷举.h"
#include "0_问题.h" //用到了QIUJIE、WEISHU
extern void qiongju( void )
{
  static int sz = JINZHI , gs_sx ; /*关于哪个数字 ,该数字个数的上限*/
  //static DASHU_t he_szNf ;//static 数据类型 he_szNf ; //各数字N次方和 ;
  //static DASHU_t N次幂倍数表[JINZHI-1][WEISHU]；
  //static unsigned 各数字的次数[JINZHI];
  switch ( sz ) {
     case JINZHI : //递归准备工作
         gs_sx = WEISHU ;
         sz -- ;
         // 各数字N次方和 = 0 ;
         // N次幂倍数表 初始化
         qiongju();
         sz = JINZHI ;
         return ;
     default : //递归过程
         {
            int i ;
            DASHU_t he_szNf_ = he_szNf ;//记录进入时的 he_szNf
            for( i = 0 ; i <= gs_sx ; i++ ){
               //记录数字sz的个数
               // 各数字的次数[sx] = i ;
               //求和
               //各数字N次方和 += i * sz^N ;
               //求和( & he_szNf , & Ncimi_bsb[sz][i] );
               sz -- ;
               gs_sx -= i ;
               qiongju ();
               //各数字N次方和 -= i * sz^N ;
               he_szNf = he_szNf_ ; //改回原来的he_szNf
               gs_sx += i ;
               sz ++ ;
            }
            return ;
         }
     case 0 : //递归终止
         //<=>验算<=>记录结果
         //验证是否满足花朵数条件：
         //判断 各数字N次方和 中的数字是否与构成组合的数字集一致
// 各数字的次数[0] = gs_sx ;
// if( 数字集一致(he_szNf,各数字的次数)){
// //记录
// }
         return ;
  }
}

     函数 数字集一致() 需要求出 he_szNf 中各个数字出现的次数，这对DASHU_t这种类型的要求是希望算法的实现比较简单。
     至此，可以考虑如何设计DASHU_t这种数据类型了。
17.对DASHU_t类型的要求汇总
   根据前面对计算过程的分析，可归纳出程序对DASHU_t类型的要求：
   ①最好能直接赋值
   ②能够精确表示WEISHU位JINZHI进制数
   ③能够表示WEISHU位以上的JINZHI进制数
   ④在进行 *WEISHU 、*(JINZHI-1)、加法运算时不产生溢出
   ⑤能方便地求出对应的JINZHI进制数的各位数字