Chinaunix首页 | 论坛 | 博客

KBTillerkbtiller.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

KBTiller

  • 博客访问： 229400
  • 博文数量： 39
  • 博客积分： 1130
  • 博客等级： 少尉
  • 技术积分： 453
  • 用 户 组： 普通用户
  • 注册时间： 2010-02-26 15:54
文章分类

全部博文（39）

文章存档

2012年（1）

2011年（31）

2010年（7）

我的朋友
最近访客
推荐博文
相关博文
华丽的递归——将正整数表示为平方数之和

分类： C/C++

2011-12-04 11:08:46

题目：There live square people in a square country.Everything in this country is square also.Thus, the Square Parliament has passed a law about a land.According to the law each citizen of the country has a right to buy land.A land is sold in squares, surely.Moreover, a length of a square side must be a positive integer amount of meters.Buying a square of land with a side a one pays a2 quadrics (a local currency) and gets a square certificate of a landowner.One citizen of the country has decided to invest all of his N quadrics into theland. He can, surely, do it, buying square pieces 1 × 1 meters.At the same time the citizen has requested to minimize an amount of pieceshe buys: "It will be easier for me to pay taxes," — he has said.He has bought the land successfully.
Your task is to find out a number of certificates he has gotten.

Input
The only line contains a positive integer N ≤ 60 000 ,that is a number of quadrics that the citizen has invested.

Output
The only line contains a number of certificates that he has gotten.

Sample
input output
344   3

Memory Limit: 16 MB

出处：1073. Square Country().

　　这个题目的要求是把一个≤60 000的正整数分解为数目最少的平方数之和。

　　首先需要考虑数据是否在求解范围，下面的伪代码的含义是不言自明的。

 

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX_N 60000

  6. typedef enum{是,否}是否_t;

  8. 是否_t 数据是否合理(int N);

  10. int main( void )
  11. {

  13.    int N = 0 ;
  14.    if(数据是否合理(N)==是)
  15.    {
  16.       printf("求解(N)");
  17.    }
  18.    else
  19.    {
  20.       puts("超出求解范围");
  21.    }

  23.   system("PAUSE");    
  24.   return 0;
  25. }

  27. 是否_t 数据是否合理(int N)
  28. {
  29.    if( N > MAX_N || N <= 0 )
  30.    {
  31.       return 否;
  32.    }
  33.    return 是;
  34. }
　　完成相应的代码非常简单，只要通过查找替换就可以了。之后进行测试。
  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX_N 60000

  6. typedef enum{SHI,FOU} SF_t;

  8. SF_t sj_sf_hl(int N);

  10. int main( void )
  11. {

  13.    int N = 1;//MAX_N ;//MAX_N+1;//-1;//0 ;
  14.    if(sj_sf_hl(N)==SHI)
  15.    {
  16.       printf("求解(N)");
  17.    }
  18.    else
  19.    {
  20.       puts("超出求解范围");
  21.    }

  23.   system("PAUSE");    
  24.   return 0;
  25. }

  27. SF_t sj_sf_hl(int N)
  28. {
  29.    if( N > MAX_N || N <= 0 )
  30.    {
  31.       return FOU;
  32.    }
  33.    return SHI;
  34. }

　　现在至少完成了一半的工作 。
　　下面开始求解问题。题目要求求出“number of quadrics” 且要求 “minimize an amount of pieces”。显然，number是N的函数，且min_number是N的函数。因而可以得到下面的伪代码：

 

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX_N 60000

  6. typedef enum{SHI,FOU} SF_t;

  8. SF_t sj_sf_hl(int N);
  9. unsigned 最小平方数个数(int);

  11. int main( void )
  12. {

  14.    int N = 1;//MAX_N ;//MAX_N+1;//-1;//0 ;
  15.    if(sj_sf_hl(N)==SHI)
  16.    {
  17.       printf("%d\n",最小平方数个数(N));//printf("求解(N)");
  18.    }
  19.    else
  20.    {
  21.       puts("超出求解范围");
  22.    }

  24.   system("PAUSE");    
  25.   return 0;
  26. }

  28. unsigned 最小平方数个数(int n)
  29. {
  30. }

  32. SF_t sj_sf_hl(int N)
  33. {
  34.    if( N > MAX_N || N <= 0 )
  35.    {
  36.       return FOU;
  37.    }
  38.    return SHI;
  39. }

 　　完成代码并测试： 

 

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX_N 60000

  6. typedef enum{SHI,FOU} SF_t;

  8. SF_t sj_sf_hl(int N);
  9. unsigned zx_pfs_gs(int);

  11. int main( void )
  12. {

  14.    int N = 1;//MAX_N ;//MAX_N+1;//-1;//0 ;
  15.    if(sj_sf_hl(N)==SHI)
  16.    {
  17.       printf("%d\n",zx_pfs_gs(N));//printf("求解(N)");
  18.    }
  19.    else
  20.    {
  21.       puts("超出求解范围");
  22.    }

  24.   system("PAUSE");    
  25.   return 0;
  26. }

  28. unsigned zx_pfs_gs(int n) //求最小平方数个数
  29. {
  30.    return 1;//这个是为了测试N为1情况而写的伪答案
  31. }

  33. SF_t sj_sf_hl(int N)
  34. {
  35.    if( N > MAX_N || N <= 0 )
  36.    {
  37.       return FOU;
  38.    }
  39.    return SHI;
  40. }

