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

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

x=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ù)練一練嘗試用二分法求解x3-x2+x-1=0操作提示：令f(x)=x3-x2+x-1，針對(duì)有解的單調(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ù)列用二分法查找時(shí)，先以________位置的元素作為比較對(duì)象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列_________為左半部分，否則為右半部分。每一次比較后都可以將查找區(qū)間縮小一半。鞏固提升3.二分法查找的前提條件是被查找的數(shù)據(jù)__________的。4.結(jié)合分治策略，遞歸也可以用___________三個(gè)字概況。分:將原有問題______成K個(gè)子問題;治:對(duì)這K個(gè)子問題______。如果子問題的規(guī)模仍然不夠小，則將其再分解為K個(gè)子問題，如此進(jìn)行下去，直到問題足夠小時(shí)，就很容易求出子問題的解。合:將求出的小規(guī)模問題的解_______為一個(gè)更大規(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