1、第二章第二章 程序設(shè)計的靈魂程序設(shè)計的靈魂算法算法清華大學 自動化系劉連臣2022年6月10日C語言程序設(shè)計與訓練語言程序設(shè)計與訓練1主要內(nèi)容o目標：以計算機能執(zhí)行的算法特征為線索，了解計算機的模型與結(jié)構(gòu)，掌握程序設(shè)計基本理念，為程序設(shè)計語言的學習奠定基礎(chǔ)。o提綱2.1 2.1 算法與計算機算法算法與計算機算法2.2 2.2 圖靈機模型圖靈機模型2.3 2.3 程序設(shè)計的靈魂程序設(shè)計的靈魂算法算法2.4 2.4 計算機算法的表示計算機算法的表示2.5 2.5 算法結(jié)構(gòu)化分析算法結(jié)構(gòu)化分析22.1 算法與計算機算法o 程序設(shè)計的目的是什么？程序設(shè)計的目的是什么？o 從計算機解決問題的過程出發(fā)，設(shè)

2、計出計算機從計算機解決問題的過程出發(fā)，設(shè)計出計算機能夠執(zhí)行的算法，并且實現(xiàn)該算法。能夠執(zhí)行的算法，并且實現(xiàn)該算法。具體問題分析問題設(shè)計算法編寫程序調(diào)試程序得到答案32.1 算法與計算機算法o 算法算法：為解決一個問題而采取的方法和步驟，或者說：為解決一個問題而采取的方法和步驟，或者說是解題步驟的精確描述。是解題步驟的精確描述?！癮 set of rules that must be followed when solving a particular problem ”o “算法”即演算法的中文名稱最早出自周髀算經(jīng)。o 英文名稱 Algorithm 來自于9世紀波斯數(shù)學家花拉子密（比阿勒霍瓦里

3、松）?！八惴ā痹瓰椤癮lgorism”（阿拉伯數(shù)字的運算法則），18世紀演變?yōu)閍lgorithm。42.1 算法與計算機算法o 對同一個問題，可有不同的解題方法和步驟對同一個問題，可有不同的解題方法和步驟o方法1：1+2，+3，+4，一直加到100 加99次o方法2：100+(1+99)+(2+98)+(49 +51)+50 = 100 + 49100 +50 加51次例： 求1001nn 好的算法：方法簡單、運算步驟少、能迅速得出正確結(jié)果的算法。 對于算法的優(yōu)劣評價可以用空間復(fù)雜度與時間復(fù)雜度來衡量。52.1 算法與計算機算法o計算機算法計算機算法：計算機能執(zhí)行的算法。：計算機能執(zhí)行的算法。

4、n是計算機處理信息的本質(zhì)，因為計算機程序本質(zhì)上是一是計算機處理信息的本質(zhì)，因為計算機程序本質(zhì)上是一個算法來告訴計算機個算法來告訴計算機確切的步驟確切的步驟（well-defined procedure）來來執(zhí)行一個指定的任務(wù)。執(zhí)行一個指定的任務(wù)。o計算機算法的特點計算機算法的特點n輸入輸入：一個算法必須有零個或以上輸入量。：一個算法必須有零個或以上輸入量。n輸出輸出：一個算法應(yīng)有一個或以上輸出量，輸出量是算法計算的結(jié)果。：一個算法應(yīng)有一個或以上輸出量，輸出量是算法計算的結(jié)果。 n明確性明確性：算法的描述必須無歧義，以保證算法的實際執(zhí)行結(jié)果是精確：算法的描述必須無歧義，以保證算法的實際執(zhí)行結(jié)果是

