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

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

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

二分查找二分查找又叫折半查找，該方法主要將數列有序排列，采用跳躍式的方式查找數據。以遞增數列為例，先以中點位置的元素作為比較對象，如果要找的元素值小于該中點元素，則將待查序列縮小為左半部分，否則為右半部分。每一次比較后可以將查找區域縮小一半。第一次分割第二次分割第三次分割二分查找x=int(input("請輸入要查找的整數:"))step=0low=1high=1000while(low<=high):mid=(low+high)//2step=step+1ifmid>x:high=mid-1elifmid<x:low=mid+1else:breakprint("查找次數為：",step)input("運行完畢，請按回車鍵退出...")思考：如果輸入的數據不在范圍內，會出現什么結果呢？程序還需要在哪些地方進行完善？二分查找x=int(input("請輸入要查找的數據："))step=0 #記錄查找次數flag1=1 #目標區域左邊界flag2=1000 #目標區域右邊界ifflag1<=x<=flag2:while(flag1<=flag2):mid=(flag1+flag2)//2step=step+1ifmid>x:flag2=mid-1elifmid<x:flag1=mid+1else:breakprint("查找次數為：",step) #輸出次數else:print("查詢超出范圍。")思考：如果輸入的數據不在范圍內，會出現什么結果呢？程序還需要在哪些地方進行完善？③遞歸算法玩轉“漢諾塔”小游戲有一個印度的古老傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。漢諾塔游戲思考：假設移動一次需要1秒，共需多長時間呢？一個平年365天有31536000秒，閏年366天有31622400秒，平均每年31556952秒，計算一下：移動3個木盤的方法是：根據木盤疊放規則，要使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桿。只要超過一個木盤，在移動過程中，總會存在起始桿、過渡桿及目標桿的問題。因此，定義函數時，用到了4個參數：hanoi(n,A,B,C),n表示需要移動的盤子數量，A表示盤子的起始桿，B表示中間過渡桿，C表示目標桿，如圖4所示。漢諾塔游戲起始桿A過渡桿B盤子數n目標桿Chanoi(盤子數，起始桿，過渡桿，目標桿)漢諾塔游戲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):#定義一個函數,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('請輸入漢諾塔的層數：'))hanno(n,'A','B','C')input("運行完畢，請按回車鍵退出...")代碼實現2個金片，移動幾次漢諾塔游戲4個金片，移動幾次5個金片，移動幾次3個金片，移動幾次3次15次31次7次一種思維模式，抽象表達的手段，求解問題的方法。直接或間接地調用自身的方法，可以簡單類比為具有自相似性重復的事物。基本思想：把規模較大的問題層層轉化為規模較小的同類問題求解遞歸算法舉例：斐波那契數列“1，1，2，3，5，8…”可定義為數學領域的遞歸算法用函數自身來定義該函數“分”“治””合”(1)分：將原問題分解成K個子問題。(2)治：對這K個子問題分別求解。如果子問題的規模仍然不夠小，則將其再分解為K個子問題，如此進行下去，直到問題足夠小時，就很容易求出子問題的解。(3)合：將求出的小規模問題的解合并為一個更大規模問題的解，自下而上逐步求出原問題的解遞歸的重要組成遞推關系、邊界條件（保證遞歸能在有限次計算后得出結果，而不會產生無限循環地情況）遞歸算法分治（二分法）+遞歸課堂測試④總結CONTRACTEDPUREANDFRESHWealthislikewater.Ifit'saglassofwater,youcane