一、問題提出
問題：把m個(gè)蘋果放入n個(gè)盤子中，允許有的盤子為空，共有多少種方法？
注：
5,1,1和1 5 1屬同一種方法
m,n均小于10
二、算法分析
設(shè)f(m,n) 為m個(gè)蘋果，n個(gè)盤子的放法數(shù)目，則先對n作討論，
當(dāng)n>m：必定有n-m個(gè)盤子永遠(yuǎn)空著，去掉它們對擺放蘋果方法數(shù)目不產(chǎn)生影響。即if(n>m) f(m,n) = f(m,m)
當(dāng)n<=m：不同的放法可以分成兩類：
有至少一個(gè)盤子空著，即相當(dāng)于f(m,n) = f(m,n-1);
所有盤子都有蘋果，相當(dāng)于可以從每個(gè)盤子中拿掉一個(gè)蘋果，不影響不同放法的數(shù)目，即f(m,n) = f(m-n,n).而總的放蘋果的放法數(shù)目等于兩者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)
遞歸出口條件說明：
當(dāng)n=1時(shí)，所有蘋果都必須放在一個(gè)盤子里，所以返回１；
當(dāng)m==0(沒有蘋果可放)時(shí)，定義為１種放法；
三、程序設(shè)計(jì)
#include <stdio.h>
#include <stdlib.h>
int Appledivide(m,n);
int main()
{
int m,n;
printf("請輸入蘋果和盤子個(gè)數(shù)（均小于10）:n");
scanf("%d%d",&m,&n);
if(m<10&&n<10)
{
int result = appledivide(m,n);
printf("將%d蘋果，放入%d個(gè)盤子，共有%d中方法",m,n,result);
}
else
printf("蘋果或盤子個(gè)數(shù)應(yīng)小于10");
return 0;
}
int appledivide(m,n)
{ // 如果碟子只有1個(gè)，無論蘋果有多少個(gè)都只有一種放法
if(m==0||n==1)
{
return 1;
}
//如果碟子的個(gè)數(shù)大于蘋果的個(gè)數(shù)
if(n>m)
{
return appledivide(m,m);
}
else
{
return appledivide(m,n-1) + appledivide(m-n,n);
}
}
四、程序結(jié)果顯示
示例：9個(gè)蘋果9個(gè)盤子