测试通过。
　　现在研究 “unsigned zx_pfs_gs(int n) //求最小平方数个数 ”这个函数的写法。
　　首先，N能用有限个平方数之和（回答问题是否有解比解答问题本身更重要），因为最不济它可以表示成N个1之和。
　　然而现在的问题是N能表示成最少几个平方数之和？很自然我们会问1个是否可以？如果1个不可以两个是否可以？ 如果两个不可以三个是否可以？……
　　换句话说，我们希望函数从1个平方数开始检查，如果不成功就检查2个，……一旦成功就返回平方数的个数。
　　这个要求可以用下面这样的结构实现
　　调用：逐个尝试(n,1U) ; //1表示从1个开始尝试
　　定义：
　　unsigned 逐个尝试( int n,unsigned 当前尝试的个数 )
　　{
   　　if(可以())
　　     return  当前尝试的个数;
　　   return 逐个尝试 (n,当前尝试的个数+1);    
　　}

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX_N 60000


  7. typedef enum{SHI,FOU} SF_t;

  9. SF_t sj_sf_hl(int N);
  10. unsigned zx_pfs_gs(int);
  11. unsigned zbcs(int ,unsigned );

  13. int main( void )
  14. {

  16.    int N = 1;//MAX_N ;//MAX_N+1;//-1;//0 ;
  17.    if(sj_sf_hl(N)==SHI)
  18.    {
  19.       printf("%d\n",zx_pfs_gs(N));//printf("求解(N)");
  20.    }
  21.    else
  22.    {
  23.       puts("超出求解范围");
  24.    }

  26.   system("PAUSE");    
  27.   return 0;
  28. }

  30. unsigned zbcs( int n,unsigned dqsm )
  31. {
  32.    if(1)// 可以())
  33.      return dqsm;
  34.    return zbcs(n,dqsm+1);
  35. }

  37. unsigned zx_pfs_gs(int n) //求最小平方数个数
  38. {
  39.    return zbcs(n,1U);//逐个尝试(n,1U) //1表示从1个开始尝试
  40. }

  42. SF_t sj_sf_hl(int N)
  43. {
  44.    if( N > MAX_N || N <= 0 )
  45.    {
  46.       return FOU;
  47.    }
  48.    return SHI;
  49. }

　　对1进行测试，正确，测试通过。
　　现在研究n是否可以表示为m个平方数之和的问题。
　　这个问题的提法显然是
　　SF_t 可以表示(int n, unsigend m);//回答n是否可以表示成m个平方数之和
　　先写出框架：

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX_N 60000

  6. typedef enum{SHI,FOU} SF_t;
  7. SF_t sj_sf_hl(int N);
  8. unsigned zx_pfs_gs(int);
  9. unsigned zbcs(int ,unsigned );
  10. SF_t ky_bs(int ,unsigned );

  12. int main( void )
  13. {

  15.    int N = 1;//MAX_N ;//MAX_N+1;//-1;//0 ;
  16.    if(sj_sf_hl(N)==SHI)
  17.    {
  18.       printf("%d\n",zx_pfs_gs(N));//printf("求解(N)");
  19.    }
  20.    else
  21.    {
  22.       puts("超出求解范围");
  23.    }

  25.   system("PAUSE");    
  26.   return 0;
  27. }

  29. SF_t ky_bs(int n,unsigned m)
  30. {
  31.    return SHI ;// for 测试
  32. }

  34. unsigned zbcs(int n,unsigned dqsm)
  35. {
  36.    if( ky_bs( n, dqsm ) == SHI )// 可以())
  37.      return dqsm;
  38.    return zbcs(n,dqsm+1);
  39. }

  41. unsigned zx_pfs_gs(int n) //求最小平方数个数
  42. {
  43.    return zbcs(n,1U);//逐个尝试(n,1U) //1表示从1个开始尝试
  44. }

  46. SF_t sj_sf_hl(int N)
  47. {
  48.    if( N > MAX_N || N <= 0 )
  49.    {
  50.       return FOU;
  51.    }
  52.    return SHI;
  53. }

