4.3非數(shù)值計(jì)算+課件+【知識(shí)精講精研】教科版（2019）高中信息技術(shù)必修1

4.3非數(shù)值計(jì)算2021.04CHEN學(xué)習(xí)目標(biāo)了解算法設(shè)計(jì)的分治思想，并運(yùn)用二分查找解決實(shí)際問(wèn)題體驗(yàn)遞歸算法，并結(jié)合具體問(wèn)題開展編程實(shí)踐運(yùn)用合適的算法形成解決問(wèn)題的方案123

運(yùn)行利用python編寫的“猜數(shù)字”游戲，計(jì)算機(jī)在1-100

中隨機(jī)產(chǎn)生一個(gè)數(shù)，試試看你要猜多少次才能猜中。課堂導(dǎo)入程序源代碼及執(zhí)行結(jié)果截圖：如何猜得又快又準(zhǔn)？二分查找又叫折半查找，將數(shù)列有序排列，采用跳躍式查找數(shù)據(jù)；以遞增數(shù)列為例，先以中點(diǎn)位置的元素作為比較對(duì)象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列縮小為左半部分，否則為右半部分；每一次比較后都可以將查找區(qū)間縮小一半。二分查找法是一種高效的查找方法。它可以明顯減少比較次數(shù)，提高查找效率。在一個(gè)有n個(gè)元素的有序序列中，利用二分查找大約需要log2n次。課堂活動(dòng)1如何實(shí)現(xiàn)？請(qǐng)學(xué)生思考：利用自然語(yǔ)言如何描述？利用程序如何實(shí)現(xiàn)？統(tǒng)計(jì)二分查找次數(shù)的源代碼和程序運(yùn)行截圖：嘗試用二分法求x3-x2+x-1=0在[-5,5]區(qū)間的解。deff(x): #定義方程returnx**3-x**2+x-1a=float(input("請(qǐng)輸入解區(qū)間的左邊界："))b=float(input("請(qǐng)輸入解區(qū)間的右邊界："))whileabs(b-a)>1e-6:x0=(a+b)/2iff(a)*f(x0)<0:b=x0iff(b)*f(x0)<0:a=x0iff(x0)==0:breakprint("解為:",x0)input("運(yùn)行完畢，請(qǐng)按回車鍵退出...")練習(xí)1二分法：對(duì)于在區(qū)間[a,b]上連續(xù)不斷，且滿足f(a)f(b)<0的函數(shù)y=f(x)，通過(guò)不斷地把函數(shù)f(x)的零點(diǎn)所在的區(qū)間二等分，使區(qū)間的兩個(gè)端點(diǎn)逐步逼近零點(diǎn)，進(jìn)而得到零點(diǎn)近似值的方法叫做二分法。程序源代碼和運(yùn)行界面截圖：1.凡治眾如治寡，分?jǐn)?shù)是也。（摘自孫子兵法）2.查找的基本算法有：順序查找、二分查找，分塊查找、哈希查找等。拓展知識(shí)3.當(dāng)while循環(huán)中執(zhí)行break語(yǔ)句時(shí)，循環(huán)會(huì)馬上終止。4.python中的sort()可以用于數(shù)據(jù)排序。

例如，以下語(yǔ)句：x=[4,6,2,1,5,9]x.sort()可以將列表x按從小到大的順序排列。

“漢諾塔”游戲源于一個(gè)古老的印度傳說(shuō)。如下圖所示，在木板上有A、B、C三根桿，A桿上有若干木盤，規(guī)定每次移動(dòng)一個(gè)木盤。且小的木盤只能疊在大的木盤上面。請(qǐng)?jiān)O(shè)計(jì)算法，用盡可能少的次數(shù)把所有的木盤從A桿全部移到C桿上。課堂活動(dòng)2直接或間接地調(diào)用自身的方法稱為遞歸?？梢詫⑦f歸簡(jiǎn)單類比為具有自相似性重復(fù)的事物。遞歸是計(jì)算科學(xué)領(lǐng)域中一種重要的計(jì)算思維模式。它既是一種抽象表達(dá)的手段，也是一種問(wèn)題求解的重要方法。遞歸遞歸函數(shù)是只用函數(shù)自身來(lái)定義該函數(shù)的方法。如斐波那契數(shù)列“1,1,2,3,5,8,13……”,可以遞歸定義為：F(n)=1(n=1或n=2)F(n-1)+F(n-2)(n>2)遞歸函數(shù)遞歸的基本思想遞歸的基本思想是把規(guī)模較大的問(wèn)題層層轉(zhuǎn)化為規(guī)模較小的同類問(wèn)題求解。對(duì)遞歸而言，遞推與回歸，二者缺一不可。遞歸可用“分”，“治”，“合”三個(gè)字概括1）分：將原有問(wèn)題分解成K個(gè)子問(wèn)題。2）治：對(duì)這K個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則將其再分解為K個(gè)子問(wèn)題，如此進(jìn)

行下去，直到問(wèn)題足夠小時(shí)，就很容易求出子問(wèn)題的解。3）合：將求出的小規(guī)模問(wèn)題的解合并為一個(gè)更大規(guī)模問(wèn)題的解，自下而上逐步求出原問(wèn)題的解。漢諾塔游戲源代碼和運(yùn)行界面截圖：漢諾塔hanno(n-1,s,t,m)#將前n-1個(gè)盤子從s移動(dòng)到m上print(s,'-->',t)#將最底下的最后一個(gè)盤子從s移動(dòng)到t上hanno(n-1,m,s,t)#將m上的n-1個(gè)盤子移動(dòng)到t上要完成最后一步，那么最后一步的前一步要做什么。漢諾塔-程序1.理解遞歸思想。2.理解遞歸算法。3.理解二分查找思想，運(yùn)用二分算法解決實(shí)際問(wèn)題。課堂小結(jié)結(jié)合4.2的知識(shí)，計(jì)算“漢諾塔”游戲移動(dòng)的次數(shù)。deff(n):ifn==0:return0else:return2*f(n-1)+1x=int(input("請(qǐng)輸入塔的個(gè)數(shù)："))print("需要移動(dòng)",f(x),"次")input("運(yùn)行完畢，請(qǐng)按回車鍵退出...")練習(xí)2漢諾塔移動(dòng)次數(shù)源代碼和運(yùn)行界面截圖：迭代程序可以轉(zhuǎn)換成等價(jià)的遞歸程序。以上一節(jié)中計(jì)算斐波那契數(shù)列第N項(xiàng)的值為例，程序間的轉(zhuǎn)換如表所示。