資源簡(jiǎn)介

學(xué)習(xí)任務(wù)單
課程基本信息
課題 數(shù)據(jù)查找
學(xué)習(xí)目標(biāo)
1.通過具體實(shí)例，理解查找的概念和基本方法。 2.掌握順序查找的算法思想，熟悉順序查找算法的代碼框架。 3.理解并掌握對(duì)分查找的算法思想，熟悉對(duì)分查找算法的代碼框架。 4.掌握順序查找與對(duì)分查找算法的使用條件和優(yōu)缺點(diǎn)。
課前學(xué)習(xí)任務(wù)
1.復(fù)習(xí)浙教版信息技術(shù)必修1《數(shù)據(jù)與計(jì)算》第3章3.3.2枚舉算法及其程序?qū)崿F(xiàn)的內(nèi)容，能熟練使用枚舉算法基本框架。
2.復(fù)習(xí)浙教版信息技術(shù)選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》第2章2.1.2數(shù)組的基本操作，能熟練使用數(shù)組元素訪問及數(shù)組遍歷的方法。 3.復(fù)習(xí)浙教版信息技術(shù)選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》第4章4.1.2二叉樹“猜數(shù)字游戲” 4、復(fù)習(xí)浙教版信息技術(shù)選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》第5章5.1.1算法的效率，時(shí)間復(fù)雜度。
課上學(xué)習(xí)任務(wù)
【學(xué)習(xí)任務(wù)一】 在打亂的撲克牌中尋找出“紅桃5”這張牌，講一講你尋找的方法。
【學(xué)習(xí)任務(wù)二】
順序查找算法程序?qū)崿F(xiàn)： 數(shù)組d[0]-d[n]存儲(chǔ)被查找的數(shù)據(jù)，key中存儲(chǔ)要查找的數(shù)據(jù)。 for i in range（ ）：#遍歷數(shù)組索引 if ：#數(shù)組中某個(gè)索引位置上的數(shù)與key相等 #輸出查找數(shù)據(jù)在數(shù)組中的索引位置 #結(jié)束查找 else: #輸出“沒找到”。 【學(xué)習(xí)任務(wù)三】 對(duì)分查找算法程序?qū)崿F(xiàn)： 數(shù)組d[0]-d[n]升序存儲(chǔ)被查找的數(shù)據(jù)，key中存儲(chǔ)要查找的數(shù)據(jù)。 key=int(input())；f=False；i=0 #變量f=False 表示查找失敗，f=True 表示查找成功 j= #j表示查找區(qū)間的終點(diǎn)索引 while : #查找條件 mid= #計(jì)算查找區(qū)間中間位置 if d[mid]==key: #查找成功并結(jié)束查找 f=True break if d[mid]>key: #查找不成功，調(diào)整下一次查找的區(qū)間范圍 else: if f==True: #輸出查找結(jié)果 print("查找成功！下標(biāo)為"+str(mid)) else: print("沒有找到！") 【學(xué)習(xí)任務(wù)四】 順序查找算法和對(duì)分查找算法對(duì)比： 查找算法順序查找對(duì)分查找優(yōu)點(diǎn)算法簡(jiǎn)單，對(duì)數(shù)據(jù)是否有序沒有要求。查找效率高，適用于大數(shù)據(jù)查找。 缺點(diǎn)查找效率較低，當(dāng)數(shù)據(jù)量大時(shí)不宜使用。要求被查找數(shù)據(jù)必須有序。查找次數(shù)一般情況是，當(dāng)需要查找的數(shù)據(jù)規(guī)模為 n 時(shí)，順序查找最少查找____次，最多查找____次，其平均查找次數(shù)是________。最少查找次數(shù)____，無論是否找到，最多進(jìn)行_____________次查找。算法思想順序查找本質(zhì)上是一種_______算法思想。對(duì)分查找思想符合_______算法的思想。
推薦的學(xué)習(xí)資源
順序查找平均查找次數(shù)：第一個(gè)數(shù)的比較次數(shù)為1，第二個(gè)數(shù)的比較次數(shù)為2。。。以此類推第N個(gè)數(shù)的比較次數(shù)為N，所以總的比較次數(shù)為1+2+…+N=N(N+1)/2,平均比較次數(shù)為(N+1)/2,也即平均查找長(zhǎng)度。 對(duì)分查找最多的查找次數(shù)(n個(gè)數(shù)據(jù))：n個(gè)數(shù)據(jù)對(duì)分x次最后變?yōu)?個(gè)數(shù)據(jù)，n/2**x=1，x=log2n 最后一個(gè)數(shù)據(jù)還要參與一次查找因此最多查找次數(shù)：int(log2n)+1。 3.猜數(shù)字游戲：在猜數(shù)字游戲中，甲方事先在紙上寫出一個(gè)100以內(nèi)的正整數(shù)，讓乙方猜，乙方每猜一次，甲方都會(huì)告訴乙方“猜大了”或是“猜小了”，直至猜出正確結(jié)果。乙方如果采取“折半”的策略進(jìn)行猜數(shù)字，就一定能夠在7次以內(nèi)猜對(duì)結(jié)果，具體過程可抽象成如下圖所示的二叉樹（每個(gè)節(jié)點(diǎn)為乙方所猜的數(shù)字，每條邊實(shí)際數(shù)字與所猜數(shù)字之間的大小關(guān)系，圖中僅呈現(xiàn)前4次的猜數(shù)字情況）。 4.推導(dǎo)大O階的方法（時(shí)間復(fù)雜度）： 用O()來體現(xiàn)算法時(shí)間復(fù)雜度，稱之為大O記法。其推導(dǎo)方法如下: （1）用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。 （2）在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。 （3）如果最高階項(xiàng)存在且不是1，那么去除與這個(gè)項(xiàng)相乘的常數(shù)。得到的結(jié)果就是大O階。 例如，1/2n(n-1)保留高階項(xiàng)，1/2n2去除常數(shù)即n2。

展開更多......

收起↑