　　现在研究 SF_t ky_bs(int n,unsigned m)  的写法。
　　函数调用ky_bs( n, m)要回答的问题是n是否可以表示为m个平方数之和，显然这个问题明显等价于：
　　ky_bs( n - 一个平方数 , m -1 )，亦即减去一个平方数之后是否可以表示为m-1个平方数。
　　最终要面对的问题是：
　　ky_bs( n - (m-1)个平方数 , 1 ),亦即判断某个数是否就是一个完全平方数 。
　　下面给出原理性示意代码  

 

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX_N 60000

  6. typedef enum{SHI,FOU} SF_t;
  7. SF_t sj_sf_hl(int N);
  8. unsigned zx_pfs_gs(int);
  9. unsigned zbcs(int ,unsigned );
  10. SF_t ky_bs(int ,unsigned );

  12. int main( void )
  13. {

  15.    int N = 3; //2 ;//1;//MAX_N ;//MAX_N+1;//-1;//0 ;
  16.    if(sj_sf_hl(N)==SHI)
  17.    {
  18.       printf("%d\n",zx_pfs_gs(N));//printf("求解(N)");
  19.    }
  20.    else
  21.    {
  22.       puts("超出求解范围");
  23.    }

  25.   system("PAUSE");    
  26.   return 0;
  27. }

  29. SF_t ky_bs(int n,unsigned m)
  30. {
  31.    if(m==1U)
  32.    {
  33.       if(n==1)
  34.         return SHI ;
  35.       else
  36.         return FOU ;
  37.    }
  38.    return ky_bs( n - 1, m - 1U) ;// 现在可以测试 N= 1,2,3
  39. }

  41. unsigned zbcs(int n,unsigned dqsm)
  42. {
  43.    if( ky_bs( n, dqsm ) == SHI )// 可以())
  44.      return dqsm;
  45.    return zbcs(n,dqsm+1);
  46. }

  48. unsigned zx_pfs_gs(int n) //求最小平方数个数
  49. {
  50.    return zbcs(n,1U);//逐个尝试(n,1U) //1表示从1个开始尝试
  51. }

  53. SF_t sj_sf_hl(int N)
  54. {
  55.    if( N > MAX_N || N <= 0 )
  56.    {
  57.       return FOU;
  58.    }
  59.    return SHI;
  60. }

