教科版高二選擇性必修1信息技術(shù)第3單元第3課《數(shù)據(jù)的查找》課件_第1頁
教科版高二選擇性必修1信息技術(shù)第3單元第3課《數(shù)據(jù)的查找》課件_第2頁
教科版高二選擇性必修1信息技術(shù)第3單元第3課《數(shù)據(jù)的查找》課件_第3頁
教科版高二選擇性必修1信息技術(shù)第3單元第3課《數(shù)據(jù)的查找》課件_第4頁
教科版高二選擇性必修1信息技術(shù)第3單元第3課《數(shù)據(jù)的查找》課件_第5頁
已閱讀5頁,還剩34頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

3.3數(shù)據(jù)的查找高中信息技術(shù)/教科版/選擇性必修1目錄1.創(chuàng)設(shè)情境,導(dǎo)入新課2.體驗(yàn)探究,初始查找3.討論探究,實(shí)現(xiàn)查找4.自主探究,二分查找5.遞歸實(shí)現(xiàn)二分查找6.課堂小結(jié)1.創(chuàng)設(shè)情境,導(dǎo)入新課在網(wǎng)上商城眾多的商品數(shù)據(jù)中,如何快速地查找到所需商品的相關(guān)信息呢?本節(jié)圍繞“網(wǎng)上商城查找商品”項目展開學(xué)習(xí),通過項目活動體驗(yàn)計算機(jī)查找數(shù)據(jù)的過程,理解算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。本節(jié)主要包含“根據(jù)品牌查找商品”和“根據(jù)價格查找商品”兩個任務(wù)。2.體驗(yàn)探究,初始查找

任務(wù)一根據(jù)品牌查找商品

活動1體驗(yàn)順序查找過程表3.3.1所示是某網(wǎng)上商城的簽字筆銷售數(shù)據(jù),如何在表中查詢到品牌為“得利”的簽字筆銷售數(shù)據(jù)呢?品牌銷量/盒價格/元評論數(shù)/條博士8066108英雄1887886永輝23658186晨輝20046190得利566850梅花1852692凌梅683265巧虎22172198表簽字筆銷售數(shù)據(jù)從表格的第1行數(shù)據(jù)開始,先比較第1行數(shù)據(jù)中的品牌與“得利”是否相等,如果相等則說明查找成功;如果不相等則繼續(xù)與下一個數(shù)據(jù)進(jìn)行比較,直到所有數(shù)據(jù)都比較完畢。

任務(wù)一根據(jù)品牌查找商品

活動1體驗(yàn)順序查找過程第1次比較:“博士”與“得利”不相等,繼續(xù)與下一個數(shù)據(jù)比較第2次比較:“英雄”與“得利”不相等,繼續(xù)與下一個數(shù)據(jù)比較。請根據(jù)這個思路,繼續(xù)完成后面幾個數(shù)據(jù)的比對過程。第3次比較:

。第4次比較:

。第5次比較:

。從第1個數(shù)據(jù)開始,按順序逐一進(jìn)行比較,經(jīng)過5次比較,找到品牌為“得利”的簽字筆銷售數(shù)據(jù)。填一填“永輝”與“得利”不相等,繼續(xù)與下一個數(shù)據(jù)比較“晨輝”與“得利”不相等,繼續(xù)與下一個數(shù)據(jù)比較“得利”與“得利”相等,結(jié)束比較通過剛才的查找體驗(yàn),你能分別給查找和順序查找下個定義嗎?查找(searching)就是在數(shù)據(jù)表中確定一個與給定值相等的數(shù)據(jù)若存在這樣的數(shù)據(jù)則表示查找成功,否則表示查找不成功。順序查找(sequentialsearch)是一種從頭開始逐個數(shù)據(jù)進(jìn)行比較的查找方法。從數(shù)據(jù)表中第1個數(shù)據(jù)開始,逐個與要查找的數(shù)據(jù)進(jìn)行比較,如果與要查找的數(shù)據(jù)相等,則查找成功;如果直至最后個數(shù)據(jù),與要查找的數(shù)據(jù)都不相等,則查找不成功。順序查找的過程3.討論探究,實(shí)現(xiàn)查找

