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

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

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

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

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

print(s,'-->',t)#將最底下的最后一個(gè)盤(pán)子從s移動(dòng)到t上

hanno(n-1,m,s,t)#將m上的n-1個(gè)盤(pán)子移動(dòng)到t上#主程序n=int(input('請(qǐng)輸入漢諾塔的層數(shù)：'))hanno(n,'A','B','C')input("運(yùn)行完畢，請(qǐng)按回車鍵退出...")代碼實(shí)現(xiàn)2個(gè)金片，移動(dòng)幾次漢諾塔游戲4個(gè)金片，移動(dòng)幾次5個(gè)金片，移動(dòng)幾次3個(gè)金片，移動(dòng)幾次3次15次31次7次一種思維模式，抽象表達(dá)的手段，求解問(wèn)題的方法。直接或間接地調(diào)用自身的方法，可以簡(jiǎn)單類比為具有自相似性重復(fù)的事物。基本思想：把規(guī)模較大的問(wèn)題層層轉(zhuǎn)化為規(guī)模較小的同類問(wèn)題求解遞歸算法舉例：斐波那契數(shù)列“1，1，2，3，5，8…”可定義為數(shù)學(xué)領(lǐng)域的遞歸算法用函數(shù)自身來(lái)定義該函數(shù)“分”“治””合”(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)題的解遞歸的重要組成遞推關(guān)系、邊界條件（保證遞歸能在有限次計(jì)算后得出結(jié)果，而不會(huì)產(chǎn)生無(wú)限循環(huán)地情況）遞歸算法分治（二分法）+遞歸課堂測(cè)試④總結(jié)CONTRACTEDPUREANDFRESHWealthislikewater.Ifit'saglassofwater,youcane