資源簡介

(共17張PPT)
Phthon編程------ 5 遞歸算法
微項目5
用遞歸算法優化程序
學習活 過程與目標 核心問題
1、跟蹤遞歸的運行過程，通過數據跟蹤實驗，了解遞歸思想的基本思路和運行過程，如何將大問題拆解為同類的小問題
2、探究遞歸算法的優勢，通過案例對比遞歸與迭代算法的不同，探究遞歸算法的優勢，遞歸的優勢是什么
學習目標
漢諾塔(Hanoi Tower)是根據印度古老傳說形成的一個問題:
有A、B、C三根柱子，A柱上有n個穿孔圓盤(n>1)，盤的尺寸由下到上依次變小，要求把所有的圓盤移動到C柱。
游戲規定，可以將圓盤臨時放在B柱，但大盤不能疊在小盤上面，并且每次只能移動一個圓盤。
漢諾塔問題
用遞歸策略編程
5
4
3
2
1
A
B
C
為漢諾塔游戲設計一個自定義函數，函數名稱為hanoi，包括四個輸人參數，依次為挑戰層數n、起止柱begin、中轉柱temp和終點柱 end，相關的Python代碼如圖所示。
程序代碼中:
① 如果層數n=1，滿足終止條件，打印圓盤移動信息。
② 如果層數n>1，連續三次遞歸調用，依次實現n-1層挑戰、1層挑戰、n-1層挑戰。
#!/usr/bin/env python3# 漢諾塔遞歸求解函數
def hanoi(n,begin,temp,end):
if n==1:
#打印圓盤移動信息
print(“移動”,begin,"-->",end)
else:
# 完成挑戰只需三步
hanoi(n-1,begin,end,temp)
hanoi(1,begin,temp,end)
hanoi(n-1,temp,begin,end)
#函數調用示例
n=5
print(“-- 漢諾塔”，n“層挑戰操作步驟 --”)
hanoi (n, “A", “B",“C")
遞歸函數的規范形式如下:
def函數名([參數列表]):
if 條件表達式: #終止條件
語句
return 值(或表達式) #可省略
else: #遞歸條件
包含自身函數名([參數列表])的語句
遞歸算法的條件
遞歸算法解決問題的核心：遞歸函數的構建。程序運行時，由于遞歸函數不斷調用自身，如果沒有設置終止條件，遞歸調用會形成無限循環。
規范的遞歸函數必須由兩個條件組成:
終止條件
遞歸條件
符合終止條件終止函數調用
符合遞歸條件則函數繼續調用自身。
活動1 跟蹤遞歸的運行過程
解決問題：
假設一個自然數n，累乘是將從1到n的所有自然數相乘，乘積m=1x2x3x4x5x…xn。
遞歸過程：
下面通過一個累乘過程的數據跟蹤檢測小實驗，來體會遞歸算法是如何工作的
遞歸算法是一種反復調用(引用)自身求得結果的算法，使用遞歸算法通常需要定義遞歸函數(直接或間接調用自身的函數)。
遞歸只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量，因此在很多函數編程中習慣使用遞歸來實現循環。
通過將問題重復分解為同類的子問題來解決問題的方法稱為遞歸，它是一種描述問題和解決問題的基本方法。
日常生活中，以相似方法重復事物的現象被稱作遞歸(如照鏡子)，而在計算機領域，遞歸是程序調用自身的編程技巧。
例如n=7 m=1x2x3x4x5x…xn 遞歸的實現過程
#!/usr/bin/env python3
def fact(n): #自定義函數
print("當前n=",n) #跟蹤顯示n，可省略
if n==1: #終止條件
return 1 #結束遞歸
else: #遞歸條件
f=n*fact(n-1) #調用遞歸
print("當前乘積:",f) #跟蹤顯示累乘的積
return f #返回乘積
#主程序
print("m=",fact(7)) #調用遞歸
當前n= 7
當前n= 6
當前n=5
當前n= 4
當前n= 3
當前n= 2
當前n= 1
當前乘積: 2
當前乘積: 6
當前乘積: 24
當前乘積: 120
當前乘積: 720
當前乘積: 5040
m= 5040
累
乘運
行
結
果
遞歸算法的程序實現
fact(7)
7* fact(6)
7*(6*fact(5))
7*(6*fact(5*fact(4)))
7*(6*fact(5*fact(4*fact(3))))
7*(6*fact(5*fact(4*fact(3*fact(2)))))
7*(6*fact(5*fact(4*fact(3*fact(2*fact(1))))))
遞歸算法求解過程
討論
1.遞歸中，自定義函數如何深入展開
2.數據運算順序有何特點
解決問題：
著名的斐波那契數列，又稱為“兔子數列”，因以兔子繁殖為例而得名。
某飼養場引進一對剛出生的新品種兔子，這種兔子第2個月長為成年兔，從第3個月起一對成年兔每個月都新生一對幼兔。每對兔子都經歷這樣的出生、成長、繁殖過程。假設所有兔子都不死，到第12個月時，該飼養場共有兔子多少對
活動2 探究遞歸算法的優勢
#!/usr/bin/envpython3
# 幼兔和成年兔第i月當月的數量分別用a、b表示
a=1 #幼兔第1月當月的數量(單位:對)
b=0 # 成年兔第1月當月的數量(單位:對)
print("第 %d 個月飼養場兔子共計 %d 對"%(1,a+b))
n=12 #總月數
#從第2月到第n月進行迭代計算
for i in range(2.n+1):
t=b # 先把上月成年兔數量存一下
b=a+b #本月成年兔數量=上月幼兔數量+成年兔數量
a=t #本月新生幼兔數量=上月成年免數量
print("第 %d個月飼養場兔子共計 %d 對“%(i.a+b))
1. 迭代算法
迭代算法的核心是通過將迭代表達式不斷重復執行，用變量的舊值推出新值，直到完成指定計算。
兔子數列形如1,1,2,3,5,8,13,21,34……
如果設f(i)為該數列的第i項，當i大于2時，f(i)=f(i-1)+f(i-2)。
通過定義遞歸函數完成數列的推算，代碼示例如圖所示。
2.遞歸算法——完成程序設計
#!/usr/bin/env python3
def f(n):
if n<=2:
return 1
else:
return f(n-1)+f(n-2) #第n月兔子為前兩個月之和
for i in range(1,13):
print("第",i,"月兔的數量是",f(i))
對比兩種解決兔子繁殖問題的程序代碼可以發現
迭代算法使用的是循環結構;
而遞歸算法通過調用自身，變成簡單問題求解，再由簡單問題逐步“回歸”得出復雜問題的答案。
迭代算法 與 遞歸算法 的對比
返回第6頁
課堂小結
什么是遞歸算法？
如何構造遞歸函數？
迭代算法的優勢是什么？
遞歸算法的優勢是什么？

展開更多......

收起↑