以前做過這么一個題目，在我們學(xué)校ACM網(wǎng)上，找了很久沒找到，郁悶！網(wǎng)上走了一遭，基本和書上介紹的差不多，雖然做過但是重新去看思路的時候還是比較慢！！！我再寫一下，加深影響！
整數(shù)劃分就是將一個正整數(shù)表示成一系列正整數(shù)之和，問有多少種不同劃分方案！
例如整數(shù)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
如果你是編程好手看到這樣的排列，可能一下子就能想到一種解題思路了！感慨，算法就是在培養(yǎng)解決問題的思路！！言歸正傳！先介紹下書上的思路：
一、p(n,m)含義：在正整數(shù)n的所有不同劃分中，最大加數(shù)不大于m的劃分?jǐn)?shù)（m<=n；m,n>=1）！求整數(shù)6有幾種劃分時，既求p(6,6)。。。
二、函數(shù)遞歸關(guān)系：
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)；
（這個等式是關(guān)鍵）
代碼如下
#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;
} 寫完書上的解題思路，我突然發(fā)現(xiàn)前面我想到的一種解題思路錯了！！不過這種遞歸算法運行效率低，計算整數(shù)35分解方案數(shù)的時候，計算速度很慢（大概兩秒出現(xiàn)答案14930352），40的時候更慢了- -，我想用二維數(shù)組填表的方式應(yīng)該會快一點！！有更好算法的可以留言！！隨時候教~~
posted on 2010-08-31 15:25
jince 閱讀(2492)
評論(2) 編輯 收藏 引用 所屬分類:
算法設(shè)計與分析