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

1、一個程序主要包括以下兩方面的信息：一個程序主要包括以下兩方面的信息：(1) 對數(shù)據(jù)的描畫。在程序中要指定用對數(shù)據(jù)的描畫。在程序中要指定用到哪些數(shù)據(jù)以及這些數(shù)據(jù)的類型和數(shù)據(jù)到哪些數(shù)據(jù)以及這些數(shù)據(jù)的類型和數(shù)據(jù)的組織方式的組織方式這就是數(shù)據(jù)構(gòu)造這就是數(shù)據(jù)構(gòu)造(data structure)(2) 對操作的描畫。即要求計算機進展對操作的描畫。即要求計算機進展操作的步驟操作的步驟也就是算法也就是算法(algorithm)數(shù)據(jù)是操作的對象數(shù)據(jù)是操作的對象操作的目的是對數(shù)據(jù)進展加工處置，以操作的目的是對數(shù)據(jù)進展加工處置，以得到期望的結(jié)果得到期望的結(jié)果著名計算機科學家沃思著名計算機科學家沃思(Nikiklau

2、s Wirth)提出一個公式：提出一個公式： 算法算法 + 數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造 = 程序程序一個程序除了算法和數(shù)據(jù)構(gòu)造這主要要一個程序除了算法和數(shù)據(jù)構(gòu)造這主要要素外，還該當采用構(gòu)造化程序設(shè)計方法素外，還該當采用構(gòu)造化程序設(shè)計方法進展程序設(shè)計，并且用某一種計算機言進展程序設(shè)計，并且用某一種計算機言語表示語表示算法、數(shù)據(jù)構(gòu)造、程序設(shè)計方法和言語算法、數(shù)據(jù)構(gòu)造、程序設(shè)計方法和言語工具是一個程序設(shè)計人員應(yīng)具備的知識工具是一個程序設(shè)計人員應(yīng)具備的知識算法是處理算法是處理“做什么和做什么和“怎樣做的問怎樣做的問題題程序中的操作語句，是算法的表達程序中的操作語句，是算法的表達不了解算法就談不上程序設(shè)計不了解算

3、法就談不上程序設(shè)計2.1 什么是算法什么是算法2.2 簡單的算法舉例簡單的算法舉例2.3 算法的特性算法的特性2.4 怎樣表示一個算法怎樣表示一個算法2.5 構(gòu)造化程序設(shè)計方法構(gòu)造化程序設(shè)計方法廣義地說，為處理一個問題而采取的方廣義地說，為處理一個問題而采取的方法和步驟，就稱為法和步驟，就稱為“算法算法對同一個問題，可以有不同的解題方法對同一個問題，可以有不同的解題方法和步驟和步驟為了有效地進展解題，不僅需求保證算為了有效地進展解題，不僅需求保證算法正確，還要思索算法的質(zhì)量，選擇適法正確，還要思索算法的質(zhì)量，選擇適宜的算法宜的算法計算機算法可分為兩大類別：計算機算法可分為兩大類別：數(shù)值運算算法

4、數(shù)值運算算法非數(shù)值運算算法非數(shù)值運算算法數(shù)值運算的目的是求數(shù)值解數(shù)值運算的目的是求數(shù)值解非數(shù)值運算包括的面非常廣泛，最常見非數(shù)值運算包括的面非常廣泛，最常見的是用于事務(wù)管理領(lǐng)域的是用于事務(wù)管理領(lǐng)域例例2.1 求求12345可以用最原始的方法進展：可以用最原始的方法進展：步驟步驟1：先求：先求1*2，得到結(jié)果，得到結(jié)果2。步驟步驟2：將步驟：將步驟1得到的乘積得到的乘積2再乘以再乘以3，得到結(jié)果得到結(jié)果6。步驟步驟3：將：將6再乘以再乘以4，得，得24。步驟步驟4：將：將24再乘以再乘以5，得，得120。這就是。這就是最后的結(jié)果。最后的結(jié)果。例例2.1 求求12345 1000太繁瑣太繁瑣改良的

