本文前一部分的链接
http://www.cnblogs.com/KBTiller/archive/2011/05/30/2060595.html

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

#ifdef CESHI               //测试

   int main( void )
   {
      qiongju();
      system("PAUSE"); 
      return 0;
   }

#endif //CESHI

   把 0_问题.h 中的 #define QIUJIE 中的 QIUJIE 改成CESHI 编译运行通过 。这表明文件包含及qiongju()函数原型等方面均没什么问题。
   下面转到 2_穷举.c 源文件中,填充那个空着的qiongju()函数定义

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

    方案1.

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

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


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

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

   这种方案在一开始不必考虑W位数的表示问题,但解的搜索空间依然很大。
   解空间巨大的原因是穷举给出的是各位数的排列,这是一个相当巨大的数目 ((JINZHI-1)*JINZHI^(W-1),对21位十进制数来说,这个值是9*10^20)。然而各种排列中有相当一部分,其各位数N次方的和是相同的(以3位数为例,110和101各位数的3次方之和都为2),不应该重复计算这些值。
   为了避免重复计算这些值,应该只验算各位数字的各种组合而不是对各位数字的排列进行验算。为此,可将穷举的循环结构改良为

   方案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)种可能)。
    这种方案比较形象直观,容易理解。 

    收工。
    收获:完成了qiongju()的测试准备。
    感想:写代码是简单的,想代码应该怎么写是困难的。用完成代码的行数来衡量程序员的工作量是愚蠢的。至于博客园把随笔移出首页所依据的标准呢?我想恐怕至少也是见仁见智的吧

作者: 键盘农夫 发表于 2011-05-31 13:33 原文链接

推荐.NET配套的通用数据层ORM框架:CYQ.Data 通用数据层框架
新浪微博粉丝精灵,刷粉丝、刷评论、刷转发、企业商家微博营销必备工具"