轉自?? ： https://blog.csdn.net/u012283461/article/details/52761238

【問題描述】

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

【輸入】

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

【輸出】

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

【問題分析】

放蘋果的問題乍看之下很復雜，盤子是一樣的，蘋果也是一樣的；只要每個盤子里面放的蘋果是一樣多的，不管順序如何最終得到的都是同一種分法。我屬于初學算法，對于算法不熟悉，一遇到問題就會用人的思維去思考問題，我會想著空一個盤子是什么情況，空兩個盤子是什么情況，一個盤子都不空又是什么情況。越想腦子越亂，最后就得不到解題方法，但是就目前看的遞歸算法而言。似乎是因為我想多了，其實我們需要把問題簡化。就拿這個放蘋果的問題而言，我們只需要分兩種情況：有空盤子和沒空盤子。

1.有空盤子：f(m,n)=f(m,n-1)//有空盤子很多人會有疑問，這不是只有一個空盤子的情況嗎？那2個3個空盤子呢？這就需要遞歸的思想，隨著一步一步的將n換成n-1你就會發現那就是2,3個空盤子的情況。

2.沒有空盤子：f(m,n)=f(m-n,n)//沒有空盤子，我們可以看成先給每一個盤子放一個蘋果，則還剩下m-n個蘋果，剩下的問題就是把這m-n個蘋果放到n個盤子里的問題了，也許有人會問，m-n個蘋果放到n個盤子也會出現空盤子的情況啊，不是和前面的有空盤子重復了？確實，會出現空盤子的情況，但是請注意，他們并不是真的空盤子，因為他們最開始已經放了一個，他們在這里的空代表著這個盤子只有最開始放的一個蘋果。

因此：f(m,n)=f(m,n-1)+f(m-n,n)

m>=n

上面的表達式并不完整，當m

因此：f(m,n)=f(m,m)

m

寫到這里主要表達式基本上已經寫完了，但是遞歸都需要有結束條件，結束條件并不是很難發現，當只有一個盤子時明顯只有一種方法，另外沒有蘋果和只有一個蘋果的時候也只有一種放法。即f(m,n)=1

n=1,m=0

綜上：

f(m,n)=1 ? ? ? ? ? ? ? ? ? ? ? ? n=1,m=0

f(m,n)=f(m,m) ? ? ? ? ? ? ? ?m

f(m,n)=f(m,n-1)+f(m-n,n)

m>=n

#include#include

using namespacestd;const int maxm=10000;intm[maxm],n[maxm],k[maxm];int putApple(int m,intn);intmain(){

memset(k,0,sizeof(k));intt;

cin>>t;for(int i=1;i<=t;i++){

cin>>m[i]>>n[i];

}for(int i=1;i<=t;i++){

k[i]=putApple(m[i],n[i]);

cout<

}

}int putApple(int m,intn){if(m==0||n==1) return 1;if(n>m)returnputApple(m,m);else

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

}

總結

以上是生活随笔為你收集整理的用python解决放苹果问题_放苹果问题（组合数学经典）的全部內容，希望文章能夠幫你解決所遇到的問題。

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