一、問題提出
問題:把m個蘋果放入n個盤子中,允許有的盤子為空,共有多少種方法?
注:
5,1,1和1 5 1屬同一種方法
m,n均小于10
二、算法分析
設f(m,n) 為m個蘋果,n個盤子的放法數目,則先對n作討論,
當n>m:必定有n-m個盤子永遠空著,去掉它們對擺放蘋果方法數目不產生影響。即if(n>m) f(m,n) = f(m,m)
當n<=m:不同的放法可以分成兩類:
有至少一個盤子空著,即相當于f(m,n) = f(m,n-1);
所有盤子都有蘋果,相當于可以從每個盤子中拿掉一個蘋果,不影響不同放法的數目,即f(m,n) = f(m-n,n).而總的放蘋果的放法數目等于兩者的和,即 f(m,n) =f(m,n-1)+f(m-n,n)
遞歸出口條件說明:
當n=1時,所有蘋果都必須放在一個盤子里,所以返回1;
當m==0(沒有蘋果可放)時,定義為1種放法;
三、程序設計
int appledivide(m,n);
int main()
{
int m,n;
printf("請輸入蘋果和盤子個數(均小于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("蘋果或盤子個數應小于10");
return 0;
}
int appledivide(m,n)
{ // 如果碟子只有1個,無論蘋果有多少個都只有一種放法
if(m==0||n==1)
{
return 1;
}
//如果碟子的個數大于蘋果的個數
if(n>m)
{
return appledivide(m,m);
}
else
{
return appledivide(m,n-1) + appledivide(m-n,n);
}
}
責任編輯:haq
-
C語言
+關注
關注
180文章
7631瀏覽量
141098 -
編程
+關注
關注
88文章
3687瀏覽量
95070
原文標題:C語言習題:蘋果裝盤問題!用遞歸如何求解?
文章出處:【微信號:cyuyanxuexi,微信公眾號:C語言編程學習基地】歡迎添加關注!文章轉載請注明出處。
發布評論請先 登錄
【斯丹麥德電子】常見問題解答:干簧繼電器在測試與測量中的應用
C語言中的socket編程基礎
BQ2404x、BQ2405x和BQ2409x常見問題解答

采用MSP430FR604x MCU的水流和燃氣流量計量超聲波傳感技術的常見問題解答(FAQ)

OMAPL138/C6748 ROM引導加載程序資源和常見問題解答

評論