一、問(wèn)題提出

問(wèn)題：把m個(gè)蘋(píng)果放入n個(gè)盤(pán)子中，允許有的盤(pán)子為空，共有多少種方法？

注：

5,1,1和1 5 1屬同一種方法

m,n均小于10

二、算法分析

設(shè)f(m,n) 為m個(gè)蘋(píng)果，n個(gè)盤(pán)子的放法數(shù)目，則先對(duì)n作討論，

當(dāng)n>m：必定有n-m個(gè)盤(pán)子永遠(yuǎn)空著，去掉它們對(duì)擺放蘋(píng)果方法數(shù)目不產(chǎn)生影響。即if(n>m) f(m,n) = f(m,m)

當(dāng)n<=m：不同的放法可以分成兩類(lèi)：

有至少一個(gè)盤(pán)子空著，即相當(dāng)于f(m,n) = f(m,n-1);

所有盤(pán)子都有蘋(píng)果，相當(dāng)于可以從每個(gè)盤(pán)子中拿掉一個(gè)蘋(píng)果，不影響不同放法的數(shù)目，即f(m,n) = f(m-n,n).而總的放蘋(píng)果的放法數(shù)目等于兩者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)

遞歸出口條件說(shuō)明：

當(dāng)n=1時(shí)，所有蘋(píng)果都必須放在一個(gè)盤(pán)子里，所以返回１；

當(dāng)m==0(沒(méi)有蘋(píng)果可放)時(shí)，定義為１種放法；

三、程序設(shè)計(jì)

#include 
#include int appledivide(m,n);int main(){    int m,n;    printf("請(qǐng)輸入蘋(píng)果和盤(pán)子個(gè)數(shù)（均小于10）:
");    scanf("%d%d",&m,&n);    if(m<10&&n<10)    {        int result = appledivide(m,n);        printf("將%d蘋(píng)果，放入%d個(gè)盤(pán)子，共有%d中方法",m,n,result);    }    else        printf("蘋(píng)果或盤(pán)子個(gè)數(shù)應(yīng)小于10");    return 0;}int appledivide(m,n){  // 如果碟子只有1個(gè)，無(wú)論蘋(píng)果有多少個(gè)都只有一種放法    if(m==0||n==1)    {        return 1;    }    //如果碟子的個(gè)數(shù)大于蘋(píng)果的個(gè)數(shù)    if(n>m)    {        return appledivide(m,m);    }    else    {        return appledivide(m,n-1) + appledivide(m-n,n);    }}

責(zé)任編輯：haq