5、算法：改良的算法：設(shè)變量設(shè)變量p為被乘數(shù)為被乘數(shù)變量變量i為乘數(shù)為乘數(shù)用循環(huán)算法求結(jié)果用循環(huán)算法求結(jié)果S1：使：使p=1，或?qū)懗?，或?qū)懗?pS2：使：使i=2，或?qū)懗?，或?qū)懗?iS3：使：使p與與i相乘，乘積仍放在變量相乘，乘積仍放在變量p中，可表中，可表示為：示為：p*ipS4：使：使i的值加的值加1，即，即i+1 iS5：假設(shè)：假設(shè)i不大于不大于5，前往重新執(zhí)行，前往重新執(zhí)行S3；否那；否那么，算法終了么，算法終了最后得到最后得到p的值就是的值就是 5!的值的值假設(shè)是假設(shè)是1000，求什么？，求什么？S1：使：使p=1，或?qū)懗?，或?qū)懗?pS2：使：使i=2，或?qū)懗桑驅(qū)懗?iS3：使：使p

6、與與i相乘，乘積仍放在變量相乘，乘積仍放在變量p中，可表中，可表示為：示為：p*ipS4：使：使i的值加的值加1，即，即i+1 iS5：假設(shè)：假設(shè)i不大于不大于5，前往重新執(zhí)行，前往重新執(zhí)行S3；否那；否那么，算法終了么，算法終了最后得到最后得到p的值就是的值就是 5!的值的值假設(shè)求假設(shè)求135791133221111相當于相當于i 11 例例2.2 有有50個學生，要求將成果在個學生，要求將成果在80分分以上的學生的學號和成果輸出。以上的學生的學號和成果輸出。用用ni代表第代表第i個學生學號，個學生學號，gi表示第表示第i個學生個學生成果成果S1：1iS2：假設(shè)：假設(shè)gi80， 那么輸出那么

7、輸出ni和和gi，否那么不輸出，否那么不輸出S3：i+1iS4：假設(shè)：假設(shè)i50，前往到步驟，前往到步驟S2，繼續(xù)執(zhí)行，繼續(xù)執(zhí)行，否那么，算法終了，否那么，算法終了 例例2.3 斷定斷定20002500年中的每一年能年中的每一年能否閏年，并將結(jié)果輸出。否閏年，并將結(jié)果輸出。閏年的條件：閏年的條件： (1)能被能被4整除，但不能被整除，但不能被100整除的年份整除的年份都是閏年，如都是閏年，如2019、2019、2048年年 (2)能被能被400整除的年份是閏年，如整除的年份是閏年，如2000年年不符合這兩個條件的年份不是閏年不符合這兩個條件的年份不是閏年例如例如2021、2100年年設(shè)設(shè)yea

8、r為被檢測的年份。算法表示如下：為被檢測的年份。算法表示如下：S1：2000yearS2：假設(shè)：假設(shè)year不能被不能被4整除，那么輸出整除，那么輸出year 的值和的值和“不是閏年。然后轉(zhuǎn)到不是閏年。然后轉(zhuǎn)到S6S3：假設(shè)：假設(shè)year能被能被4整除，不能被整除，不能被100整除，整除，那么輸出那么輸出year的值和的值和“是閏年。然后轉(zhuǎn)到是閏年。然后轉(zhuǎn)到S6S4：假設(shè)：假設(shè)year能被能被400整除，那么輸出整除，那么輸出year的值和的值和“是閏年是閏年 ，然后轉(zhuǎn)到，然后轉(zhuǎn)到S6S5: 其他情況輸出其他情況輸出year的值和的值和“不是閏年不是閏年S6：year+1yearS7：當：當y

