資源簡介

(共26張PPT)
高中信息技術 必修1 數據與計算
4.3 非數值計算
第二課時 神奇的遞歸
學習目標
01
02
運用合適的算法形成解決問題的方案；
了解算法中的分治思想；
03
體驗遞歸算法，并結合具體問題開展編程實踐。
4.3 非數值計算——神奇的遞歸
項目內容
本節我們將圍繞“生活中的算法”項目，嘗試用“算法的眼睛”看待生活，用“算法的思維”去解決實際問題。
項目任務
任務一：巧翻字典
任務二：玩轉“漢諾塔”游戲
本節任務
玩“漢諾塔”游戲
“漢諾塔”游戲由來：有一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。
4.3 非數值計算——神奇的遞歸
4.3 非數值計算——神奇的遞歸
“漢諾塔”游戲規則來：
1、有三根相鄰的柱子，標號為A,B,C。
2、A柱子上從下到上按金字塔狀疊放著n個不同大小的圓盤。
3、現在把所有盤子一個一個移動到柱子B上，并且每次移動同一根柱子上都不能出現大盤子在小盤子上方。
A
B
C
玩“漢諾塔”游戲
4.3 非數值計算——神奇的遞歸
請打開學案中的“漢諾塔”游戲，趕快體驗一下吧！
玩“漢諾塔”游戲
4.3 非數值計算——神奇的遞歸
分析玩的過程
以3個木盤為例
A
B
C
A B
A C
4.3 非數值計算——神奇的遞歸
分析玩的過程
以3個木盤為例
A
B
C
C B
A C
4.3 非數值計算——神奇的遞歸
分析玩的過程
以3個木盤為例
C
B
A
B C
B A
4.3 非數值計算——神奇的遞歸
分析玩的過程
以3個木盤為例
A
B
C
A C
總結移動規律
三步移動
將A上面兩個木盤從A B
將A最下面的一個木盤從A C
將B上面兩個木盤從B C
將A上面一個木盤從A C
將B最下面一個木盤從A B
將C上面一個木盤從C B
將B上面一個木盤從B A
將B最下面一個木盤從B C
將A上面一個木盤從A C
3個木盤的移動問題成功解決了，
就可以解決更多木盤的移動問題了。
知識探究：遞歸
直接或間接地調用自身的方法稱為遞歸。可以將遞歸簡單類比為具有自相似性重復的事物。
遞歸是計算科學領域中一種重要的計算思維模式。它既是一種抽象表達的手段，也是一種問題求解的重要方法。
知識探究：遞歸函數
遞歸函數是只用函數自身來定義該函數的方法。如斐波那契數列“1,1,2,3,5,8,13……”,可以遞歸定義為：
F(n)=
1(n=1或n=2)
F(n-1)+F(n-2)(n>2)
知識探究：遞歸的重要組成
遞推關系是遞歸的重要組成；
邊界條件是遞歸的另一要素（保證遞歸能在有限次計算后得出結果，而不會產生無限循環地情況）
F(n)=
1(n=1或n=2)
F(n-1)+F(n-2)(n>2)
邊界條件
遞推關系
知識探究：遞歸的基本思想
遞歸的基本思想是把規模較大的問題層層轉化為規模較小的同類問題求解。對遞歸而言，遞推與回歸，二者缺一不可。
1）分：將原有問題分解成K個子問題。
2）治：對這K個子問題分別求解。如果子問題的規模仍然不夠小，則將其再分解為K個子問題，如此進 行下去，直到問題足夠小時，就很容易求出子問題的解。
3）合：將求出的小規模問題的解合并為一個更大規模問題的解，自下而上逐步求出原問題的解。
遞歸可用“分”，“治”，“合”三個字概括
“漢諾塔”游戲程序實現
hanoi(盤子數，起始桿，過渡桿，目標桿)
hanoi(n,A,B,C)
從A移到C
hanoi(n-1,B,A,C)
hanoi(n-1,A,C,B)
前n-1個木盤從A移動到了B
前n-1個木盤從B移動到了C
漢諾塔遞歸過程圖示
“漢諾塔”游戲程序實現
上機實踐
“漢諾塔”游戲程序執行的過程
def move(n,s,m,t):
if n==1:
print(s,'-->',t)
move(n-1,s,t,m)
print(s,'-->',t)
move(n-1,m,s,t) move(3,'a','b','c')
move(3,'a','b','c')調用
move(2,'a','c','b')
print('a','-->','c')
move(2,'b','a','c')
move(1,'a','b','c')
print('a','-->','b')
move(1,'c','a','b')
move(1,'b','c','a')
print('b','-->','c')
move(1,'a','b','c')
輸出：a-->c輸出：a-->b
輸出：c-->b輸出：a-->c輸出：b-->a
輸出：b-->c輸出：a-->c
else:
拓展練習
計算“漢諾塔”游戲移動的次數。
2個金片，移動幾次
4個金片，移動幾次
5個金片，移動幾次
3個金片，移動幾次
3次
15次
31次
7次
……
n個金片，移動幾次
2n-1次
拓展練習
計算“漢諾塔”游戲移動的次數。
def f(n):
if n==0:
return 0
else:
return 2*f(n-1)+1
x=int(input("請輸入塔的個數："))
print("需要移動",f(x),"次")
input("運行完畢，請按回車鍵退出...")
方法1
拓展練習
計算“漢諾塔”游戲移動的次數。
方法2
c=0
c=c+1
c=c+1
拓展知識
迭代程序可以轉換成等價的遞歸程序。以上一節中計算斐波那契數列第N項的值為例，程序間的轉換如表所示。
迭代與遞歸算法都需要重復執行某些代碼，兩者既有區另又有密切的聯系。迭代是重復反饋過程的活動，其目的通常是逼迫所需目標或結果。遞歸是重復調用函數自身。遞歸滿足終止條件的情況時逐層返回。迭代則通常使用計數器結束循環。
拓展知識
迭代 遞歸
兩種算法均需重復執行某些代碼
一次次重復過程 從而接近或達到目標或結果 重復調用函數自己本身
層層化解為規模較小的同類問題
三步驟：確定迭代變量 建立迭代關系式 控制迭代過程 遞歸二要素：遞推+回歸
步驟：確定遞推關系式
確定邊界條件
用循環控制迭代進程 遇到邊界條件時逐層返回
循環次數較大時，迭代效率明顯高于遞歸
課堂小結
1. 理解遞歸思想。
2. 理解遞歸算法。
3. 結合具體問題開展編程實踐。
課后作業
了解生活中的遞歸
有5個人坐在一起，問第五個人多少歲？他說比第4個人大2歲。問第4個人歲數，他說比第3個人大2歲。問第三個人，又說比第2人大兩歲。問第2個人，說比第一個人大兩歲。最后問第一個人，他說是10歲。請問第五個人多大？
學無止境 永攀高峰
感謝觀看

展開更多......

收起↑