資源簡介

(共22張PPT)
高中信息技術(shù) 必修1 數(shù)據(jù)與計算
4.3 非數(shù)值計算
第一課時 二分查找
學(xué)習(xí)目標(biāo)
01
02
了解算法中的分治思想；
掌握運用二分查找解決實際問題；
03
在python中用二分法解決問題。
4.3 非數(shù)值計算
游戲?qū)?br/>【尋找假幣游戲】
——在100個硬幣中找出偽幣
有100個硬幣，其中有1個偽幣，它除了質(zhì)量比真幣輕一點之外，沒有別的區(qū)別，如何通過天平快速找到這個偽幣。
請同學(xué)們思考并討論“如何快速找出假幣”？
游戲?qū)?br/>【尋找假幣游戲】
——在100個硬幣中找出偽幣
以重量判斷為例 重量輕的是假幣
首先是將100個硬幣分成兩個50，使用天平進行衡量，然后確定偽幣在比較輕的那50個里，接著再將50分成2個25，將25分成兩個12和1個1，將12分成2個6，將6分成2個3，將3分成3個1，這樣6次就可以找到偽幣，比50次少很多。
游戲?qū)?br/>【尋找假幣游戲】
——在100個硬幣中找出偽幣
以重量判斷為例 重量輕的是假幣
首先是將100個硬幣分成兩個50，使用天平進行衡量，然后確定偽幣在比較輕的那50個里，接著再將50分成2個25，將25分成兩個12和1個1，將12分成2個6，將6分成2個3，將3分成3個1，這樣6次就可以找到偽幣，比50次少很多。
算法：分治
項目內(nèi)容
本節(jié)我們將圍繞“生活中的算法”項目，嘗試用“算法的眼睛”看待生活，用“算法的思維”去解決實際問題。
項目任務(wù)
任務(wù)一：巧翻字典
任務(wù)二：玩轉(zhuǎn)“漢諾塔”游戲
本節(jié)任務(wù)
任務(wù)：巧翻字典 活動：統(tǒng)計查字典次數(shù)
查漢字、查單詞、查成語等查字典的活動，早已成為我們學(xué)習(xí)生活的部分。假設(shè)一本字典大約1000頁，目標(biāo)信息在第328頁。請記錄你翻頁過程，和同學(xué)們比比，看誰翻的次數(shù)最少。
次數(shù) 翻至頁碼 下一步?jīng)Q策
第一次
第二次
第三次
第四次
第五次
……
有的同學(xué)翻得特別快，他們用了什么方法呢？原來看似普通的翻字典，不僅是一門技術(shù)， 更是一種能力，是算法思想的體現(xiàn)。
任務(wù)：巧翻字典 活動：統(tǒng)計查字典次數(shù)
次數(shù) 翻至頁碼 下一步?jīng)Q策
第1次 500 往前 1-499
第2次 250 往后 251-499
第3次 375 往前 251-374
第4次 312 往后 313-374
第5次 343 往前 313-342
第6次 327 往后 328-342
第7次 335 往前 328-334
第8次 331 往前 328-330
第9次 329 往前 328-328
第10次 328
策略 1
找到區(qū)間的中位數(shù)
策略 2
根據(jù)情況確定更精確的區(qū)間
知識探究：二分查找/折半查找
二分思想：將數(shù)列有序排列，采用跳躍的方式查找數(shù)據(jù)。
分治策略
將難以直接解決的大問題，分割成較小的同類問題
方法：以遞增數(shù)列為例，以中點位置元素作為比較對象，若要查找元素值小于該中點元素，將待查找序列縮小為左半部分，否則為右半部分。每次比較后都能將查找區(qū)間縮小一半。
找一半
按照順序找一半，
一比較，舍一半。
繼續(xù)找一半，
一半又一半，
快速找答案！
知識探究：二分查找/折半查找
左邊界
flag1
右邊界
flag2
目標(biāo)數(shù)x
中間數(shù)
mid
！！！若中間數(shù)mid比目標(biāo)數(shù)x大，則區(qū)間變?yōu)樽蟀雲(yún)^(qū)間，右邊界更新
左邊界
flag1
右邊界
flag2
目標(biāo)數(shù)x
中間數(shù)
mid
！！！若中間數(shù)mid比目標(biāo)數(shù)x小，則區(qū)間變?yōu)橛野雲(yún)^(qū)間，左邊界更新
知識探究：二分查找/折半查找
在有n個元素的有序序列中，利用二分查找大約需要log2n次。
n = 1000 需要10次
二分思想：將數(shù)列有序排列，采用跳躍的方式查找數(shù)據(jù)。
任務(wù)：巧翻字典 程序編寫——補充程序
x = int(input('請輸入要查找的數(shù)據(jù)：'))
step = 0 #查找次數(shù)
flag1 = 1 #目標(biāo)區(qū)域左邊界
flag2 = 1000 #目標(biāo)區(qū)域右邊界
while flag1 <= flag2 : #區(qū)間左邊界不大于右邊界則執(zhí)行
mid = (flag1 + flag2)//2 #表示區(qū)間中間值 //為整除
step = step + 1 #查找次數(shù)加1
if mid > x: #區(qū)域中間值大于目標(biāo)數(shù)
flag2 = mid - 1 #范圍往左側(cè)區(qū)域找 = 右邊界前移
elif mid < x: #區(qū)域中間值大于目標(biāo)數(shù)
flag1 = mid + 1 #范圍往右側(cè)區(qū)域找 = 左邊界后移
else:
break
print('查找次數(shù)為：',step)
任務(wù)：巧翻字典
x = int(input('請輸入要查找的數(shù)據(jù)：'))
step = 0 #查找次數(shù)
flag1 = 1 #目標(biāo)區(qū)域左邊界
flag2 = 1000 #目標(biāo)區(qū)域右邊界
while flag1 <= flag2 : #區(qū)間左邊界不大于右邊界則執(zhí)行
mid = (flag1 + flag2)//2 #表示區(qū)間中間值 //為整除
step = step + 1 #查找次數(shù)加1
if mid > x: #區(qū)域中間值大于目標(biāo)數(shù)
flag2 = mid - 1 #范圍往左側(cè)區(qū)域找 = 右邊界前移
elif mid < x: #區(qū)域中間值大于目標(biāo)數(shù)
flag1 = mid + 1 #范圍往右側(cè)區(qū)域找 = 左邊界后移
else:
break
print('查找次數(shù)為：',step)
上機實踐1
二分查找的應(yīng)用：找出1-1000之間的某個數(shù)
random包可以稱為隨機包，它有如下函數(shù)：
random.randint(1,10) # 產(chǎn)生 1 到 10 的一個整數(shù)型隨機數(shù)
random.random() # 產(chǎn)生 0 到 1 之間的隨機浮點數(shù)
random.uniform(1.1,5.4) # 產(chǎn)生 1.1 到 5.4 之間的隨機浮點數(shù)，區(qū)間可以不是整數(shù)
random.choice('tomorrow') # 從序列中隨機選取一個元素
random.randrange(1,100,2) # 生成從1到100的間隔為2的隨機整數(shù)
二分查找的應(yīng)用：找出1-1000之間的某個數(shù)
import random
x = random.randint(1,1000)
while 0y = int(input("請輸入這個數(shù)："))
if xprint("大了")
elif x>y:
print("小了")
else:
print("就是",x)
break
上機實踐2
課堂練習(xí)
1．二分查找又叫_________，該方法主要將數(shù)列_________排列，采用___________的方式查找數(shù)據(jù)。二分查找是一種高效的查找方法。它可以明顯減少比較次數(shù)，提高查找效率。
2．遞增數(shù)列用二分法查找時，先以________位置的元素作為比較對象，如果要找的元素值小于該中點元素，則將待查序列_________為左半部分，否則為右半部分。每一次比較后都可以將查找區(qū)間縮小一半。
課堂練習(xí)
3.二分法查找的前提條件是被查找的數(shù)據(jù)__________的。
4.結(jié)合分治策略，遞歸也可以用___________三個字概況。分:將原有問題______成K個子問題;治:對這K個子問題______。如果子問題的規(guī)模仍然不夠小，則將其再分解為K個子問題，如此進行下去，直到問題足夠小時，就很容易求出子問題的解。合:將求出的小規(guī)模問題的解_______為一個更大規(guī)模問題的解，自下而上逐步求出原問題的解。
課堂練習(xí)
5.二分查找又稱折半查找，是一種應(yīng)用于有序數(shù)列的高效查找算法。下列數(shù)列中適合二分查找算法的是()
A.85 78 59 53 19 18
B.67 62 68 41 1 7
C.11 99 4 25 3 39
D.43 71 78 81 6 55
課堂小結(jié)
4.3 非數(shù)值計算
分治策略
二分查找
將一個難以直接解決的大問題，分割成一些較小的同類問題，各個擊破 。
二分查找又叫折半查找， 該方法主要將數(shù)列有序排列， 采用跳躍式的方式查找數(shù)據(jù)。
二分法查找的前提條件是被查找的數(shù)據(jù)必須是有序的。
分：原問題分解成若干子問題
治：對子問題分別求解
合：子問題的解合并成原問題的解
課后作業(yè)
嘗試用二分法求解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。為方程的解。
課后作業(yè)
def f(x): #定義方程
return x**3-x**2+x-1
a=float(input("請輸入解區(qū)間的左邊界："))
b=float(input("請輸入解區(qū)間的右邊界："))
while abs(b-a)>1e-6:
x0=(a+b)/2
if f(a)*f(x0)<0:
b=x0
if f(b)*f(x0)<0:
a=x0
if f(x0)==0:
break
print("解為:",x0)
input("運行完畢，請按回車鍵退出...")
嘗試用二分法求解x3-x2+x-1=0
參考代碼
學(xué)無止境 永攀高峰
感謝觀看

展開更多......

收起↑