第二章 程序靈魂—算法(1)

1、第二章第二章 程序的靈魂程序的靈魂算法算法算法的概念算法的概念簡(jiǎn)單算法舉例簡(jiǎn)單算法舉例算法的特性算法的特性怎樣表示一個(gè)算法怎樣表示一個(gè)算法結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法2.1 2.1 算法的概念算法的概念算法的定義算法的定義 廣義地說，為解決一個(gè)問題而采取的方法和廣義地說，為解決一個(gè)問題而采取的方法和步驟，就稱為步驟，就稱為“算法算法”。計(jì)算機(jī)算法的分類計(jì)算機(jī)算法的分類數(shù)值運(yùn)算算法：求方程的根，求函數(shù)的積分等數(shù)值運(yùn)算算法：求方程的根，求函數(shù)的積分等非數(shù)值運(yùn)算算法：圖書管理，人事管理，行車非數(shù)值運(yùn)算算法：圖書管理，人事管理，行車調(diào)度等調(diào)度等1.2 1.2 簡(jiǎn)單算法舉例簡(jiǎn)單算法舉例步驟步驟1

2、 1：先求：先求1 x 21 x 2，得結(jié)果，得結(jié)果2 2。步驟步驟2 2：將步驟：將步驟1 1得到的乘積得到的乘積2 2再乘以再乘以3 3，得到結(jié)果，得到結(jié)果6 6。步驟步驟3 3：將：將6 6再乘以再乘以4 4，得，得2424。步驟步驟4 4：將：將2424再乘以再乘以5 5，得，得120120，這就是最后的結(jié)果。，這就是最后的結(jié)果。最原始的方法：最原始的方法：54321例例2.1 2.1 求求p1S1:S1:pipS3:S3:i2S2:S2:i1iS4:S4:5i S5:S5:若若 ，返回，返回S3S3；否則，結(jié)束。；否則，結(jié)束。100321 5 4321 改成把9 7531 5 432

3、1 改成把p : p : 被乘數(shù)和每一步驟的乘積被乘數(shù)和每一步驟的乘積i: i: 乘數(shù)乘數(shù)改進(jìn)的算法：改進(jìn)的算法：例例2.32.3（1 1） 判定某一給定年份判定某一給定年份y y是否為閏年，是否為閏年，將結(jié)果輸出將結(jié)果輸出S1S1： 輸入輸入y yS2S2： 若若y y不能被不能被4 4整除，則輸出整除，則輸出y“y“不是閏年不是閏年” ” ，轉(zhuǎn)，轉(zhuǎn)S6S6S3S3： 若若y y能被能被4 4整除，但不能被整除，但不能被100100整除，則輸出整除，則輸出y y “是閏年是閏年” ” ，轉(zhuǎn)，轉(zhuǎn)S6S6S4S4： 若若y y能被能被100100整除，但又能被整除，但又能被400400整除，則輸

4、出整除，則輸出y y “是閏年是閏年” ” ，轉(zhuǎn)，轉(zhuǎn)S6S6S5S5：輸出：輸出y“y“不是閏年不是閏年”S6S6：算法結(jié)束：算法結(jié)束閏年：閏年：能被能被4 4整除，但不能整除，但不能被被100100整除的年份整除的年份能能100100整除，同時(shí)有能被整除，同時(shí)有能被400400整除的年份整除的年份非閏年：非閏年：不能被不能被4 4整除的年份整除的年份能能100100整除，但不能被整除，但不能被400400整整除的年份除的年份例例2.3 2.3 判定判定2000-25002000-2500年中的每一年是否為閏年，年中的每一年是否為閏年，將結(jié)果輸出將結(jié)果輸出S1S1：S2S2： 若若y y不能被

5、不能被4 4整除，則輸出整除，則輸出y“y“不是閏年不是閏年”，然后轉(zhuǎn)到，然后轉(zhuǎn)到S6S6S3S3： 若若y y能被能被4 4整除，但不能被整除，但不能被100100整除，則輸出整除，則輸出y “y “是是 閏年閏年” ” ，然后轉(zhuǎn)到，然后轉(zhuǎn)到S6S6S4S4： 若若y y能被能被100100整除，但又能被整除，但又能被400400整除，則輸出整除，則輸出y “y “是是 閏年閏年” ” ，然后轉(zhuǎn)到，然后轉(zhuǎn)到S6S6S5S5：輸出：輸出y“y“不是閏年不是閏年”S6S6：S7S7：當(dāng)：當(dāng) 時(shí)，轉(zhuǎn)時(shí)，轉(zhuǎn)S2S2繼續(xù)執(zhí)行，否則，算法停止。繼續(xù)執(zhí)行，否則，算法停止。y2000y1y5002yy :

