算法基礎(chǔ)二Python遞歸算法解析ppt課件

1、遞歸,算法,人理解迭代，神理解遞歸,遞歸：指在函數(shù)的定義中使用函數(shù)自身的方法。 ”遞歸“ 表達(dá)了兩個(gè)意思：”遞“”歸“，基本思想是把規(guī)模大的問(wèn)題轉(zhuǎn)化為規(guī)模小的相似的子問(wèn)題來(lái)解決。 在函數(shù)實(shí)現(xiàn)時(shí)，因?yàn)榻鉀Q大問(wèn)題的方法和解決小問(wèn)題的方法往往是同一個(gè)方法，所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況。另外這個(gè)解決問(wèn)題的函數(shù)必須有明顯的結(jié)束條件，這樣就不會(huì)產(chǎn)生無(wú)限遞歸的情況了,遞歸應(yīng)用三步法： 1). 明確遞歸終止條件 例如：當(dāng)N=0時(shí)，遞歸終止 2). 給出遞歸終止時(shí)的處理辦法 例如： if n=0 : return 1 3). 提取重復(fù)的邏輯，遞歸的一般式，縮小問(wèn)題規(guī)模 例如：return n*f（n-1,例

2、1：應(yīng)用三步法解決實(shí)際問(wèn)題：階乘問(wèn)題 1). 明確遞歸終止條件 當(dāng)N=0時(shí)，遞歸終止 2). 給出遞歸終止時(shí)的處理辦法 if n=0 : return 1 3). 提取重復(fù)的邏輯，縮小問(wèn)題規(guī)模 重復(fù)的邏輯是： return n*f（n-1,defjiecheng(n): ifn=0: return1 else: returnn*jiecheng(n-1) zzshu=int(input(輸入待求的階乘的正整數(shù)) print(zzshu,的階乘是,jiecheng(zzshu,例2：應(yīng)用三步法解決實(shí)際問(wèn)題：斐波那契數(shù)列 1). 明確遞歸終止條件 當(dāng)N=1,或n=2時(shí)，遞歸終止 2). 給出遞歸終

3、止時(shí)的處理辦法 if n=1 or n=2: return 1 3). 提取重復(fù)的邏輯，縮小問(wèn)題規(guī)模* 重復(fù)的邏輯是： f（n）=f(n-1)+f（n-2,deffbnqsl(n): ifn=1orn=2: return1 else: returnfbnqsl(n-1)+fbnqsl(n-2) zzshu=int(input(輸入待求的斐波那切數(shù)列的個(gè)數(shù)為) print(zzshu,個(gè)斐波那切數(shù)列的是) foriinrange(1,zzshu+1): print(fbnqsl(i,例3：應(yīng)用三步法解決實(shí)際問(wèn)題：稍微復(fù)雜一點(diǎn)的例題：漢諾塔問(wèn)題,法國(guó)數(shù)學(xué)家愛(ài)德華盧卡斯曾編寫(xiě)過(guò)一個(gè)印度的古老傳說(shuō)：在

4、世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡,畫(huà)圖是分析問(wèn)題的一個(gè)好習(xí)慣,1、先假設(shè)除最下面的盤(pán)子之外，我們已經(jīng)成功地將上面的63個(gè)盤(pán)子移到了b柱，此時(shí)只要將最下面的盤(pán)子由a移動(dòng)到c即可。如圖,分解問(wèn)題,2、當(dāng)最大的盤(pán)子由a移到c后，b上

5、是余下的63個(gè)盤(pán)子，a為空。因此現(xiàn)在的目標(biāo)就變成了將這63個(gè)盤(pán)子由b移到c。這個(gè)問(wèn)題和原來(lái)的問(wèn)題完全一樣，只是由a柱換為了b柱，規(guī)模由64變?yōu)榱?3。因此可以采用相同的方法，先將上面的62個(gè)盤(pán)子由b移到a，再將最下面的盤(pán)子移到c,3、 要以B為輔助將A上64個(gè)盤(pán)子轉(zhuǎn)移到C上 將c柱子作為輔助，把a(bǔ)上的63個(gè)圓盤(pán)移動(dòng)到b上 將a上最后一個(gè)圓盤(pán)移動(dòng)到c 這樣問(wèn)題轉(zhuǎn)移成，接下來(lái)要以a為輔助，將B上所有63盤(pán)子轉(zhuǎn)移到C上,defmove(n,a,b,c):#將A柱上N個(gè)盤(pán)子以B柱為輔助移動(dòng)到C柱上 ifn=1: print(a,-,c)#如果只有1個(gè)盤(pán)子，直接將A柱上的盤(pán)子移動(dòng)到c柱上 else: m

6、ove(n-1,a,c,b)#將N-1個(gè)盤(pán)子從A柱上以c柱為輔助移動(dòng)到b柱上,這時(shí)a柱上只有當(dāng)前最大一個(gè)盤(pán)子 move(1,a,b,c)#將a柱上剩下的這個(gè)最大的盤(pán)子從A柱上以b柱為輔助（實(shí)際用不上B柱）移動(dòng)到c柱上,這時(shí)a柱為空 move(n-1,b,a,c)#將B柱上剩下的N-1個(gè)盤(pán)子以A柱為輔助，移動(dòng)到C柱上 move(4,A,B,C,遞歸習(xí)題1：八皇后問(wèn)題：八重循環(huán)？體會(huì)遞歸之美！ 十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。 遞歸習(xí)題2：波蘭表達(dá)式 波蘭表達(dá)式是一種把

7、運(yùn)算符前置的算術(shù)表達(dá)式，例如普通的表達(dá)式2 + 3的逆波蘭表示法為+ 2 3。逆波蘭表達(dá)式的優(yōu)點(diǎn)是運(yùn)算符之間不必有優(yōu)先級(jí)關(guān)系，也不必用括號(hào)改變運(yùn)算次序，例如(2 + 3) * 4的逆波蘭表示法為* + 2 3 4。本題求解逆波蘭表達(dá)式的值，其中運(yùn)算符包括+ - * /四個(gè)。 輸入 輸入為一行，其中運(yùn)算符和運(yùn)算數(shù)之間都用空格分隔，運(yùn)算數(shù)是浮點(diǎn)數(shù) 輸出 輸出為一行，表達(dá)式的值。 遞歸習(xí)題3：表達(dá)式計(jì)算 輸入為四則運(yùn)算表達(dá)式，僅由整數(shù)、+、*、/ 、(、) 組成，沒(méi)有空格，要求求其值。假設(shè)運(yùn)算符結(jié)果都是整數(shù)。/結(jié)果也是整數(shù) 遞歸習(xí)題4：爬樓梯 樹(shù)老師爬樓梯，他可以每次走1級(jí)或者2級(jí)，輸入樓梯的級(jí)數(shù)，

8、求不同的走法數(shù) 例如：樓梯一共有3級(jí)，他可以每次都走一級(jí)，或者第一次走一級(jí)，第二次走兩級(jí)，也可以第一次走兩級(jí)，第二次走一級(jí)，一共3種方法。 輸入 輸入包含若干行，每行包含一個(gè)正整數(shù)N，代表樓梯級(jí)數(shù)，1 = N = 30輸出不同的走法數(shù)，每一行輸入對(duì)應(yīng)一行,遞歸習(xí)題5：放蘋(píng)果 把M個(gè)同樣的蘋(píng)果放在N個(gè)同樣的盤(pán)子里，允許有的盤(pán)子空著不放，問(wèn)共有多少種不同的分法？5，1，1和1，5，1 是同一種分法。 輸入 第一行是測(cè)試數(shù)據(jù)的數(shù)目t（0 = t = 20）。以下每行均包含二個(gè)整數(shù)M和N，以空格分開(kāi)。1=M，N=10。 輸出 對(duì)輸入的每組數(shù)據(jù)M和N，用一行輸出相應(yīng)的K。 樣例輸入 1 7 3 樣例輸出

9、 8 。 遞歸習(xí)題6：算24 輸入 輸入數(shù)據(jù)包括多行，每行給出一組測(cè)試數(shù)據(jù)，包括4個(gè)小于10個(gè)正整數(shù)。最后一組測(cè)試數(shù)據(jù)中包括4個(gè)0，表示輸入的結(jié)束，這組數(shù)據(jù)不用處理。 輸出 對(duì)于每一組測(cè)試數(shù)據(jù)，輸出一行，如果可以得到24，輸出“YES”；否則，輸出“NO”。 樣例輸入 5 5 5 1 1 1 4 2 0 0 0 0 樣例輸出 YES NO,謝謝,觀看,八皇后問(wèn)題,國(guó)際象棋的皇后能吃掉橫向縱向和斜向的棋子，非常厲害，比中國(guó)象棋里的車(chē)厲害多了。 一個(gè)皇后放到棋盤(pán)中央，就一小半的格子不能放了其他皇后了。 按什么思路去求解呢？ 我們假定存在一組數(shù)a=a0,a1,a2,a3,a4,a5,a6,a7 每個(gè)

10、數(shù)字都是大于等于0小于8的正整數(shù)，表示某一行皇后所處的位置。這樣的一組數(shù)如果滿(mǎn)足了八皇后題面的要求，我們稱(chēng)之為八皇后問(wèn)題的一個(gè)解。 1、64選8，從64個(gè)格子里選8個(gè)，要計(jì)算44.26億種可能 2、考慮每一行每一列只能放置一個(gè)棋子，8！，是40320種可能，這樣好算多了，但是如果這樣要寫(xiě)8重循環(huán)，如果是20行呢，寫(xiě)20重循環(huán),遞歸習(xí)題1：八皇后問(wèn)題： 共有92種布局,回溯法解題思想： 回溯法解題思想有通用解題思路之稱(chēng)。 從遞歸的思想來(lái)看，我們?cè)趶牡谝恍虚_(kāi)始給每一行的皇后確定一個(gè)位置。每來(lái)到新的一行時(shí)，對(duì)本行的所有可能位置（皇后放在這個(gè)位置和前面所有已放置的皇后無(wú)沖突）分別進(jìn)行遞歸地深入；若某一

11、行可能的位置數(shù)為0，則表明這是一條死路，返回上一層遞歸尋找其他辦法；若來(lái)到的這一行是第九行（不存在第九行，只不過(guò)是說(shuō)明前八行都已經(jīng)正確配置，已經(jīng)得到一個(gè)解決方案），這說(shuō)明得到解決方案。 可以看到，尋找一行內(nèi)皇后應(yīng)該擺放的位置這是個(gè)遞歸過(guò)程，并且在進(jìn)入遞歸時(shí)，應(yīng)該要告訴這個(gè)過(guò)程的東西包括兩個(gè)： 1. 之前皇后放置的狀態(tài)， 2. 現(xiàn)在是第幾行。 所以，遞歸主體函數(shù)可以設(shè)計(jì)為 8queen(queenset, row)，其中queenset表示的是當(dāng)前棋盤(pán)的狀態(tài)（比如一個(gè)數(shù)組，0表示該行未放置，非零表示該行放置皇后的位置）。另外還可以有一個(gè)check(queenset,row，pos)，pos可以是

12、一個(gè)第row行放置queen的位置，check函數(shù)用來(lái)返回以當(dāng)前的棋盤(pán)狀態(tài)，如果在第row行pos位置再放置一個(gè)皇后是否會(huì)有沖突,某一行的某一個(gè)位置是不是一個(gè)與已有皇后位置不沖突的位置，可以看成三個(gè)檢測(cè)問(wèn)題： 1、檢測(cè)是不是同一行：因?yàn)橐恍兄环乓粋€(gè)皇后，這個(gè)問(wèn)題不用檢測(cè)了 2、檢測(cè)是不是同一列：第a行第b列已經(jīng)有了一個(gè)皇后，要檢查第row行，第pos列是否沖突，就是b=pos 3、檢測(cè)是不是同一斜線|（a-row）|=|b-pos| 如果以上三條，實(shí)際是是兩條，如果滿(mǎn)足，就返回錯(cuò)誤，如果不滿(mǎn)足程序繼續(xù)；如果該位置與所有已有皇后都不沖突，則該位置是一個(gè)暫時(shí)可用的位置，可以進(jìn)入下一行去判斷,習(xí)題一

