4.3非數(shù)值計算課件-高中信息技術(shù)教科版必修一課件

非數(shù)值計算Non-numericCalculations朔州市實驗中學(xué)校李娜目標(biāo)運用合適的算法形成解決問題的方案。GOALS體驗遞歸算法，并結(jié)合具體問題開展編程實踐。了解算法設(shè)計中的分治思想，并運用二分查找解決實際問題。計算的一定是數(shù)嗎？導(dǎo)入①計算一定是數(shù)嗎？除了數(shù)還有什么？這些屬于數(shù)值計算嗎？計算一定是數(shù)嗎？01除了數(shù)還有什么？0203這些屬于數(shù)值計算嗎？導(dǎo)入在數(shù)值計算中，我們更多考慮的是“數(shù)”，但計算應(yīng)該是一個更廣泛的領(lǐng)域。計算的對象可以是自然界和人類社會的一切事物。更確切地說，計算的對象可以是某些信息，如數(shù)據(jù)、文字、語言、圖形、知識、事物的運動過程及思維過程。如果說數(shù)值計算主要探討數(shù)學(xué)問題的話，那么非數(shù)值計算更多探討＂算法”問題。

在解決非數(shù)值類計算問題時，一些基礎(chǔ)的思維方式可以借鑒，如分治、遞歸、解析等。分治算法：重要的二分法分治策略②

小問題小問題小問題難以解決的較大問題小問題小問題分治策略分治的設(shè)計思想，是將個難以直接解決的大問題，分割成些較小的同類問題，各個擊破，最終達(dá)到解決問題的目的。二分查找實際上一就是分治策略的種典型運用。二分查找二分直接二分查找importrandomx=random.randint(1,1000)while0<x<1000:y=int(input("請輸入這個數(shù)："))ifx<y:print("大了")elifx>y:print("小了")else:print("就是",x)breakrandom包可以稱為隨機包，它有如下函數(shù)：random.randint(1,10)#產(chǎn)生1到10的一個整數(shù)型隨機數(shù)random.random()#產(chǎn)生0到1之間的隨機浮點數(shù)random.uniform(1.1,5.4)#產(chǎn)生1.1到5.4之間的隨機浮點數(shù)，區(qū)間可以不是整數(shù)random.choice('tomorrow')#從序列中隨機選取一個元素random.randrange(1,100,2)#生成從1到100的間隔為2的隨機整數(shù)小游戲：如何找出1-1000之間的某個數(shù)？

