高中信息技術(shù)教科版必修1課件4-3非數(shù)值計算（第一課時）

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

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

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

x=random.randint(1,1000)

while0<x<1000:

y=int(input("請輸入這個數(shù)："))

ifx<y:

print("大了")

elifx>y:

print("小了")

else:

print("就是",x)

breakrandom包可以稱為隨機(jī)包，它有如下函數(shù)：random.randint(1,10)#產(chǎn)生1到10的一個整數(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ī)選取一個元素random.randrange(1,100,2)#生成從1到100的間隔為2的隨機(jī)整數(shù)練一練嘗試用二分法求解x3-x2+x-1=0操作提示：令f(x)=x3-x2+x-1，針對有解的單調(diào)區(qū)間(a,b)，取x。=（a+b)/2:若f(a)*f(x。)＜0，則f(x)在(a,x。)內(nèi)有解；若f(x。）*f（b)<0，則f(x)在(x。,b)內(nèi)有解；若|f(x。)|＜10-6，則x。為方程的解。鞏固提升1．二分查找又叫_________，該方法主要將數(shù)列_________排列，采用___________的方式查找數(shù)據(jù)。二分查找是一種高效的查找方法。它可以明顯減少比較次數(shù)，提高查找效率。2．遞增數(shù)列用二分法查找時，先以________位置的元素作為比較對象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列_________為左半部分，否則為右半部分。每一次比較后都可以將查找區(qū)間縮小一半。鞏固提升3.二分法查找的前提條件是被查找的數(shù)據(jù)__________的。4.結(jié)合分治策略，遞歸也可以用___________三個字概況。分:將原有問題______成K個子問題;治:對這K個子問題______。如果子問題的規(guī)模仍然不夠小，則將其再分解為K個子問題，如此進(jìn)行下去，直到問題足夠小時，就很容易求出子問題的解。合:將求出的小規(guī)模問題的解_______為一個更大規(guī)模問題的解，自下而上逐步求出原問題的解。鞏固提升5.二分查找又稱折半查找，是一種應(yīng)用于有序數(shù)列的高效查找算法。下列數(shù)列中適合二分查找算法的是()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