5、精確地符合要求或期望，并且要求實際執(zhí)行結(jié)果是確定的。地符合要求或期望，并且要求實際執(zhí)行結(jié)果是確定的。 n有限性有限性：（計算機只有有限個狀態(tài)、有限個輸入符號和有限個指令）：（計算機只有有限個狀態(tài)、有限個輸入符號和有限個指令）規(guī)定算法必須在有限個步驟內(nèi)完成任務(wù)。規(guī)定算法必須在有限個步驟內(nèi)完成任務(wù)。 n有效性有效性：又稱可行性。算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基：又稱可行性。算法中描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)。本運算執(zhí)行有限次來實現(xiàn)。 62.1 算法與計算機算法o算盤有二五珠算盤 、一五珠算盤 、九珠算盤等o用算珠來表示數(shù)字。o有對應(yīng)四則運算的珠算法則。o有操作指

6、法。o思考思考n輸入？輸入？n輸出？輸出？n明確性？明確性？n有限性？有限性？n有效性？有效性？72.2 圖靈機模型o什么是“確切的步驟確切的步驟” 精確的定義？o20世紀的英國數(shù)學家圖靈提出了著名的圖靈論題，并提出一種假想的計算機的抽象模型，這個模型被稱為圖靈機。1912年6月23日1954年6月7日圖靈機的藝術(shù)表示 （1936年提出）82.2 圖靈機模型o 圖靈的基本思想是用機器來模擬人們用紙筆進行數(shù)學運算的過程n在紙上寫上或擦除某個符號； n把注意力從紙的一個位置移動到另一個位置； o 而在每個階段，人要決定下一步的動作，依賴于 n(a) 此人當前所關(guān)注的紙上某個位置的符號。n(b) 此

7、人當前思維的狀態(tài)。92.2 圖靈機模型圖靈機組成圖靈機組成o構(gòu)造出一臺假想的機器，該機器由以構(gòu)造出一臺假想的機器，該機器由以下幾個部分組成：下幾個部分組成：n一條無限長的紙帶一條無限長的紙帶 TAPE。n一個讀寫頭一個讀寫頭 HEAD。n一套控制規(guī)則一套控制規(guī)則 TABLE。n一個狀態(tài)寄存器。一個狀態(tài)寄存器。n注意這個機器的每一部分都是有限注意這個機器的每一部分都是有限的，但它有一個潛在的無限長的紙的，但它有一個潛在的無限長的紙帶，因此這種機器只是一個理想的帶，因此這種機器只是一個理想的設(shè)備。圖靈認為這樣的一臺機器就設(shè)備。圖靈認為這樣的一臺機器就能模擬人類所能進行的任何計算過能模擬人類所能進行

8、的任何計算過程。程。102.2 圖靈機模型圖靈機工作原理圖靈機工作原理o從讀寫頭在紙帶上讀出一個方格從讀寫頭在紙帶上讀出一個方格的信息的信息o并且根據(jù)它當前的內(nèi)部狀態(tài)開始并且根據(jù)它當前的內(nèi)部狀態(tài)開始對控制規(guī)則進行查尋。然后得出對控制規(guī)則進行查尋。然后得出一個輸出動作，也就是是否往紙一個輸出動作，也就是是否往紙帶上寫信息，還是移動讀寫頭到帶上寫信息，還是移動讀寫頭到下一個方格。程序也會告訴它下下一個方格。程序也會告訴它下一時刻內(nèi)部狀態(tài)轉(zhuǎn)移到哪一個。一時刻內(nèi)部狀態(tài)轉(zhuǎn)移到哪一個。o具體的控制規(guī)則就是一個列表，具體的控制規(guī)則就是一個列表，其實就是程序，樣子如右側(cè)表。其實就是程序，樣子如右側(cè)表。當前狀當

