資源簡介

(共17張PPT)
第四單元 非數值計算
4.3 非數值計算
---探尋“漢諾塔”中的奧秘
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
二分查找/折半查找 p112
二分思想：將數列有序排列，采用跳躍的方式查找數據。
左邊界
flag1
右邊界
flag2
目標數x
中間數
mid
！！！若中間數mid比目標數x大，則區間變為左半區間，右邊界更新
左邊界
flag1
右邊界
flag2
目標數x
中間數
mid
！！！若中間數mid比目標數x小，則區間變為右半區間，左邊界更新
在有n個元素的有序序列中，利用二分查找大約需要log2n次。
n = 1000
需要10次
方法：以遞增數列為例，以中點位置元素作為比較對象，若要查找元素值小于該中點元素，將待查找序列縮小為左半部分，否則為右半部分。每次比較后都能將查找區間縮小一半。
找一半
按照順序找一半，
一比較，舍一半。
繼續找一半，
一半又一半，
快速找答案！
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
分治策略：
其設計思想為，將一個難以直接解決的大問題，分割成較小的同類問題，各個擊破，最終達到解決問題的目的。
A B C D E F G H I
需要解決的問題
第一次分割
第二次分割
第三次分割
二分查找
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
有了實際操作經驗，我們來嘗試完善下面的二分查找程序。
填充代碼，調試程序
優勢：明顯減少比較次數，提高查找效率；
局限：被查找數據必須是有序的。
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
如果輸入的數據不在范圍內，會出現什么結果呢？程序還需要在哪些地方進行完善？大家一起來試試吧。
x=int(input(“請輸入要查找的數據：＂））
step=0 ＃記錄查找次數
flagl=l ＃目標區域左邊界
flag2=400 ＃目標區域右邊界
if x>flag2 or xwhile(flag2-flag1>1) ＃區間數據范圍小于1則結束循環
mid=（flag1+flag2)/2 ＃中間值
step=step+1 ＃查找次數加1
if mid>x:
flag2=mid #有邊界前移
elif midflag1=mid #左邊界后移
else:
break ＃恰好找到目標數據， 退出循環
print(“查詢次數為：”，step) #輸出次數
else:
print(“查詢超出范圍。”)
循環結構：計算機程序周而復始地重復同樣的步驟，稱為循環。
知識點回顧
s=1
for i in range(1,6):
s=s*i
print（s）
如果求5！的結果，你可以用循環實現嗎？
如果求任意數的階乘呢？
while
自定義函數——可以復用的代碼
知識點回顧
基本格式
def 函數名(參數)：
語句或語句組
return 返回值
n可以取任意的值，完成調用。
知識點分析
分解：
5*4！
5*4*3！
5*4*3*2！
5*4*3*2*1！
5！可以如何求解呢？
得出：
5！=5*4！
4！=4*3！
3！=3*2！
2！=2*1！
F（n）=
1（n=1）
n*f(n-1) (n>2)
調用本身
遞歸
遞歸算法
直接或間接地調用自身的方法稱為遞歸。可以將遞歸簡單類比為具有自相似性重復的事物。
遞歸的基本思想
遞歸的“分”-“治”-“合”
把規模較大的問題層層轉化為規模較小的同類問題求解。對遞歸而言，遞推與回歸，二者缺一不可。
1）分：將原有問題分解成K個子問題。
2）治：對這K個子問題分別求解。如果子問題的規模仍然不夠小，則將其再分解為K個子問題，如此進行下去，直到問題足夠小時，就很容易求出子問題的解。
3）合：將求出的小規模問題的解合并為一個更大規模問題的解，自下而上逐步求出原問題的解。
探尋漢諾塔的奧秘
漢諾塔(Tower of Hanoi)源于印度傳說中，大梵天創造世界時造了三根金鋼石柱子，其中一根柱子自底向上疊著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。
e7d195523061f1c0c2b73831c94a3edc981f60e396d3e182073EE1468018468A7F192AE5E5CD515B6C3125F8AF6E4EE646174E8CF0B46FD19828DCE8CDA3B3A044A74F0E769C5FA8CB87AB6FC303C8BA3785FAC64AF5424764E128FECAE4CC72BD54E486F2F2A60F51B8A1D54097D49F626B96969F5CCE921267A92A2F22AC8A839D5EE3DCAA21587D0441DCE9CD8276
解決移動3個木盤的問題。
第1步：A→C
第2步：A→B
第3步：C→B
第4步：A→C
第5步：B→A
第6步：B→C
第7步：A→C
A
B
C
尋找算法
如果是n個盤子呢？
先把最大圓盤上方的所有圓盤,即n-1個圓盤從起始桿s移動到過渡桿m；
接著把最大圓盤，即第n個圓盤移動到目標桿t；
再把過渡桿m上的圓盤移動到目標桿t。
S m t
當n>1時：
def hanoi(n, ____,_____,_____):
hanoi(n-1, ____,____,____)
print(__ , ‘-->’, ____)
hanoi(n-1, ___,_____,____)
s
m
t
if n==1:
print(__ , ‘-->’, ____)
else:
起始桿
中間桿
目標桿
探尋漢諾塔的奧秘
先把最大盤子上方的所有盤子,即n-1個盤子從起始桿s移動到過渡桿m；
接著把最大盤子，即第n個盤子移動到目標桿t；
再把過渡桿m上的盤子移動到目標桿t。
當n=1時：s→t
s
t
m
s
t
s
t
m
s
t
你能知道圓盤一共移動了多少次嗎？
想一想什么時候需要計數呢？自主完善漢諾塔次數.py程序
想一想什么時候需要計數呢？
課堂小結
遞歸：直接或間接地調用自己的方法。
遞：分解調用
有限次數
歸： 求解返回
分
治
合
參考代碼：

展開更多......

收起↑