6、y : 被檢測(cè)的年份被檢測(cè)的年份例例2.4 2.4 求求1001991.4131211sign 1 :S1sum 1 :S2deno 2 :S3sum termsum :S6deno 1 deno :S7signsign1)( :S4 term (1/deno)sign :S5001 deno S8: S8: 若若 返回返回S4S4，否則算法結(jié)束，否則算法結(jié)束sum : sum : 累加和累加和deno: deno: 分母分母sign: sign: 符號(hào)符號(hào) term: term: 某一項(xiàng)某一項(xiàng)例例2.5 2.5 對(duì)于一個(gè)大于對(duì)于一個(gè)大于3 3的正整數(shù)，判斷它是不是的正整數(shù)，判斷它是不是 一個(gè)

7、素?cái)?shù)一個(gè)素?cái)?shù)素?cái)?shù)：除了素?cái)?shù)：除了1 1和該數(shù)本身之外，不能被其它任何和該數(shù)本身之外，不能被其它任何整數(shù)整除的數(shù)整數(shù)整除的數(shù)ni i1i1nii2 0r S1S1：輸入：輸入 n n 的值的值S2S2： （i i 作為除數(shù)）作為除數(shù)）S3S3：n n 被除被除 i i，得余數(shù)得余數(shù) r rS4S4：如果如果 ，則打印則打印 n “n “不是素?cái)?shù)不是素?cái)?shù)”，算，算法結(jié)束；否則執(zhí)行法結(jié)束；否則執(zhí)行S5S5S5S5：S6S6：如果如果 ，則返回，則返回S3S3；否則打印否則打印 n n “是素?cái)?shù)是素?cái)?shù)”，然后結(jié)束。，然后結(jié)束。n : n : 被判斷的數(shù)被判斷的數(shù)i: i: 除數(shù)除數(shù)r: r: 被除數(shù)被

8、除數(shù)2.3 2.3 算法的特性算法的特性n有窮性有窮性n確定性確定性n有零個(gè)或多個(gè)輸入有零個(gè)或多個(gè)輸入n有一個(gè)或多個(gè)輸出有一個(gè)或多個(gè)輸出n有效性有效性2.4 2.4 怎樣表示一個(gè)算法怎樣表示一個(gè)算法用自然語言表示算法用自然語言表示算法用傳統(tǒng)流程圖表示算法用傳統(tǒng)流程圖表示算法用用N-SN-S流程圖表示算法流程圖表示算法用偽代碼表示算法用偽代碼表示算法用計(jì)算機(jī)語言表示算法用計(jì)算機(jī)語言表示算法用流程圖表示算法用流程圖表示算法流程圖是用一些圖框表示各種操作流程圖是用一些圖框表示各種操作起止框起止框輸入輸出框輸入輸出框判斷框判斷框流程線流程線連接點(diǎn)連接點(diǎn)注釋框注釋框處理框處理框0?x 打印x打印-xYN

9、例例 2.6 2.6 求求5!5!的算法用流程圖表示的算法用流程圖表示pipi5i1i結(jié)束結(jié)束開始開始N NY Yi2p1p1S1:S1:pipS3:S3:i2S2:S2:i1iS4:S4:5i S5:S5:若若 ，返回，返回S3S3；否則，結(jié)束；否則，結(jié)束。例例 2.10 2.10 將判斷素?cái)?shù)的算法用流程將判斷素?cái)?shù)的算法用流程圖表示圖表示輸入輸入n ni2r的余數(shù)inr=0?ni i1i打印n是素?cái)?shù)結(jié)束結(jié)束開始開始打印打印n n不不是素?cái)?shù)是素?cái)?shù)YNNYi1i1nii2 0rS1S1：輸入：輸入 n n 的值的值S2S2： （i i 作為除數(shù)）作為除數(shù)）S3S3：n n 被除被除 i i，得余

10、數(shù)得余數(shù) r rS4S4：如果如果 ，則打印則打印 n “n “不是素不是素?cái)?shù)數(shù)”，算法結(jié)束；否則執(zhí)行，算法結(jié)束；否則執(zhí)行S5S5S5S5：S6S6：如果如果 ，則返回，則返回S3S3；否則打否則打印印 n “n “是素?cái)?shù)是素?cái)?shù)”，然后結(jié)束。，然后結(jié)束。 改進(jìn)的流程圖改進(jìn)的流程圖ABabpABba成立成立不成立不成立只有一個(gè)入口只有一個(gè)入口只有一個(gè)出口只有一個(gè)出口結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到結(jié)構(gòu)內(nèi)不存在結(jié)構(gòu)內(nèi)不存在“死循環(huán)死循環(huán)” 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 選擇結(jié)構(gòu)選擇結(jié)構(gòu) 順序結(jié)構(gòu)順序結(jié)構(gòu)A1pab成立成立當(dāng)型循環(huán)當(dāng)型循環(huán)2pAab不成立不成立直到型循環(huán)直到型循環(huán)

