題目鏈接：HRBUST-2004

遞歸法:

1.當n=1時，此時只有1種解{1};

2.當m=1時，此時也只有1種解{1,1,1, …

3.當n> m時，要分為最大數包含m和不包含m兩種情況。

●包含m:此時就是{mx1,2…}. 其中x1+x2+3.+… =n-m, 就相當于求和為n-m,最大值為m的劃分個數: f(n-m,m)
●不包含m:此時最大數最大為m-1,相當于把n劃分為最大數為m-1的劃分個數: f(n,m-1)

因此:當n>m時劃分個數為f (n-m,m) +f (n,m-1)

4.當n=m時，此時也要分為兩種情況，包含m和不包含m。

●包含m,此時就只有一種情況，{m}
●不包含m,此時最大值為m-1, f(n,m-1)

因此:當n=m時， 劃分個數為1+f (n, m-1) ;

5.當n<m時,此時不可能包含m,最大值最大就是n,最大劃分個數為f (n,n) 。也可以分為包含n和不包含n兩種情況:

●包含n，此時就只有一種情況，{n};●不包含n，最大值是n-1, f(n,n-1)

因此可以寫成1+(n,n-1).
相關問題分析：算法設計與分析——分治與遞歸——整數劃分問題
問題點：注意 多組測試數據，輸入到文件結束

#include<iostream> #include<vector> using namespace std; int q(int n,int m)//整數n的劃分，劃分中最大數為m {if((n<0)||(m<0))return 0;if((n==1)||(m==1))return 1;if(n<m)return q(n,n);if(n==m)return (1+q(n,m-1));if(1<m<n)return q(n,m-1)+q(n-m,m); } int main() {int n;vector<int> vec;while(scanf("%d",&n)!=EOF){vec.push_back(q(n,n));} for(int i=0;i<vec.size();i++){cout<<vec[i]<<endl;}return 0;}

總結

以上是生活随笔為你收集整理的算法题目——整数划分(HRBUST-2004)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。