算法設(shè)計(jì)課件

1、2022/7/28北京大學(xué)1上堂課的主要內(nèi)容程序設(shè)計(jì)語言（也被稱為“編程語言”，Programming Language）是人們描述（編制）程序所使用的規(guī)范和方法（語言）。機(jī)器語言匯編語言高級(jí)語言第六講 算法設(shè)計(jì)北京大學(xué) 信息科學(xué)技術(shù)學(xué)院2022年7月28日2022/7/28北京大學(xué)3主要內(nèi)容了解算法的基本概念掌握描述算法的三種基本結(jié)構(gòu)學(xué)會(huì)算法的流程圖描述介紹幾種基本算法2022/7/28北京大學(xué)41 算法的基本概念計(jì)算機(jī)只是一個(gè)計(jì)算工具，它本身不能主動(dòng)幫助我們做任何事情，需要我們告訴它如何進(jìn)行計(jì)算。程序設(shè)計(jì)就是要告訴計(jì)算機(jī)如何進(jìn)行計(jì)算的。這與我們中學(xué)時(shí)代的數(shù)學(xué)解題過程是一樣的，只不過描述的手

2、段有所變化而已。2022/7/28北京大學(xué)51 算法的基本概念1984年圖靈獎(jiǎng)獲得者瑞士科學(xué)家尼克勞斯沃斯（Niklaus Wirth，Pascal語言的發(fā)明者和結(jié)構(gòu)化程序設(shè)計(jì)創(chuàng)始者）1976年出版了算法+數(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/7/28北京大學(xué)61 算法的基本概念算法的定義設(shè)計(jì)程序的目的是為了求解問題，為解決一個(gè)問題所采取的方法和步驟，就稱為“算法”算法

3、是一個(gè)由一組嚴(yán)格定義的指令組成的過程，給定一個(gè)出始狀態(tài)，這個(gè)過程能夠結(jié)束在一個(gè)確定終止?fàn)顟B(tài)。大多數(shù)算法都可以用程序?qū)崿F(xiàn)。常用算法一般都被實(shí)現(xiàn)為算法庫，供程序員調(diào)用。2022/7/28北京大學(xué)71 算法的基本概念一個(gè)實(shí)例：找出一組正整數(shù)中的最大的數(shù)2022/7/28北京大學(xué)81 算法的基本概念逐步求解，定義算法的動(dòng)作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è)Large

4、st為第五個(gè)數(shù)2022/7/28北京大學(xué)91 算法的基本概念算法動(dòng)作精化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/7/28北京大學(xué)101 算法的基本概念算法范化從N個(gè)正整數(shù)中找出最大數(shù)的通用算法S0: 設(shè)Largest為0，當(dāng)前位置p為0S1: 若當(dāng)前數(shù)比Largest大，則設(shè)Largest為

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

6、空間復(fù)雜度低算法的效率可以測試，用大量輸入數(shù)據(jù)測量運(yùn)行的時(shí)間和占用的內(nèi)存，通過比較判別和選擇效率高的算法。更重要的是編程前的分析和估計(jì)，即理論的計(jì)算，給出事前的判斷。2022/7/28北京大學(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/7/28北京大學(xué)142 描述算法的三種基本結(jié)構(gòu)已經(jīng)證明，只使用如下三種結(jié)構(gòu)，就可以描述任何算法，且算法結(jié)構(gòu)優(yōu)良順序結(jié)構(gòu)（Sequence）分支結(jié)構(gòu)（Decision）循環(huán)結(jié)構(gòu)（Repetit

7、ion）每一種基本結(jié)構(gòu)分別只有一個(gè)入口和一個(gè)出口2022/7/28北京大學(xué)152.1 順序結(jié)構(gòu)順序結(jié)構(gòu)：動(dòng)作（語句）序列，順序執(zhí)行動(dòng)作1動(dòng)作2動(dòng)作3動(dòng)作n動(dòng)作1動(dòng)作2動(dòng)作3動(dòng)作12022/7/28北京大學(xué)162.2 分支結(jié)構(gòu)分支結(jié)構(gòu)：根據(jù)條件判斷執(zhí)行什么動(dòng)作（語句）如果 條件成立 則動(dòng)作1否則動(dòng)作2分支結(jié)束條件成立？動(dòng)作1動(dòng)作2是否2022/7/28北京大學(xué)172.3 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)：重復(fù)執(zhí)行一系列動(dòng)作當(dāng) 條件成立 做動(dòng)作1動(dòng)作2動(dòng)作n循環(huán)結(jié)束處條件成立？動(dòng)作1動(dòng)作n是否2022/7/28北京大學(xué)183 流程圖表示算法算法是讓人來理解的，因此需要有效的算法表示機(jī)制自然語言表示法偽代碼表達(dá)法流

8、程圖表示法2022/7/28北京大學(xué)193 流程圖表示算法流程圖顯示了程序的流程判斷結(jié)構(gòu)。通常包含如下符號(hào)：開始和結(jié)束流程線輸入和輸出處理（動(dòng)作）條件判斷開始/結(jié)束處理（動(dòng)作）流程線輸入/輸出條件判斷2022/7/28北京大學(xué)203 流程圖表示算法判斷x0y = xy = -xYesNo2022/7/28北京大學(xué)213 流程圖表示算法循環(huán)k41455345=452022/7/28北京大學(xué)414.3 二分法搜索算法、程序開始返回-1子序列為空？low=0, high=n-1mid=(low+high)/2返回midx =Amid？xAmid？high=mid-1low=mid+1YYYNNN20

9、22/7/28北京大學(xué)424.4 基本算法 迭代與遞歸迭代(iterative)與遞歸(recursive)2022/7/28北京大學(xué)431974年圖靈獎(jiǎng)獲得者美國科學(xué)家唐納德克努特(Donad E.Knuth，排版軟件的先驅(qū)(TEX) ）經(jīng)典巨著計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù)(The Art of Computer Programming)The Art of Computer Programming 卷1為基礎(chǔ)運(yùn)算法則，該書以基本的編程概念和技術(shù)為開始，然后講述信息結(jié)構(gòu)計(jì)算機(jī)內(nèi)信息的表示法，數(shù)據(jù)元素間的結(jié)構(gòu)關(guān)系以及處理它們的有效方法。主要應(yīng)用于模擬、數(shù)字方法、符號(hào)計(jì)算、軟件和系統(tǒng)設(shè)計(jì)。 卷2對半數(shù)值算法領(lǐng)域做了全面介紹，分隨機(jī)數(shù)和算術(shù)兩章。本卷總結(jié)了主要算法范例及這些算法的基本理論，廣泛剖析了計(jì)算機(jī)程序設(shè)計(jì)與數(shù)值分析間的相互聯(lián)系。 卷3為分揀和搜索，它對計(jì)算機(jī)分揀和搜索的一流技術(shù)的最全面的研究，它擴(kuò)展了卷1中數(shù)據(jù)結(jié)構(gòu)的處理方法，將數(shù)據(jù)庫以及內(nèi)存和外部存儲(chǔ)都包