9、前狀態(tài)態(tài)s s輸入數(shù)輸入數(shù)值值i i輸出輸出動作動作o o下一時刻狀態(tài)下一時刻狀態(tài)s sB1前移CA0 往紙帶上寫1BC 0后移A112.2 圖靈機模型o 圖靈機只要根據(jù)每一時刻讀寫頭讀到的信息和當前的內(nèi)部狀圖靈機只要根據(jù)每一時刻讀寫頭讀到的信息和當前的內(nèi)部狀態(tài)進行查表就可以確定它下一時刻的內(nèi)部狀態(tài)和輸出動作。態(tài)進行查表就可以確定它下一時刻的內(nèi)部狀態(tài)和輸出動作。o 圖靈機就是這么簡單！而只要你變化它的程序（也就是上面的規(guī)則表），那么它就可能為你做任何計算機能夠完成的工作?？梢哉f，圖靈機就是一個最簡單的計算機模型！122.3 程序設(shè)計的靈魂算法o一個程序應(yīng)包括兩個方面的內(nèi)容n對數(shù)據(jù)的描述：數(shù)據(jù)結(jié)

10、構(gòu)(data structure)n對操作的描述：算法(algorithm)o完整的程序設(shè)計程序設(shè)計應(yīng)該是:著名計算機科學家沃思提出一個公式數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + 算法算法 = 程序程序程序程序語言程序程序語言132.3 程序設(shè)計的靈魂算法例例2.1: 求求12345步驟1：先求12，得到結(jié)果2步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6步驟3：將6再乘以4，得24步驟4：將24再乘以5，得120n如果要求如果要求1 12 210001000，則要寫，則要寫999999個步驟個步驟n應(yīng)該怎么辦呢？應(yīng)該怎么辦呢？142.3 程序設(shè)計的靈魂算法可以設(shè)兩個變量：可以設(shè)兩個變量：一個變量代表被乘數(shù)，

11、一個變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。設(shè)p為被乘數(shù)，i為乘數(shù)。用循環(huán)算法來求結(jié)果, 算法可改寫：S1：使p=1。S2：使i=2。S3：使pi，乘積仍放在變量p中，可表示為：pi p S4：使i的值加1，即i+1 i。S5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否則，算法結(jié)束。最后得到p的值就是5!的值。152.3 程序設(shè)計的靈魂算法如果題目改為：求1357911算法只需作很少的改動：S1： 1pS2： 3 iS3： pi pS4： i+2 pS5：若i11，返回S3。否則，結(jié)束。 用這種方法表示的算法具有通用性、靈活性。S3到

12、S5組成一個循環(huán)，在實現(xiàn)算法時 要反復(fù)多次執(zhí)行S3，S4，S5等步驟，直到某一時刻，執(zhí)行S5步驟時經(jīng)過判斷，乘數(shù)i已超過規(guī)定的數(shù)值而不返回S3步驟為止。此時算法結(jié)束，變量p的值就是所求結(jié)果。162.3 程序設(shè)計的靈魂算法例例2.2 判定判定20002500年中的每一年是否閏年中的每一年是否閏年，輸出結(jié)果。年，輸出結(jié)果。n 分析：閏年的條件是：o 能被4整除，但不能被100整除的年份都是閏年，如1996，2004年是閏年；o 能被100整除，又能被400整除的年份是閏年。如1600,2000年是閏年。1. 不符合這兩個條件的年份不是閏年。 172.3 程序設(shè)計的靈魂算法設(shè)設(shè)y y為被檢測的年份，

13、算法可表示如下為被檢測的年份，算法可表示如下 ：S1：2000 yS2：若y不能被4整除，則輸出y “不是閏年”。然后轉(zhuǎn)到S6。S3：若y能被4整除，不能被100整除，則輸出y “是閏年”。然后轉(zhuǎn)到S6。S4：若y能被100整除，又能被400整除，輸出y“是閏年”，否則輸出“不是閏年”。 然后轉(zhuǎn)到S6。S5: 輸出y “不是閏年”。S6：y+1 yS7：當y2500時，轉(zhuǎn)S2繼續(xù)執(zhí)行，如y2500，算法停止。18o以上算法中每做一步都分別分離出一些范圍(巳能判定為閏年或非閏年)，逐步縮小范圍，直至執(zhí)行S5時，只可能是非閏年。o“其它” 包括能被4整除，又能被100整除，而不能被400整除的那些