9、ear2500時，轉(zhuǎn)時，轉(zhuǎn)S2，否那么停頓，否那么停頓year不能不能被被4整除整除非閏年非閏年year被被4整整除，但不能除，但不能被被100整除整除閏年閏年year被被100整除，又能整除，又能被被400整除整除閏年閏年其他其他非閏年非閏年逐漸減少判逐漸減少判別的范圍別的范圍例例2.4 求求規(guī)律：規(guī)律：第第1項的分子分母都是項的分子分母都是1 第第2項的分母是項的分母是2，以后每一項的分母子，以后每一項的分母子都是前一項的分母加都是前一項的分母加1 笫笫2項前的運算符為項前的運算符為“-，后一項前面的，后一項前面的運算符都與前一項前的運算符相反運算符都與前一項前的運算符相反10019914

10、131211例例2.4 求求S1：sign=1S2：sum=1S3：deno=2S4：sign=(-1)*signS5：term=sign*(1/deno)S6：sum=sum+termS7：deno=deno+1S8：假設(shè)：假設(shè)deno100前往前往S4；否那么算；否那么算法終了法終了10019914131211sign當前項符號當前項符號term當前項的值當前項的值sum當前各項的和當前各項的和deno當前項分母當前項分母-1-1/21-1/23滿足，前往滿足，前往S4例例2.4 求求S1：sign=1S2：sum=1S3：deno=2S4：sign=(-1)*signS5：term=si

11、gn*(1/deno)S6：sum=sum+termS7：deno=deno+1S8：假設(shè)：假設(shè)deno100前往前往S4；否那么算；否那么算法終了法終了10019914131211sign當前項符號當前項符號term當前項的值當前項的值sum當前各項的和當前各項的和deno當前項分母當前項分母11/31-1/2+1/34滿足，前往滿足，前往S4例例2.4 求求S1：sign=1S2：sum=1S3：deno=2S4：sign=(-1)*signS5：term=sign*(1/deno)S6：sum=sum+termS7：deno=deno+1S8：假設(shè)：假設(shè)deno100前往前往S4；否那么

12、算；否那么算法終了法終了1001991413121199次循環(huán)后次循環(huán)后sum的值的值就是所要求的結(jié)果就是所要求的結(jié)果 例例2.5 給出一個大于或等于給出一個大于或等于3的正整數(shù)，判的正整數(shù)，判別它是不是一個素數(shù)。別它是不是一個素數(shù)。所謂素數(shù)所謂素數(shù)(prime)，是指除了，是指除了1和該數(shù)本身和該數(shù)本身之外，不能被其他任何整數(shù)整除的數(shù)之外，不能被其他任何整數(shù)整除的數(shù)例如，例如，13是素數(shù)，由于它不能被是素數(shù)，由于它不能被2，3，4，12整除。整除。判別一個數(shù)判別一個數(shù)n(n3)能否素數(shù)：將能否素數(shù)：將n作為作為被除數(shù)，將被除數(shù)，將2到到(n-1)各個整數(shù)先后作為各個整數(shù)先后作為除數(shù)，假設(shè)都不

13、能被整除，那么除數(shù)，假設(shè)都不能被整除，那么n為素數(shù)為素數(shù)S1：輸入：輸入n的值的值S2：i=2 i作為除數(shù)作為除數(shù)S3：n被被i除，得余數(shù)除，得余數(shù)rS4：假設(shè)：假設(shè)r=0，表示，表示n能被能被i整除，那么輸整除，那么輸出出n“不是素數(shù)，算法終了；否那么執(zhí)行不是素數(shù)，算法終了；否那么執(zhí)行S5S5：i+1iS6：假設(shè)：假設(shè)in-1，前往，前往S3；否那么輸出；否那么輸出n “是素數(shù)，然后終了。是素數(shù)，然后終了?？筛臑榭筛臑閚/2n一個有效算法應(yīng)該具有以下特點：一個有效算法應(yīng)該具有以下特點：(1) 有窮性。一個算法應(yīng)包含有限的有窮性。一個算法應(yīng)包含有限的操作步驟，而不能是無限的。操作步驟，而不能是

