第2章程序的靈魂算法ppt課件

1、C 程 序 設(shè) 計(jì)陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院魯 來(lái) 鳳1第二章 程序的靈魂算法一個(gè)程序應(yīng)包括兩個(gè)方面的內(nèi)容:對(duì)數(shù)據(jù)的描畫：數(shù)據(jù)構(gòu)造(data structure)對(duì)操作的描畫：算法(algorithm)著名計(jì)算機(jī)科學(xué)家沃思提出一個(gè)公式:數(shù)據(jù)構(gòu)造 + 算法 = 程序 2算法的概念 算法的表示構(gòu)造化程序設(shè)計(jì)方法 數(shù)據(jù)構(gòu)造算法程序設(shè)計(jì)方法言語(yǔ)工具完好的程序設(shè)計(jì)應(yīng)該是:3一、算法的概念二、簡(jiǎn)單算法舉例三、算法的特性四、算法的表示五、構(gòu)造化程序設(shè)計(jì)方法 第二章 程序的靈魂算法4一、算法的概念 廣義地說(shuō)，為處理一個(gè)問(wèn)題而采取的方法和步驟，就稱為“算法。方法1：1+2，+3，+4，不斷加到100 加9

2、9次方法2：100+(1+99)+(2+98)+(49 +51)+50 = 100 + 49100 +50 加51次對(duì)同一個(gè)問(wèn)題，可有不同的解題方法和步驟例： 求5 為了有效地進(jìn)展解題，不僅需求保證算法正確，還要思索算法的質(zhì)量，選擇適宜的算法。希望方法簡(jiǎn)單，運(yùn)算步驟少。計(jì)算機(jī)算法可分為兩大類別：數(shù)值運(yùn)算算法：求數(shù)值解，例如求方程的根、求函數(shù)的定積分等。非數(shù)值運(yùn)算：包括的面非常廣泛，最常見(jiàn)的是用于事務(wù)管理領(lǐng)域，例如圖書(shū)檢索、人事管理、行車調(diào)度管理等。6 二、簡(jiǎn)單算法舉例例2.1: 求12345 步驟1：先求12，得到結(jié)果2步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6步驟3：將6再乘以4，得2

3、4步驟4：將24再乘以5，得120太繁瑣假設(shè)要求121000，那么要寫999個(gè)步驟7 S1：使p=1。 S2：使i=2。 S3：使pi，乘積仍放在變量p中，可表示為：pip S4：使i的值加1，即i+1i。 S5：假設(shè)i不大于5，前往重新執(zhí)行步驟S3以及其后的步驟S4和S5；否那么，算法終了。最后得到p的值就是5!的值。可以設(shè)兩個(gè)變量：一個(gè)變量代表被乘數(shù)，一個(gè)變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。設(shè)p為被乘數(shù)，i為乘數(shù)。用循環(huán)算法來(lái)求結(jié)果, 算法可改寫： 8S1：1pS2：3 iS3：pi pS4：i+2 iS5：假設(shè)i11，前往S3。否那么，終了。 假

4、設(shè)標(biāo)題改為：求1351000算法只需作很少的改動(dòng)：算法簡(jiǎn)練9 用這種方法表示的算法具有通用性、靈敏性。S3到S5組成一個(gè)循環(huán)，在實(shí)現(xiàn)算法時(shí) 要反復(fù)多次執(zhí)行S3，S4，S5等步驟，直到某一時(shí)辰，執(zhí)行S5步驟時(shí)經(jīng)過(guò)判別，乘數(shù)i已超越規(guī)定的數(shù)值而不前往S3步驟為止。此時(shí)算法終了，變量p的值就是所求結(jié)果。10例2.2 有50個(gè)學(xué)生，要求將他們之中成果在80分以上者打印出來(lái)。設(shè)n表示學(xué)號(hào)， n1代表第一個(gè)學(xué)生學(xué)號(hào)， 代表第i個(gè)學(xué)生學(xué)號(hào)。用G代表學(xué)生成果 ， gi代表第i個(gè)學(xué)生成果，算法表示如下: S1：1 i S2：假設(shè)80，那么打印和，否那么不打印。 S3：i+1 i S4：假設(shè)i50，前往S2，繼續(xù)

