放蘋果

拿蘋果

描述

把M個(gè)同樣的蘋果放在N個(gè)同樣的盤子里，允許有的盤子空著不放，問

共有多少種不同的分法？5，1，1和1，5，1 是同一種分法。

輸入

第一行是測(cè)試數(shù)據(jù)的數(shù)目t（0 <= t <= 20）。以下每行均包含二個(gè)整

數(shù)M和N，以空格分開。1<=M，N<=10。

輸出

對(duì)輸入的每組數(shù)據(jù)M和N，用一行輸出相應(yīng)的K。

樣例輸入

1

7 3

樣例輸出

8

分析：

設(shè)i個(gè)蘋果放在k個(gè)盤子里放法總數(shù)是 f(i,k)，則： k > i 時(shí)， f(i,k) = f(i,i) k <= i 時(shí)，總放法 =

有盤子為空的放法+沒盤子為空的放法 f(i,k) = f(i,k-1) + f(i-k,k)

注意：

這個(gè)沒盤子為空的算法，首先做一步，往每個(gè)盤子放一個(gè)蘋果。然后蘋果剩下i-k，把他們放到k個(gè)盤子里面

#include using namespace std; int f(int m, int n) { if(m < n) return f(m, m); if(m == 0) return 1; if(n == 0) return 0; return f(m, n-1)+f(m-n, n); } int main() { int T; int m, n; cin >> T; while(T--) { cin >> m >> n; cout << f(m, n) << endl; } return 0; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。