第5課

經(jīng)典算法—枚舉與遞歸第三單元

基于算法的編程基礎(chǔ)山東省2024青島版初中Python同步教學(xué)設(shè)計(jì)技術(shù)支持1什么是枚舉、遞歸算法？2如何使用枚舉算法解決百錢(qián)買(mǎi)百雞問(wèn)題？如何用遞歸算法解決斐波那契數(shù)列問(wèn)題？3在程序設(shè)計(jì)中如何使用枚舉、遞歸算法解決生活中的問(wèn)題？學(xué)習(xí)目標(biāo)目錄contents0102探究二用遞歸算法解決問(wèn)題03探究三我實(shí)踐我創(chuàng)新04課堂小結(jié)探究一用枚舉算法解決問(wèn)題基本思想

枚舉算法的基本思想是把問(wèn)題所有可能的解一一列舉，然后逐一判斷每一個(gè)列舉出的解是否為正解。一一列舉，逐個(gè)檢驗(yàn)解題思路探究一

用枚舉算法解決問(wèn)題1不能遺漏任何一個(gè)正確解盡可能地縮小解的枚舉范圍，提高算法的效率確定枚舉對(duì)象、范圍確定判斷條件

逐一枚舉可能解并判斷操作模塊程序一一列舉循環(huán)結(jié)構(gòu)for語(yǔ)句/while語(yǔ)句逐個(gè)比較判斷分支結(jié)構(gòu)if語(yǔ)句枚舉算法程序?qū)崿F(xiàn)11探究一

用枚舉算法解決問(wèn)題在一串不同的鑰匙中找到機(jī)房門(mén)鑰匙。計(jì)算機(jī)程序123計(jì)算并聯(lián)電路的電阻值。查找100以內(nèi)所有能同時(shí)被3和7整除的正整數(shù)。下列問(wèn)題能否用枚舉算法求解11探究一

用枚舉算法解決問(wèn)題優(yōu)點(diǎn)：是對(duì)現(xiàn)實(shí)生活的直接描述，易于理解。注意事項(xiàng)：要做到既不遺漏任何一個(gè)解，也不重復(fù)枚舉。探究一

用枚舉算法解決問(wèn)題1百錢(qián)百雞100元買(mǎi)100只雞，公雞5元1只，母雞3元1只，小雞1元3只。求公雞、母雞和小雞各應(yīng)買(mǎi)的數(shù)量。

最多買(mǎi)100只雞，每種雞的數(shù)量范圍是1—100，我們用三個(gè)變量來(lái)存儲(chǔ)3種雞的數(shù)量，a代表公雞數(shù)量，b代表母雞數(shù)量，c代表小雞數(shù)量，可列出方程組：0<=a<=100,0<=b<=100,0<=c<=100a+b+c=0,5*a+3*b+c/3=1008x+y+z=100and5*a+3*b+c/3=100

開(kāi)始結(jié)束z=z+1探究一

用枚舉算法解決問(wèn)題1x=1to100y=1to100Z=1to100輸出x、y、zy=y+1x=x+1FFFFforxinrange(1,100):foryinrange(1,100):forzinrange(1,100):if(x+y+z=100)and(x+y+z=100)print(“雞翁:”,x,“雞翁母:”,y,“雞雛:”,z)探究二

用遞歸算法解決問(wèn)題2斐波那契數(shù)列（Fibonaccisequence），又稱黃金分割數(shù)列，因數(shù)學(xué)家萊昂納多·斐波那契（LeonardodaFibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”。

斐波那契數(shù)列指的是這樣一個(gè)數(shù)列：0，1，1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，2584，4181，6765，10946，17711……

它的規(guī)律是：這個(gè)數(shù)列從第3項(xiàng)開(kāi)始，每一項(xiàng)都等于前兩項(xiàng)之和。探究二

用遞歸算法解決問(wèn)題2分析問(wèn)題探究二

用遞歸算法解決問(wèn)題21月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合計(jì)1123581321345589144分析問(wèn)題探究二

用遞歸算法解決問(wèn)題2遞歸算法：函數(shù)不斷引用自身，直到引用的對(duì)象已知，否則會(huì)成為死循環(huán)而不能正常結(jié)束。思路清晰，代碼少。斐波那契數(shù)列探究二

用遞歸算法解決問(wèn)題2探究二

用遞歸算法解決問(wèn)題2開(kāi)始返回f(n)=f(n-1)+f(n-2)n==1orn==2輸出月份返回f(n)=1輸出x、y、z結(jié)束輸出n個(gè)月后兔子對(duì)數(shù)為f(n)設(shè)計(jì)算法18%28%探究二

用遞歸算法解決問(wèn)題1編寫(xiě)程序deff(n):

ifn==1or

:

return1

else:

returnf(n-1)+f(

)n=int(input(“請(qǐng)輸入月份：”))print（n,“個(gè)月后兔子對(duì)數(shù)為：”，f(n)）探究二：用遞歸算法解決問(wèn)題2遞歸

遞歸算法是把問(wèn)題轉(zhuǎn)化為規(guī)?？s小了的同類問(wèn)題的子問(wèn)題，然后遞歸調(diào)用函數(shù)（或過(guò)程）來(lái)表示問(wèn)題的解。因此，設(shè)計(jì)遞歸算法的關(guān)鍵在于，確定遞歸公式（過(guò)程的描述中包含他本身）和確定邊界（終了）條件。遞歸作為一種算法被應(yīng)用在程序設(shè)計(jì)語(yǔ)言中，是指函數(shù)/過(guò)程/子程序在運(yùn)行過(guò)程中直接或間接調(diào)用自身而產(chǎn)生的重入現(xiàn)象。探究二：用遞歸算法解決問(wèn)題2探究二：用遞歸算法解決問(wèn)題2上臺(tái)階:10級(jí)臺(tái)階每次可上1級(jí)或2級(jí)，有多少種上法?1級(jí)臺(tái)階1 1種2級(jí)臺(tái)階 1+1，2 2種3級(jí)臺(tái)階 1+1+1，1+2，2+13種4級(jí)臺(tái)階1+1+1+1，1+1+2，1+2+1，2+1+1，2+25種……

……

……10級(jí)臺(tái)階

？若對(duì)第一步進(jìn)行分析，則有兩種情況：假設(shè)第一步上1級(jí)，則余n-1級(jí)。假設(shè)第一步上2級(jí)，則余n-2級(jí)。12345678910123581321345589設(shè)Sn為n級(jí)的上法，則有：Sn=S(n-1)+S(n-2)

(n≥3)S1=1S2=2探究二：用遞歸算法解決問(wèn)題212遞歸算法是把問(wèn)題轉(zhuǎn)化為規(guī)?？s小了的同類問(wèn)題的子問(wèn)題