第七講2算法與流程圖

第七講

算法北京大學(xué)信息學(xué)院2014年11月2023/5/24北京大學(xué)2主要內(nèi)容了解算法的基本概念掌握描述算法的三種基本結(jié)構(gòu)學(xué)會算法的流程圖描述介紹幾種基本算法難、有意思、數(shù)學(xué)、編程的基礎(chǔ)2023/5/24北京大學(xué)31算法的基本概念計算機是一個計算工具，它本身不能主動幫助我們做任何事情，需要我們告訴它如何進(jìn)行計算。程序設(shè)計就是要告訴計算機如何進(jìn)行計算的。這與我們中學(xué)時代的數(shù)學(xué)解題過程是一樣的，只不過描述的手段有所變化而已。2023/5/24北京大學(xué)41算法的基本概念1984年圖靈獎獲得者瑞士科學(xué)家尼克勞斯·沃斯（NiklausWirth，Pascal語言的發(fā)明者和結(jié)構(gòu)化程序設(shè)計創(chuàng)始者）1976年出版了《算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計》一書，提出了著名的公式：“程序＝數(shù)據(jù)結(jié)構(gòu)＋算法”。程序：刻畫現(xiàn)實世界，解決現(xiàn)實世界中的問題程序設(shè)計語言：實現(xiàn)的工具算法：問題的解的描述數(shù)據(jù)結(jié)構(gòu)：現(xiàn)實世界的數(shù)據(jù)模型程序就是在數(shù)據(jù)的某些特定的表示方式和結(jié)構(gòu)的基礎(chǔ)上對抽象算法的具體表述。一行行代碼、語言2023/5/24北京大學(xué)51算法的基本概念算法的定義設(shè)計程序的目的是為了求解問題，為解決一個問題所采取的方法和步驟，就稱為“算法”算法是一個由一組嚴(yán)格定義的動作組成的過程，給定一個出始狀態(tài)，這個過程能夠結(jié)束在一個確定終止?fàn)顟B(tài)。大多數(shù)算法都可以用程序?qū)崿F(xiàn)。常用算法一般都被實現(xiàn)為算法庫，供程序員調(diào)用。算法的基本思想如何把大象關(guān)在冰箱里?分3步：第一步：打開冰箱門;第二步：把大象推進(jìn)冰箱;第三步：關(guān)上冰箱門;2023/5/24北京大學(xué)71算法的基本概念一個實例：找出一組正整數(shù)中的最大的數(shù)2023/5/24北京大學(xué)81算法的基本概念逐步求解，定義算法的動作S1:設(shè)Largest為第一個數(shù)S2:若第二個數(shù)比Largest大，則設(shè)Largest為第二個數(shù)S3:若第三個數(shù)比Largest大，則設(shè)Largest為第三個數(shù)S4:若第四個數(shù)比Largest大，則設(shè)Largest為第四個數(shù)S5:若第五個數(shù)比Largest大，則設(shè)Largest為第五個數(shù)2023/5/24北京大學(xué)91算法的基本概念算法動作精化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ù)2023/5/24北京大學(xué)101算法的基本概念算法動作精化S0:設(shè)Largest為0,執(zhí)行5遍SSSS:若當(dāng)前數(shù)比Largest大，則設(shè)Largest為當(dāng)前數(shù)2023/5/24北京大學(xué)111算法的基本概念算法范化從N個正整數(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；否則返回LargestS0S2S12023/5/24北京大學(xué)121算法的基本概念算法的基本性質(zhì)通用性：即適用于某一類問題中的所有個體，而不只是用來解決一個具體的問題。有效性：即應(yīng)有明確的步驟一步一步地引導(dǎo)計算的進(jìn)行。確定性：即每個步驟都是機械的、有明確定義的動作，不需要計算者臨時動腦筋。有限性：對滿足算法要求的輸入數(shù)據(jù)，算法應(yīng)在有限多步內(nèi)結(jié)束，并給出明確的計算結(jié)果。離散性：算法的輸入數(shù)據(jù)及輸出數(shù)據(jù)都應(yīng)是離散的符號。2023/5/24北京大學(xué)131算法的基本概念算法的基本要求正確易維護(hù)（可讀，易修改）方便使用高效速度快運行時間少，時間復(fù)雜度低占用內(nèi)存少，空間復(fù)雜度低算法的效率可以測試，用大量輸入數(shù)據(jù)測量運行的時間和占用的內(nèi)存，通過比較判別和選擇效率高的算法。更重要的是可以在編程前進(jìn)行分析和估計（算法分析），即理論的計算，給出事前的判斷。2023/5/24北京大學(xué)141算法的基本概念不了解施加于數(shù)據(jù)上的算法就無法決定如何構(gòu)造數(shù)據(jù)；反之，算法的結(jié)構(gòu)和選擇卻常常在很大程度上依賴于作為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。簡而言之，程序的構(gòu)成（算法）與數(shù)據(jù)結(jié)構(gòu)是兩個不可分割地聯(lián)系在一起的問題。2023/5/24北京大學(xué)152描述算法的三種基本結(jié)構(gòu)計算機科學(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）每一種基本結(jié)構(gòu)分別只有一個入口和一個出口2023/5/24北京大學(xué)162.1順序結(jié)構(gòu)順序結(jié)構(gòu)：動作（語句）序列，順序執(zhí)行，每個動作只執(zhí)行一次，各動作對執(zhí)行結(jié)果產(chǎn)生的影響是獨立的動作1動作2動作3…動作n動作1動作2動作3…動作n2.1順序結(jié)構(gòu)按部就班先來后到循序漸進(jìn)接連不斷起床刷牙吃早飯上課吃中飯午休上課吃晚飯晚自習(xí)洗漱睡覺2023/5/24北京大學(xué)17現(xiàn)實生活中的示例2023/5/24北京大學(xué)182.2分支結(jié)構(gòu)分支結(jié)構(gòu)：根據(jù)條件判斷執(zhí)行什么動作（序列），最多只有一個動作（序列）被執(zhí)行如果條件成立則動作（或動作序列）1否則動作（或動作序列）2分支結(jié)束條件成立？動作（序列）1動作（序列）2是否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é)校否則落榜選擇二選一條條道路通羅馬如果明天天晴小明就去郊游否則就在家里看書2023/5/24北京大學(xué)19現(xiàn)實生活中的示例2023/5/24北京大學(xué)202.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周如果是周一到周五上課否則休息放寒假2023/5/24北京大學(xué)21現(xiàn)實生活中的示例一個循環(huán)結(jié)構(gòu)示例：

求1~1000的平方和S←0j←1S←S+j*jj←j+1j>1000打印SYesNo三種基本控制結(jié)構(gòu)可相互組合和嵌套使用，形成更為復(fù)雜的控制，完成各種復(fù)雜的工作。開始結(jié)束2023/5/24北京大學(xué)233用流程圖表示算法算法是讓人來理解的，因此需要有效的算法表示機制自然語言表示法偽代碼表達(dá)法流程圖表示法2023/5/24北京大學(xué)243用流程圖表示算法流程圖顯示了程序的流程判斷結(jié)構(gòu)。通常包含如下符號：開始和結(jié)束流程線輸入和輸出處理（動作）條件判斷開始/結(jié)束處理（動作）流程線輸入/輸出條件判斷2023/5/24北京大學(xué)253用流程圖表示算法判斷x>0y=xy=-xYesNo2023/5/24北京大學(xué)263用流程圖表示算法循環(huán)k<10動作k=k+1YesNo動作k=0吃蟹黃湯包理解算法結(jié)構(gòu)問題1：吃過嗎？口訣：輕輕提,慢慢移,先開窗,再喝湯。吃一只蟹黃湯包的“算法”順序很重要：將包子從蒸籠中輕輕提起，andthen將包子慢慢移動到面前的小碟子中，andthen在包子的正上方咬開一個小口，andthen通過小口吸食包子里的湯(當(dāng)心別燙著)，andthen將包子送入口中。完成！問題2：但是我們并不只是吃一只，那怎么辦呢？策略一：控制數(shù)量假如規(guī)定吃8只：開始設(shè)一個計數(shù)器，并將其值設(shè)定為0。吃一只湯包計數(shù)器值加1，并判斷其是否為8否是結(jié)束注意：計數(shù)器設(shè)初始值策略二：吃飽為止是否已飽？是否問題：如果即使飽了，也希望至少品嘗一只，該怎么辦？有人知道飽不飽，但有人不知道！開始要吃湯包的人不到5歲嗎？是選用策略1選用策略2否結(jié)束問題7：如果要判斷的不止是兩種可能，那怎么辦？分類定量控制開始要吃湯包的人不到5歲嗎？否參數(shù)設(shè)為2是結(jié)束要吃湯包的人不到60歲嗎？參數(shù)設(shè)為8是參數(shù)設(shè)為4否選用策略1(帶參數(shù))2023/5/24北京大學(xué)343用流程圖表示算法判斷閏年能被4整除且不能被100整除；能被400整除2023/5/24北京大學(xué)353流程圖表示算法判斷閏年能被4整除且不能被100整除；能被400整除用C語言實現(xiàn)算法2023/5/24北京大學(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基本算法–

日期判斷（Ｃ語言實現(xiàn)）2023/5/24北京大學(xué)38intyear,month,day,total,i;scanf(“%d%d%d”,&year,&month,&day);total=0;for(i=1;i<month;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;elsetotal=total+28;}}total=total+day;2023/5/24北京大學(xué)394.1基本算法-求平方根求一個數(shù)的平方根：

x=迭代公式

x1=1xn+1=(xn+a/xn)/2

迭代計算，直到xn+1–xn的絕對值小于誤差要求，例如小于0.00001，即保留小數(shù)點后5位。開始初始化：x1=1x2=(x1+a/x1)/2x2-x1的絕對值

小于0.00001？N結(jié)束Y輸出x2輸入數(shù)a2023/5/24北京大學(xué)404.1基本算法-求平方根求一個數(shù)的平方根：

x=迭代公式

x1=1xn+1=(xn+a/xn)/2

迭代計算，直到xn+1–xn的絕對值小于誤差要求，例如小于0.00001，即保留小數(shù)點后5位。開始初始化：x2=1x1=x2x2=(x1+a/x1)/2x2-x1的絕對值

小于0.00001？N結(jié)束Y輸出x2輸入數(shù)a2023/5/24北京大學(xué)414.1基本算法-求平方根(C語言實現(xiàn))2023/5/24北京大學(xué)424.1基本算法–

素數(shù)判定與

歌德巴赫猜想問題：判定一個數(shù)是否為素數(shù)求解除2之外，偶數(shù)都不是素數(shù)對于一個奇數(shù)P，看它是否能被某個大于1，小于P的奇數(shù)整除，如果存在，則P不是素數(shù)，否則P就是素數(shù)初始化：isPrime=ture,i=3開始p能否被２整除？N結(jié)束Yi=i+2輸入：pi<half？p能否被i整除？YNYNP等于２嗎？half=pisPrime=falseYNisPrime=falsehalf=p/2half=sqrt(p)輸出isPrime2023/5/24北京大學(xué)44intisPrimeNumber(intp){ inti,half,isPrime＝1; if(p%2==0){ if(p==2){ returnisPrime; }isPrime=0; returnisPrime; }

half=p;//half=p/2; for(i=3;i<=half;i=i+2){ if(p%i==0){ isPrime=0; break; } } returnisPrime;}4.1基本算法–

素數(shù)判定與

歌德巴赫猜想2023/5/24北京大學(xué)454.1基本算法–

素數(shù)判定與

歌德巴赫猜想歌德巴赫猜想：任何大于6的偶數(shù)都能分成兩個奇素數(shù)之和問題分析對一個偶數(shù)N，把它分解成兩個奇數(shù)的和分別驗證這兩個數(shù)是否為素數(shù)，如果都是，則N滿足歌德巴赫猜想初始化：i=3開始結(jié)束i=i+2輸入：ni<=half？i和n-i是否都為素數(shù)？YYNhalf=n/2N4.1基本算法–

素數(shù)判定與

歌德巴赫猜想輸出：n為素數(shù)i和

n-i之