14、無限的。(2) 確定性。算法中的每一個步驟都確定性。算法中的每一個步驟都該當是確定的，而不該當是模糊的、該當是確定的，而不該當是模糊的、模棱兩可的。模棱兩可的。一個有效算法應(yīng)該具有以下特點：一個有效算法應(yīng)該具有以下特點：(3) 有零個或多個輸入。所謂輸入是有零個或多個輸入。所謂輸入是指在執(zhí)行算法時需求從外界獲得必要的指在執(zhí)行算法時需求從外界獲得必要的信息。信息。(4) 有一個或多個輸出。算法的目的有一個或多個輸出。算法的目的是為了求解，是為了求解，“解解 就是輸出。就是輸出。沒有輸出的算法是沒有意義的。沒有輸出的算法是沒有意義的。(5) 有效性。算法中的每一個步驟都有效性。算法中的每一個步驟都

15、該當能有效地執(zhí)行，并得到確定的結(jié)果該當能有效地執(zhí)行，并得到確定的結(jié)果。對于普通最終用戶來說對于普通最終用戶來說:他們并不需求在處置每一個問題時都要他們并不需求在處置每一個問題時都要本人設(shè)計算法和編寫程序本人設(shè)計算法和編寫程序可以運用他人已設(shè)計好的現(xiàn)成算法和程可以運用他人已設(shè)計好的現(xiàn)成算法和程序序只需根據(jù)知算法的要求給予必要的輸入只需根據(jù)知算法的要求給予必要的輸入，就能得到輸出的結(jié)果，就能得到輸出的結(jié)果輸入輸入3個數(shù)個數(shù)黑箱子黑箱子3個數(shù)中最大數(shù)個數(shù)中最大數(shù)求求3個數(shù)的個數(shù)的最大數(shù)最大數(shù)常用的方法有：常用的方法有：自然言語自然言語傳統(tǒng)流程圖傳統(tǒng)流程圖構(gòu)造化流程圖構(gòu)造化流程圖偽代碼偽代碼2.4.1

16、 用自然言語表示算法用自然言語表示算法2.4.2 用流程圖表示算法用流程圖表示算法2.4.3 三種根本構(gòu)造和改良的流程圖三種根本構(gòu)造和改良的流程圖2.4.4 用用N-S流程圖表示算法流程圖表示算法2.4.5 用偽代碼表示算法用偽代碼表示算法2.4.6 用計算機言語表示算法用計算機言語表示算法2.2節(jié)引見的算法是用自然言語表示的節(jié)引見的算法是用自然言語表示的用自然言語表示通俗易懂，但文字冗長，容用自然言語表示通俗易懂，但文字冗長，容易出現(xiàn)歧義性易出現(xiàn)歧義性用自然言語描畫包含分支和循環(huán)的算法，不用自然言語描畫包含分支和循環(huán)的算法，不很方便很方便除了很簡單的問題外，普通不用自然言語除了很簡單的問題外

17、，普通不用自然言語流程圖是用一些圖框來表示各種操作流程圖是用一些圖框來表示各種操作用圖形表示算法，直觀籠統(tǒng)，易于了解用圖形表示算法，直觀籠統(tǒng)，易于了解起止框起止框輸入輸出框輸入輸出框處置框處置框判別框判別框流程線流程線銜接點銜接點注釋框注釋框x0YN一個入口一個入口兩個出口兩個出口流程圖是用一些圖框來表示各種操作流程圖是用一些圖框來表示各種操作用圖形表示算法，直觀籠統(tǒng)，易于了解用圖形表示算法，直觀籠統(tǒng)，易于了解起止框起止框輸入輸出框輸入輸出框處置框處置框判別框判別框流程線流程線銜接點銜接點注釋框注釋框位置不夠位置不夠防止交叉防止交叉 例例2.6 將例將例2.1的算的算法用流程圖表示。法用流程圖

