1、第七講 算法北京大學(xué)信息學(xué)院2013年10月2022/9/23北京大學(xué)2主要內(nèi)容了解算法的基本概念掌握描述算法的三種基本結(jié)構(gòu)學(xué)會算法的流程圖描述介紹幾種基本算法難、有意思、數(shù)學(xué)、編程的基礎(chǔ)2022/9/23北京大學(xué)31 算法的基本概念計(jì)算機(jī)是一個(gè)計(jì)算工具，它本身不能主動幫助我們做任何事情，需要我們告訴它如何進(jìn)行計(jì)算。程序設(shè)計(jì)就是要告訴計(jì)算機(jī)如何進(jìn)行計(jì)算的。這與我們中學(xué)時(shí)代的數(shù)學(xué)解題過程是一樣的，只不過描述的手段有所變化而已。2022/9/23北京大學(xué)41 算法的基本概念1984年圖靈獎獲得者瑞士科學(xué)家尼克勞斯沃斯（Niklaus Wirth，Pascal語言的發(fā)明者和結(jié)構(gòu)化程序設(shè)計(jì)創(chuàng)始者）19

2、76年出版了算法+數(shù)據(jù)結(jié)構(gòu) = 程序設(shè)計(jì)一書，提出了著名的公式：“程序 數(shù)據(jù)結(jié)構(gòu) 算法” 。程序：刻畫現(xiàn)實(shí)世界，解決現(xiàn)實(shí)世界中的問題程序設(shè)計(jì)語言：實(shí)現(xiàn)的工具算法：問題的解的描述數(shù)據(jù)結(jié)構(gòu)：現(xiàn)實(shí)世界的數(shù)據(jù)模型程序就是在數(shù)據(jù)的某些特定的表示方式和結(jié)構(gòu)的基礎(chǔ)上對抽象算法的具體表述。一行行代碼、語言2022/9/23北京大學(xué)51 算法的基本概念算法的定義設(shè)計(jì)程序的目的是為了求解問題，為解決一個(gè)問題所采取的方法和步驟，就稱為“算法”算法是一個(gè)由一組嚴(yán)格定義的動作組成的過程，給定一個(gè)出始狀態(tài)，這個(gè)過程能夠結(jié)束在一個(gè)確定終止?fàn)顟B(tài)。大多數(shù)算法都可以用程序?qū)崿F(xiàn)。常用算法一般都被實(shí)現(xiàn)為算法庫，供程序員調(diào)用。算法的基

3、本思想如何把大象關(guān)在冰箱里?分3步：第一步：打開冰箱門;第二步：把大象推進(jìn)冰箱;第三步：關(guān)上冰箱門;2022/9/23北京大學(xué)71 算法的基本概念一個(gè)實(shí)例：找出一組正整數(shù)中的最大的數(shù)2022/9/23北京大學(xué)81 算法的基本概念逐步求解，定義算法的動作S1: 設(shè)Largest為第一個(gè)數(shù)S2: 若第二個(gè)數(shù)比Largest大，則設(shè)Largest為第二個(gè)數(shù)S3: 若第三個(gè)數(shù)比Largest大，則設(shè)Largest為第三個(gè)數(shù)S4: 若第四個(gè)數(shù)比Largest大，則設(shè)Largest為第四個(gè)數(shù)S5: 若第五個(gè)數(shù)比Largest大，則設(shè)Largest為第五個(gè)數(shù)2022/9/23北京大學(xué)91 算法的基本概念算法

4、動作精化S0: 設(shè)Largest為0S1: 若當(dāng)前數(shù)比Largest大，則設(shè)Largest為當(dāng)前數(shù)S2: 若當(dāng)前數(shù)比Largest大，則設(shè)Largest為當(dāng)前數(shù)S3: 若當(dāng)前數(shù)比Largest大，則設(shè)Largest為當(dāng)前數(shù)S4: 若當(dāng)前數(shù)比Largest大，則設(shè)Largest為當(dāng)前數(shù)S5: 若當(dāng)前數(shù)比Largest大，則設(shè)Largest為當(dāng)前數(shù)2022/9/23北京大學(xué)101 算法的基本概念算法范化從N個(gè)正整數(shù)中找出最大數(shù)的通用算法循環(huán)結(jié)構(gòu)S0: 設(shè)Largest為0，當(dāng)前位置p為0S1: 若當(dāng)前數(shù)比Largest大，則設(shè)Largest為當(dāng)前數(shù)S2: 若p比N小，則p增加1，并返回S1；否則返