5、執(zhí)行。否那么算法終了 變量i作為下標(biāo)，用來(lái)控制序號(hào)(第幾個(gè)學(xué)生，第幾個(gè)成果)。當(dāng)i超越50時(shí)，表示 已對(duì)50個(gè)學(xué)生的成果處置終了，算法終了。11例2.3 斷定20002500年中的每一年能否閏年，將結(jié)果輸出。 變量i作為下標(biāo)，用來(lái)控制序號(hào)(第幾個(gè)學(xué)生，第幾個(gè)成果)。當(dāng)i超越50時(shí)，表示 已對(duì)50個(gè)學(xué)生的成果處置終了，算法終了。分析：閏年的條件是：(1)能被4整除，但不能被100整除的年份都是閏年，如1996,2004年是閏年；(2)能被100整除，又能被400整除的年份是閏年。如1600,2000年是閏年。不符合這兩個(gè)條件的年份不是閏年。 12設(shè)y為被檢測(cè)的年份，算法可表示如下 ：S1：200

6、0 yS2：假設(shè)y不能被4整除，那么輸出y “不是閏年。然后轉(zhuǎn)到S6。S3：假設(shè)y能被4整除，不能被100整除，那么輸出y “是閏年。然后轉(zhuǎn)到S6。S4：假設(shè)y能被100整除，又能被400整除，輸出y“是閏年，否那么輸出“不是閏年。 然后轉(zhuǎn)到S6。S5: 輸出y “不是閏年。S6：y+1 yS7：當(dāng)y2500時(shí)，轉(zhuǎn)S2繼續(xù)執(zhí)行，如y2500，算法停頓。13 以上算法中每做一步都分別分別出一些范圍(巳能斷定為閏年或非閏年)，逐漸減少范圍，直至執(zhí)行S5時(shí)，只能夠是非閏年。“其它 包括能被4整除，又能被100整除，而不能被400整除的那些年份(如1990) 是非閏年。14例2.4 求算法如下 ： S

7、1：sign=1 S2：sum=1 S3：deno=2 S4：sign=(-1)sign S5：term=sign(1/deno) S6：sum=sum+term S7：deno=deno+1 S8：假設(shè)deno100前往S4，否那么算法終了。單詞作變量名，以使算法更易于了解：sum表示累加和，deno是英文分母denom inator縮寫，sign代表數(shù)值的符號(hào)，term代表某一項(xiàng)。 反復(fù)執(zhí)行S4到S8步驟，直到分母大于100為止。一共執(zhí)行了99次循環(huán)，向sum累參與了99個(gè)分?jǐn)?shù)。sum最后的值就是多項(xiàng)式的值。 15 例2.5 對(duì)一個(gè)大于或等于3的正整數(shù)，判別它是不是一個(gè)素?cái)?shù)。 概念：所謂素

8、數(shù)，是指除了1和該數(shù)本身之外，不能被其它任何整數(shù)整除的數(shù)。例如，13是素?cái)?shù)。由于它不能被2，3，4，12整除。分析：判別一個(gè)數(shù)n(n3)能否素?cái)?shù)的方法： 將n作為被除數(shù)，將2到(n-1)各個(gè)整數(shù)輪番作為除數(shù)，假設(shè)都不能被整除，那么n為素?cái)?shù)。 16算法如下 ：S1：輸入n的值S2：i=2 i作為除數(shù)S3：n被i除，得余數(shù)rS4：假設(shè)r=0，表示n能被i整除，那么打印n“不是素?cái)?shù)，算法終了。否那么執(zhí)行S5S5：i+1iS6：假設(shè)in-1，前往S3。否那么打印 n “是素?cái)?shù)。然后終了。 實(shí)踐上，n不用被2到(n-1)的整數(shù)除，只需被2到n/2間整數(shù)除，甚至只需被2到 之間的整數(shù)除即可。17三、算法的

