4.3《非數(shù)值計算》第一課時

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

學目

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

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

前

復

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

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

數(shù)

字

游

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

數(shù)

字

游

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

數(shù)

字

游

戲import①#導入隨機數(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次沒有猜中，游戲結束")是否是否是否任務一：將程序補充完整

一

分

治

算

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

舉

算

法二分查找效率低

一

分

治

算

法

二分查找實際上就是分治策略的典型運用

大事化小，小事化了分

治

算

法

一

分

治

算

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

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

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

一

分

治

算

法目標數(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ù)量)

一

分

治

算

法

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

一

分

治

算

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

一

分

治

算

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

二

遞歸

算

法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重復執(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]直接或間接地調用自身的方法稱為遞歸?？梢詫⑦f歸簡單類比為具有自相似性重復的事物。遞歸

二

遞歸

算

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

數(shù)

字

游

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

②:left.appen