非數值計算第一課時第4單元4.3學習目標★運用合適的算法形成解決問題的方案。★了解算法設計中的分治思想，并運用二分查找解決實際問題。★體驗遞歸算法，并結合具體問題開展編程實踐。在數值計算中，我們更多考慮的是“數”，但計算應該是一個更廣泛的領域。計算的對象可以是自然界和人類社會的一切事物。更確切地說，計算的對象可以是某些信息，如數據、文字、語言、圖形、知識、事物的運動過程及思維過程。如果說數值計算主要探討數學問題的話，那么非數值計算更多探討＂算法”問題。許多程序設計問題的解決，要依靠標準算法和現成的模型，更需要編程者開闊思路，提出一些新穎、巧妙的算法，或者設計出一些獨特的數據結構來支撐和實現算法。在解決非數值類計算問題時，一些基礎的思維方式可以借鑒，如分治、遞歸、解析等。活動統計查字典次數查漢字、查單詞、查成語等查字典的活動，早已成為我們學習生活的部分。假設一本字典大約500頁，目標信息在第269頁。請記錄你翻頁過程，和同學們比比，看誰翻的次數最少。次數翻至頁碼下一步決策第一次250第二次第三次第四次第五次……有的同學翻得特別快，他們用了什么方法呢？原來看似普通的翻字典，不僅是一門技術，更是一種能力，是算法思想的體現。分治策略分治的設計思想，是將個難以直接解決的大問題，分割成些較小的同類問題，各個擊破，最終達到解決問題的目的。二分查找實際上一就是分治策略的種典型運用。ABCDEFGHI需要解決的問題二分查找二分查找又叫折半查找，該方法主要將數列有序排列，采用跳躍式的方式查找數據。以遞增數列為例，先以中點位置的元素作為比較對象，如果要找的元素值小于該中點元素，則將待查序列縮小為左半部分，否則為右半部分。每一次比較后可以將查找區域縮小一半。第一次分割第二次分割第三次分割需要解決的問題在翻頁過程中借助兩個書簽，劃定目標所屬范圍，然后翻到兩個書簽的中間位置。每次目標區域都更新為原來的“二分之一”，當數據范圍縮小到只有1個數的時候肯定能得到問題的解。1000以內的頁碼，最多翻10次肯定能找到解。目標信息在第269頁。第0頁第1000頁第0頁第500頁第250頁第500頁第250頁第375頁第250頁第312頁有了翻字典的實際操作經驗，我們來嘗試完善下面的二分查找程序。x=int(input(“請輸入要查找的數據：＂））step=0 ＃記錄查找次數flagl=l ＃目標區域左邊界flag2=1000 ＃目標區域右邊界while(flag1<=flag2) ＃區間數據范圍小于1則結束循環 mid=（flag1+flag2)/2 ＃中間值 step=step+1

＃查找次數加1 ifmid>x: flag2=mid-1 #有邊界前移 elifmid<x: flag1=mid+1 #左邊界后移 else: break ＃恰好找到目標數據，退出循環print(“查詢次數為：”，step) #輸出次數如果輸入的數據不在范圍內，會出現什么結果呢？程序還需要在哪些地方進行完善？大家一起來試試吧。x=int(input(“請輸入要查找的數據：＂））step=0 ＃記錄查找次數flagl=l ＃目標區域左邊界flag2=1000 ＃目標區域右邊界ifx>flag2orx<flag1:while(flag2-flag1>1) ＃區間數據范圍小于1則結束循環 mid=（flag1+flag2)/2 ＃中間值 step=step+1

＃查找次數加1 ifmid>x: flag2=mid #有邊界前移 elifmid<x: flag1=mid #左邊界后移 else: break ＃恰好找到目標數據，退出循環print(“查詢次數為：”，step) #輸出次數else: print(“查詢超出范圍。”)random包的randint()函數可以生成某個范圍內的隨機數。活動應用“二分查找”，找出1-1000之間的某個數importrandom

x=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的隨機整數練一練嘗試用二分法求解x3-x2+x-1=0操作提示：令f(x)=x3-x2+x-1，針對有解的單調區間(a,b)，取x。=（a+b)/2:若f(a)*f(x。)＜0，則f(x)在(a,x。)內有解；若f(x。）*f（b)<0，則f(x)在(x。,b)內有解；若|f(x。)|＜10-6，則x。為方程的解。鞏固提升1．二分查找又叫_________，該方法主要將數列_________排列，采用___________的方式查找數據。二分查找是一種高效的查找方法。它可以明顯減少比較次數，提高查找效率。2．遞增數列用二分法查找時，先以________位置的元素作為比較對象，如果要找的元素值小于該中點元素，則將待查序列_________為左半部分，否則為右半部分。每一次比較后都可以將查找區間縮小一半。鞏固提升3.二分法查找的前提條件是被查找的數據__________的。4.結合分治策略，遞歸也可以用___________三個字概況。分:將原有問題______成K個子問題;治:對這K個子問題______。如果子問題的規模仍然不夠小，則將其再分解為K個子問題，如此進行下去，直到問題足夠小時，就很容易求出子問題的解。合:將求出的小規模問題的解_______為一個更大規模問題的解，自下而上逐步求出原問題的解。鞏固提升5.二分查找又稱折半查找，是一種應用于有序數列的高效查找算法。下列數列中適合二分查找算法的是()A.85 78 59 53 19 18B.67 62 68 41 1 7C.11 99 4 25 3 39D.43 71 78 81 6 5