18、表示。 求求12345假設(shè)需求將最后結(jié)果輸假設(shè)需求將最后結(jié)果輸出出:1ti5開場開場2it*iti+1i終了終了NY 例例2.6 將例將例2.1的算的算法用流程圖表示。法用流程圖表示。 求求12345假設(shè)需求將最后結(jié)果輸假設(shè)需求將最后結(jié)果輸出出:1t輸出輸出ti5開場開場2it*iti+1i終了終了NY 例例2.7 例例2.2的算法用流程圖表示。有的算法用流程圖表示。有50個學生，要求將成果在個學生，要求將成果在80分以上的學生的分以上的學生的學號和成果輸出。學號和成果輸出。1ii50開場開場i+1i終了終了NY輸入輸入ni、gi1i開場開場gi80輸出輸出ni、gii+1ii50NYYN假設(shè)

19、包括輸入數(shù)據(jù)部分假設(shè)包括輸入數(shù)據(jù)部分1ii50開場開場i+1i終了終了NY輸入輸入ni、gi1igi80輸出輸出ni、gii+1ii50NYYN假設(shè)包括輸入數(shù)據(jù)部分假設(shè)包括輸入數(shù)據(jù)部分 例例2.8 例例2.3斷定閏年的算法用流程圖表示斷定閏年的算法用流程圖表示。斷定。斷定20002500年中的每一年能否閏年中的每一年能否閏年，將結(jié)果輸出。年，將結(jié)果輸出。NYN開場開場2000yearyear不能不能被被4整除整除year是閏年是閏年year不能不能被被100整除整除year+1yearyear2500終了終了Yyear不能不能被被400整除整除year不是閏年不是閏年year是閏年是閏年yea

20、r不是閏年不是閏年YNYN例例2.9 將例將例2.4的算法用流程圖表示。求的算法用流程圖表示。求100199141312111sum2deno1sign(-1)*signsignsign*(1/deno)termsum+termsumdeno+1denoNdeno100Y輸出輸出sum終了終了開場開場 例例2.10 例例2.5判別素數(shù)的算法用流程圖表判別素數(shù)的算法用流程圖表示。對一個大于或等于示。對一個大于或等于3的正整數(shù)，判別它的正整數(shù)，判別它是不是一個素數(shù)。是不是一個素數(shù)。NY輸出輸出n是素數(shù)是素數(shù)終了終了開場開場輸入輸入n2in%irr=0i+1iin輸出輸出n是素數(shù)是素數(shù)YN經(jīng)過以上幾

21、個例子可以看出流程圖是表示經(jīng)過以上幾個例子可以看出流程圖是表示算法的較好的工具算法的較好的工具一個流程圖包括以下幾部分：一個流程圖包括以下幾部分：(1) 表示相應(yīng)操作的框表示相應(yīng)操作的框(2) 帶箭頭的流程線帶箭頭的流程線(3) 框內(nèi)外必要的文字闡明框內(nèi)外必要的文字闡明流程線不要忘記畫箭頭，否那么難以斷定流程線不要忘記畫箭頭，否那么難以斷定各框的執(zhí)行次序各框的執(zhí)行次序1.傳統(tǒng)流程圖的弊端傳統(tǒng)流程圖的弊端傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對流程線的運用沒有嚴厲限制，對流程線的運用沒有嚴厲限制運用者可以毫不受限制地使流程隨意地轉(zhuǎn)來運用者可以毫不受限制地使

