程序的靈魂算法課件

1、第四章 程序的靈魂算法1、對數(shù)據(jù)的描述。（配料，指出應(yīng)使用那些原料）2、對操作的描述。（操作步驟，如何用料做成菜肴）3、程序設(shè)計(jì)方法。4、語言工具和環(huán)境。程序=數(shù)據(jù)結(jié)構(gòu)+算法+程序設(shè)計(jì)方法+語言工具和環(huán)境.1 算法的概念為解決一個(gè)問題而采取的方法和步驟，為解決一個(gè)問題而采取的方法和步驟，就稱為算法。就稱為算法。從北京到天津開會(huì)一首歌曲的譜子太極拳圖解計(jì)算機(jī)算法分兩大類：數(shù)值運(yùn)算算法和計(jì)算機(jī)算法分兩大類：數(shù)值運(yùn)算算法和 非數(shù)值運(yùn)算算法。非數(shù)值運(yùn)算算法。.2 簡單算法舉例例例1：求：求1*2*3*4*5方法一：步驟1：先求1*2，得到結(jié)果2。步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6。步驟3

2、：將步驟2得到的乘積6再乘以4，得到結(jié)果24。步驟4：將步驟3得到的乘積24再乘以5， 得到最后結(jié)果120。方法二：步驟1：設(shè)p=1（p為乘數(shù)）。步驟2：設(shè)i=2（i為被乘數(shù)）。步驟3：使p*i，乘積仍放在變量p中，可表示為p=p*i。步驟4：使i的值加1，可表示為i=i+1 。步驟5：如果i不大于5，返回重新執(zhí)行步驟3、4、5； 否則算法結(jié)束。最后求得的p的值就是5！的值。例例2 2 有兩個(gè)變量有兩個(gè)變量a a和和b b，將它們的值交換。，將它們的值交換。 a tb采用間接交換方法。采用間接交換方法。1、at2、 ba3、 t b例例3 3 有有50個(gè)學(xué)生，要求將他們之中成績在個(gè)學(xué)生，要求將

3、他們之中成績在80分以分以上者打印出來。用上者打印出來。用n表示學(xué)生學(xué)號(hào)，表示學(xué)生學(xué)號(hào)，n1代表第一代表第一個(gè)學(xué)生學(xué)號(hào)，個(gè)學(xué)生學(xué)號(hào)，ni代表第代表第i個(gè)學(xué)生學(xué)號(hào)。用個(gè)學(xué)生學(xué)號(hào)。用g代表學(xué)代表學(xué)生成績，生成績，gi代表第代表第i個(gè)學(xué)生成績，算法可表示如下。個(gè)學(xué)生成績，算法可表示如下。S1：1=iS2：如果：如果gi80，則打印，則打印ni和和gi，否則不打，否則不打印印S3：i+1=iS4：如果：如果i50，返回，返回S2，繼續(xù)執(zhí)行；否則，繼續(xù)執(zhí)行；否則，算法結(jié)束。算法結(jié)束。例例4 4 給定一個(gè)正整數(shù)給定一個(gè)正整數(shù)M M，判斷它是否為素?cái)?shù)。，判斷它是否為素?cái)?shù)。所謂素?cái)?shù)，是指除了所謂素?cái)?shù)，是指除了

4、1和該數(shù)本身之外，不能被和該數(shù)本身之外，不能被其他任何整數(shù)整除的數(shù)。例如，其他任何整數(shù)整除的數(shù)。例如，13是素?cái)?shù)，因是素?cái)?shù)，因?yàn)樗荒鼙粸樗荒鼙?，3，4，12整除。整除。判斷一個(gè)數(shù)判斷一個(gè)數(shù)n(n3)是否素?cái)?shù)的方法是很簡單的：是否素?cái)?shù)的方法是很簡單的：將將n作為被除數(shù)，將作為被除數(shù)，將2到到(n-1)各個(gè)整數(shù)輪流作為各個(gè)整數(shù)輪流作為除數(shù)，如果都不能被整除，則除數(shù)，如果都不能被整除，則n為素?cái)?shù)。為素?cái)?shù)。S1：輸入：輸入n的值的值S2：2=i （i作為除數(shù)）作為除數(shù)）S3：n被被i除，得余數(shù)除，得余數(shù)rS4：如果：如果r=0，表示，表示n能被能被i整除，則打印整除，則打印n“不是素不是素?cái)?shù)數(shù)”

