黑马程序员技术交流社区

标题: 整数的分划问题 [打印本页]

---

作者: 张昶    时间: 2013-4-23 23:28
标题: 整数的分划问题


如，对于正整数n=6，可以分划为：
6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1+1
现在的问题是，对于给定的正整数n,编写算法打印所有划分。
用户从键盘输入 n （范围1~10）
程序输出该整数的所有划分。

---

作者: 曾德强    时间: 2013-4-26 23:38
用递归算
算法如下：
！，设P(n)为整数n的不同划分个数
2，q(n,m)表示在整数n的所有不同划分中，将最大加数n1不大于m的划分个数记做q(n,m);
建立递归关系，分别有如下情况：
1，q(n,1)=1,n>=1;
2，q(n,m)=q(n,n),m>=n;
3，q(n,n)=q(n,n-1)+1;正整数n的划分和n1<=n-1的划分组成
4,q(n,m)=q(n,m-1)+q(n-m,m),n>m>1
代码如下：
public int q(int n,int m){
if((n<1)||(m<1))return 0;
if((n==1)||m==0)return 1;
if(n<m)return q(n,n);
if(n==m)return q(n,m-1)+1;
return q(n,m-1)+q(n-m,m);
}
以前搞过这个问题，思想大体就是这样，不太容易理解，但理解之后挺有意思的，参照书上的，非原创；

---

作者: 张昶    时间: 2013-4-27 16:11
谢谢，却是有意思

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2