大學計算機基礎-基于計算思維（Windows 10+Office 2016）（第2版）課件 第10章 算法思維與應用

大學計算機基礎——基于計算思維（Windows10+Office2016）第10章算法思維與應用10.1.1什么是算法10.1算法初步

什么是算法描述了一個求兩個數(shù)的最大公約數(shù)的步驟，現(xiàn)在被稱作歐幾里德算法。古希臘人亞歷山大所著《幾何原本》01

記載了各種計數(shù)法：太一算、兩儀算、三才算、五行算、八卦算、九宮算、珠算等，這些方法中已經(jīng)體現(xiàn)了現(xiàn)代程序中的選擇設計思想、并行原則、搜索原則等。中國古代數(shù)學典籍《數(shù)術記遺》02什么是算法

什么是算法“賈憲三角”“增乘開方法”“秦九韶法”等都是數(shù)學中的經(jīng)典算法，開創(chuàng)了中國傳統(tǒng)數(shù)學構造性和機械化的算法模式。中國古代劉徽所著《九章算術》03

算法的概念建立在哥德爾圖靈“算法可計算”概念嚴格的數(shù)學刻畫基礎上什么是算法

算法是一系列解決問題的清晰指令，也就是說，對于符合一定規(guī)范的輸入，能夠在有限時間內(nèi)獲得所要求的輸出，如圖所示。能夠理解和執(zhí)行所給出算法指令的人或物，在當今特指能夠高速自動運算的電子計算機。什么是算法

算法表現(xiàn)什么是算法解決問題的步驟描述可以使用語言文字或各種圖形來描述（稱作推理實現(xiàn)的算法）也可以直接使用計算機中的各種語言工具描述并執(zhí)行得到結果（稱作操作實現(xiàn)的算法）可以看作是解決問題的一類特殊方法——它雖然不是問題的答案，但它是經(jīng)過準確定義以獲得答案的過程。

算法什么是算法無論是否涉及計算機，特定的算法設計技術都能看作問題求解的有效策略。找不到一種使人長生不老的算法，也找不到一種能夠準確預判股票漲跌的算法。它所能夠解決的問題種類

什么是算法算法思想固有的精確性限制了比如