13、：這是求解8皇后問(wèn)題的程序 #這個(gè)程序?qū)⒂眠f歸的思路來(lái)求解8皇后問(wèn)題，設(shè)置存放8皇后解的為一個(gè)名為queenpos的列表【queenpos0，queenpos1，queenpos2，?！?defcheckqueen(pos,queenpos):#檢查第len(queenpos)行，因?yàn)樾蛱?hào)從0開(kāi)始，就是當(dāng)前行，pos位置（從0開(kāi)始）的皇后是否與之前的皇后相沖突 foriinrange(len(queenpos):#逐個(gè)皇后檢查 ifpos=queenposi: returnFalse#如果同列返回沖突，false elifabs(len(queenpos)-i)=abs(pos-queenpo

14、si): returnFalse#如果同斜線返回沖突，F(xiàn)ALSE returnTrue#和之前的全部皇后都不沖突，返回真 defqueen8(row=8,queenpos=(): foriinrange(row):#在第一行一個(gè)一個(gè)嘗試 ifcheckqueen(i,queenpos):#如果當(dāng)前位置可用，就看是不是最后一行，如果是就記錄位置返回 iflen(queenpos)=(row-1): yield(i,) else:#如果不是最后一行就看下一行直至遞歸調(diào)用到最后一行能不能找到解，如果能找到解，就一路遞歸返回，記錄位置 #如果找不到就什么都不干，在同一行找下一個(gè)位置 forjiedai

