資源簡介

(共20張PPT)
4.3非數值計算
第二課時
循環結構：計算機程序周而復始地重復同樣的步驟，稱為循環。
知識點回顧
例如：
For n in range(1,100)：
print(‘我愛你，中國’)
例如：
n=1
while n<=100：
print(‘我愛你，中國’)
n=n+1
自定義函數——可以復用的代碼
知識點回顧
基本格式
def 函數名(參數)： #函數說明（函數實現功能）
語句或語句組 # 空四格
return 返回值
Part 01
任務驅動
求解5！、10！、100!值為多少？
5！的階乘 1*2*3*4*5
程序代碼：
s=1
for i in range(1,6):
s=s*i
print（s）
請同學完善程序，運行程序能同時計算出5！、10！、100!值
循環 復制粘貼，修改代碼
自定義函數
策略
01
02
調用 自定義函數
新知新授
Part 02
比一比誰的速度快？
6！階乘值是多少？
知識點分析,運用分支策略——分
6！的值
6*5！
6*5*4！
6*5*4*3！
6*5*4*3*2！
6*5*4*3*2*1！
6*5*4*3*2*1*0！
6*5*4*3*2*1*0*-1!
……………
知識點分析,運用分支策略——治
6！的值
6*5！
6*5*4！
6*5*4*3！
6*5*4*3*2！
6*5*4*3*2*1！
6*5*4*3*2*1*0！
6*5*4*3*2*1*0*-1!
……………
F（n）=
1（n=1）
n*f(n-1) (n>2)
知識點分析,運用分支策略——合
F（n）=
1（n=1）
n*f(n-1) (n>2)
遞歸算法
直接或間接地調用自身的方法稱為遞歸。可以將遞歸簡單類比為具有自相似性重復的事物。
遞歸的基本思想
遞歸的基本思想是把規模較大的問題層層轉化為規模較小的同類問題求解。對遞歸而言，遞推與回歸，二者缺一不可。
遞歸可用“分”，“治”，“合”三個字概括
1）分：將原有問題分解成K個子問題。
2）治：對這K個子問題分別求解。如果子問題的規模仍然不夠小，則將其再分解為K個子問題，如此進 行下去，直到問題足夠小時，就很容易求出子問題的解。
3）合：將求出的小規模問題的解合并為一個更大規模問題的解，自下而上逐步求出原問題的解。
新知新授
Part 03
體驗經典小游戲——漢諾塔
漢諾塔(Tower of Hanoi)源于印度傳說中，大梵天創造世界時造了三根金鋼石柱子，其中一根柱子自底向上疊著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
初始狀態 第四步
第一步 第五步
第二步 第六步
第三步 第七步
重點難點解讀
遞歸可用“分”，“治”，“合”三個字概括
2、漢諾塔的遞歸
1）漢諾塔的遞歸過程：
將N個木盤從A桿移動到C桿，需要借助中間的B桿，只要超過一個木盤，在移動過程中，總會存在起始桿、過渡桿及目標桿的問題。因此，定義函數時，用到了4個參數：haooi(n,s,m,t),n表示需要移動的盤子數量，S表示盤子的起始桿，m表示中間過渡桿，t表示目標桿。可用下圖表示：
編程如下：
總結
1. 理解遞歸思想。
2. 理解遞歸算法。
3. 迭代與遞歸的異同。
作業
思考：斐波那契數列能否用遞歸算法解決問題。
感謝聆聽

展開更多......

收起↑