二分查找二分查找又叫折半查找，該方法主要將數(shù)列有序排列，采用跳躍式的方式查找數(shù)據(jù)。以遞增數(shù)列為例，先以中點位置的元素作為比較對象，如果要找的元素值小于該中點元素，則將待查序列縮小為左半部分，否則為右半部分。每一次比較后可以將查找區(qū)域縮小一半。第一次分割第二次分割第三次分割二分查找x=int(input("請輸入要查找的整數(shù):"))step=0low=1high=1000while(low<=high):mid=(low+high)//2step=step+1ifmid>x:high=mid-1elifmid<x:low=mid+1else:breakprint("查找次數(shù)為：",step)input("運行完畢，請按回車鍵退出...")思考：如果輸入的數(shù)據(jù)不在范圍內(nèi)，會出現(xiàn)什么結(jié)果呢？程序還需要在哪些地方進(jìn)行完善？二分查找x=int(input("請輸入要查找的數(shù)據(jù)："))step=0 #記錄查找次數(shù)flag1=1 #目標(biāo)區(qū)域左邊界flag2=1000 #目標(biāo)區(qū)域右邊界ifflag1<=x<=flag2:while(flag1<=flag2):mid=(flag1+flag2)//2step=step+1ifmid>x:flag2=mid-1elifmid<x:flag1=mid+1else:breakprint("查找次數(shù)為：",step) #輸出次數(shù)else:print("查詢超出范圍。")思考：如果輸入的數(shù)據(jù)不在范圍內(nèi)，會出現(xiàn)什么結(jié)果呢？程序還需要在哪些地方進(jìn)行完善？③遞歸算法玩轉(zhuǎn)“漢諾塔”小游戲有一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。漢諾塔游戲思考：假設(shè)移動一次需要1秒，共需多長時間呢？一個平年365天有31536000秒，閏年366天有31622400秒，平均每年31556952秒，計算一下：移動3個木盤的方法是：根據(jù)木盤疊放規(guī)則，要使A桿上最大的木盤（記為x)移動到C桿上（子問題1,如圖第4步），必須先把x上方的所有木盤移動到B桿上（子問題2,如圖4中的前3步），然后再將B桿上所有的木盤移動到C桿上（子問題3,如圖中的后3步）。漢諾塔游戲3個木盤的移動問題成功解決了，就可以解決更多木盤的移動問題了。第1步：A→C第2步：A→B第3步：C→B第4步：A→C第5步：B→A第6步：B→C第7步：A→C將n個木盤從A桿移動到C桿，需要借助中間的B桿。只要超過一個木盤，在移動過程中，總會存在起始桿、過渡桿及目標(biāo)桿的問題。因此，定義函數(shù)時，用到了4個參數(shù)：hanoi(n,A,B,C),n表示需要移動的盤子數(shù)量，A表示盤子的起始桿，B表示中間過渡桿，C表示目標(biāo)桿，如圖4所示。漢諾塔游戲起始桿A過渡桿B盤子數(shù)n目標(biāo)桿Chanoi(盤子數(shù)，起始桿，過渡桿，目標(biāo)桿)漢諾塔游戲hanoi(n,A,B,C)從A移到Chanoi(n-1,B,A,C)hanoi(n-1,A,C,B)前n-1個木盤從A移動到了B前n-1個木盤從B移動到了C漢諾塔遞歸過程圖示漢諾塔游戲defhanno(n,s,m,t):#定義一個函數(shù),n層塔，將盤子從s借助m移動到tifn==1:print(s,'-->',t)#將一個盤子從s移動到telse:hanno(n-1,s,t,m)#將前n-1個盤子從s移動到m上

print(s,'-->',t)#將最底下的最后一個盤子從s移動到t上

hanno(n-1,m,s,t)#將m上的n-1個盤子移動到t上#主程序n=int(input('請輸入漢諾塔的層數(shù)：'))hanno(n,'A','B','C')input("運行完畢，請按回車鍵退出...")代碼實現(xiàn)2個金片，移動幾次漢諾塔游戲4個金片，移動幾次5個金片，移動幾次3個金片，移動幾次3次15次31次7次一種思維模式，抽象表達(dá)的手段，求解問題的方法。直接或間接地調(diào)用自身的方法，可以簡單類比為具有自相似性重復(fù)的事物?；舅枷耄喊岩?guī)模較大的問題層層轉(zhuǎn)化為規(guī)模較小的同類問題求解遞歸算法舉例：斐波那契數(shù)列“1，1，2，3，5，8…”可定義為數(shù)學(xué)領(lǐng)域的遞歸算法用函數(shù)自身來定義該函數(shù)“分”“治””合”(1)分：將原問題分解成K個子問題。(2)治：對這K個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則將其再分解為K個子問題，如此進(jìn)行下去，直到問題足夠小時，就很容易求出子問題的解。(3)合：將求出的小規(guī)模問題的解合并為一個更大規(guī)模問題的解，自下而上逐步求出原問題的解遞歸的重要組成遞推關(guān)系、邊界條件（保證遞歸能在有限次計算后得出結(jié)果，而不會產(chǎn)生無限循環(huán)地情況）遞歸算法分治（二分法）+遞歸課堂測試④總結(jié)CONTRACTEDPUREANDFRESHWealthislikewater.Ifit'saglassofwater,youcane