5、回Largest2022/9/23北京大學(xué)111 算法的基本概念算法的基本性質(zhì)通用性：即適用于某一類問題中的所有個(gè)體，而不只是用來解決一個(gè)具體的問題。有效性：即應(yīng)有明確的步驟一步一步地引導(dǎo)計(jì)算的進(jìn)行。確定性：即每個(gè)步驟都是機(jī)械的、有明確定義的動作，不需要計(jì)算者臨時(shí)動腦筋。有限性：對滿足算法要求的輸入數(shù)據(jù)，算法應(yīng)在有限多步內(nèi)結(jié)束，并給出明確的計(jì)算結(jié)果。離散性：算法的輸入數(shù)據(jù)及輸出數(shù)據(jù)都應(yīng)是離散的符號。2022/9/23北京大學(xué)121 算法的基本概念算法的基本要求正確易維護(hù)（可讀，易修改）方便使用高效速度快 運(yùn)行時(shí)間少，時(shí)間復(fù)雜度低占用內(nèi)存少，空間復(fù)雜度低算法的效率可以測試，用大量輸入數(shù)據(jù)測量運(yùn)行

6、的時(shí)間和占用的內(nèi)存，通過比較判別和選擇效率高的算法。更重要的是可以在編程前進(jìn)行分析和估計(jì)（算法分析），即理論的計(jì)算，給出事前的判斷。高斯，查字典2022/9/23北京大學(xué)131 算法的基本概念不了解施加于數(shù)據(jù)上的算法就無法決定如何構(gòu)造數(shù)據(jù)；反之，算法的結(jié)構(gòu)和選擇卻常常在很大程度上依賴于作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。簡而言之，程序的構(gòu)成（算法）與數(shù)據(jù)結(jié)構(gòu)是兩個(gè)不可分割地聯(lián)系在一起的問題。2022/9/23北京大學(xué)142 描述算法的三種基本結(jié)構(gòu)計(jì)算機(jī)科學(xué)家已經(jīng)證明，只使用如下三種結(jié)構(gòu)，就可以描述任何算法，且算法結(jié)構(gòu)優(yōu)良順序結(jié)構(gòu)（Sequence）分支結(jié)構(gòu)（Decision）循環(huán)結(jié)構(gòu)（Repetition）每

7、一種基本結(jié)構(gòu)分別只有一個(gè)入口和一個(gè)出口2022/9/23北京大學(xué)152.1 順序結(jié)構(gòu)順序結(jié)構(gòu)：動作（語句）序列，順序執(zhí)行，每個(gè)動作只執(zhí)行一次，各動作對執(zhí)行結(jié)果產(chǎn)生的影響是獨(dú)立的動作1動作2動作3動作n動作1動作2動作3動作n2.1 順序結(jié)構(gòu)按部就班先來后到循序漸進(jìn)接連不斷起床刷牙吃早飯上課吃中飯午休上課吃晚飯晚自習(xí)洗漱睡覺2022/9/23北京大學(xué)16現(xiàn)實(shí)生活中的示例2022/9/23北京大學(xué)172.2 分支結(jié)構(gòu)分支結(jié)構(gòu)：根據(jù)條件判斷執(zhí)行什么動作（序列），最多只有一個(gè)動作（序列）被執(zhí)行如果 條件成立 則動作（或動作序列）1否則動作（或動作序列） 2分支結(jié)束條件成立？動作（序列）1動作（序列）2

