第四屆程序設(shè)計大賽 蘋果

Time Limit:1000MS? Memory Limit:65536K

Total Submit:90 Accepted:48

Description

把M個同樣的蘋果放在N個同樣的盤子里，允許有的盤子空著不放，問共有多少種不同的分法？(用K表示)5，1，1和1，5，1 是同一種分法。

Input

第一行是測試數(shù)據(jù)的數(shù)目t(0 <= t <= 20)。以下每行均包含二個整數(shù)M和N，以空格分開。1<=M，N<=10。

Output

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

Sample Input

1

7 3

Sample Output

8

分析轉(zhuǎn)自：http://uzone.univs.cn/blog_2984978_mgf8x9eow0qnb2wreow1.html

分析：放法要分盤子全放滿了和沒放滿的情況。

由于當(1)：蘋果數(shù)少于盤子數(shù)時，此時把盤子減少一個，對結(jié)果沒影響。(為什么？試想如果10個蘋果放1000個盤子，是不是很多盤子沒用呢？嘿嘿)這樣此時

fun(m,n)=fun(m,n-1);

(2)：蘋果數(shù)少于盤子數(shù)，此時仍可以分成兩種情況：放滿和沒有放滿。

沒放滿：fun(m,n)轉(zhuǎn)化成fun(m,n-1)(因為你有盤子沒用)

放滿：放滿即為每個盤子都有蘋果，那么我把每個盤子的蘋果拿一個出來結(jié)果仍然會是一樣。此時的fun(m,n)轉(zhuǎn)化成fun(m-n,m);(既然每個盤子必須有個蘋果，那么這些蘋果的存在與否可以當作不影響結(jié)果，比如拿5個蘋果放2個盤子，又要滿足每個盤子必須有個蘋果的話那肯定有兩個蘋果不能動，必須放在盤子下，然后他們就與盤子融為一體，我們就當作看不見他們了。。。。。嘿嘿)；

好了，函數(shù)進來盤子與蘋果的數(shù)量關(guān)系每次都滿足上面的兩種情況，每次又歸化成更簡單的繼續(xù)下去，那么很顯然就想到了遞歸。

代碼如下：

#include

int fun(int m,int n)

{

if(m<=1||n==1)

return 1;//為m可能為和n相等，此時如果要滿足每個盤子都有的話只有一種放法。只有一個盤子也只有一種

if(n==0)

return 0;

if(n>m)//至少有一個盤子為空

return fun(m,n-1);

else//至少一個盤子為空 + 所有盤子都不為空

return fun(m,n-1)+fun(m-n,n);

}

int main()

{

printf("%d\n",fun(7,3));

}

My ?code：

#include

int fun(int m,int n)

{

if(m<=1||n==1)

return 1;//為m可能為和n相等，此時如果要滿足每個盤子都有的話只有一種放法。只有一個盤子也只有一種

if(n==0)

return 0;

if(n>m)//至少有一個盤子為空

return fun(m,n-1);

else//至少一個盤子為空 + 所有盤子都不為空

return fun(m,n-1)+fun(m-n,n);

}

int main()

{

int m,t,n;

while(scanf("%d",&t)==1)

{

while(t--)

{

scanf("%d%d",&m,&n);

printf("%d\n",fun(m,n));

}

}

return 0;

}

總結(jié)

以上是生活随笔為你收集整理的java递归分苹果_递归较难题——分苹果问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。