14、年份(如1990) 是非閏年。2.3 程序設(shè)計的靈魂算法192.3 程序設(shè)計的靈魂算法o 算法的三種基本結(jié)構(gòu)算法的三種基本結(jié)構(gòu)n Bohra和和Jacopini于于1966年提出了以下三種基本年提出了以下三種基本結(jié)構(gòu)：結(jié)構(gòu)：o 順序執(zhí)行結(jié)構(gòu)順序執(zhí)行結(jié)構(gòu)o 選擇執(zhí)行結(jié)構(gòu)選擇執(zhí)行結(jié)構(gòu)o 循環(huán)執(zhí)行結(jié)構(gòu)循環(huán)執(zhí)行結(jié)構(gòu)o由三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，可以解決任何復(fù)雜問題。由三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，可以解決任何復(fù)雜問題。o由基本結(jié)構(gòu)所構(gòu)成的算法屬于由基本結(jié)構(gòu)所構(gòu)成的算法屬于“結(jié)構(gòu)化結(jié)構(gòu)化”的算法，它不存在無規(guī)的算法，它不存在無規(guī)律的轉(zhuǎn)向，只在本基本結(jié)構(gòu)內(nèi)才允許存在分支和向前或向后的跳律的轉(zhuǎn)向，只

15、在本基本結(jié)構(gòu)內(nèi)才允許存在分支和向前或向后的跳轉(zhuǎn)。轉(zhuǎn)。202.4 計算機算法的表示2.4.1 用自然語言表示算法用自然語言表示算法o 自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以是漢語或英自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以是漢語或英語或其它語言。用自然語言表示通俗易懂，但文字冗語或其它語言。用自然語言表示通俗易懂，但文字冗長，容易出現(xiàn)長，容易出現(xiàn)“歧義性歧義性”。自然語言表示的含義往往。自然語言表示的含義往往不大嚴格，要根據(jù)上下文才能判斷其正確含義，描述不大嚴格，要根據(jù)上下文才能判斷其正確含義，描述包含分支和循環(huán)的算法時也不很方便。因此，除了那包含分支和循環(huán)的算法時也不很方便。因此，除了那些很簡單的問

16、題外，一般不用自然語言描述算法。些很簡單的問題外，一般不用自然語言描述算法。212.4 計算機算法的表示2.4.2 用流程圖表示算法用流程圖表示算法n美國國家標準化協(xié)會美國國家標準化協(xié)會ANSI(American National Standard Institute)1985年發(fā)布并規(guī)定了一些常用的流年發(fā)布并規(guī)定了一些常用的流程圖符號。（國際標準化組織公布的標準程圖符號。（國際標準化組織公布的標準ISO5807-85）n國家標準局批準的國家標準國家標準局批準的國家標準(GB1525-89)起止框起止框判斷框判斷框處理框處理框輸入輸入/輸出框輸出框注釋框注釋框流向線流向線連接點連接點222.4

17、 計算機算法的表示o 三種基本結(jié)構(gòu)的圖示：順序結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)選擇結(jié)構(gòu)232.4 計算機算法的表示o 循環(huán)結(jié)構(gòu)的圖示： 當型當型(While型型)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 直到型直到型(Until型型)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 242.4 計算機算法的表示o 三種基本結(jié)構(gòu)的共同特點：三種基本結(jié)構(gòu)的共同特點： n 只有一個入口。只有一個入口。 n 只有一個出口。（只有一個出口。（請注意：請注意：一個菱形判斷框一個菱形判斷框有兩個出口，而一個選擇結(jié)構(gòu)只有一個出口。有兩個出口，而一個選擇結(jié)構(gòu)只有一個出口。不要將菱形框的出口和選擇結(jié)構(gòu)的出口混不要將菱形框的出口和選擇結(jié)構(gòu)的出口混淆。）淆。）n 結(jié)構(gòu)內(nèi)的每一部分都有

