以前做过这么一个题目,在我们学校ACM网上,找了很久没找到,郁闷!网上走了一遭,基本和书上介绍的差不多,虽然做过但是重新去看思路的时候还是比较慢!!!我再写一下,加深影响!
整数划分就是将一个正整数表示成一系列正整数之和,问有多少种不同划分方案!
例如整数6可以划分成一下11中方案:
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
如果你是编程好手看到这样的排列,可能一下子就能想到一种解题思路了!感慨,算法就是在培养解决问题的思路!!言归正传!先介绍下书上的思路:
一、p(n,m)含义:在正整数n的所有不同划分中,最大加数不大于m的划分数(m<=n;m,n>=1)!求整数6有几种划分时,既求p(6,6)。。。
二、函数递归关系:
1、n<1||m<1,return 0;
2、n==1||m==1,p(n,m)=1;
3、n<m,p(n,m)=p(n,n);例如:p(6,10)=p(6,6)
4、n>m,p(n,m)=p(n,m-1)+p(n-m,m);例如:p(6,5)=p(6,4)+p(2,4); p(6,2)=p(6,1)+p(4,2);
(这个等式是关键)
代码如下
#include<cstdio>
int q(int n,int m)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
if((n<1)||(m<1)) return 0;
if(n==1||m==1) 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);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
printf("%d\n", q(6,6));
return 0;
}
写完书上的解题思路,我突然发现前面我想到的一种解题思路错了!!不过这种递归算法运行效率低,计算整数35分解方案数的时候,计算速度很慢(大概两秒出现答案14930352),40的时候更慢了- -,我想用二维数组填表的方式应该会快一点!!有更好算法的可以留言!!随时候教~~
posted on 2010-08-31 15:25
jince 阅读(2402)
评论(2) 编辑 收藏 引用 所属分类:
算法设计与分析