任務(wù)一根據(jù)品牌查找商品

活動2建立數(shù)據(jù)結(jié)構(gòu)創(chuàng)建一個線性表對象alist,存放表3.3.1所示的簽字筆銷售數(shù)據(jù)對象。請補(bǔ)全下面的代碼。填一填01.fromlinearListimportLinearList

#導(dǎo)人線性表02.alist=

#創(chuàng)建線性表對象03.alist.appendItem(pen("博士",80,66,108))#添加簽字筆數(shù)據(jù)元素04.alist.appendItem(pen("英雄",188,78,86))#添加簽字筆數(shù)據(jù)元素05.alist.appendItem(pen("永輝",236,58,186))#添加簽字筆數(shù)據(jù)元素LinearList()

任務(wù)一

任務(wù)一根據(jù)品牌查找商品

活動2建立數(shù)據(jù)結(jié)構(gòu)06.alist.appendItem(pen())#添加簽字筆數(shù)據(jù)元素07.alist.appendItem(pen())#添加簽字筆數(shù)據(jù)元素08.alist.appendItem(pen())#添加簽字筆數(shù)據(jù)元素09.alist.appendItem(pen())#添加簽字筆數(shù)據(jù)元素10.alist.appendItem(pen())#添加簽字筆數(shù)據(jù)元素"晨輝",200,46,190"得利",56,68,50"梅花",185,26,92"凌美",68,32,65"巧虎",221,72,198任務(wù)一根據(jù)品牌查找商品

活動3順序查找算法的設(shè)計與實(shí)現(xiàn)假設(shè)有n個簽字筆銷售數(shù)據(jù),實(shí)現(xiàn)順序查找的算法描述如下。(1)從線性表中的第1個數(shù)據(jù)開始,依次進(jìn)行操作(2)(2)將當(dāng)前數(shù)據(jù)與要查找數(shù)據(jù)進(jìn)行比較,如果相等,則查找成功,返回數(shù)據(jù)在表中的位置,查找結(jié)束。如果不相等,則繼續(xù)查找。(3)查找失敗。請將上述順序查找的算法過程轉(zhuǎn)化為流程圖。

任務(wù)一根據(jù)品牌查找商品

活動3順序查找算法的設(shè)計與實(shí)現(xiàn)根據(jù)上述算法,定義sequentialSearch(alist,key,item)函數(shù),參數(shù)alist表示存儲數(shù)據(jù)的線性表,key表示查找的關(guān)鍵詞,參數(shù)item表示要查找的數(shù)據(jù)。請補(bǔ)全下面的代碼。11.#順序查找算法12.defsequentialSearch(alist,key,item):13.i=0

#初始化循環(huán)變量14.whilei<alist.size():15.#判斷第i個位置上的數(shù)據(jù)與查找的數(shù)據(jù)是否相等16.ifgetattr(

,key)==item:17.return

#返回查找到的數(shù)據(jù)在表中的位置18.else:19.i=i+l

#進(jìn)行下一個數(shù)據(jù)比較19.return-1

#返回查找失敗alist.getItem(i)i

任務(wù)一根據(jù)品牌查找商品

活動3順序查找算法的設(shè)計與實(shí)現(xiàn)以表3.3.1中的數(shù)據(jù)為例,利用順序查找法查找品牌為“得利”的簽字筆,并顯示查找到的簽字筆銷售數(shù)據(jù)。請補(bǔ)全下面的代碼。21.result=sequentialSearch(alist,

)#調(diào)用順序查找函數(shù)22.print(“順序查找的結(jié)果是:“)23.ifresult==-1:24.print("查找失敗")25.else:print(getattr(alist.getItem(result),'brand'),

,

,

)#顯示查找結(jié)果

‘brand’‘凌美’alist.getItem(result),'sales'alist.getItem(result),'price'alist.getItem(result),'comments'假設(shè)有n個數(shù)據(jù),利用順序查找法,整個查找過程需要進(jìn)行k(1kn)次數(shù)據(jù)比較,可以利用循環(huán)語句實(shí)現(xiàn)。4.自主探究,二分查找