18、機會被執(zhí)行到。結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到。n 結(jié)構(gòu)內(nèi)不存在結(jié)構(gòu)內(nèi)不存在“死循環(huán)死循環(huán)”( (無終止的循環(huán)無終止的循環(huán)) )。252.4 計算機算法的表示o流程圖是表示算法的較好的工具。包括以下幾部分 ：n表示相應(yīng)操作的框；n帶箭頭的流程線；n框內(nèi)外必要的文字說明。1.將例將例2.1求求5!的算法用流程圖表示。的算法用流程圖表示。262.4 計算機算法的表示o將例將例2.2判定閏年的算法用流判定閏年的算法用流程圖表示程圖表示用流程圖表示算法要比用文字描述算法邏輯清晰、易于理解。 272.4 計算機算法的表示2.4.2 用用N-S流程圖表示算法流程圖表示算法1.1.傳統(tǒng)流程圖的弊端傳統(tǒng)流程圖

19、的弊端o流程線的使用沒有嚴格限制o占用太多地方2 . 19732 . 1973年，年， I.NassiI.Nassi和和B.ShneidermanB.Shneiderman進行改進。進行改進。o完全去掉了帶箭頭的流程線。o全部算法寫在一個矩形框內(nèi)，在該框內(nèi)還可以包含其它的從屬于它的框，或者說，由一些基本的框組成一個大的框。o這種流程圖又稱N-S結(jié)構(gòu)化流程圖。28 N-S流程圖用以下的流程圖符號： (1)順序結(jié)構(gòu)(2)選擇結(jié)構(gòu)(3)循環(huán)結(jié)構(gòu)2.4 計算機算法的表示29將例將例2.1的求的求5!算法用算法用N-S圖表示圖表示2.4 計算機算法的表示30 將例將例2.3判定閏判定閏年的算法用年的算法

20、用N-S圖表示圖表示31 2.4.3 用偽代碼表示算法用偽代碼表示算法o 概念：偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法。o 特點：它如同一篇文章一樣 ，自上而下地寫下來。每一行(或幾行)表示一個基本操作。它不用圖形符號，因此書寫方便 、格式緊湊，也比較好懂，也便于向計算機語言算法(即程序)過渡。o 用處：適用于設(shè)計過程中需要反復(fù)修改時的流程描述。2.4 計算機算法的表示32 IF x is positive THEN print x ELSE print -x也可以用漢字偽代碼表示：也可以用漢字偽代碼表示： 若若 x為正為正 打印打印 x 否則否則 打印打印 -x也可以中

21、英文混用，如：也可以中英文混用，如： IF x 為正為正 print x ELSE print -x例： “打印x的絕對值”的算法可以用偽代碼表示為：2.4 計算機算法的表示33開始開始 置置t的初值為的初值為1 置置i的初值為的初值為2 當當i=5，執(zhí)行下面操作：，執(zhí)行下面操作： 使使t=ti 使使i=i+1 循環(huán)體到此結(jié)束循環(huán)體到此結(jié)束 輸出輸出t的值的值 結(jié)束結(jié)束也可以寫成以下形式：也可以寫成以下形式： BEGIN算法開始算法開始 1t 2 i while i5 ti t i+1 i print t END算法結(jié)束算法結(jié)束例求例求5!。用偽代碼表示算法：。用偽代碼表示算法：2.4 計算機

22、算法的表示342.4 計算機算法的表示2.4.4 用計算機語言表示算法用計算機語言表示算法n概念：概念：用計算機實現(xiàn)算法。用計算機實現(xiàn)算法。計算機是無法識別流程圖的。計算機是無法識別流程圖的。只有只有用計算機語言編寫的程序才能被計算機執(zhí)行。因此在用流程圖用計算機語言編寫的程序才能被計算機執(zhí)行。因此在用流程圖描述出一個算法后，還要將它轉(zhuǎn)換成計算機語言程序。描述出一個算法后，還要將它轉(zhuǎn)換成計算機語言程序。 o程序設(shè)計語言n特點：特點：用計算機語言表示算法必須嚴格遵循所用的語言的語法用計算機語言表示算法必須嚴格遵循所用的語言的語法規(guī)則。規(guī)則。提供了一種表達數(shù)據(jù)與處理數(shù)據(jù)的功能提供了一種表達數(shù)據(jù)與處理

