4.3非數(shù)值計算——猜數(shù)字游戲教

學(xué)目

標(biāo)通過分析問題-設(shè)計算法-編程實現(xiàn)-測試運(yùn)行的解決問題的過程，能夠根據(jù)具體問題設(shè)計合適的算法形成解決問題的方案。

了解分治算法的優(yōu)缺點(diǎn)及其在生活中的應(yīng)用。通過“猜數(shù)字小游戲”,了解分治思想，并運(yùn)用二分查找解決實際問題。課

前

復(fù)

習(xí)1.random.randint(1,10)的作用是：（

）知識點(diǎn)檢測A.從1-10之間隨機(jī)生成一個整數(shù)B.生成1-10之間所有整數(shù)C.從1-9之間隨機(jī)生成一個整數(shù)D.生成1-9之間所有整數(shù)Arange(m,n)==>生成[m，n)之間的所有整數(shù)。random是一個生成隨機(jī)數(shù)的模塊，randint()是random的一個函數(shù)，用于生成一個隨機(jī)整數(shù)，使用之前需要導(dǎo)入random（importrandom）。random.randint(m,n)=>從[m,n]之間隨機(jī)生成一個整數(shù)。猜

數(shù)

字

游

戲運(yùn)行”猜數(shù)字游戲“，嘗試描述游戲功能及實現(xiàn)步驟如何編寫代碼實現(xiàn)游戲？1.系統(tǒng)隨機(jī)生成一個數(shù)字2.猜數(shù)字，猜對則跳出程序，否則繼續(xù)猜測，直至5次后跳出，輸出這個數(shù)字。思考：猜

數(shù)

字

游

戲如何編寫代碼實現(xiàn)游戲？1.計算機(jī)隨機(jī)生成一個數(shù)m=random.randint(1,100)3.輸入要猜的數(shù)字t=int(input("請輸入你猜的數(shù)："))2.要猜幾次？foriinrange(5):4.比較m與t若5次之內(nèi)猜中，跳出循環(huán)否則輸出沒有猜中，游戲結(jié)束。終止循環(huán)語句break猜

數(shù)

字

游

戲import①#導(dǎo)入隨機(jī)數(shù)模塊m=random.randint(1,100)foriinrange(5):t=int(input("請輸入你猜的數(shù)："))ift>m:print("大了")②t<m:print("小了")else:print("恭喜你,答對了！")③ift!=m:print("這個數(shù)是：",m)print("5次沒有猜中，游戲結(jié)束")是否是否是否任務(wù)一：將程序補(bǔ)充完整

一

分

治

算

法”猜數(shù)字游戲“，如何猜的又快又準(zhǔn)?枚

舉

算

法二分查找效率低

一

分

治

算

法

二分查找實際上就是分治策略的典型運(yùn)用

大事化小，小事化了分

治

算

法

一

分

治

算

法左邊界low右邊界high目標(biāo)數(shù)x中間數(shù)mid=(low+high)//2

若中間數(shù)mid比目標(biāo)數(shù)x大，則區(qū)間變?yōu)樽蟀雲(yún)^(qū)間，右邊界更新為high=mid-1,low不變。左邊界low右邊界high目標(biāo)數(shù)x中間數(shù)Mid(low+high)//2

若中間數(shù)mid比目標(biāo)數(shù)x小，則區(qū)間變?yōu)橛野雲(yún)^(qū)間，左邊界更新為low=mid+1,high不變。

一

分

治

算

法目標(biāo)數(shù):912345678910low=1high=10mid=(1+10)//2=5<9678910low=mid+1→6high=10mid=8<9910low=mid+1→9high=10mid=9=9第一輪第二輪第三輪最壞的情況需要查找n次滿足:2n>N(N為查找的總數(shù)量)

一

分

治

算

法

再次運(yùn)行”猜數(shù)字游戲”，體驗利用二分查找實現(xiàn)最快的找到數(shù)字“任務(wù)二：

一

分

治

算

法二分法查找最快需要幾步？x=int(input("請輸入要查找的100以內(nèi)的整數(shù):"))step=0#記錄查找次數(shù)low=1#目標(biāo)區(qū)域左邊界high=100#目標(biāo)區(qū)域右邊界while(low<=high):mid=(low+high)//2#中間值step=step+1#查找次數(shù)加ifmid>x:high=①#右邊界前移②mid<x:low=mid+1#左邊界后移else:break#找到目標(biāo)數(shù)據(jù)，退出循環(huán)print("查找次數(shù)為：",③)任務(wù)三：將程序補(bǔ)充完整。統(tǒng)計二分法查找次數(shù)二分查找的前提：被查找的數(shù)據(jù)必須是有序的!

一

分

治

算

法如何對一組無序的數(shù)據(jù)如何進(jìn)行排序呢？lst=[9，6，45，23，48，7]優(yōu)點(diǎn)：效率高缺點(diǎn)：

二

遞歸

算

法lst=[9，6，45，23，48，7]9[6,7][45,23,48][][7][23,45,48][6,7][6,7,9,23,45,48]645[23][48]1.取一個數(shù)作為基數(shù)：如92.將大于基數(shù)的數(shù)和小于基數(shù)的數(shù)分成兩個數(shù)組：left=[6,7],right=[45,23,48]3.分別對left和right重復(fù)執(zhí)行1，2，直到列表元素小于等于一個元素為止4.將left+基數(shù)+right合并----分----治----合遞歸

算

法

二

遞歸

算

法9[6,7][45,23,48][][7][23,45,48][6,7][6,7,9,23,45,48]645[23][48]直接或間接地調(diào)用自身的方法稱為遞歸。可以將遞歸簡單類比為具有自相似性重復(fù)的事物。遞歸

二

遞歸

算

法遞歸的基本思想是把規(guī)模較大的問題層層轉(zhuǎn)化為規(guī)模較小的同類問題求解?？捎谩胺帧?，“治”，“合”三個字概括遞歸的基本思想遞推關(guān)系遞歸的條件邊界條件+len(lst)<=1quickSort(left)+lst[0:1]+quickSort(right)猜

數(shù)

字

游

戲任務(wù)四：將程序補(bǔ)充完整，實現(xiàn)遞歸排序defquickSort(lst):right=[]left=[]iflen(lst)①:returnlstforiinlst[1:]:ifi>=lst[0]:right.append(i)

②:left.appen