以前做过这么一个题目，在我们学校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)
{
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);
}
int main()
{
printf("%d\n", q(6,6));
return 0;
} 写完书上的解题思路，我突然发现前面我想到的一种解题思路错了！！不过这种递归算法运行效率低，计算整数35分解方案数的时候，计算速度很慢（大概两秒出现答案14930352），40的时候更慢了- -，我想用二维数组填表的方式应该会快一点！！有更好算法的可以留言！！随时候教~~
posted on 2010-08-31 15:25
jince 阅读(2428)
评论(2) 编辑 收藏 引用 所属分类:
算法设计与分析