C語言解決放蘋果問題

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

輸入：第一行是測試資料的數目t（0 <= t <= 20）。 以下每行均包含二個整數M和N， 以空格分開。 1<=M， N<=10。

輸出：對輸入的每組資料M和N， 用一行輸出相應的K。

程式：

#include

int apple(int m,int n)

{

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

return 1;

else if(n > m)

return apple(m, m);

else

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

}

int main(void)

{

int t, m, n;

scanf("%d", &t);

while(t--) {

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

printf("%d ", apple(m, n));

}

return 0;

}

此問題的解決需要嚴密的邏輯推理能力。 現分析如下：

m個蘋果放在n個盤子中， 那麼定義函數為apple(m,n)：

m=0。 沒有蘋果， So 僅有一種放法。 apple(0,n)=1。

n=1。 只有一個盤子， So僅有一種放法。 apple(m,1)=1。

n>m。 因為盤子太多， 即使每個盤子裡只放一個蘋果也用不完所有的盤子， So apple(m,n)=apple(m,m)。

n<=m。 這種情況又需要分類討論。 有兩種情況。

一， 所有盤子裡都有蘋果。 二， 至少有一個盤子裡沒有蘋果。 先看第一種情況， 所有盤子都有蘋果， 也就是至少每個盤子有一個蘋果， m個蘋果中的n個放在n個盤子中， 剩下的m-n個蘋果， 這和m-n個蘋果放在n個盤子中是是一樣的， 即=apple(m-n, n)。 再看第二種情況， 至少有一個盤子空著， So， apple(m,n)=apple(m,n-1)。 綜上， 這時apple(m,n)=apple(m-n,n)+apple(m,n-1)。

學習C++加群753647735