任務(wù)二根據(jù)價格查找商品

活動1體驗(yàn)二分查找過程在表3.3.1中如何快速查找到價格是68的簽字筆銷售數(shù)據(jù)呢?品牌銷量/盒價格/元評論數(shù)/條博士8066108英雄1887886永輝23658186晨輝20046190得利566850梅花1852692凌梅683265巧虎22172198表3.3.1按價格升序排列后的簽字筆銷售數(shù)據(jù)把簽字筆銷售數(shù)據(jù)表按照價格進(jìn)行升序排列,找到中間項(位于表中間位置)數(shù)據(jù),如果查找項與中間項相等,則查找結(jié)束。如果查找項比中間項大,可以把數(shù)據(jù)表中較小的那部分(包括中間項)排除了,因?yàn)槿绻檎翼椩谥校撬欢ㄔ谳^大的那一半中。接下來,可以在較大的一半中重這個過程。如果查找項比中間項小,可以把數(shù)據(jù)表中較大的那部分包括中間項)排除了,因?yàn)槿绻檎翼椩诒碇校撬欢ㄔ谳^小的那一半中。接下來,在較小的一半中重復(fù)這個過程即可。

任務(wù)二根據(jù)價格查找商品

活動1體驗(yàn)二分查找過程品牌銷量/盒價格/元評論數(shù)/條梅花1852692凌梅683265晨輝20046190永輝23658186博士8066108得利566850巧虎22172198英雄1887886表3.3.2按價格升序排列后的簽字筆銷售數(shù)據(jù)

任務(wù)二根據(jù)價格查找商品

活動1體驗(yàn)二分查找過程第1次查找:確定數(shù)據(jù)表的中間項是價格為58的簽字筆,如圖所示。將查找項與中間項進(jìn)行比較,68>58,排除較小的那部分和中間項。梅花26凌梅32晨輝46永輝58博士66得利68巧虎72英雄78中間項第1次查找

任務(wù)二根據(jù)價格查找商品

活動1體驗(yàn)二分查找過程第2次查找:在數(shù)據(jù)表較大的部分中繼續(xù)查找,確定數(shù)據(jù)表較大部分的中間項是68,如圖所示。將查找項與中間項進(jìn)行比較,68=68,查找成功。博士66得利68巧虎72英雄78中間項第2次查找請根據(jù)這個思路,寫出查找價格是46的簽字筆銷售數(shù)據(jù)的過程。

任務(wù)二根據(jù)價格查找商品

活動1體驗(yàn)二分查找過程第1次查找:確定數(shù)據(jù)表的中間項是價格為58的簽字筆,將查找項與中間項進(jìn)行比較,46<58,排除較大的那部分和中間項。梅花26凌梅32晨輝46永輝58博士66得利68巧虎72英雄78中間項第2次查找:確定數(shù)據(jù)表的中間項是價格為32的簽字筆,將查找項與中間項進(jìn)行比較,46>32,排除較小的那部分和中間項。梅花26凌梅32晨輝46中間項第1次查找第2次查找第3次查找:確定數(shù)據(jù)表的中間項是價格為46的簽字筆,46=46,查找成功。對于有序表的查找,從表的中間項開始比對,如果表的中間項匹配查找項,則查找結(jié)束。如果不匹配,就有兩種情況:表的中間項比查找項大,那么查找項只可能出現(xiàn)在前半部分;表的中間項比查找項小,那么查找項只可能出現(xiàn)在后半部分。重復(fù)上述查找過程,每次都會將比對范圍縮小一半,直到查找結(jié)束。這種查找的方法,稱為二分查找。二分查找概念

任務(wù)二根據(jù)價格查找商品

活動2二分查找算法的設(shè)計與實(shí)現(xiàn)假設(shè)有n種商品,實(shí)現(xiàn)二分查找的算法描述如下:(1)確定查找范圍,每次查找如步驟(2)和(3),如果沒有完成則繼續(xù)操作。第1次查找的范圍是n個數(shù)據(jù)。(2)取得查找范圍的中間位置,將查找數(shù)據(jù)與中間位置的數(shù)據(jù)進(jìn)行比對,如果二者相等則查找成功,返回數(shù)據(jù)在表中的位置。(3)如果查找數(shù)據(jù)小于中間位置的數(shù)據(jù)則縮小查找范圍至前半部分,如果大于中間位置的數(shù)據(jù)則縮小查找范圍至后半部分。二分查找的算法步驟