5、，算法結(jié)束；否則執(zhí)行，算法結(jié)束；否則執(zhí)行S5S5：i+1=iS6：如果：如果in-1，返回，返回S3；否則打??；否則打印 n “是素?cái)?shù)是素?cái)?shù)”，然后結(jié)束。然后結(jié)束。.3 算法的特點(diǎn)1、有窮性：一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無限的。2、確定性：算法中每一個(gè)步驟都應(yīng)當(dāng)是確定的，不能含糊、模棱兩可。3、有零個(gè)或多個(gè)輸入。4、有一個(gè)或多個(gè)輸出。5、有效性。一、算法的特征 二、算法設(shè)計(jì)的要求二、算法設(shè)計(jì)的要求 1 正確性。正確性。算法應(yīng)當(dāng)滿足具體問題的需求?！罢_”一詞 的含義在通常的用法中有很大差別，大體 可分為四個(gè)層次： a. 程序不含語法錯(cuò)誤。 b. 程序?qū)捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明

6、 要求的結(jié)果。 c. 程序?qū)τ诰倪x擇的典型、苛刻而帶有刁 難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說 明要求的結(jié)果。 d. 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足 規(guī)格說明要求的結(jié)果。 2 可讀性。可讀性。算法主要是為了人的閱讀和交流，可讀性 好有助于 人對算法的理解。3 健壯性。健壯性。當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)做出 反應(yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙 的輸出結(jié)果。4 效率與低存儲(chǔ)量需求。效率與低存儲(chǔ)量需求。效率指算法執(zhí)行的時(shí)間； 存儲(chǔ)量需求算法執(zhí)行過程中所需要的 最大存儲(chǔ)空間。二、算法設(shè)計(jì)的要求二、算法設(shè)計(jì)的要求 .4 算法的描述。算法的描述。 常用的描述工具有：自然語言，流程圖，N-S結(jié)

7、構(gòu)化流程圖，PAD圖，偽代碼等。 1. 程序流程圖程序流程圖 流程圖是一種傳統(tǒng)的算法表示法，它利用幾何圖形框來代表各種不同性質(zhì)的操作，用流程線來指示算法的執(zhí)行方向。由于它簡單直觀，所以應(yīng)用廣泛，特別是在早期語言階段，只有通過流程圖才能簡明地表述算法，流程圖成為程序員們交流的重要手段，直到結(jié)構(gòu)化的程序設(shè)計(jì)語言出現(xiàn)，對流程圖的依賴才有所降低。處理框判斷框起始框流程線輸入/輸出框常用符號(hào)：常用符號(hào)：例1 打印x的絕對值例例2 求求5!的算法用流程圖表示的算法用流程圖表示例例3 將將50名學(xué)生中成績在名學(xué)生中成績在80分以上者的學(xué)號(hào)和成績打印出來分以上者的學(xué)號(hào)和成績打印出來例例4 判斷素?cái)?shù)的算法判斷素?cái)?shù)的算法三種基本結(jié)構(gòu)：順序結(jié)構(gòu)，選擇結(jié)構(gòu)，循環(huán)結(jié)構(gòu)。AB順序結(jié)構(gòu)PBA是否選擇結(jié)構(gòu)P1A是否當(dāng)型循環(huán)BP2否是直到型循環(huán)三種基本結(jié)構(gòu)有以下共同特點(diǎn)： 1 只有一個(gè)入口。 2 只有一個(gè)出口。 3 結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到， 且路徑是唯一的。 4 結(jié)構(gòu)內(nèi)沒有死循環(huán)。2. N-S結(jié)構(gòu)化流程圖結(jié)構(gòu)化流程圖 N-S圖完全去掉了流程圖中的控制流程的流線和箭頭。AB順