以前做過這么一個題目，在我們學校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 閱讀(2451)
評論(2) 編輯 收藏 引用 所屬分類:
算法設計與分析