15、nqueen8(row,queenpos+(i,): yield(i,)+jieda#如果能找到解，就一路遞歸返回，保存一個(gè)解 h=queen8() forjinh: print(j) print(8皇后問(wèn)題一共有,len(list(queen8(),種解法,習(xí)題2.1 逆波蘭表達(dá)式求值 網(wǎng)上很多習(xí)題甚至教材都將逆波蘭表達(dá)式和波蘭表達(dá)式搞混了。教材里的所謂遞歸求解逆波蘭表達(dá)式，實(shí)質(zhì)是求解波蘭表達(dá)式。 逆波蘭表達(dá)式，簡(jiǎn)單直接求解就可以了，不用去寫(xiě)遞歸。 左邊的圖里演示，用了兩個(gè)函數(shù)，一個(gè)函數(shù)用于計(jì)算一個(gè)單步計(jì)算。 另一個(gè)函數(shù)用于一個(gè)個(gè)彈出逆波蘭表達(dá)式中的元素， 如果是運(yùn)算符，那么之前兩個(gè)元素一定

16、是數(shù)字，三個(gè)元素進(jìn)行計(jì)算，結(jié)果壓進(jìn)堆棧 如果是數(shù)字，直接壓進(jìn)堆棧 全部元素彈出，最后剩下的就是結(jié)果,逆波蘭表達(dá)式是后綴表達(dá)式 #先寫(xiě)一個(gè)函數(shù)，計(jì)算兩個(gè)被運(yùn)算數(shù)的值和一個(gè)操作符的操作結(jié)果，cal1(leftnum,rightnum,op) #其中rightnum先從堆棧里彈出 #開(kāi)始讀入算式，如果是運(yùn)算數(shù)就入堆棧，如果是操作符就彈出兩個(gè)運(yùn)算數(shù)。 defcalc1(expr): token= foriinexpr.split(): ifiin+,-,*,/: rightnum,leftnum=float(token.pop(),float(token.pop() print(leftnum,i,r

17、ightnum) token.append(str(cal1(leftnum,rightnum,i) else: token.append(i) returnfloat(token0) defcal1(leftnum,rightnum,i):#leftnum和rightnum是浮點(diǎn)型，i是字符型的運(yùn)算符 ifi=+: returnleftnum+rightnum ifi=-: returnleftnum-rightnum ifi=*: returnleftnum*rightnum ifi=/: returnleftnum/rightnum print(calc1(31.0434.0+434.0

18、*,遞歸習(xí)題2.2：波蘭表達(dá)式,波蘭表達(dá)式是一種把運(yùn)算符前置的算術(shù)表達(dá)式，例如普通的表達(dá)式2 + 3的波蘭表示法為+ 2 3。波蘭表達(dá)式的優(yōu)點(diǎn)是運(yùn)算符之間不必有優(yōu)先級(jí)關(guān)系，也不必用括號(hào)改變運(yùn)算次序，例如(2 + 3) * 4的逆波蘭表示法為* + 2 3 4。本題求解逆波蘭表達(dá)式的值，其中運(yùn)算符包括+ - * /四個(gè)。 輸入 ： 輸入為一行，其中運(yùn)算符和運(yùn)算數(shù)之間都用空格分隔，運(yùn)算數(shù)是浮點(diǎn)數(shù) 輸出 ： 輸出為一行，表達(dá)式的值,很多書(shū)籍、資料包括郭老師的講課中都將這個(gè)表達(dá)式稱(chēng)為逆波蘭表達(dá)式，我自己也為這個(gè)事困惑了一個(gè)多星期，在這里還是將逆波蘭表達(dá)式和波蘭表達(dá)式的例程都提供出來(lái)，供讀者參考,Pol

19、ishNotation這是波蘭表達(dá)式的程序 #輸入為一行，其中運(yùn)算符和運(yùn)算數(shù)之間都用空格分隔，運(yùn)算數(shù)是浮點(diǎn)數(shù)。 #樣例輸入：*+11.012.0+24.035.0 #1)一個(gè)數(shù)是一個(gè)波蘭表達(dá)式，值為該數(shù) #2)運(yùn)算符波蘭表達(dá)式波蘭表達(dá)式是波蘭表達(dá)式，值為兩個(gè)逆波蘭表達(dá)式的值運(yùn)算的結(jié)果 #一個(gè)小工具：Pythonsplit()通過(guò)指定分隔符對(duì)字符串進(jìn)行切片，如果參數(shù)num有指定值，則分隔num+1個(gè)子字符串，默認(rèn)分割符為全部空字符 #自左至右彈出元素，如果是運(yùn)算符，就繼續(xù)彈出左運(yùn)算數(shù)和右運(yùn)算數(shù)，左運(yùn)算數(shù)是一個(gè)波蘭表達(dá)式，右運(yùn)算數(shù)也是一個(gè)波蘭表達(dá)式 #對(duì)于左右運(yùn)算數(shù)分別調(diào)用函數(shù)自身求值，直到只剩一

20、個(gè)數(shù)，則返回遞歸。 defPolishNotation(expr): elem= elem=expr.pop() ifelemnotin+,-,*,/: returnfloat(elem) else: ifelem=+: returnPolishNotation(expr)+PolishNotation(expr) ifelem=-: returnPolishNotation(expr)-PolishNotation(expr) ifelem=*: returnPolishNotation(expr)*PolishNotation(expr) ifelem=/: returnPolishNot

21、ation(expr)/PolishNotation(expr) exprstr=*+11.012.0+24.035.0 expr=exprstr.split() expr.reverse() print(PolishNotation(expr,這是一個(gè)遞歸求解四則運(yùn)算的例程，對(duì)只包含加減乘除括號(hào)和數(shù)字的四則運(yùn)算，中綴運(yùn)算符，進(jìn)行求解 #用遞歸算法的思路來(lái)編寫(xiě)程序 表達(dá)式由項(xiàng)組成，一個(gè)單獨(dú)的項(xiàng)可以是一個(gè)表達(dá)式，一個(gè)項(xiàng)加減另一個(gè)項(xiàng)也可以是一個(gè)表達(dá)式，由是可以調(diào)用項(xiàng)的定義循環(huán)定義無(wú)數(shù)次 項(xiàng)由因子組成，一個(gè)單獨(dú)的因子可以是一個(gè)項(xiàng)，一個(gè)因子乘除另一個(gè)因子也是一個(gè)項(xiàng)，由是可以調(diào)用因子的定義循環(huán)定義無(wú)窮

22、因子可以是由一對(duì)括號(hào)和其內(nèi)的表達(dá)式組成（這里間接構(gòu)造了遞歸調(diào)用的一般形式），因子也可以由一個(gè)數(shù)直接組成（這里間接構(gòu)造了遞歸的終止條件） 一般遞歸是A調(diào)用A，這個(gè)程序是A調(diào)用B，B調(diào)用C，C調(diào)用A的間接遞歸 def表達(dá)式(expr): 結(jié)果=項(xiàng)(expr)#取出第一個(gè)項(xiàng)，表達(dá)式至少有一個(gè)項(xiàng) 還有項(xiàng)=True while還有項(xiàng): iflen(expr)0andexpr-1in+,-:#一開(kāi)始寫(xiě)這個(gè)程序沒(méi)有加上列表是否為空的檢測(cè)，總是出現(xiàn)下標(biāo)越界 操作=expr.pop() if操作=+: 結(jié)果=結(jié)果+項(xiàng)(expr) else: 結(jié)果=結(jié)果-項(xiàng)(expr) else: 還有項(xiàng)=False retur

23、n結(jié)果,這是遞歸求解四則運(yùn)算的第二部分，接上一頁(yè)P(yáng)PT def項(xiàng)(expr): 項(xiàng)結(jié)果=因子(expr)#取出該項(xiàng)的第一個(gè)因子，項(xiàng)至少有一個(gè)因子，也可以由多個(gè)因子乘除構(gòu)成。 還有因子=True while還有因子: iflen(expr)0andexpr-1in*,/:#一開(kāi)始寫(xiě)這個(gè)程序沒(méi)有加上列表是否為空的檢測(cè)，總是出現(xiàn)下標(biāo)越界 操作=expr.pop() if操作=*: 項(xiàng)結(jié)果=項(xiàng)結(jié)果*因子(expr) else: 項(xiàng)結(jié)果=項(xiàng)結(jié)果/因子(expr) else: 還有因子=False return項(xiàng)結(jié)果 def因子(expr): 因子結(jié)果=0 ifexpr-1notin+,-,*,/,(,)

24、:#如果是數(shù)字因子結(jié)果就等于數(shù)字 因子結(jié)果=float(expr.pop() elifexpr-1=(:#如果是括號(hào)就說(shuō)明后面是一個(gè)表達(dá)式 expr.pop()#先把左括號(hào)去掉 因子結(jié)果=表達(dá)式(expr) expr.pop()#再去掉右括號(hào) return因子結(jié)果 expr1=3-4+5*6/2*(2*3+2)+1.0 expr2=expr1.split() expr2.reverse() print(expr2) print(表達(dá)式(expr2,樹(shù)老師上臺(tái)階，一步上一臺(tái)階，或者一步上兩臺(tái)階，對(duì)于給定N個(gè)臺(tái)階有多少種走法。 #假定有N個(gè)臺(tái)階有F(N)種走法。 #走第一步時(shí)，可能走一步，也可能走

25、兩步；F(n)=F(n-1)+F(n-2),由此得到遞歸的一般式 #f(2)=2,f(1)=1；由此得到遞歸的終止條件 def樹(shù)老師走路(n): ifn=1: return1 elifn=2: return2 else: return樹(shù)老師走路(n-1)+樹(shù)老師走路(n-2) print(樹(shù)老師走路(10,遞歸習(xí)題4：爬樓梯 樹(shù)老師爬樓梯，他可以每次走1級(jí)或者2級(jí)，輸入樓梯的級(jí)數(shù)，求不同的走法數(shù) 例如：樓梯一共有3級(jí)，他可以每次都走一級(jí)，或者第一次走一級(jí)，第二次走兩級(jí)，也可以第一次走兩級(jí)，第二次走一級(jí)，一共3種方法,這是遞歸求解放蘋(píng)果問(wèn)題的例程：把M個(gè)同樣的蘋(píng)果放在N個(gè)同樣的盤(pán)子里，允許有的盤(pán)

26、子空著不放，問(wèn)共有多少種不同的分法？（用K表示）5，1，1和1，5，1是同一種分法。 輸入：第一行是測(cè)試數(shù)據(jù)的數(shù)目t（0=t=20）。以下每行均包含二個(gè)整數(shù)M和N，以空格分開(kāi)。1=M，N=10。 輸出：對(duì)輸入的每組數(shù)據(jù)M和N，用一行輸出相應(yīng)的K 思路：設(shè)定m個(gè)蘋(píng)果放進(jìn)n個(gè)盤(pán)子里一共有f(m,n)種方法 1、如果m小于n,則f(m,n)=f(m,m);m小于n時(shí)，總有n-m個(gè)盤(pán)子是空的，可以先把n-m個(gè)盤(pán)子拿走，不影響結(jié)果 2、如果m大于n,則分為兩類(lèi)問(wèn)題有盤(pán)子為空的算法+沒(méi)有盤(pán)子為空的算法 2.1、有盤(pán)子為空的算法則至少有一個(gè)盤(pán)子為空，把這一個(gè)盤(pán)子拿走就演變成求f(m,n-1)的總數(shù) 2.2、沒(méi)有盤(pán)子為空時(shí)，則至少每個(gè)盤(pán)子都有一個(gè)蘋(píng)果，從每個(gè)盤(pán)子里都拿走一個(gè)拼過(guò)，就演變成求f(m-n,n)的總數(shù) 如此構(gòu)成遞歸的一般式 3、遞歸的終止式： 只剩下0個(gè)蘋(píng)果或1個(gè)盤(pán)子的時(shí)候，返回0 deff(m,n): ifmn: returnf(m,m) else: ifm=0: return1 elifn=1: return1 else: returnf(m,n-1)+f(m-n,n)