?

2001年NOIP全國聯賽提高組

?時間限制: 1 s

?空間限制: 128000 KB

?題目等級 : 黃金 Gold

題解

題目描述?Description

將整數n分成k份，且每份不能為空，任意兩種劃分方案不能相同(不考慮順序)。
例如：n=7，k=3，下面三種劃分方案被認為是相同的。
1 1 5

1 5 1

5 1 1
問有多少種不同的分法。

輸入描述?Input Description

輸入：n，k (6，2<=k<=6)

輸出描述?Output Description

輸出：一個整數，即不同的分法。

樣例輸入?Sample Input

?7 3

樣例輸出?Sample Output

4

數據范圍及提示?Data Size & Hint

?{四種分法為：1，1，5;1，2，4;1，3，3;2，2，3;}

代碼：

#include

using namespace std;

#include

int f(int,int,int);

int main()

{

??? int n,k;

?????? cin>>n>>k;

?????? cout<<f(n,k,1)<<endl;

?????? return 0;

}

int f(int a,int b,int c)

{

?????? int g=0;

?????? if(b==1) return 1;

?????? else{

????????????? for(int i=c;i<=a/b;++i)//i<=a/b的含義就是當前的a/b，a分為b分，每一份起碼大于i曾能再用i去分a這個數，

????????????? g+=f(a-i,b-1,i);

????????????? return g;

?????? }

}

轉載于:https://www.cnblogs.com/c1299401227/p/5370781.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的42.递归算法---数的划分的全部內容，希望文章能夠幫你解決所遇到的問題。

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