9、特性有窮性：包含有限的操作步驟。確定性：算法中的每一個(gè)步驟都該當(dāng)是確定的。 有零個(gè)或多個(gè)輸入：輸入是指在執(zhí)行算法時(shí)需求從外界獲得必要的信息。有一個(gè)或多個(gè)輸出：算法的目的是為了求解，“解 就是輸出。 有效性：算法中的每一個(gè)步驟都該當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果 。一個(gè)算法應(yīng)該具有以下特點(diǎn)：18 四、算法的表示可以用不同的方法表示算法，常用的有：自然言語(yǔ)傳統(tǒng)流程圖構(gòu)造化流程圖偽代碼PAD圖19 2.4.1 用自然言語(yǔ)表示算法 自然言語(yǔ)就是人們?nèi)粘＿\(yùn)用的言語(yǔ)，可以是漢語(yǔ)或英語(yǔ)或其它言語(yǔ)。用自然言語(yǔ)表示通俗易懂，但文字冗長(zhǎng)，容易出現(xiàn)“歧義性。自然言語(yǔ)表示的含義往往不大嚴(yán)厲，要根據(jù)上下文才干判別其正確

10、含義，描畫包含分支和循環(huán)的算法時(shí)也不很方便。因此，除了那些很簡(jiǎn)單的問(wèn)題外，普通不用自然言語(yǔ)描畫算法。 20 2.4.2 用流程圖表示算法美國(guó)國(guó)家規(guī)范化協(xié)會(huì)ANSI(American National Standard Institute)規(guī)定了一些常用的流程圖符號(hào)：起止框判別框處置框輸入/輸出框注釋框流向線銜接點(diǎn)21例2.6 將求5!的算法用流程圖表示假設(shè)需求將最后結(jié)果打印出來(lái)，可在菱形框的下面加一個(gè)輸出框。 22 例2.7 將例2.2的算法用流程圖表示。打印50名 學(xué)生中成果在80分以上者的學(xué)號(hào)和成果。23假設(shè)假設(shè)包括這個(gè)輸入數(shù)據(jù)的部分，流程圖為24 例2.8 將例2.3斷定閏年的算法用流程

11、圖表示 用流程圖表示算法要比用文字描畫算法邏輯明晰、易于了解。 25 例2.9 將例2.4的算法用流程圖表示 26 例2.10 將例2.5判別素?cái)?shù)的算法用流程圖表示 27小結(jié)：流程圖是表示算法的較好的工具。一個(gè)流程圖包括以下幾部分 ：(1)表示相應(yīng)操作的框；(2)帶箭頭的流程線；(3)框內(nèi)外必要的文字闡明。 28 2.4.3 三種根本構(gòu)造和改良的流程圖1.傳統(tǒng)流程圖的弊端 傳統(tǒng)流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的運(yùn)用沒(méi)有嚴(yán)厲限制。因此，運(yùn)用者可以毫不受限制地使流程隨意地轉(zhuǎn)向，使流程圖變得毫無(wú)規(guī)律，閱讀者要花很大精神去追蹤流程，使人難以了解算法的邏輯。如圖：29傳統(tǒng)流程圖的流程可以是：

12、這種好像亂麻一樣的算法稱為BS型算法，意為一碗面條(A Bowl of Spaghetti)，亂無(wú)頭緒。缺陷：難以閱讀、修正，使算法的可靠性和可維護(hù)性難以保證。處理方法：必需限制箭頭的濫用，即不允許無(wú)規(guī)律地使流程隨意轉(zhuǎn)向，只能順序地進(jìn)展下去。 302.三種根本構(gòu)造 Bohra和Jacopini提出了以下三種根本構(gòu)造： 順序構(gòu)造、選擇構(gòu)造、循環(huán)構(gòu)造 用這三種根本構(gòu)造作為表示一個(gè)良好算法的根本單元。31三種根本構(gòu)造的圖示： 順序構(gòu)造選擇構(gòu)造32循環(huán)構(gòu)造的圖示： 當(dāng)型(While型)循環(huán)構(gòu)造 直到型(Until型)循環(huán) 33三種根本構(gòu)造的共同特點(diǎn)：(1)只需一個(gè)入口。 (2)只需一個(gè)出口。請(qǐng)留意：一

