PowerPoint 簡報

Size: px

Start display at page:

Download "PowerPoint 簡報"

流武上官
5 years ago
Views:

1 13.1 為何需要檢索 (Searching)? 提取資訊是其中一項最重要的電腦應用檢索類型外部檢索 : 需檢索的資料是貯存在硬碟中的大型數據庫中內部檢索 : 需檢索的資料是貯存在陣列等電腦記憶體中 1

2 13.1 為何需要檢索? 在進行檢索時, 會根據一項資料 ( 例如名字 ID 或數字 ) 來尋找有關的記錄這項資料稱為關鍵碼 (key) 檢索的目的, 就是要找出關鍵碼與目標相符的記錄檢索記錄內的關鍵碼很耗時以下因素對程序的效能都有很大的影響 : 記錄的排列檢索方法 2

3 13.2 線性檢索 Linear/Sequential Search 線性檢索的概念線性檢索又稱為順序檢索這種方法是由第一個陣列元素開始至最後一個, 把目標值與關鍵碼逐一比較最常用於對未經排序的記錄的檢索 3

4 13.2 線性檢索線性檢索的概念名字分數 PETER 89 HENRY 75 PAUL 60 BRIAN 55 VINCENT 70 ADA 72 CINDY 69 SAM 77 DANIEL 81 SAMUEL 68 PRISCA 73 十一名學生的考試分數 ( 未排序 ) 4

5 13.2 線性檢索線性檢索的概念要檢索目標學生名字 PAUL, 我們會由表列中的第一個名字開始, 把它與目標作比較若沒有找到配對, 便繼續比較表列中的下一個名字, 直至 : 找到目標, 或已達表列的結尾 5

6 13.2 線性檢索線性檢索的概念利用線性檢索找尋學生 PAUL 6

7 13.2 線性檢索程序實現假設以上的學生記錄貯存在以下的文字檔 'exam.txt' 中 : 貯存在文字檔 'exam.txt' 中的學生記錄 7