什么是算法隨著計算機技術和信息技術的飛速發(fā)展，算法不僅是計算機科學的核心，也是一種一般性的智能工具，它已滲透到宇宙學、物理學、生物學乃至經(jīng)濟學和社會科學等諸多領域，必定有助于對其他學科的理解和應用。感謝聆聽！大學計算機基礎——基于計算思維（Windows10+Office2016）大學計算機基礎——基于計算思維（Windows10+Office2016）第10章算法思維與運用10.1.2算法的基本性質(zhì)10.1算法初步算法的5個基本性質(zhì)算法初步①具有零個輸入或多個輸入輸入的目的是為算法提供原始數(shù)據(jù)或初始狀態(tài)，輸入可以來自鍵盤、文件或其他輸入設備。對于絕大多數(shù)算法，輸入都是必要的，但對于個別情況，輸入可以是零個。輸入為算法提供原始數(shù)據(jù)或初始狀態(tài)來自鍵盤、文件或其他輸入設備算法的5個基本性質(zhì)算法初步②有窮性算法必須保證在執(zhí)行有限次步驟后能自動結束，且需要的時間是在可接受的范圍之內(nèi)，而不會出現(xiàn)無限循環(huán)。執(zhí)行有限次步驟后需要的時間是在可接受的范圍之內(nèi)能自動結束算法的5個基本性質(zhì)算法初步③確定性算法的每一步驟都具有確定的含義，不會出現(xiàn)二義性，以保證在一定條件下只有一條執(zhí)行路徑，相同的輸入只能有唯一的輸出結果。每一步驟都具有確定的含義在一定條件下只有一條執(zhí)行路徑，相同的輸入只能有唯一的輸出結果不會出現(xiàn)二義性算法的5個基本性質(zhì)算法初步④可行性算法的每一步都必須是可行的，都能夠通過執(zhí)行有限次基本運算完成，即算法可以轉(zhuǎn)換為程序上機運行，并得到正確的結果。每一步都必須是可行的得到正確的結果執(zhí)行有限次基本運算完成算法的5個基本性質(zhì)算法初步⑤至少有一個或多個輸出輸出即算法的結果，沒有輸出的算法是沒有用的。輸出的形式通常通過屏幕顯示，也可以寫入到文件中，或通過其他輸出設備輸出。算法運算后至少有一個或多個輸出通過屏幕顯示，也可以寫入到文件中，或通過其他輸出設備輸出算法的5個基本性質(zhì)算法初步要確定需要哪些輸入數(shù)量、類型、輸入設備想得到什么輸出數(shù)量、類型、輸出設備通過若干步驟實現(xiàn)順序、選擇、循環(huán)感謝聆聽！大學計算機基礎——基于計算思維（Windows10+Office2016）大學計算機基礎——基于計算思維（Windows10+Office2016）第10章算法思維與運用10.1.3算法設計的要求10.1算法初步算法的4點要求算法初步①正確性對于任何合法的輸入都能夠得到正確的結果。任何合法的輸入正確的結果也能做出處理算法的4點要求算法初步②健壯性對于不合法的輸入，也能做出相關處理，而不會產(chǎn)生中斷等異常情況或無法解釋的結果。不合法的輸入不會產(chǎn)生中斷等異常情況或無法解釋的結果算法的4點要求算法初步③可讀性要便于閱讀、理解和交流，才能使后續(xù)工作輕松（包括程序代碼的編寫、調(diào)試和修改）。好的算法晦澀難懂的算法往往隱含錯誤，不易被發(fā)現(xiàn)，也難于調(diào)試和修改。在算法中增加注釋語句，對重要變量和決策語句的用途進行說明是個很好的習慣。算法的4點要求算法初步④時間效率高和存儲量需求低指算法的執(zhí)行時間，執(zhí)行時間越短效率越高。時間效率存儲量需求指算法程序運行時所占用的內(nèi)存或外部硬盤存儲空間。用最少的存儲空間，花最少的時間，求出同樣的結果就是好的算法。感謝聆聽！大學計算機基礎——基于計算思維（Windows10+Office2016）大學計算機基礎——基于計算思維（Windows10+Office2016）第10章算法思維與運用10.2.1簡單蠻力法10.2蠻力算法問題1簡單蠻力算法某國際型運動會開幕式準備策劃一個大型團體操，人數(shù)在50~500之間，但根據(jù)隊形變化要求，每10人排成一行要余2人領操，每12人排成一行要余4人領操，每4人排成一行不多不少，問需要的人數(shù)可以有多少種方案。1.問題分析既然已知所有可能解的范圍為50~500，那么就從下限50開始判斷其是否滿足所有要求（稱為約束條件），是即輸出，不是就不輸出，同理再逐一判斷51、52、53直至上限500是否滿足要求，即可求出所有的方案。問題1簡單蠻力算法2.算法實現(xiàn)①在所有可能解的范圍50~500中逐一判斷，明顯用循環(huán)結構實現(xiàn)。設一個循環(huán)變量number初值為50，終值為500，且按步長值為1遞增，據(jù)此首先構建一層循環(huán)結構。初值為50終值為500步長值為1遞增問題1簡單蠻力算法2.算法實現(xiàn)②循環(huán)體內(nèi)判斷number是否滿足所有要求，滿足則輸出number的值，否則不輸出。同時滿足3個條件可用邏輯運算符and連接，3個條件類似，都是判斷number除以某數(shù)的余數(shù)，可用求余運算符mod。判斷number是否滿足所有要求問題1簡單蠻力算法2.算法實現(xiàn)最后完整的Raptor流程圖如圖所示。問題1簡單蠻力算法3.運行結果問題1簡單蠻力算法4．問題總結上述求解問題的算法是直接根據(jù)問題的描述，從可能的集合中一一枚舉各個元素，用給定的約束條件判定哪些是問題的解，哪些不是問題的解，這種最簡單的“justdoit”的設計策略稱為蠻力法。力蠻法計算機的“計算能力”感謝聆聽！大學計算機基礎——基于計算思維（Windows10+Office2016）大學計算機基礎——基于計算思維（Windows10+Office2016）第10章算法思維與運用10.2.2復雜蠻力法10.2蠻力算法問題2復雜蠻力算法劉老師帶了41名同學去公園劃船，共租了10條船。每條大船坐6人，每條小船坐4人，問大船、小船各租幾條則剛好坐下所有人？1.問題分析對于此問題，我們可以馬上列出一個二元一次方程組：