13、個(gè)菱形判別框有兩個(gè)出口，而一個(gè)選擇構(gòu)造只需一個(gè)出口。不要將菱形框的出口和選擇構(gòu)造的出口混淆。(3)構(gòu)造內(nèi)的每一部分都有時(shí)機(jī)被執(zhí)行到。(4)構(gòu)造內(nèi)不存在“死循環(huán)(無(wú)終止的循環(huán))。 34 圖中沒(méi)有一條從入口到出口的途徑經(jīng)過(guò)A框不正確的流程表示：流程內(nèi)的死循環(huán)35小結(jié)：由三種根本構(gòu)造順序組成的算法構(gòu)造，可以處理任何復(fù)雜的問(wèn)題。由根本構(gòu)造所構(gòu)成的算法屬于“構(gòu)造化的算法，它不存在無(wú)規(guī)律的轉(zhuǎn)向，只在本根本構(gòu)造內(nèi)才允許存在分支和向前或向后的跳轉(zhuǎn)。36擴(kuò)展：只需具有上述四個(gè)特點(diǎn)的都可以作為根本構(gòu)造?？梢员救硕x根本構(gòu)造，并由這些根本構(gòu)造組成構(gòu)造化程序。此圖符合根本構(gòu)造的特點(diǎn)37 這是一個(gè)多分支選擇構(gòu)造，根據(jù)表

14、達(dá)式的值決議執(zhí)行道路。虛線框內(nèi)的構(gòu)造是一個(gè)入口一個(gè)出口，并且有上述全部的四個(gè)特點(diǎn)。由此構(gòu)成的算法構(gòu)造也是構(gòu)造化的算法。可以以為這是由三種根本構(gòu)造所派生出來(lái)的。38 2.4.4 用N-S流程圖表示算法 1973年美國(guó)學(xué)者I.Nassi和B.Shneiderman提出了一種新的流程圖方式。在這種流程圖中，完全去掉了帶箭頭的流程線。全部算法寫在一個(gè)矩形框內(nèi)，在該框內(nèi)還可以包含其它的從屬于它的框，或者說(shuō)，由一些根本的框組成一個(gè)大的框。這種流程圖又稱N-S構(gòu)造化流程圖。39 N-S流程圖用以下的流程圖符號(hào)： (1)順序構(gòu)造(2)選擇構(gòu)造(3)循環(huán)構(gòu)造40 用三種N-S流程圖中的根本框，可以組成復(fù)雜的N-

15、S流程圖。圖中的A框或B框，可以是一個(gè)簡(jiǎn)單的操作，也可以是三個(gè)根本構(gòu)造之一。 A框可以是一個(gè)選擇構(gòu)造 B框可以是一個(gè)循環(huán)構(gòu)造 41例2.11 將例2.1的求5!算法用N-S圖表示42例2.12 將例2.2的算法用N-S圖表示。打印50名學(xué)生中成果高于80分的學(xué)號(hào)和成果沒(méi)有輸入數(shù)據(jù)43例2.12 將例2.2的算法用N-S圖表示。打印50名學(xué)生中成果高于80分的學(xué)號(hào)和成果有輸入數(shù)據(jù)44例2.13 將例2.3斷定閏年的算法用N-S圖表示45例2.14 將例2.4的算法用N-S圖表示46例2.15 將例2.5判別素?cái)?shù)的算法用N-S流程圖表示。傳統(tǒng)流程圖分析：出口1出口2此圖不符合根本構(gòu)造特點(diǎn)！由于不能

16、分解為三種根本構(gòu)造，就無(wú)法直接用N-S流程圖的三種根本構(gòu)造的符號(hào)來(lái)表示。因此，應(yīng)領(lǐng)先作必要的變換。47例2.15 將例2.5判別素?cái)?shù)的算法用N-S流程圖表示。傳統(tǒng)流程圖變換為：一個(gè)出口48用N-S流程圖表示：49N-S圖表示算法的優(yōu)點(diǎn)比文字描畫直觀、籠統(tǒng)、 易于了解；比傳統(tǒng)流程圖緊湊易畫。尤其是它廢除了流程線，整個(gè)算法構(gòu)造是由各個(gè)根本構(gòu)造按順序組成的，N-S流程圖中的上下順序就是執(zhí)行時(shí)的順序。用N-S圖表示的算法都是構(gòu)造化的算法，由于它不能夠出現(xiàn)流程無(wú)規(guī)律的跳轉(zhuǎn)，而只能自上而下地順序執(zhí)行。50小結(jié)：一個(gè)構(gòu)造化的算法是由一些根本構(gòu)造順序組成的。在根本構(gòu)造之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存