23、數(shù)據(jù)的功能程序的執(zhí)行過程實際上是對程序所表達的數(shù)據(jù)進行處理的程序的執(zhí)行過程實際上是對程序所表達的數(shù)據(jù)進行處理的過程。過程。359種控制語句：if( )elsefor( )while( )dowhile( )continuebreakswitchgotoreturn數(shù)據(jù)類型基本類型構(gòu)造類型指針類型空類型void自定義類型typedef數(shù)值類型字符類型char枚舉類型enum整 型浮點型單精度型float雙精度型double短整型short長整型long整型int數(shù)組結(jié)構(gòu)體struct共用體union34種運算符：算術(shù)運算符：+ - * / % + -關(guān)系運算符： = !=邏輯運算符：！ & |位

24、運算符 ： | &賦值運算符：= 及其擴展條件運算符：?:逗號運算符：,指針運算符：* &求字節(jié)數(shù) ：sizeof強制類型轉(zhuǎn)換：(類型）分量運算符：. -下標運算符：其它 ：( ) -32個關(guān)鍵字：(auto break case char constcontinue default do double elseenum extern float for gotoif int long register returnshort signed sizeof static structswitch typedef unsigned union voidvolatile while2.4 計算機算法

25、的表示362.4 計算機算法的表示例例 將例將例2.1表示的算法（求表示的算法（求5!） 用用C語言表示。語言表示。#include void main( ) int i,t; t=1; i=2; do t=t*i; i=i+1; while (i=5) printf(%dn,t); 變量定義循環(huán)結(jié)構(gòu)輸出語句應(yīng)當強調(diào)說明：應(yīng)當強調(diào)說明：寫出了寫出了C程序，仍然只是程序，仍然只是描述了算法，并未實現(xiàn)算法。只有運行程描述了算法，并未實現(xiàn)算法。只有運行程序才是實現(xiàn)算法。應(yīng)該說，用計算機語言序才是實現(xiàn)算法。應(yīng)該說，用計算機語言表示的算法是計算機能夠執(zhí)行的算法。表示的算法是計算機能夠執(zhí)行的算法。37 2

26、.5 結(jié)構(gòu)化程序設(shè)計方法o 一個結(jié)構(gòu)化程序一個結(jié)構(gòu)化程序 就是用高級語言表示的結(jié)構(gòu)化算法。用就是用高級語言表示的結(jié)構(gòu)化算法。用三種基本結(jié)構(gòu)組成的程序必然是結(jié)構(gòu)化的程序，這種程三種基本結(jié)構(gòu)組成的程序必然是結(jié)構(gòu)化的程序，這種程序便于編寫、便于閱讀、便于修改和維護。序便于編寫、便于閱讀、便于修改和維護。o 結(jié)構(gòu)化程序設(shè)計強調(diào)程序設(shè)計風格和程序結(jié)構(gòu)的規(guī)范化，結(jié)構(gòu)化程序設(shè)計強調(diào)程序設(shè)計風格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)。提倡清晰的結(jié)構(gòu)。o 結(jié)構(gòu)化程序設(shè)計方法的基本思路是：把一個復(fù)雜問題的結(jié)構(gòu)化程序設(shè)計方法的基本思路是：把一個復(fù)雜問題的求解過程求解過程 分階段進行，每個階段處理的問題都控制在人分階段進行，每個階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。 38采取以下方法來保證得到結(jié)構(gòu)化的程序：采取以下方法來保證得到結(jié)構(gòu)化的程序：o自頂向下；自頂向下；o逐步細化；逐步細化；o模塊化設(shè)計；模塊化設(shè)計；o結(jié)構(gòu)化編碼。結(jié)構(gòu)化編碼。兩種