small+big=104×small+6×big=42用消元法可以很快解出該方程組問題2復雜蠻力算法但怎么讓計算機來解這個方程組呢？用蠻力法試試。①確定窮舉對象小船small

大船big②確定窮舉范圍0~100~10③確定約束條件small+big=104×small+6×big=42④窮舉可能的解從（0，0）開始，然后依次判斷（0，1）、（0，2）、（0，3）…（0，10），（1，0）、（1，1）…(10，10)是否同時滿足兩個約束條件問題2復雜蠻力算法2．算法實現(xiàn)①用循環(huán)結構內(nèi)再嵌套循環(huán)結構來實現(xiàn)。此問題中，用small作為外循環(huán)還是用big作為外循環(huán)，都不影響結果。假設用small作外循環(huán)，big作內(nèi)循環(huán)：small+big=104×small+6×big=42當small=0時，big分別從0取到10，判斷每種組合是否滿足兩個約束條件；然后再取small=1，big又從0取到10，再判斷；最后small=10時，big又從0取到10，再判斷，這樣就能窮舉所有可能的解。問題2復雜蠻力算法2．算法實現(xiàn)操作實現(xiàn)時，則應先搭好完整的外層循環(huán)結構（small從0到10），然后在其內(nèi)的循環(huán)體內(nèi)再搭建內(nèi)層循環(huán)（big從0到10），如圖所示。問題2復雜蠻力算法2．算法實現(xiàn)②在內(nèi)層循環(huán)體內(nèi)（big層內(nèi)）再判斷是否同時滿足2個約束條件，是則輸出small和big的值，否則不輸出，如圖所示。問題2復雜蠻力算法3．運行結果問題2復雜蠻力算法4．算法優(yōu)化本例中為了提高該算法的時間效率，可以減少窮舉對象和縮小窮舉范圍。因為大小船只總數(shù)是固定的，所以只要以big為窮舉對象，根據(jù)方程1的約束條件就可得small=10-big；small=10-bigsmall+big=10問題2復雜蠻力算法4．算法優(yōu)化再根據(jù)方程2可將big的窮舉范圍縮小為從0到7，這樣用一個單循環(huán)（big從0到7）就可實現(xiàn)了。4×small+6×big=42Big≤7問題2復雜蠻力算法4．算法優(yōu)化循環(huán)體內(nèi)首先由big計算出small，即small=10-big，然后只要判斷是否滿足另一個約束條件：4×small+6×big=42即可。問題2復雜蠻力算法4．算法優(yōu)化這樣就只要對big窮舉8次，明顯縮短了算法的執(zhí)行時間，使算法得以優(yōu)化。優(yōu)化后感謝聆聽！大學計算機基礎——基于計算思維（Windows10+Office2016）大學計算機基礎——基于計算思維（Windows10+Office2016）第10章算法思維與運用10.3.1冒泡排序10.3排序算法基本排序算法冒泡排序冒泡排序選擇排序直接插入排序問題3冒泡排序大學入學軍訓時要求n人一列從低到高排列，現(xiàn)在已知n人的身高（無序），請按要求完成任務。1.問題分析冒泡排序的過程類似水中冒氣泡的過程，將待排序的n個身高數(shù)據(jù)看作是垂直排列的重量不同的氣泡。根據(jù)重氣泡不能在輕氣泡上面的原則，從上往下掃描，比較相鄰數(shù)據(jù)，如果它們是逆序的話就交換它們的位置，重復多次后，最大數(shù)據(jù)就“沉到”了最后位置，稱為第1趟掃描冒泡。問題3冒泡排序1.問題分析第2遍操作對剩余的數(shù)據(jù)進行掃描冒泡，將第二大的數(shù)據(jù)沉下去。這樣一直做，經(jīng)過n-1趟以后，所有數(shù)據(jù)就排好序了。問題3冒泡排序2．算法實現(xiàn)（1）設計輸入子程序input。先設計一個子程序來完成數(shù)據(jù)的輸入功能（名稱為input），要求生成n個150~190的隨機整數(shù)存儲到數(shù)組a[]中。數(shù)組名a作為“輸出”參數(shù)，如圖所示為input的各接口參數(shù)問題3冒泡排序2．算法實現(xiàn)（1）設計輸入子程序input。在子程序中要生成n個150~190的隨機整數(shù)存儲到a[]數(shù)組中，可設計一個循環(huán)結構（設循環(huán)變量為i，從1遞增到n）由隨機函數(shù)構建公式產(chǎn)生1個150~190的隨機整數(shù)存放到數(shù)組a[i]元素中問題3冒泡排序2．算法實現(xiàn)（2）設計輸出子程序output。設計一個子程序來完成數(shù)據(jù)的輸出功能（名稱為output），要求將上述數(shù)組a[]中的所有數(shù)據(jù)輸出，數(shù)據(jù)間用空格分隔。在創(chuàng)建子程序output時，要已知數(shù)組的大小n和數(shù)組名a，而且在output中都不會改變其值，所以n和a都作為“輸入?yún)?shù)”問題3冒泡排序2．算法實現(xiàn)（2）設計輸出子程序output。在子程序output中要輸出a數(shù)組中所有元素，可設計一個循環(huán)結構（設循環(huán)變量為i，從1遞增到n），在循環(huán)體內(nèi)按格式輸出數(shù)組元素a[i]。問題3冒泡排序2．算法實現(xiàn)（3）設計main子圖main子圖的主要功能是：①輸入要排隊列人數(shù)n。②調(diào)用input子程序生成數(shù)組a，模擬待排人的身高數(shù)據(jù)。③調(diào)用output子程序顯示數(shù)組a（無序）。問題3冒泡排序2．算法實現(xiàn)（3）設計main子圖右圖所示為該程序調(diào)試運行中的一組數(shù)據(jù)（10個）問題3冒泡排序（4）設計冒泡子程序bubble表中列出了a數(shù)組有5個元素的冒泡排序過程。問題3冒泡排序（4）設計冒泡子程序bubble從表中，我們要找出a數(shù)組有n個元素時冒泡排序的一般規(guī)律。問題3冒泡排序（4）設計冒泡子程序bubble完成bubble子程序，實現(xiàn)步驟如下：①創(chuàng)建bubble子程序，其各參數(shù)如圖所示。問題3冒泡排序（4）設計冒泡子程序bubble②在bubble子程序中首先構建掃描冒泡趟數(shù)的循環(huán)i（1～n-1）。③然后在每趟冒泡i的循環(huán)體內(nèi)再構建一個比較次數(shù)的循環(huán)j（從上往下掃描1～n-i）。④在內(nèi)循環(huán)j的循環(huán)體內(nèi)，從上到下比較相鄰元素，若a[j]>a[j+1]則交換其中的內(nèi)容。問題3冒泡排序（5）完善main子圖①調(diào)用bubble子程序，對數(shù)組a進行冒泡排序。②調(diào)用output子程序輸出數(shù)組a（有序）。問題3冒泡排序運行結果冒泡排序某次運行結果感謝聆聽！大學計算機基礎——基于計算思維（Windows10+Office2016）大學計算機基礎——基于計算思維（Windows10+Office2016）第10章算法思維與運用10.3.2選擇排序10.3排序算法1．問題分析選擇排序在冒泡排序算法的每趟冒泡中，相鄰元素只要逆序，就交換，那每趟冒泡可能交換多次。改進最小元素1a[1]最小元素2a[2]a[n]...最小元素n...1．問題分析選擇排序如表所示為5個元素的選擇排序的過程，對比冒泡排序其交換次數(shù)由8次降為4次。1．問題分析選擇排序從表中，我們要找出a數(shù)組有n個元素時選擇排序的一般規(guī)律。2．算法實現(xiàn)選擇排序設計選擇排序子程序select①創(chuàng)建select子程序，其各參數(shù)如圖所示。2．算法實現(xiàn)選擇排序設計選擇排序子程序select②構造外層循環(huán)i，決定掃描選擇的趟數(shù)，并在每趟掃描中做好準備工作（minz=a[i]，minw=i）。①接口參數(shù)②外循環(huán)（控制掃描選擇趟數(shù)，做好基準準備）2．算法實現(xiàn)選擇排序設計選擇排序子程序select③構造內(nèi)層循環(huán)j，決定每趟比較次數(shù)，并在其內(nèi)進行比較操作（若minz>a[j]，則minz=a[j]，minw=j）。③內(nèi)循環(huán)（控制比較次數(shù)，進行比較找每趟最小值）2．算法實現(xiàn)選擇排序設計選擇排序子程序select④在每趟所有比較后得到本趟最小值的位置，將其和基準位置a[i]交換。④內(nèi)循環(huán)結束后，每趟最小值和基準位置交換2．算法實現(xiàn)選擇排序設計選擇排序子程序select子程序select的完整Raptor流程圖如圖所示。感謝聆聽！大學計算機基礎——基于計算思維（Windows10+Office2016）大學計算機基礎——基于計算思維（Windows10+Office2016）第10章算法思維與運用10.3.3直接插入排序10.3排序算法1．問題分析直接插入排序班級花名冊已按學號排好了，但突然轉(zhuǎn)來了其他幾位學生（已有學號，入學后就不會變）。軍訓已有某些人按高低順序排好了隊，后來又來了一些人。怎樣將這幾位同學也按學號排到花名冊中呢?這些人怎樣插入到隊列中而不影響隊伍的高低順序呢？例如例如1．問題分析直接插入排序?qū)τ谂R時產(chǎn)生的無序數(shù)據(jù)要實現(xiàn)實時排序采用直接插入排序1．問題分析直接插入排序直接插入排序能實現(xiàn)實時排序，是因為除了無序隊列外，還需要專門的區(qū)域存儲有序隊列。1．問題分析直接插入排序然后每次從無序隊列中取出一個元素，先在有序隊列中找到相應的插入位置，再插入到有序隊列中完成1趟插入，取出一個元素在有序隊列中找到相應的插入位置插入1．問題分析直接插入排序如此反復，直到無序隊列中的元素都取完。取出一個元素在有序隊列中找到相應的插入位置插入2．算法實現(xiàn)直接插入排序（1）設計main子圖粗框圖。在main子圖中若要調(diào)用其他子程序時，因子程序還沒有創(chuàng)建，所以可只畫出空的調(diào)用框，然后給每個調(diào)用框添加注釋，注明該子程序名字和功能，這樣先有個總體思路和設計，等其他子程序完成后就可回頭補充完善main子圖。2．算法實現(xiàn)直接插入排序（1）設計main子圖粗框圖。main子圖要完成的功能①輸入待排數(shù)據(jù)的個數(shù)n。①2．算法實現(xiàn)直接插入排序（1）設計main子圖粗框圖。main子圖要完成的功能②調(diào)用一個輸入子程序input，隨機產(chǎn)生n個無序數(shù)據(jù)存放到數(shù)組a中。②2．算法實現(xiàn)直接插入排序（1）設計main子圖粗框圖。main子圖要完成的功能③調(diào)用一個輸出子程序output，顯示輸出無序數(shù)組a中的所有元素。③2．算法實現(xiàn)直接插入排序（1）設計main子圖粗框圖。main子圖要完成的功能④取出a中的第1元素放到有序數(shù)組order[1]中，生成一個有序數(shù)組order。④2．算法實現(xiàn)直接插入排序（1）設計main子圖粗框圖。main子圖要完成的功能⑤調(diào)用直接插入排序子程序insert進行排序。⑤2．算法實現(xiàn)直接插入排序（1）設計main子圖粗框圖。main子圖要完成的功能⑥調(diào)用輸出子程序output，顯示輸出有序數(shù)組order中所有元素。⑥2．算法實現(xiàn)直接插入排序（2）設計輸入和輸出子程序（input、output）。2個子程序與冒泡排序中的相同，請自行完成。2．算法實現(xiàn)直接插入排序（3）設計直接插入排序子程序insert粗框圖。insert子程序要實現(xiàn)的就是從無序隊列的第2個元素開始取，在有序數(shù)組order中找其插入位置，然后插入，直到無序隊列尾部。2．算法實現(xiàn)直接插入排序（3）設計直接插入排序子程序insert粗框圖。根據(jù)功能分析，可在insert子程序中設計一個循環(huán)結構，循環(huán)體內(nèi)調(diào)用一子程序location找a[i]在order中的插入位置，再調(diào)用子程序into將a[i]插入到order中相應位置。設循環(huán)變量為i，從2變化到n2．算法實現(xiàn)直接插入排序（4）設計找插入位置子程序location。location要實現(xiàn)的功能是找a[i]在order中的插入位置，所以其“輸入”參數(shù)有a、i、order，其中i表示取無序數(shù)組的第幾個（i）元素，應增加一個“輸出”參數(shù)wz來保存找到的插入位置并返回。2．算法實現(xiàn)直接插入排序（4）設計找插入位置子程序location。找插入位置的方法是：將a[i]和order的第1個元素開始比較，如果a[i]大，則再和order中的下一個元素比較。直到比較到a[i]小了，則order元素所在位置就是插入位置，不用再比較了。若比較到oder的最后一個元素（下標i-1），a[i]都大，則插入位置就是i。2．算法實現(xiàn)直接插入排序（4）設計找插入位置子程序location。所以設計一個循環(huán)結構（設循環(huán)變量為wz），從order的第1個元素（wz=1）開始，循環(huán)結束條件有2個：一個是a[i]<order[wz]，一個是到最后1個元素后（wz>i-1），這兩個條件用or運算符連接。從order的第1個元素開始循環(huán)結束的2個條件2．算法實現(xiàn)直接插入排序（4）設計找插入位置子程序location。注意應把wz>i-1放在or的左邊，因為or的運算順序是“從左到右”，而且左邊表達式若為“真”，則就不會再判斷右邊的表達式，所以應先判斷是否到了order的尾部，到了，則不再判斷a[i]<order[wz]。若把a[i]<order[wz]放在左邊，若a[i]一直大，wz就會超過order的尾部i-1，先判斷左邊的a[i]<order[wz]時就會出現(xiàn)下標超出范圍的錯誤了。因為or的運算順序是“從左到右”2．算法實現(xiàn)直接插入排序（5）設計插入子程序intointo子程序?qū)崿F(xiàn)的功能是將a[i]插入到order中wz的位置處，所以其“輸入”參數(shù)有a、i、order、wz，order同時也應作為“輸出”參數(shù)返回。2．算法實現(xiàn)直接插入排序（5）設計插入子程序into為了不破壞order中的原有元素，在插入之前應該先騰出該位置，即:將從order[wz]位置到order尾部的元素都往后移一位，但應從最后一個元素（i-1位置）開始后移（移到i位置），i-2位置的元素移到i-1位置，如此反復，直到wz位置的元素移到wz+1。2．算法實現(xiàn)直接插入排序（5）設計插入子程序into設計一個循環(huán)結構（設循環(huán)變量為k，從i-1遞減到wz），注意步長值為-1（即k=k-1）。循環(huán)變量為k，從i-1遞減到wz步長值為-12．算法實現(xiàn)直接插入排序（6）完善insert子程序和main子圖找插入位置子程序location和插入子程序into完成后，就可以將其所屬上級程序insert補充完善完善后的insert子程序2．算法實現(xiàn)直接插入排序（6）完善insert子程序和main子圖最后將main子圖完成，注意main子圖中：排序前調(diào)用output輸出的是無序數(shù)組a，排序后調(diào)用output輸出的是有序數(shù)組order。直接插入排序main子圖感謝聆聽！大學計算機基礎——基于計算思維（Windows10+Office2016）大學計算機基礎——基于計算思維（Windows10+Office2016）第10章算法思維與運用10.4.1順序查找10.4查找算法查找算法在手機中查找聯(lián)系人查找是從較大的數(shù)據(jù)集中找出或定位某個給定值（鍵值）的過程在圖書館中查找圖書問題4順序查找數(shù)據(jù)文件“data1.txt”中，有若干英語單詞（每行一個），現(xiàn)從鍵盤輸入一個單詞，請在文件中查找該詞，若找到則給出其位置（第幾行），若沒找到，提示“nofound”。1．問題分析由于數(shù)據(jù)集是存儲在文本文件中的，所以首先要按順序讀出這些數(shù)據(jù)存放到某數(shù)組中，然后在數(shù)組中查找。但這些數(shù)據(jù)是無序的，所以只能從數(shù)組第1個元素（或最后1個元素）開始，按正序（或逆序）逐個掃描每個元素是否和鍵值相等，若相等則數(shù)組下標即為其位置，若掃描結束都不相等，則表明沒有所查的數(shù)據(jù)（稱為查找失敗），所以稱這種查找算法為順序查找（sequentialsearch）。123456鍵值正序逆序順序查找問題4順序查找2．算法實現(xiàn)（1）設計main子圖粗框圖在main中應完成的功能是：①調(diào)用input子程序讀文件到數(shù)組a中。②輸入鍵值存入key中。③調(diào)用search子程序在數(shù)組a中查找key。④調(diào)用output子程序輸出查找結果。①②③④問題4順序查找2．算法實現(xiàn)（2）設計讀文件子程序input該子程序的目的就是將文本文件中的數(shù)據(jù)讀出到數(shù)組a中，所以a應作為其輸出參數(shù)。a數(shù)組的大小n也應作為輸出參數(shù)返回，以便控制查找范圍，本題中n是動態(tài)的，由文件長度決定。順序查找讀文件子程序input問題4順序查找2．算法實現(xiàn)（3）設計順序查找子程序searchsearch的功能是從a數(shù)組的第1個元素開始到最后第n個元素，逐個掃描并和鍵值key比較，并返回一個值表示找到還是未找到，找到了還要返回所在位置。1234...nkeysearch返回一個值找到未找到所在位置問題4順序查找2．算法實現(xiàn)（3）設計順序查找子程序search注意在search中不做最后的輸出處理，而是在output子程序中輸出結果，所以輸入?yún)?shù)有a、n、key，再增加2個輸出參數(shù)，一個輸出參數(shù)flag，目的是用來區(qū)分不同種狀態(tài)。例如flag=0表示沒找到，flag=1表示找到，通常稱flag為狀態(tài)變量，另一個輸出參數(shù)為找到時的位置wz。問題4順序查找2．算法實現(xiàn)（3）設計順序查找子程序search在search中，查找前可以分別賦給狀態(tài)變量和找到的位置一個初值（flag=0，wz=0），然后構造一個循環(huán)結構（設循環(huán)變量為i，初始值i=1，循環(huán)結束條件是i>n），在循環(huán)體內(nèi)判斷a[i]=key是否成立，若成立則狀態(tài)變量發(fā)生改變（flag=1），同時保存當前位置wz=i，但循環(huán)不會中途結束，還會繼續(xù)，所以可以在循環(huán)結束條件中再增加一個條件，或者找到了（即flag=1），也結束循環(huán)；而若a[i]=key不成立，則繼續(xù)循環(huán)判斷，此時狀態(tài)變量一直不變化（flag=0）。所以循環(huán)結束后，通過flag返回的值就可判斷找到還是沒找到。順序查找子程序search問題4順序查找2．算法實現(xiàn)（4）設計輸出子程序output根據(jù)search子程序查找的結果分別輸出：若找到了（flag=1），則輸出其位置wz，若沒找到（flag=0），則顯示輸出“nofound”，所以其只要2個輸入?yún)?shù)flag和wz。順序查找輸出子程序output問題4順序查找2．算法實現(xiàn)（5）完善main子圖當所有子程序設計好后，就可以將main子圖補充完整，運行調(diào)試了。順序查找的完整main子圖感謝聆聽！大學計算機基礎——基于計算思維（Windows10+Office2016）大學計算機基礎——基于計算思維（Windows10+Office2016）第10章算法思維與運用10.4.2二分查找10.4查找算法問題5二分查找某體校要招各類體育專長人員，根據(jù)專業(yè)不同，對身高有不同的要求?，F(xiàn)有若干人的身高數(shù)據(jù)按從低到高的順序存放在數(shù)據(jù)文件“data2.txt”中（每行一個），當招生人員從鍵盤輸入一個身高值，請在文件中查找該身高值，若找到則給出其位置（第幾行），若沒找到，提示“nofound”。data2.txt若找到則給出其位置（第幾行）輸入查找若沒找到，提示“nofound”輸出問題5二分查找1．問題分析本問題中數(shù)據(jù)集中的數(shù)據(jù)是有序的，已按從低到高的順序排好，那能不能利用這一條件提高查找效率呢？問題5二分查找1．問題分析先看這樣一個游戲：猜某件商品的價格，已知商品的價格范圍（假設為1~100元），每猜一次主持人可以回答游戲者所猜價格比實際價格高了還是低了，若在規(guī)定次數(shù)內(nèi)就能猜對者，就可免費獲得該商品。為了減少猜的次數(shù)，提高命中的效率，你會怎樣猜呢？通常會從1到100元的中間值50元開始猜，如果高了，則進一步從1到50元的中間值25再開始猜；而如果低了，則從50到100元的中間值75開始猜，這種猜價格的方法稱為折半方法。把折半方法應用在查找中，就稱為折半查找法（又稱二分查找），它是在一個有序的元素列表中查找特定值的一種方法，該順序可以是升序，也可以是降序。問題5二分查找1．問題分析二分查找順序查找問題5二分查找2.算法實現(xiàn)設計折半查找子程序halfsearchhalfsearch的參數(shù)和順序查找算法中search的一樣，輸入?yún)?shù)有a、n、key，輸出參數(shù)有flag、wz。問題5二分查找2.算法實現(xiàn)設計折半查找子程序halfsearch假設用left表示每次查找范圍的最小值，right表示每次查找范圍的最大值，第1次查找范圍是(left=1,right=n)，以后每次不是left變，就是right變，當最后變到left>right就說明查找失敗，所以其也作為循環(huán)結束的一個條件。第1次查找范圍(left=1,right=n)......第n次查找范圍left>right,查找失敗問題5二分查找2.算法實現(xiàn)設計折半查找子程序halfsearch在查找前，要完成flag、wz、left、right和middle（中間位置）的初始化。完成初始化問題5二分查找2.算法實現(xiàn)設計折半查找子程序halfsearch開始查找后，是取中間位置的值（即a[middle]）和key比較，若相等，則狀態(tài)變量flag=1；否則還要判斷a[middle]是小于