17、在于一個(gè)根本構(gòu)造范圍之內(nèi)(如循環(huán)中流程的跳轉(zhuǎn))；一 個(gè)非構(gòu)造化的算法可以用一個(gè)等價(jià)的構(gòu)造化算法替代，其功能不變 。假設(shè)一個(gè)算法不能分解為假設(shè)干個(gè)根本構(gòu)造，那么它必然不是一個(gè)構(gòu)造化的算法。51 2.4.5 用位代碼表示算法概念：偽代碼是用介于自然言語(yǔ)和計(jì)算機(jī)言語(yǔ)之間的文字和符號(hào)來(lái)描畫算法。特點(diǎn)：它好像一篇文章一樣 ，自上而下地寫下來(lái)。每一行(或幾行)表示一個(gè)根本操作。它不用圖形符號(hào)，因此書(shū)寫方便 、格式緊湊，也比較好懂，也便于向計(jì)算機(jī)言語(yǔ)算法(即程序)過(guò)渡。用途：適用于設(shè)計(jì)過(guò)程中需求反復(fù)修正時(shí)的流程描畫。52 IF x is positive THEN print x ELSE print -x

18、也可以用漢字偽代碼表示： 假設(shè) x為正 打印 x 否那么 打印 -x也可以中英文混用，如： IF x 為正 print x ELSE print -x例： “打印x的絕對(duì)值的算法可以用偽代碼表示為：53開(kāi)場(chǎng) 置t的初值為1 置i的初值為2 當(dāng)i=5，執(zhí)行下面操作： 使t=ti 使i=i+1 循環(huán)體到此終了 輸出t的值 終了也可以寫成以下方式： BEGIN算法開(kāi)場(chǎng) 1t 2 i while i5 ti t i+1 i print t END算法終了例2.16 求5!。用偽代碼表示算法：54例2.17 輸出50個(gè)學(xué)生中成果高于80分者的學(xué)號(hào)和成果。用偽代碼表示算法：BEGIN算法開(kāi)場(chǎng) 1 i wh

19、ile i50 input ni and gi i+1 i 1 i while i50 if gi80 print ni and gi i+1 i END算法終了55 2.4.6 用計(jì)算機(jī)言語(yǔ)表示算法概念：用計(jì)算機(jī)實(shí)現(xiàn)算法。計(jì)算機(jī)是無(wú)法識(shí)別流程圖和偽代碼的。只需用計(jì)算機(jī)言語(yǔ)編寫的程序才干被計(jì)算機(jī)執(zhí)行。因此在用流程圖或偽代碼描畫出一個(gè)算法后，還要將它轉(zhuǎn)換成計(jì)算機(jī)言語(yǔ)程序。 特點(diǎn)：用計(jì)算機(jī)言語(yǔ)表示算法必需嚴(yán)厲遵照所用的言語(yǔ)的語(yǔ)法規(guī)那么，這是和偽代碼不同的。用途：要完成一件任務(wù)，包括設(shè)計(jì)算法和實(shí)現(xiàn)算法兩個(gè)部分。設(shè)計(jì)算法的目的是為了實(shí)現(xiàn)算法。56#include void main( ) int i,t; t=1; i=2; while(i=5) t=t*i; i=i+1; printf(%dn,t); 例 2.20 將例2.16表示的算法求5!用C言語(yǔ)表示。57該當(dāng)強(qiáng)調(diào)闡明：寫出了C程序，依然只是描畫了算法，并未實(shí)現(xiàn)算法。只需運(yùn)轉(zhuǎn)程序才是