非數(shù)值計算-課件完整版

教科版（2019版）信息技術(shù)（高中）4.3非數(shù)值計算第4單元計算與問題解決必修1數(shù)據(jù)與計算

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

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

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

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

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