整数的所有不同分割数目—-2013年2月15日
问题描述:把一个正整数写成若干个正整数的和。比如4=3+1,2+2,2+1+1,香港服务器,1+1+1+1,再加上自己,就一共有5种分割方式。
思路:求解4的所有分割方式,实际上就是求分割中以4为最大值而且和为4的所有分割方式,可以用p[4][4]来表示。抽象出来,就是p[n][m],表示分割中以m为最大值而且和为n的所有分割方式。那么,就有以下几种情况。
1.第一步当然是n==m,所以第一个分割肯定是n本身了。最大值为n的分割肯定只有一个,所以接下来,就要求p[n][m-1]了。归纳出来:p[n][m]=p[n][m-1]+1;
2.从第一步m-1后,n肯定是大于m了。所以,p[n][m]的分割中,服务器空间,要么不含m,比如p[4][2],4可以分割成1+1+1+1,这就不含2。这样的话最大值就是1,也就是m-1,所以这种情况归纳出来就是p[n][m-1];要么 含一个或以上m,比如2+2,这样的话p[n][m]=p[n-m][m],或者p[n-2m][m]……因为剔除掉若干个m,数目是一样的。
3.通过以上分析,可以很明显的看出这个程序可以用递归写出来。写递归,关键的一点就是递归结束的条件。在这里比较简单,就是p[n][1]=1,p[1][m]=1了。还要注意,n<m没什么意义,所以这里把n<m时的p[n][m]直接定义成p[n][n];
归纳一下,递归的详细步骤如下:
1.n==1 || m==1 p[n][m]=1
2.n==m p[n][n]=p[n][m-1]+1
3.n>m p[n][m]=p[n][m-1]+p[n-m][m]
4.n<m p[n][m]=p[n][n]
代码如下:
1 #include <stdio.h> 2 #define MAX 1000p[MAX][MAX]={0};process(int n,int m); main()10 {11int n=4; 12int result=process(n,n);13result=p[n][n];,result);;16 17 }process(int n,int m)20 {(p[n][m]=1);(p[n][m]=process(n,n));25if(p[n][m]!=0)26return p[n][m];27if(n==m)28return (p[n][m]=1+process(n,m-1));29return (p[n][m]=process(n,m-1)+process(n-m,m));30 }
参考资料:《C语言精选名题百则技巧篇》
如果你觉得我的文章对你有帮助,香港虚拟主机,请推荐一下,非常感谢!
posted on
Copyright ©2013 NeilHappy Powered by: 博客园 模板提供:沪江博客
害怕攀登高峰的人,永远在山下徘徊。