: 0..100 end; const Num = 11; { number of

8 13.2 線性檢索程序實現說明記錄陣列 Student, 來貯存學生名字和考試分數 : type ExamType = record Name : string[30]; Mark : end; const Num = 11; { number of students } var Student : array[1..num] of ExamType; 8

9 13.2 線性檢索程序實現程序 SearchRecord 的結構 9

10 13.2 線性檢索程序實現過程 InputData 會從文字檔 'exam.txt' 中讀取學生記錄, 並把它們貯存在記錄陣列 Student 中 10

11 13.2 線性檢索程序實現程序和過程 InputData: 行號程序語句 program SearchRecord; type ExamType = record Name : string[30]; Mark : end; const Num = 11; { number of students } var Student : array[1..num] of ExamType; position : integer; { target student in array } 11

12 13.2 線性檢索程序實現行號程序語句 procedure InputData; var Examfile : text; { text file storing student records } count : integer; begin assign(examfile, 'exam.txt'); reset(examfile); count := 0; while not eof(examfile) do begin count := count + 1; with Student[count] do begin 12

13 13.2 線性檢索程序實現行號程序語句 readln(examfile, Name); readln(examfile, Mark) end end; close(examfile) { close file } end; { InputData } { procedure Search declaration } { procedure DisplayResult declaration } begin { main program } InputData; Search(position); DisplayResult(position) end. 13

14 13.2 線性檢索實現線性檢索在過程 Search 中, 透過鍵盤輸入目標學生名字, 然後與陣列 Student 中的名字逐一作比較 ( 第 54 和 55 行 ) 若找到配對, 該目標學生的位置便會被貯存在參數 index 中, 否則貯存的值為零迭代的次數會被記錄下來, 以表示檢索的效率若記錄中有重複的名字, 只會找出第一次出現的目標名字 14

15 13.2 線性檢索實現線性檢索行號程序語句 procedure Search(var index : integer); { linear search } var target : string; { name of student to be searched for } found : boolean; { indicate search status } count : integer; { store number of iterations } begin write( 'Enter name of student: '); readln(target); found := false; count := 0; index := 0; 15

16 13.2 線性檢索實現線性檢索行號程序語句 repeat count := count + 1; with Student[count] do if Name = target { compare name key with target } then begin index := count; found := true { successful search } end until found or (count = Num); writeln( 'Number of iterations = ', count) end; { Search } 16

17 13.2 線性檢索實現線性檢索行號程序語句 procedure DisplayResult(index : integer); begin if index = 0 { if search is unsuccessful, index remains zero } then writeln('record not found!') else with Student[index] do begin writeln( 'Record found!'); writeln( 'Student name = ', Name); writeln( 'Exam mark = ', Mark) end end; { DisplayResult } 17

18 13.2 線性檢索實現線性檢索若記錄中並沒有目標名字, 迭代的次數將等於記錄的總數當要處理大量記錄時, 線性檢索的效率便會下降輸出例子 1 輸出例子 2 Enter name of student: ADA Number of iterations = 6 Record found! Student name = ADA Exam mark = 72 Enter name of student: PASCAL Number of iterations = 11 Record not found! 18

19 13.3 二分檢索 Binary Search 二分檢索的概念線性檢索易於實現, 但若應用於長表列, 其效率則偏低令效率大幅提升的方法 : 把表列排序重整檢索算法 19

20 13.3 二分檢索二分檢索的概念若我們要從電話簿翻查一個名字, 例如 Peter, 而電話簿的名字是按英文字母由 A 到 Z 順序排列從第一個名字開始逐個查看的做法是不夠效率的較有效率和明智的做法, 是從中間開始查看若中間的一頁上寫的是由 P 之前的字母所開頭的名字時, 便應由電話簿的下半部分繼續查看 ; 否則, 便應查看上半部分若重複步驟, 每次要檢索的表列中的名字便會減少一半這算法也因而被稱為二分檢索 20

21 13.3 二分檢索二分檢索的概念利用二分檢索從電話簿中檢索 Peter 21

22 13.3 二分檢索二分檢索的例子再次考慮前一節中的例子, 但這次所用的是依學生名字排序的表列 : 名字分數 ADA 72 BRIAN 55 CINDY 69 DANIEL 81 HENRY 75 PAUL 60 PETER 89 PRISCA 73 SAM 77 十一名學生的考試分數表列 ( 依學生名字排序 ) SAMUEL 68 VINCENT 70 22

23 13.3 二分檢索二分檢索的例子假設我們要在表列中檢索 'PETER' 這個名字二分檢索需要經過數次迭代, 才能找出目標的位置 23

24 13.3 二分檢索二分檢索的例子第 1 次迭代 : 中間元素 =(1 + 11)div 2 = 第 6 個元素由於 'PAUL' < 'PETER'( 根據字串的順序值作比較 ), 因此, 目標應在表列的下半部分 ( 第 7 至 11 項 ) 24

25 13.3 二分檢索二分檢索的例子第 2 次迭代 : 中間元素 =(7 + 11)div 2 = 第 9 個元素由於 'SAM' > 'PETER', 目標應在表列的上半部分 ( 第 7 至 8 項 ) 25

26 13.3 二分檢索二分檢索的例子第 3 次迭代 : 中間元素 =(7 + 8)div 2 = 第 7 個元素由於 'PETER' = 'PETER', 即是說, 我們在第 7 個元素中找到目標名字 26

27 13.3 二分檢索二分檢索的例子顯而易見, 二分檢索所需的比較數目 (3 個 ), 較線性檢索所需的數目 (7 個 ) 少得多 top 和 bottom 分別代表表列中的首個和最後一個索引, middle 代表中間的索引 27

28 13.3 二分檢索二分檢索的例子 'Target' = 'PETER' 迭代 top middle bottom 與中間的名字作比較備註表列中元素的數目 Target > 'PAUL' 目標在下半部分 Target < 'SAM' 目標在上半部分 Target = 'PETER' 成功找到目標 2 尋找 PETER 所使用的二分檢索的迭代總結 28

29 13.3 二分檢索二分檢索的例子每次完成比較後, 若目標在下半部, 便把 middle + 1 賦予 top 來進行下一次迭代 ( 綠色箭號 ) 若目標在上半部, 則把 middle 1 賦予 bottom( 藍色箭號 ) 由於二分檢索需要不斷在表列的其中一端與中間跳來跳去, 因此要檢索的記錄必須貯存在陣列等可隨機存取的數據結構中 29

30 13.3 二分檢索二分檢索的例子以上的二分檢索算法的總結 : 偽代碼 found false top 1 bottom 11 repeat middle (top + bottom) div 2 if target > Name in middle then top middle + 1 else if target < Name in middle then bottom middle 1 else found true until target is found or list is empty 30

31 13.3 二分檢索檢索失敗的條件如果進行二分檢索的表列中並沒有所輸入的目標名字時, 會出現甚麼情況呢? 若輸入的名字是 PASCAL, 二分檢索最後的結果會是 : 31

32 13.3 二分檢索檢索失敗的條件 'Target' = 'PASCAL' 迭代 top middle bottom 與中間的名字作比較備註表列中元素的數目 Target < 'PAUL' 目標在上半部分 Target > 'CINDY' 目標在下半部分 Target > 'DANIEL' 目標在下半部分 Target > 'HENRY' 目標在下半部分 top > bottom - 利用表達式 top > bottom 來確定表列是否包含目標 32

33 13.3 二分檢索檢索失敗的條件若檢索表列中並沒有目標名字, 在最後一次迭代中,top 的值會大於 bottom 的值可利用布爾表達式 top > bottom 來標示一個空白的表列 33

34 13.3 二分檢索實現二分檢索行號程序語句 procedure Search(var index : integer); { Require student records sorted alphabetically } var target : string; { name of student to be searched for } found : boolean; { indicates search status } count : integer; { stores number of iterations } top, bottom, middle : integer; begin write('enter name of student:'); readln(target); found := false; count := 0; index := 0; top := 1; bottom := Num; 34

35 13.3 二分檢索實現二分檢索行號程序語句 repeat count := count + 1; middle := (top + bottom) div 2; with Student[middle] do begin if target > Name then top := middle + 1 { lower half } else if target < Name then bottom := middle - 1 { upper half } else begin index := middle; found := true { search successful } end end until found or (top > bottom); { empty list } writeln('number of iterations = ', count) end; { Search } 35

36 13.3 二分檢索實現二分檢索輸出例子 1 輸出例子 2 Enter name of student: ADA Number of iterations = 3 Record found! Student name = ADA Exam mark = 72 Enter name of student: PASCAL Number of iterations = 4 Record not found! 36

37 13.3 二分檢索分析二分檢索二分檢索所需的迭代次數較線性檢索的為少 37

38 13.3 二分檢索分析二分檢索目標所需迭代的次數 ADA 3 BRIAN 4 CINDY 2 DANIEL 3 HENRY 4 PAUL 1 PETER 3 PRISCA 4 SAM 2 SAMUEL 3 VINCENT 4 PASCAL 4 ZOEY 4 檢索特定目標所需的迭代次數成功的檢索 ( 平均 = 3) 失敗的檢索 38

39 13.3 二分檢索分析二分檢索檢索成功與否, 對所需的迭代次數影響不大在最差的情況中, 只需 4 次迭代, 遠較線性檢索所需的為少二分檢索的性能可預測性也較線性檢索的為高若原來的表列中有 N 個元素, 在第一次迭代後, 剩下大約 N/2 個元素假設在第 k 個迭代之後找到目標元素, 即表列中只剩下一個元素 39

40 13.3 二分檢索分析二分檢索含 N 個元素的表列所需的迭代次數, 可由以下的公式估計出來 : N 2 k N 1 2 logn k log 2 k k logn log 2 對於很大的 N 值 ( 如 10,000), 所需的迭代次數 (k) 會遠較線性檢索所需的為少 40

41 13.4 比較線性檢索和二分檢索線性檢索容易實現在處理長表列時, 其效率偏低二分檢索在處理長表列時, 其效率相當高不容易實現有關的表列必須先經排序不知道表列是否已經排序使用線性檢索 41

42 13.4 比較線性檢索和二分檢索線性檢索二分檢索算法邏輯簡單複雜程序實現容易困難對表列的要求沒有必須先經排序及支援隨機存取對於一個含 N 個元素的表列, 所需的迭代次數平均約為 : 成功的檢索失敗的檢索 ( N 1) 2 N logn log2 logn log2 應用適用於短表列適用於已排序的長表列線性檢索及二分檢索的比較 42

43 13.4 比較線性檢索和二分檢索當表列中有 20 個或以上的元素時, 二分檢索所需的迭代, 顯然遠較線性檢索所需的為少 43

Microsoft Word - _m30.doc

Microsoft Word - _m30.doc 1 2 3 4 5 6 7 8 公式 2 4 2 1 能整除因此後玩者贏且關鍵數字為3 的倍數 3 0 3 1 不能整除所以先拿餘數 2 關鍵數字是 4的倍數 2 先玩者贏 4 0 4 1 能整除因此後玩者贏且關鍵數字為 5 的倍數 5 0 5 1 不能整除所以先拿餘數 2 關鍵數字是 6的倍數 2 先玩者贏 7 0 6 1 能整除因此後玩者贏且關鍵數字為7