任務(wù)二根據(jù)價格查找商品

活動2二分查找算法的設(shè)計與實(shí)現(xiàn)根據(jù)上述算法,定義binarySearch(alist,key,item)函數(shù),參數(shù)alist表示按關(guān)鍵字key排序后的線性表,參數(shù)key表示查找的關(guān)鍵字,參數(shù)item表示要查找的數(shù)據(jù)。請補(bǔ)全下面的代碼。填一填11.#二分找算法12.defbinarySearch(alist,key,item):13.first=0

#標(biāo)記查找范圍起始位置14.last=alist.size()-1

#標(biāo)記查找范圍終點(diǎn)位置15.whilefirst<=last:16.mid=(

)//2

#取得查找范圍的中間位置first+last

任務(wù)二根據(jù)價格查找商品

活動2二分查找算法的設(shè)計與實(shí)現(xiàn)填一填17.#判斷中間項是否等于查找項18.ifgetattr(alist.getItem(mid),key)==item:19.#返回查找到的商品在線性表中的位置20.returnmid21.else:22.#判斷查找項是否小于中間項23.ifitem<getattr(

):24.last=mid-1

#縮小查找范圍至前半部分25.else:26.first=

.27.return-1

#返回查找失敗alist.getItem(mid),keymid+1

任務(wù)二根據(jù)價格查找商品

活動2二分查找算法的設(shè)計與實(shí)現(xiàn)以表3.3.1中的數(shù)據(jù)為例,利用二分查找法查找價格為68的簽字筆銷售數(shù)據(jù),并顯示查找到的簽字筆銷售數(shù)據(jù)。請補(bǔ)全下面的代碼。28.bubbleSort(alist,'price')

#調(diào)用冒泡排序函數(shù)29.result=binarySearch(alist,

,

#調(diào)用二分查找函數(shù)30.print("二分查找法查找的結(jié)果是:“)31.ifresult==-1:32.print("查找失敗")33.else:34.print(getattr(alist.getItem(result),'brand'),

35.

,

)‘price’68getattr(alist.getItem(result),'price')getattr(alist.getItem(result),'sales')getattr(alist.getItem(result),'comments')5.遞歸實(shí)現(xiàn)二分查找

任務(wù)二根據(jù)價格查找商品

活動3利用遞歸法實(shí)現(xiàn)二分查找利用遞歸法實(shí)現(xiàn)二分查找,定義recursionSearch(alist,key,item,first,last)函數(shù),參數(shù)alist表示按關(guān)鍵字key排序后的線性表對象,參數(shù)key表示查找的關(guān)鍵字,參數(shù)item表示要查找的數(shù)據(jù),參數(shù)first表示查找范圍的起始位置,參數(shù)last表示查找范圍的結(jié)束位置。利用Pvthon編寫的代碼如下,請補(bǔ)全下面的代碼。01.#利用遞歸方法實(shí)現(xiàn)二分查找算法02.defrecursionSearch(alist,key,item,first,last):03.iffirst<=last:04.mid=(first+last)//2

#取得中間項位置05.else:06.return-1

#返回查找失敗

任務(wù)二根據(jù)價格查找商品

活動3利用遞歸法實(shí)現(xiàn)二分查找以表3.3.1中的數(shù)據(jù)為例,利用遞歸二分查找法查找商品價格為32的商品,并顯示該商品的相關(guān)信息。請補(bǔ)全下面的代碼。18.bubbleSort(alist,'price')

#調(diào)用冒泡排序函數(shù)19.#調(diào)用遞歸二分查找函數(shù)20.result=recursionSearch(alist,

,

,

,

)21.print(“遞歸二分查找法查找的結(jié)果是:“)22.ifresult==-1:23.print("查找失敗")24.else:25.#顯示查找結(jié)果26.print(getattr(

,‘brand'),

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論