22、流程隨意地轉(zhuǎn)來轉(zhuǎn)去，使人難以了解算法的邏輯轉(zhuǎn)去，使人難以了解算法的邏輯2.三種根本構(gòu)造三種根本構(gòu)造(1) 順序構(gòu)造順序構(gòu)造AB2.三種根本構(gòu)造三種根本構(gòu)造(2) 選擇構(gòu)造選擇構(gòu)造ABYpNAYpN2.三種根本構(gòu)造三種根本構(gòu)造(3) 循環(huán)構(gòu)造循環(huán)構(gòu)造 當型循環(huán)構(gòu)造當型循環(huán)構(gòu)造AYp1NYx51t輸出輸出t2it*iti+1i 例例2.12 將例將例2.2的的算法用算法用N-S圖表示圖表示。將。將50名學生中成名學生中成果高于果高于80分者的學分者的學號和成果輸出。號和成果輸出。直到直到i501t1ii+1i輸入輸入ni、gii+1i直到直到i50gi80否否是是輸出輸出ni,gi例例2.13 將

23、例將例2.3斷定閏年的算法用斷定閏年的算法用N-S圖表示圖表示直到直到y(tǒng)ear25002000yearyear+1year否否是是year%4為為0否否是是輸出輸出year非閏年非閏年year%100不為不為0year%400為為0是是否否輸出輸出year非閏年非閏年輸出輸出year閏年閏年輸出輸出year閏年閏年例例2.14 將例將例2.4的算法用的算法用N-S圖圖表示。求表示。求10019914131211直到直到deno100deno+1deno輸出輸出sum1sum1sign2deno(-1)*signsignsign*(1/deno)termsum+termsum 例例2.15 將例

24、將例2.5判別素數(shù)的算法用判別素數(shù)的算法用N-S流程圖表示。流程圖表示。例例2.10的流程圖不是由三種根本構(gòu)造組的流程圖不是由三種根本構(gòu)造組成的成的循環(huán)有兩個出口，不符合根本構(gòu)造的特點循環(huán)有兩個出口，不符合根本構(gòu)造的特點無法直接用無法直接用N-S流程圖的三種根本構(gòu)造的流程圖的三種根本構(gòu)造的符號來表示符號來表示先作必要的變換先作必要的變換NY開場開場輸入輸入n0w 2in%irr=0i+1ii 和和w=0nYN1w輸出輸出n是素數(shù)是素數(shù)終了終了w=0輸出輸出n不是素數(shù)不是素數(shù)輸入輸入nr=0是是否否0w2in%ir1wi+1i直到直到i 或或w 0nw=0是是否否輸出輸出n是素數(shù)是素數(shù)輸出輸出n

25、不是素數(shù)不是素數(shù)一個構(gòu)造化的算法是由一些根本構(gòu)造順序一個構(gòu)造化的算法是由一些根本構(gòu)造順序組成的組成的在根本構(gòu)造之間不存在向前或向后的跳轉(zhuǎn)在根本構(gòu)造之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個根本構(gòu)造范圍，流程的轉(zhuǎn)移只存在于一個根本構(gòu)造范圍之內(nèi)之內(nèi)一個非構(gòu)造化的算法可以用一個等價的構(gòu)一個非構(gòu)造化的算法可以用一個等價的構(gòu)造化算法替代，其功能不變造化算法替代，其功能不變假設(shè)一個算法不能分解為假設(shè)干個根本構(gòu)假設(shè)一個算法不能分解為假設(shè)干個根本構(gòu)造，那么它必然不是一個構(gòu)造化的算法造，那么它必然不是一個構(gòu)造化的算法偽代碼是用介于自然言語和計算機言語之偽代碼是用介于自然言語和計算機言語之間的文字和符號來描畫算法間的文字和符號來描畫算法用偽代碼寫算法并無固定的、嚴厲的語法用偽代碼寫算法并無固定的、嚴厲的語法規(guī)那么，可以用英文，也可以中英文混用規(guī)那么，可以用英文，也可以中英文混用例例2.16 求求5!。begin (算法開場算法開場) 1 t 2 i while i5 t*i t i+1 i print tend (算法終了算法終了)例例2.17 求求begin 1 sum 2 deno 1 sign while deno 100 (-1)*