資源簡介

(共21張PPT)
4.3非數值計算
學習目標
了解算法設計的分治思想，并運用二分查找解決實際問題
體驗遞歸算法，并結合具體問題開展編程實踐
運用合適的算法形成解決問題的方案
1
2
3
運行利用python編寫的“猜數字”游戲，計算機在1-100
中隨機產生一個數，試試看你要猜多少次才能猜中。
課堂導入
程序源代碼及執行結果截圖：
如何猜得又快又準？
二分查找又叫折半查找，將數列有序排列，采用跳躍式查找數據；以遞增數列為例，先以中點位置的元素作為比較對象，如果要找的元素值小于該中點元素，則將待查序列縮小為左半部分，否則為右半部分；每一次比較后都可以將查找區間縮小一半。
二分查找法是一種高效的查找方法。它可以明顯減少比較次數，提高查找效率。在一個有n個元素的有序序列中，利用二分查找大約需要log2n次。
課堂活動1
如何實現？
請學生思考：利用自然語言如何描述？利用程序如何實現？
統計二分查找次數的源代碼和程序運行截圖：
嘗試用二分法求 x3 - x2 + x - 1 = 0 在[-5,5]區間的解。
def f(x): #定義方程
return x**3-x**2+x-1
a=float(input("請輸入解區間的左邊界："))
b=float(input("請輸入解區間的右邊界："))
while abs(b-a)>1e-6:
x0=(a+b)/2
if f(a)*f(x0)<0:
b=x0
if f(b)*f(x0)<0:
a=x0
if f(x0)==0:
break
print("解為:",x0)
input("運行完畢，請按回車鍵退出...")
練習1
二分法：對于在區間[a,b]上連續不斷，且滿足f(a)f(b)<0的函數y=f(x)，通過不斷地把函數f(x)的零點所在的區間二等分，使區間的兩個端點逐步逼近零點，進而得到零點近似值的方法叫做二分法。
程序源代碼和運行界面截圖：
1. 凡治眾如治寡，分數是也。（摘自孫子兵法）
2. 查找的基本算法有：順序查找、二分查找，分塊查找、哈希查找等。
拓展知識
3. 當while循環中執行break語句時，循環會馬上終止。
4. python中的sort( )可以用于數據排序。
例如，以下語句：
x=[4,6,2,1,5,9]
x.sort( )
可以將列表x按從小到大的順序排列。
“漢諾塔”游戲源于一個古老的印度傳說。如下圖所示，在木板上有A、B、C三根桿，A桿上有若干木盤，規定每次移動一個木盤。且小的木盤只能疊在大的木盤上面。請設計算法，用盡可能少的次數把所有的木盤從A桿全部移到C桿上。
課堂活動2
直接或間接地調用自身的方法稱為遞歸。可以將遞歸簡單類比為具有自相似性重復的事物。
遞歸是計算科學領域中一種重要的計算思維模式。它既是一種抽象表達的手段，也是一種問題求解的重要方法。
遞歸
遞歸函數是只用函數自身來定義該函數的方法。如斐波那契數列“1,1,2,3,5,8,13……”,可以遞歸定義為：
F(n)=
1(n=1或n=2)
F(n-1)+F(n-2)(n>2)
遞歸函數
遞歸的基本思想
遞歸的基本思想是把規模較大的問題層層轉化為規模較小的同類問題求解。對遞歸而言，遞推與回歸，二者缺一不可。
遞歸可用“分”，“治”，“合”三個字概括
1）分：將原有問題分解成K個子問題。
2）治：對這K個子問題分別求解。如果子問題的規模仍然不夠小，則將其再分解為K個子問題，如此進 行下去，直到問題足夠小時，就很容易求出子問題的解。
3）合：將求出的小規模問題的解合并為一個更大規模問題的解，自下而上逐步求出原問題的解。
漢諾塔游戲源代碼和運行界面截圖：
漢諾塔
hanno(n-1,s,t,m) #將前n-1個盤子從s移動到m上
print(s,'-->',t) #將最底下的最后一個盤子從s移動到t上
hanno(n-1,m,s,t) #將m上的n-1個盤子移動到t上
要完成最后一步，那么最后一步的前一步要做什么。
漢諾塔-程序
1. 理解遞歸思想。
2. 理解遞歸算法。
3. 理解二分查找思想，運用二分算法解決實際問題。
課堂小結
結合4.2的知識，計算“漢諾塔”游戲移動的次數。
def f(n):
if n==0:
return 0
else:
return 2*f(n-1)+1
x=int(input("請輸入塔的個數："))
print("需要移動",f(x),"次")
input("運行完畢，請按回車鍵退出...")
練習2
漢諾塔移動次數源代碼和運行界面截圖：
迭代程序可以轉換成等價的遞歸程序。以上一節中計算斐波那契數列第N項的值為例，程序間的轉換如表所示。
迭代與遞歸算法都需要重復執行某些代碼，兩者既有區另又有密切的聯系。迭代是重復反饋過程的活動，其目的通常是逼迫所需目標或結果。遞歸是重復調用函數自身。遞歸滿足終止條件的情況時逐層返回。迭代則通常使用計數器結束循環。
拓展知識

展開更多......

收起↑