8、是否2.2 分支結(jié)構(gòu)如果分?jǐn)?shù)達(dá)到一本線錄取到一本大學(xué)如果分?jǐn)?shù)達(dá)到二本線錄取到二本大學(xué)如果分?jǐn)?shù)達(dá)到三本線錄取到三本大學(xué)如果分?jǐn)?shù)達(dá)到?？凭€錄取到專科學(xué)校否則落榜選擇二選一條條道路通羅馬如果明天天晴小明就去郊游否則就在家里看書2022/9/23北京大學(xué)18現(xiàn)實(shí)生活中的示例2022/9/23北京大學(xué)192.3 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)：重復(fù)執(zhí)行一系列動作當(dāng) 條件成立 做動作1動作2動作n循環(huán)結(jié)束處條件成立？動作1動作n是否2.3 循環(huán)結(jié)構(gòu)周而復(fù)始轉(zhuǎn)圈輪回（第幾周）如果小于20周 如果是周一到周五上課否則休息放寒假2022/9/23北京大學(xué)20現(xiàn)實(shí)生活中的示例一個(gè)循環(huán)結(jié)構(gòu)示例：求11000的平方和S0j1SS

9、+ j*jjj+1j1000打印SYesNo三種基本控制結(jié)構(gòu)可相互組合和嵌套使用，形成更為復(fù)雜的控制，完成各種復(fù)雜的工作。開始結(jié)束2022/9/23北京大學(xué)223 用流程圖表示算法算法是讓人來理解的，因此需要有效的算法表示機(jī)制自然語言表示法偽代碼表達(dá)法流程圖表示法2022/9/23北京大學(xué)233 用流程圖表示算法流程圖顯示了程序的流程判斷結(jié)構(gòu)。通常包含如下符號：開始和結(jié)束流程線輸入和輸出處理（動作）條件判斷開始/結(jié)束處理（動作）流程線輸入/輸出條件判斷2022/9/23北京大學(xué)243 用流程圖表示算法判斷x0y = xy = -xYesNo2022/9/23北京大學(xué)253 用流程圖表示算法循環(huán)

10、k10動作k=k+1YesNo動作k=0吃蟹黃湯包理解算法結(jié)構(gòu)問題1：吃過嗎？口訣：輕輕提, 慢慢移, 先開窗, 再喝湯。吃一只蟹黃湯包的“算法”順序很重要：將包子從蒸籠中輕輕提起，and then將包子慢慢移動到面前的小碟子中，and then 在包子的正上方咬開一個(gè)小口，and then通過小口吸食包子里的湯(當(dāng)心別燙著)，and then將包子送入口中。完成！問題2：你如何確保過程無誤？假如我們認(rèn)為在步驟4和5執(zhí)行前要確保前面的結(jié)果是正確的，可以在相應(yīng)的地方設(shè)個(gè)“監(jiān)視哨” “guard”。問題3：但是我們并不只是吃一只，那怎么辦呢？策略一：控制數(shù)量假如規(guī)定吃8只：開始設(shè)一個(gè)計(jì)數(shù)器，并將其

11、值設(shè)定為0。吃一只湯包計(jì)數(shù)器值加1，并判斷其是否為8否是結(jié)束注意：計(jì)數(shù)器的初始值策略二：吃飽為止是否已飽？是否 問題4：如果即使飽了，也希望至少品嘗一只，該怎么辦？有人知道飽不飽，但有人不知道！開始要吃湯包的人不到5歲嗎？是選用策略1選用策略2否結(jié)束問題7：如果要判斷的不止是兩種可能，那怎么辦？分類定量控制開始要吃湯包的人不到5歲嗎？否參數(shù)設(shè)為2是結(jié)束要吃湯包的人不到60歲嗎？參數(shù)設(shè)為8是參數(shù)設(shè)為4否選用策略1(帶參數(shù))2022/9/23北京大學(xué)343 用流程圖表示算法判斷閏年能被4整除且不能被100整除；能被400整除2022/9/23北京大學(xué)353 流程圖表示算法判斷閏年能被4整除且不能被

12、100整除；能被400整除用C語言實(shí)現(xiàn)算法2022/9/23北京大學(xué)364.1基本算法 日期判斷問題：給定年月日，判斷該日是這年的第幾天。求解按月累加天數(shù)區(qū)分大、小月區(qū)分閏年、平年初始化：total=0, i=1開始total = total + 31i month？N結(jié)束Yi = i+1輸入：year, month, dayi是大月？i是小月？total = total + 30YNYNyear是閏年？total = total + 29total = total + 28total = total + day輸出：total4.1基本算法 日期判斷（語言實(shí)現(xiàn)）2022/9/23北京大學(xué)38

