一、問題提出

問題：把m個蘋果放入n個盤子中，允許有的盤子為空，共有多少種方法？

注：

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

m,n均小于10

二、算法分析

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

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

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

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

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

遞歸出口條件說明：

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

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

三、程序設(shè)計

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

責(zé)任編輯：haq