算法設計--整數劃分問題(遞歸)
整數劃分問題是算法中的一個經典命題之一。把一個正整數n表示成一系列正整數之和:n=n1+n2+.....+nk(其中,n1≥n2≥......nk≥1,k≥1)。
正整數n的這種表示稱為正整數n的劃分。正整數n的不同劃分個數稱為正整數n的劃分數,記作p(n)。
正整數6有如下11中不同的劃分,是以p(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
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHLx0keNRTTq1keRpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLzATM4ETMwYTM4ADNwAjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
#include<bits/stdc++.h>
using namespace std;
int split(int n,int m)
{
if(n==1||m==1)return 1;
else if(n<m)return split(n,n);
else if(n==m)return split(n,n-1)+1;
else return split(n,m-1)+split(n-m,m);
}
int main()
{
int n,m;
cin>>n>>m;
cout<<split(n,m);//輸出劃分種類數
}