13、int year, month, day, total, i;scanf(“%d%d%d”, &year, &month, &day);total = 0;for( i=1; imonth; i+) if ( i =1 | i=3 | i=5 | i=7 | i=8 | i=10 | i=12) total = total +31; if ( i =4 | i=6 | i=9 | i=11) total = total +30; if ( i =2) if( (year%4=0&year%100!=0) | year%400=0 ) total = total +29; else total

14、= total +28; total = total + day;2022/9/23北京大學(xué)394.1基本算法 - 求平方根求一個(gè)數(shù)的平方根： x = 迭代公式 x1 = 1 xn+1 = (xn + a/xn)/2 迭代計(jì)算，直到 xn+1 xn 的絕對值小于誤差要求，例如小于0.00001，即保留小數(shù)點(diǎn)后5位。開始初始化：x2=1x1 = x2x2 = (x1 + a/x1)/2x2-x1的絕對值小于0.00001？N結(jié)束Y輸出x2輸入數(shù)a2022/9/23北京大學(xué)404.1基本算法 - 求平方根(C語言實(shí)現(xiàn))2022/9/23北京大學(xué)414.1基本算法 素?cái)?shù)判定 與歌德巴赫猜想問題：判定

15、一個(gè)數(shù)是否為素?cái)?shù)求解除2之外，偶數(shù)都不是素?cái)?shù)對于一個(gè)奇數(shù)P，看它是否能被某個(gè)大于1，小于P的奇數(shù)整除，如果存在，則P不是素?cái)?shù)，否則P就是素?cái)?shù)初始化：isPrime = ture, i = 3開始p能否被整除？N結(jié)束Yi = i+2輸入：pi half ？p能否被i整除？YNYNP等于嗎？half = pisPrime = falseYNisPrime = falsehalf = p/2half = sqrt(p)輸出isPrime2022/9/23北京大學(xué)43int isPrimeNumber(int p)int i, half, isPrime1;if ( p % 2 = 0 ) if (

16、p = 2 ) return isPrime; isPrime = 0;return isPrime;half = p; / half = p / 2;for( i = 3; i = half; i = i+2 ) if( p % i = 0 ) isPrime = 0;break;return isPrime;4.1基本算法 素?cái)?shù)判定 與歌德巴赫猜想2022/9/23北京大學(xué)444.1基本算法 素?cái)?shù)判定 與歌德巴赫猜想歌德巴赫猜想：任何大于6的偶數(shù)都能分成兩個(gè)奇素?cái)?shù)之和問題分析對一個(gè)偶數(shù)N，把它分解成兩個(gè)奇數(shù)的和分別驗(yàn)證這兩個(gè)數(shù)是否為素?cái)?shù)，如果都是，則N滿足歌德巴赫猜想初始化：i = 3開始

17、結(jié)束i = i+2輸入：ni = half ？i和n-i是否都為素?cái)?shù) ？YYNhalf = n/2N4.1基本算法 素?cái)?shù)判定 與歌德巴赫猜想輸出：n為素?cái)?shù)i和 n-i 之和2022/9/23北京大學(xué)46判斷一個(gè)偶數(shù)是否滿足歌德巴赫猜想4.1基本算法 素?cái)?shù)判定 與歌德巴赫猜想void GoldbachConjecture(int n)int half = n/2; / 求出半數(shù)n/2待用int i; / 循環(huán)變量int isPrime1, isPrime2; / 臨時(shí)變量for( i = 3; i 41455345=452022/9/23北京大學(xué)614.3 二分法搜索算法、程序開始返回-1子序列為空？low=0, high=n-1mid=(low+high)/2返回midx =Amid？x1n=1n14.4 基本算法 迭代與遞歸2022/9/23北京大學(xué)63一個(gè)關(guān)于遞歸的故事 一個(gè)沒有去過北京的人問：天安門是什么樣子？去過北京的人答道：天安門有個(gè)城樓，城樓上有個(gè)國徽，國徽里有個(gè)天安門，天安門有個(gè)城樓，城樓上有個(gè)國