11、循環(huán)結(jié)構(gòu)舉例循環(huán)結(jié)構(gòu)舉例x1x結(jié)束結(jié)束開始開始Y YN Nx05x 打印xx1x結(jié)束結(jié)束開始開始N NY Yx05x 打印x用用N-SN-S流程圖表示算法流程圖表示算法ABP成立成立不成立不成立AB當(dāng)當(dāng) 成立成立1pA直到直到 成立成立2pA 選擇結(jié)構(gòu)選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 順序結(jié)構(gòu)順序結(jié)構(gòu)r=0.08r=0.08r=0.06r=0.06成立成立不成立不成立當(dāng)當(dāng)10n 100p pr)(1pAB例例2.11 2.11 求求5!5!的算法用的算法用N-SN-S流程圖表示流程圖表示打印pp1i2pipi1i直到 i 5i 5pipi5i1i結(jié)束結(jié)束開始開始N NY Yi2p1打印p例2.15輸

12、入輸入n ni2r的余數(shù)inr=0?r=0?ni i1i打印打印n n是素?cái)?shù)是素?cái)?shù)結(jié)束結(jié)束開始開始打印打印n n不不是素?cái)?shù)是素?cái)?shù)Y YN NN NY Y輸入輸入n nrin的余數(shù)r=0?r=0?i1i打印打印n n是素?cái)?shù)是素?cái)?shù)開始開始Y YN NN NY Yi2w0ni 1w w=0?w=0?打印打印n n非素?cái)?shù)非素?cái)?shù)結(jié)束結(jié)束Y YN Nw1或輸入n輸出輸出n n是素?cái)?shù)是素?cái)?shù)輸出輸出n n不是素?cái)?shù)不是素?cái)?shù)是是否否w=0直到 i 或w 0nw1i1i是是否否r=0n / i 的余數(shù) rw0i2 用偽代碼表示算法用偽代碼表示算法 偽代碼是用介于自然語言和計(jì)算機(jī)語言之間偽代碼是用介于自然語言和計(jì)算機(jī)

13、語言之間的文字符號(hào)來描述算法。的文字符號(hào)來描述算法。若若 x x 為正為正 打印打印 x x否則否則 打印打印 - -x xif x if x 為正為正 print xprint xelseelse print -x print -x打印打印 x x 的絕對(duì)值的絕對(duì)值例例2.16 2.16 將求將求5!5!的算法用偽代碼表示的算法用偽代碼表示BEIGN(BEIGN(算法開始算法開始) ) while i = 5 while i = 5 print t print tEND(END(算法結(jié)束算法結(jié)束) )t1i2titi1i用計(jì)算機(jī)語言表示算法用計(jì)算機(jī)語言表示算法例例2.20 2.20 將求將求

14、5!5!的算法用的算法用C C語言表示語言表示2.5 2.5 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法的特點(diǎn)：結(jié)構(gòu)化程序設(shè)計(jì)方法的特點(diǎn)：n自頂向下自頂向下n逐步細(xì)化逐步細(xì)化n模塊化設(shè)計(jì)模塊化設(shè)計(jì)n結(jié)構(gòu)化編碼結(jié)構(gòu)化編碼例例2.22 2.22 將將1-10001-1000之間的素?cái)?shù)打印出來之間的素?cái)?shù)打印出來把所有非素?cái)?shù)去掉把所有非素?cái)?shù)去掉打印全部素?cái)?shù)打印全部素?cái)?shù)輸入輸入1-n1-nA AB BC C輸入輸入n ni1ixii1ini 當(dāng)當(dāng)A：例例2.102.10將將 去掉去掉當(dāng)當(dāng)i i 的整數(shù)部分的整數(shù)部分i2ixni1i如如 未去掉未去掉，則則 將將 到到 間間全部是全部是 倍數(shù)倍數(shù)的數(shù)去掉的數(shù)去掉ix1ixnxix1B2B3BB：D將將 到到 范圍內(nèi)范圍內(nèi)是是 倍數(shù)的數(shù)去掉倍數(shù)的數(shù)去掉是是否否1ixnxix0 xiD：E將能將能 被整除的被整除的 去掉去掉j1i當(dāng)