　　好的，对1,2,3的测试通过了。程序成功地算出了1,2,3分别为最少1,2,3个完全平方数之和。
　　下面考虑解决N==4的问题。
　　很显然，只要解决了判断一个正整数是否是完全平方数并将之替换ky_bs(int n,unsigned m)函数中的“n==1”就可以解决这个问题。而判断某个数是否是完全平方数是非常容易解决的（参见拙著《狂人C》p148）。
　　但是出于卖弄一下递归的虚荣心理，所以在这里我首先构造一个小小的数据结构：
　　typedef struct{ unsigned 平方;unsigned 奇数;} 平方_奇数_t;
　　这个数据结构能够帮助我们用递归的方法完成判断一个正整数是否是完全平方数。
　　原理如下：
　　原型：SF_t 是否完全平方(int ,平方_奇数_t);
　　定义：
　　SF_t 是否完全平方(int n,平方_奇数_t pf_js )
　　{
　　   if(n==pf_js.平方)
 　　     return 是;
　　   if(n　　      return 否;
　　   {
　　      平方_奇数_t 下一个;
　　      下一个.奇数 = pf_js.奇数 + 2 ;
　　      下一个.平方 = pf_js.平方 + 下一个.奇数 ;
　　      return 是否完全平方(n,下一个) ;
　　   }  
　　}
　　据此完成代码：

 

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX_N 60000

  6. typedef enum {
  7.                  SHI ,
  8.                  FOU
  9.                } SF_t;
  10. typedef struct {
  11.                 unsigned pf;
  12.                 unsigned js;
  13.                } PF_JS_t; //typedef struct{ unsigend 平方,unsigend 奇数} 平方_奇数_t;
  14. SF_t sj_sf_hl(int N);
  15. unsigned zx_pfs_gs(int);
  16. unsigned zbcs(int ,unsigned );
  17. SF_t ky_bs(int ,unsigned );

  19. SF_t sf_pf( int ,PF_JS_t ) ;

  21. int main( void )
  22. {

  24.    int N = 16;//9;//4;//3; //2 ;//1;//MAX_N ;//MAX_N+1;//-1;//0 ;
  25.    if(sj_sf_hl(N)==SHI)
  26.    {
  27.       printf("%d\n",zx_pfs_gs(N));//printf("求解(N)");
  28.    }
  29.    else
  30.    {
  31.       puts("超出求解范围");
  32.    }

  34.   system("PAUSE");    
  35.   return 0;
  36. }

  38. SF_t sf_pf( int n , PF_JS_t pf_js )
  39. {
  40.    if(n==pf_js.pf)
  41.       return SHI;
  42.    if(n<pf_js.pf)
  43.       return FOU;
  44.    {
  45.       PF_JS_t xyg;
  46.       xyg.js = pf_js.js + 2 ;
  47.       xyg.pf = pf_js.pf + xyg.js ;
  48.       return sf_pf(n,xyg) ;
  49.    }
  50. }

  52. SF_t ky_bs(int n,unsigned m)
  53. {
  54.    if(m==1U)
  55.    {
  56.       PF_JS_t qs={1U,1U};
  57.       if(sf_pf(n,qs)==SHI)//这里修改为判断n是否是完全平方
  58.         return SHI ;
  59.       else
  60.         return FOU ;
  61.    }
  62.    return ky_bs( n - 1, m - 1U) ;// 现在可以测试 N= 1,2,3
  63. }

  65. unsigned zbcs(int n,unsigned dqsm)
  66. {
  67.    if( ky_bs( n, dqsm ) == SHI )// 可以())
  68.      return dqsm;
  69.    return zbcs(n,dqsm+1);
  70. }

  72. unsigned zx_pfs_gs(int n) //求最小平方数个数
  73. {
  74.    return zbcs(n,1U);//逐个尝试(n,1U) //1表示从1个开始尝试
  75. }

  77. SF_t sj_sf_hl(int N)
  78. {
  79.    if( N > MAX_N || N <= 0 )
  80.    {
  81.       return FOU;
  82.    }
  83.    return SHI;
  84. }

　　编译通过。如不出意料，现在4,9,16……这样的完全平方数是可以求出是由1个平方数组成。运行，测试——如愿以偿.现在程序已经完成1/4强了。
　　回头审视代码，ky_bs()函数中的局部变量qs非常别捏。此外发现，SF_t ky_bs(int n,unsigned m)这个函数写得实际上有错误，它还应该需要一个参数。
　　这个错误非常严重，造成这个错误的原因是当初问题的提法不完整。
　　现在需要重新写ky_bs()这个函数了。
　　这个函数的正确提法应该是n能否表示为m个不小于k平方的平方数之和，理由是递归过程中必然会遇到这个问题。例如对于15，首先从1,4,9中选择一个作为尝试，在后面的选择中应该选择不小于前一个选择的平方数作为尝试。这样进行有序选择的理由是问题的解本身是无序的，进行有序选择可以避免重复的解。这样
　　ky_bs()函数的原型应该是：
　　SF_t ky_bs(int ,unsigned ,PF_JS_t);
　　在zbcs()中的第一次调用应该为：
　　ky_bs(n, dqsm ,(PF_JS_t){1U,1U}) ;
　　这个函数的定义为：
　　SF_t ky_bs(int n,unsigned m,PF_JS_t qs)
　　{
　　   if(n
　　   {
　　      return FOU;
　　   }
　　   if(m==1U)
　　   {
　　      PF_JS_t qs={1U,1U};
　　      if(sf_pf(n,qs)==SHI)//这里修改为判断n是否是完全平方
　　        return SHI ;
　　      else
　　        return FOU ;
　　   }
　　   if( ky_bs( n - qs.pf , m - 1U, qs)==SHI)
　　   {
　　      return SHI;
　　   }
　　   else
 　　  {
　　      return ky_bs( n - qs.pf , m - 1U, xyg(qs) );
　　   } 
　　}
　　其中xyg(qs)为求下一个qs。
　　原型：PF_JS_t  xyg(PF_JS_t);
　　定义：
　　PF_JS_t  xyg(PF_JS_t qian)
　　{
　　   PF_JS_t hou;
　　   hou.js = qian.js + 2 ;
 　　  hou.pf = qian.pf + hou.js ;
 　　  return hou ;  
　　}
　　为提高速度，SF_t sf_pf(n,qs)也做了修改。

 

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX_N 60000

  6. typedef enum {
  7.                  SHI ,
  8.                  FOU
  9.                } SF_t;
  10. typedef struct {
  11.                 unsigned pf;
  12.                 unsigned js;
  13.                } PF_JS_t; //typedef struct{ unsigend 平方,unsigend 奇数} 平方_奇数_t;
  14. SF_t sj_sf_hl(int N);
  15. unsigned zx_pfs_gs(int);
  16. unsigned zbcs(int ,unsigned );
  17. //SF_t ky_bs(int ,unsigned );
  18. SF_t ky_bs(int ,unsigned ,PF_JS_t);
  19. SF_t sf_pf( int ,PF_JS_t ) ;
  20. PF_JS_t xyg(PF_JS_t);
  21. int main( void )
  22. {
  23.    int test_N[]={5,6,7,8,10,11,12,13,14,15},t;//for test
  24.    int N = 5;//MAX_N ;//MAX_N+1;//-1;//0 ;//16;//9;// 4;//3; //2 ;//1;//
  25.    //for test
  26.    for(t=0;t<sizeof test_N /sizeof *test_N;t++)
  27.    {
  28.       N=test_N[t];
  29.       printf("%d ",zx_pfs_gs(N));//printf("求解(N)");
  30.    }
  31.    //for test
  32.    if(sj_sf_hl(N)==SHI)
  33.    {
  34.       printf("%d\n",zx_pfs_gs(N));//printf("求解(N)");
  35.    }
  36.    else
  37.    {
  38.       puts("超出求解范围");
  39.    }

  41.   system("PAUSE");    
  42.   return 0;
  43. }
  44. PF_JS_t xyg(PF_JS_t qian)
  45. {
  46.    PF_JS_t hou;
  47.    hou.js = qian.js + 2 ;
  48.    hou.pf = qian.pf + hou.js ;
  49.    return hou ;
  50. }

  52. SF_t sf_pf( int n , PF_JS_t pf_js )
  53. {
  54.    if(n==pf_js.pf)
  55.       return SHI;
  56.    if(n<pf_js.pf)
  57.       return FOU;
  58.    return sf_pf(n,xyg(pf_js)) ;
  59. }

  61. SF_t ky_bs(int n,unsigned m,PF_JS_t qs)
  62. {
  63.    if(n<qs.pf)
  64.    {
  65.       return FOU;
  66.    }
  67.    if(m==1U)
  68.    {
  69.       //PF_JS_t qs={1U,1U};
  70.       if(sf_pf(n,qs)==SHI)//这里修改为判断n是否是不小于qs.pf的完全平方
  71.         return SHI ;
  72.       else
  73.         return FOU ;
  74.    }
  75.    if( ky_bs( n - qs.pf , m - 1U, qs)==SHI)
  76.    {
  77.       return SHI;
  78.    }
  79.    else
  80.    {
  81.       return ky_bs( n - qs.pf , m - 1U , xyg(qs) );//return ky_bs( n - qs.pf , m - 1U, xyg(qs) );
  82.    }
  83. }
  84. //SF_t ky_bs(int n,unsigned m)
  85. //{
  86. // if(m==1U)
  87. // {
  88. // PF_JS_t qs={1U,1U};
  89. // if(sf_pf(n,qs)==SHI)//这里修改为判断n是否是完全平方
  90. // return SHI ;
  91. // else
  92. // return FOU ;
  93. // }
  94. // return ky_bs( n - 1, m - 1U) ;// 现在可以测试 N= 1,2,3
  95. //}

  97. unsigned zbcs(int n,unsigned dqsm)//逐步尝试
  98. {
  99.    static PF_JS_t const qs={1U,1U};
  100.    if( ky_bs( n, dqsm , qs) == SHI )// 可以表示
  101.      return dqsm;
  102.    return zbcs( n , dqsm + 1 );
  103. }

  105. unsigned zx_pfs_gs(int n) //求最小平方数个数
  106. {
  107.    return zbcs(n,1U);//逐个尝试(n,1U) //1表示从1个开始尝试
  108. }

  110. SF_t sj_sf_hl(int N)
  111. {
  112.    if( N > MAX_N || N <= 0 )
  113.    {
  114.       return FOU;
  115.    }
  116.    return SHI;
  117. }

　　编译之后，重新测试。这次有点心虚，毕竟改动太大了，最主要的是修改了ky_bs()的接口。
　　不过万幸的是前面的数据都测试通过了。
　　现在测试5,6,7,8,10,11,12,13,14,15
　　测试结果为
　　2  3  4  5  2  3  4  4  3  4
　　发现有两组数据是错误的
　　8 13
　　5 4
　　由于几乎从来不调试，所以对调试非常生疏，只好用走查的办法排查BUG。
　　走查发现ky_bs()的逻辑存在错误（递归就是这样，失之毫厘，谬之千里）。 
　　经过一番艰苦卓绝的实在不足与外人道的3个小时左右的折腾(你懂的)……%￥#“：？《%4#@！…：&《“：(*&Z(7Z76”：》*&%……#(此处删去1842个字) ，最后终于：

 

  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define MAX_N 60000

  6. typedef enum {
  7.                  SHI ,
  8.                  FOU ,
  9.                } SF_t;
  10.                
  11. typedef struct {
  12.                 unsigned pf;
  13.                 unsigned js;
  14.                } PF_JS_t; //typedef struct{ unsigend 平方,unsigend 奇数} 平方_奇数_t;
  15. SF_t sj_sf_hl(int N);
  16. unsigned zx_pfs_gs(int);
  17. unsigned zbcs(int ,unsigned );
  18. //SF_t ky_bs(int ,unsigned );
  19. SF_t ky_bs(int ,unsigned ,PF_JS_t);
  20. SF_t sf_pf( int ,PF_JS_t ) ;
  21. PF_JS_t xyg(PF_JS_t);
  22. int main( void )
  23. {
  24.    int test_N[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},t;//for test
  25.    int N = 16;//9;// 4;//3; //2 ;//1;//5;//MAX_N ;//MAX_N+1;//-1;//0 ;//
  26.    //for test
  27.    for(t=0;t<sizeof test_N /sizeof *test_N;t++)
  28.    {
  29.       N=test_N[t];
  30.       printf("%d,",zx_pfs_gs(N));//printf("求解(N)");
  31.    }

  33.    //for test

  35.    if(sj_sf_hl(N)==SHI)
  36.    {
  37.       printf("%d\n",zx_pfs_gs(N));//printf("求解(N)");
  38.    }
  39.    else
  40.    {
  41.       puts("超出求解范围");
  42.    }


  45.   system("PAUSE");    
  46.   return 0;
  47. }
  48. PF_JS_t xyg(PF_JS_t qian)
  49. {
  50.    PF_JS_t hou;
  51.    hou.js = qian.js + 2 ;
  52.    hou.pf = qian.pf + hou.js ;
  53.    return hou ;
  54. }

  56. SF_t sf_pf( int n , PF_JS_t pf_js )
  57. {
  58.    if(n==pf_js.pf)
  59.       return SHI;
  60.    if(n<pf_js.pf)
  61.       return FOU;
  62.    return sf_pf(n,xyg(pf_js)) ;
  63. }

  65. SF_t ky_bs(int n,unsigned m,PF_JS_t qs)
  66. {
  67.    if(n<qs.pf)
  68.    {
  69.       return FOU;
  70.    }
  71.    if(m==1U)
  72.    {
  73.       if(sf_pf(n,qs)==SHI)
  74.         return SHI ;
  75.       else
  76.         return FOU ;
  77.    }
  78.    if( ky_bs( n - qs.pf , m - 1U, qs)==SHI )
  79.    {
  80.       return SHI;
  81.    }
  82.    else
  83.    {
  84.       return ky_bs( n , m , xyg(qs) );
  85.    }
  86. }

  88. unsigned zbcs(int n,unsigned dqsm)//逐步尝试
  89. {
  90.    static PF_JS_t const qs={1U,1U};
  91.    if( ky_bs( n, dqsm , qs) == SHI )// 可以表示
  92.      return dqsm;
  93.    return zbcs( n , dqsm + 1 );
  94. }

  96. unsigned zx_pfs_gs(int n) //求最小平方数个数
  97. {
  98.    return zbcs(n,1U);//逐个尝试(n,1U) //1表示从1个开始尝试
  99. }

  101. SF_t sj_sf_hl(int N)
  102. {
  103.    if( N > MAX_N || N <= 0 )
  104.    {
  105.       return FOU;
  106.    }
  107.    return SHI;
  108. }

　　继续测试。 测试结果为

　　1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
　　输出：
 　　1,2,3,1,2,3,4,2,1,2,3,3,2,3,4,1,2,2,3,2,

　　这回总算对了。现在我终于可以重新整理一下代码了。

 

  1. /*
  2.   Name: 正整数分解为平方和问题
  3.   Copyright:
  4.   Author: 键盘农夫
  5.   Date: 04-12-11 00:22
  6.   Description: 递归，递归，还是递归
  7. */

  9. #include <stdio.h>
  10. #include <stdlib.h>

  12. #define MAX_N 60000
  13. #define TEST 1
  14. typedef enum { //我习惯的Bool类型
  15.                  SHI , //是
  16.                  FOU , //否
  17.                } SF_t;
  18.                
  19. typedef struct { //这个结构描述了前n个奇数的和为n的平方这个事实
  20.                 unsigned pf; //平方
  21.                 unsigned js; //奇数
  22.                } PF_JS_t; //平方_奇数_t;
  23.               
  24. SF_t sj_sf_hl ( int ); //判断输入数据是否合理
  25. unsigned zx_pfs_gs( int ,unsigned ); //求构成某数的平方数的最小个数
  26. SF_t ky_bs( int ,unsigned ,PF_JS_t ); //判断某数是否可以由若干个一定范围的平方数组成
  27. SF_t sf_pf( int ,PF_JS_t ) ; //判断某数是否是完全平方
  28. PF_JS_t xyg( PF_JS_t ); //由某个完全平方数求得下一个完全平方数

  30. int main( void )
  31. {
  32.    
  33.   #if TEST
  34.       int test_N[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},t;
  35.       for( t = 0 ; t < sizeof test_N /sizeof *test_N ; t++ )
  36.          printf("%d:%d ;" , t + 1 , zx_pfs_gs(test_N[t] , 1U ));
  37.       putchar('\n');
  38.   #else
  39.       int N ;
  40.       
  41.       puts("输入要判断的正整数");
  42.       scanf("%d",&N);

  44.       if( sj_sf_hl(N) == SHI )
  45.          printf("%d\n",zx_pfs_gs( N , 1U ) );
  46.       else
  47.          puts("超出求解范围");

  49.   #endif

  51.   system("PAUSE");    
  52.   return 0;
  53. }

  55. /*
  56. PF_JS_t xyg(PF_JS_t qian);
  57. 功能：由qian求得下一个完全平方数（及构成这个数的前n个连续奇数中的最大奇数）
  58. 例 ：xyg((PF_JS_t){1,1}) -> (PF_JS_t){4,3}
  59.       xyg((PF_JS_t){4,3}) -> (PF_JS_t){9,5}
  60. */

  62. PF_JS_t xyg(PF_JS_t qian)
  63. {
  64.    PF_JS_t hou;
  65.    hou.js = qian.js + 2 ;
  66.    hou.pf = qian.pf + hou.js ;
  67.    return hou ;
  68. }

  70. /*
  71. SF_t sf_pf( int n , PF_JS_t pf_js )
  72. 功能：判断n是否是不小于pf_js.pf的完全平方数
  73. 例 ：sf_pf( 1,(PF_JS_t){1,1}) -> SHI
  74.       sf_pf( 1,(PF_JS_t){4,3}) -> FOU
  75.       sf_pf( 5,(PF_JS_t){4,3}) -> FOU
  76.       sf_pf( 9,(PF_JS_t){4,3}) -> SHI
  77. */

  79. SF_t sf_pf( int n , PF_JS_t pf_js )
  80. {
  81.    if( n == pf_js.pf )
  82.       return SHI;
  83.    if( n < pf_js.pf )
  84.       return FOU;
  85.    return sf_pf( n , xyg(pf_js) ) ;
  86. }

  88. /*
  89. SF_t ky_bs(int n,unsigned m,PF_JS_t qs)
  90. 功能：判断n是否由m个不小于qs.pf的完全平方数和表示
  91. 例 ：ky_bs( 1,1,(PF_JS_t){1,1}) -> SHI
  92.       ky_bs( 3,3,(PF_JS_t){1,1}) -> SHI
  93.       ky_bs( 4,3,(PF_JS_t){1,1}) -> SHI
  94.       ky_bs( 5,2,(PF_JS_t){1,1}) -> SHI
  95.       ky_bs( 3,2,(PF_JS_t){1,1}) -> FOU
  96.       ky_bs( 9,2,(PF_JS_t){4,3}) -> FOU
  97.       ky_bs( 8,2,(PF_JS_t){4,3}) -> SHI
  98. */

  100. SF_t ky_bs( int n , unsigned m , PF_JS_t qs )
  101. {
  102.    if( n < qs.pf )
  103.       return FOU;

  105.    if( m == 1U )
  106.       if( sf_pf( n , qs ) == SHI )
  107.         return SHI ;
  108.       else
  109.         return FOU ;
  110.    
  111.    if( ky_bs( n - qs.pf , m - 1U, qs) == SHI )
  112.       return SHI;
  113.    else
  114.       return ky_bs( n , m , xyg( qs ) );
  115. }

  117. /*
  118. unsigned zx_pfs_gs(int n,unsigned dqsm);
  119. 功能：从dqsm起逐步尝试n能表示为几个平方数的和，返回最小值
  120. 例 ：zbcs( 1 , 1U )-> 1U
  121.       zbcs( 2 , 1U )-> 2U
  122.       zbcs( 3 , 1U )-> 3U
  123.       zbcs( 4 , 1U )-> 1U
  124.       zbcs( 5 , 1U )-> 2U
  125. */

  127. unsigned zx_pfs_gs(int n,unsigned dqsm)
  128. {
  129.    static PF_JS_t const qs={1U,1U};
  130.    if( ky_bs( n, dqsm , qs) == SHI )
  131.      return dqsm;
  132.    return zx_pfs_gs( n , dqsm + 1 );
  133. }

  135. /*
  136. SF_t sj_sf_hl(int N);
  137. 功能：判断输入数据是否合理
  138. */

  140. SF_t sj_sf_hl(int N)
  141. {
  142.    if( N > MAX_N || N <= 0 )
  143.    {
  144.       return FOU;
  145.    }
  146.    return SHI;
  147. }

　　最后删除了一个没有什么意义的函数，其他部分基本没有什么变化。
总结：
　　这篇代码刻意地没有使用乘除法 ，相当于自缚一手；同时完全没有使用循环语句， 相当于又缚一手。所以如果我说这是我用脚丫子写出的代码，不至于有人反对吧。
　　当然，这种刻意的自我束缚在真正的开发中是没有必要的。但作为一种练习，这样可以更深刻地理解程序设计语言的某些结构，极大地提高自己C语言的表达能力。
　　自觉最精彩的部分是ky_bs()函数，这个函数描述了一种双向的递归，再加上其中对sf_pf()这个递归函数的调用，构成了一种华丽的“三维”“立体”递归。
　　最后，这种写法并不需要事先知道“任何一个正整数可以写成四个平方数之和”这样高深的数学定理，显然这种写法对于更一般的同类问题也同样适用。例如，可以用这种办法求解把一个正整数表示为若干立方数之和的问题等等。

阅读(3394) | 评论(1) | 转发(0) |
0

上一篇：理解浮点数—《狂人C》习题解答20(第三章习题10)

下一篇：Index(1)

给主人留下些什么吧！~~

最大行业软件2012-12-30 10:59:04

ANSA.v14.0.Pre.16.11.2012.Win32_64 1CD

Beta-CAE MetaPost 6.8.2 Win32_64 1CD

CMG Suite v2012.0 Win32-ISO 1DVD

CMG Suite v2012.0 Win64-ISO 1DVD

Delcam.PowerShape.2013.SP6.Update.Only.Win32_64 2CD

ESI PAM-Stamp 2G 2012.0 Linux32_64 1DVD

Surpac v6.3.2 Win32 1CD

Topcon.Tools.v8.2 1CD

Embird Plus v8.0 1CD

Keil RealView Microcontroller Development Kit 4.60 1CD

回复 | 举报
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6