中國科技大學(xué)C語言講義

1、1第第2 2章章 程序的靈魂程序的靈魂-算法算法2.1 2.1 算法的概念（算法的概念（2.12.1）2.2 2.2 算法的特性算法的特性(2.3)(2.3)2.3 2.3 算法的表示算法的表示(2.2 2.4)(2.2 2.4)2.4 2.4 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法(2.5)(2.5)22.1 2.1 算法的概念算法的概念一個(gè)程序應(yīng)包括對數(shù)據(jù)的描述和對數(shù)據(jù)處理的描述一個(gè)程序應(yīng)包括對數(shù)據(jù)的描述和對數(shù)據(jù)處理的描述對數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)對數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)(data structure)(data structure)。 對數(shù)據(jù)處理的描述，即計(jì)算機(jī)算法對數(shù)據(jù)處理的描述，即計(jì)算機(jī)

2、算法(algorithm)(algorithm)。 算法是為解決一個(gè)問題而采取的方法和步驟，是算法是為解決一個(gè)問題而采取的方法和步驟，是程序的靈魂。程序的靈魂。Nikiklaus WirthNikiklaus Wirth公式：公式： 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + + 算法算法 = = 程序程序數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + + 算法算法+ +計(jì)算機(jī)語言計(jì)算機(jī)語言+ +程序設(shè)計(jì)方法程序設(shè)計(jì)方法= = 程序程序3算法算法:為解決一個(gè)問題所采取的方法和步驟為解決一個(gè)問題所采取的方法和步驟分類分類: 數(shù)值算法數(shù)值算法 非數(shù)值算法非數(shù)值算法評估評估: 時(shí)間復(fù)雜度時(shí)間復(fù)雜度 空間復(fù)雜度空間復(fù)雜度42.2 2.2 算法的特點(diǎn)

3、算法的特點(diǎn)v確定性確定性 算法的每一種運(yùn)算必須要有確切的定義，算法的每一種運(yùn)算必須要有確切的定義，即每一種運(yùn)算應(yīng)該執(zhí)行何種動(dòng)作必須是相當(dāng)清楚的、即每一種運(yùn)算應(yīng)該執(zhí)行何種動(dòng)作必須是相當(dāng)清楚的、無二義性的。無二義性的。v數(shù)據(jù)輸入數(shù)據(jù)輸入 一個(gè)算法有零個(gè)或多個(gè)數(shù)據(jù)輸入，它們一個(gè)算法有零個(gè)或多個(gè)數(shù)據(jù)輸入，它們是在算法開始之前對算法最初賦予的量，這些輸入是在算法開始之前對算法最初賦予的量，這些輸入取自特定的對象集合。取自特定的對象集合。v數(shù)據(jù)輸出數(shù)據(jù)輸出 一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，它們是一個(gè)算法產(chǎn)生一個(gè)或多個(gè)輸出，它們是同輸入有某種特定關(guān)系的量。同輸入有某種特定關(guān)系的量。v有窮性有窮性 一個(gè)算法總是在

4、執(zhí)行了有窮步之后終止。一個(gè)算法總是在執(zhí)行了有窮步之后終止。v有效性有效性 有效執(zhí)行有效執(zhí)行52.32.3算法的表示算法的表示v自然語言自然語言易出現(xiàn)易出現(xiàn)”歧義歧義”v流程圖流程圖直觀形象、易理解直觀形象、易理解vN-SN-S流程圖流程圖改進(jìn)的流程圖改進(jìn)的流程圖v偽代碼偽代碼v計(jì)算機(jī)語言表示計(jì)算機(jī)語言表示6求求5! 5! 例例2.12.1設(shè)設(shè)p p為被乘數(shù)，為被乘數(shù)，i i為乘數(shù)。用循環(huán)算法來求結(jié)果。為乘數(shù)。用循環(huán)算法來求結(jié)果。 S1S1：使：使p=lp=l S2 S2：使：使i=2i=2 S3 S3：使：使pXipXi，乘積仍放在變量，乘積仍放在變量p p中，可表示為中，可表示為 pXi=p

5、pXi=p S4 S4：使：使i i的值加的值加1 1，即，即i+1=ii+1=i s5 s5：如果：如果i i不大于不大于5 5，返回重新執(zhí)行步驟，返回重新執(zhí)行步驟s3s3以及其后的以及其后的步驟步驟S4S4和和s5s5；否則，輸出；否則，輸出p,p,算法結(jié)束。最后得到算法結(jié)束。最后得到p p的的值就是值就是5!5!的值。的值。7起止框起止框輸入輸入/出框出框判斷框判斷框處理框處理框流程線流程線注釋框注釋框連接點(diǎn)連接點(diǎn)8開始開始1=p1=p2=i2=ipxi=ppxi=pi+1=ii+1=ii5i5打印打印p p結(jié)束結(jié)束N NY Y9順序結(jié)構(gòu)順序結(jié)構(gòu)10選擇結(jié)構(gòu)選擇結(jié)構(gòu)11循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)當(dāng)

6、當(dāng)型型循循環(huán)環(huán)直直到到型型循循環(huán)環(huán)直到條件成立直到條件成立a a塊塊12一個(gè)入口一個(gè)入口一個(gè)出口一個(gè)出口結(jié)構(gòu)內(nèi)每一部分都會(huì)被執(zhí)行結(jié)構(gòu)內(nèi)每一部分都會(huì)被執(zhí)行結(jié)構(gòu)內(nèi)無結(jié)構(gòu)內(nèi)無”死循環(huán)死循環(huán)”13開始開始1=p1=p2=i2=ipxi=ppxi=pi+1=ii+1=ii5i5打印打印p p結(jié)束結(jié)束N NY Y1=p1=p2=i2=ip xi=pp xi=pi+1=ii+1=i直到直到i5i5打印打印p p142.32.3算法的表示算法的表示v自然語言自然語言易出現(xiàn)易出現(xiàn)”歧義歧義”v流程圖流程圖直觀形象、易理解直觀形象、易理解vN-SN-S流程圖流程圖改進(jìn)的流程圖改進(jìn)的流程圖v偽代碼偽代碼v計(jì)算機(jī)語言

7、表示計(jì)算機(jī)語言表示15判定判定2000-25002000-2500年中的每一年是否閏年，將結(jié)果輸出年中的每一年是否閏年，將結(jié)果輸出閏年的條件是：閏年的條件是：能被能被4 4整除，但不能被整除，但不能被100100整除的年份都是整除的年份都是閏年，如閏年，如19961996年，年，20042004年是閏年；年是閏年；能被能被100100整除，又能被整除，又能被400400整除的年份是閏年如整除的年份是閏年如16001600年、年、20002000年是閏年不符合年是閏年不符合這兩個(gè)條件的年份不是閏年。這兩個(gè)條件的年份不是閏年。（2.32.3） 設(shè)設(shè)y y為被檢測的年份。采取以下步驟；為被檢測的年份

8、。采取以下步驟； S1S1：2000=y2000=y S2 S2：若：若y y不能被不能被4 4整除，則輸出整除，則輸出y“y“不是閏年不是閏年” ”。轉(zhuǎn)。轉(zhuǎn)S5S5 S3 S3：若：若y y能被能被4 4整除，不能被整除，不能被100100整除，則輸出整除，則輸出y“y“是閏年是閏年” ”。轉(zhuǎn)。轉(zhuǎn)S5S5 S4 S4：若：若y y能被能被100100整除，又能被整除，又能被400400整除，輸出整除，輸出y”y”是閏年是閏年” ”；否則；否則 輸出輸出“ “不是閏年不是閏年” ”。轉(zhuǎn)。轉(zhuǎn)S5S5 S5 S5：y+1=yy+1=y S6 S6：當(dāng)：當(dāng)y2500y2500時(shí)，轉(zhuǎn)時(shí)，轉(zhuǎn)S2S2繼續(xù)

9、執(zhí)行，如繼續(xù)執(zhí)行，如y2500y2500，算法停止。，算法停止。162000= y是是 Y/4Y/4的余數(shù)為的余數(shù)為0 0 否否是是 Y/100Y/100余數(shù)不為余數(shù)不為0 0 否否打印打印y”y”非閏年非閏年”打印打印y”是是閏年閏年”是是 Y/400Y/400余數(shù)為余數(shù)為0 0 否否打印打印y”是是閏年閏年”打印打印y”非閏年非閏年” y+1=y 直到直到y(tǒng)250017對一個(gè)大于或等于對一個(gè)大于或等于3 3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。 判素?cái)?shù)的方法判素?cái)?shù)的方法: :將將n n作為被除數(shù)，將作為被除數(shù)，將2 2到到(n(n一一1)1)各個(gè)整數(shù)輪流作各個(gè)整數(shù)

10、輪流作為除數(shù)，如果都不能被整除，則為除數(shù)，如果都不能被整除，則n n為素?cái)?shù)。為素?cái)?shù)。（2.52.5）S1S1：輸入：輸入n n的值的值S2S2：i=2(ii=2(i作為除數(shù)作為除數(shù)) )S3S3：n n被被i i除，得余數(shù)除，得余數(shù)r rS4S4：如果：如果r=Or=O，表示，表示n n能被能被i i整除，則打印整除，則打印n“n“不是素?cái)?shù)不是素?cái)?shù)” ”，算法結(jié)束；，算法結(jié)束；否則執(zhí)行否則執(zhí)行S5S5S5S5：i+1=ii+1=iS6S6：如果：如果i=n-1i=n-1，返回，返回S3S3；否則打??；否則打印n“n“是素?cái)?shù)是素?cái)?shù)” ”，然，然 后結(jié)束。后結(jié)束。S6S6：如果：如果i=niin/

11、i 的余數(shù)的余數(shù)=rr=0?i+1=iin1/2打印打印“n n是素?cái)?shù)是素?cái)?shù)” 結(jié)束結(jié)束打印打印“n n不是素?cái)?shù)不是素?cái)?shù)”YNYN19開始開始輸入輸入n2=i 0=wn/i 的余數(shù)的余數(shù)=rr=0?i+1=iiwYN結(jié)束結(jié)束打印打印“n n不是素?cái)?shù)不是素?cái)?shù)”打印打印“n n是素?cái)?shù)是素?cái)?shù)” W=0?YNYN20輸入輸入n0=w2=in/i的余數(shù)的余數(shù)=r是是 r=0 否否1= w i+1=i 直到直到rn1/2或或w!=0是是 w=0 否否輸出輸出n”是素?cái)?shù)是素?cái)?shù)“ 輸出輸出n”不是素?cái)?shù)不是素?cái)?shù)“212.42.4結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法v為何提出為何提出: :v基本思路基本思路: :

12、 把一個(gè)復(fù)雜的問題分解成若干個(gè)簡單的小問把一個(gè)復(fù)雜的問題分解成若干個(gè)簡單的小問題題. .自頂向下自頂向下 逐步細(xì)化逐步細(xì)化 模塊化設(shè)計(jì)模塊化設(shè)計(jì) 結(jié)構(gòu)化編碼結(jié)構(gòu)化編碼22例例 將將1 1到到10001000之間的素?cái)?shù)打印出來。之間的素?cái)?shù)打印出來。 “ “埃拉托色尼埃拉托色尼(Eratosthenes)(Eratosthenes)篩法篩法” ”: :在一張紙上寫上在一張紙上寫上1 1到到10001000全部整數(shù)，然后逐個(gè)判斷它們是否素?cái)?shù)，找出一個(gè)全部整數(shù)，然后逐個(gè)判斷它們是否素?cái)?shù)，找出一個(gè)非素?cái)?shù)，就把它挖掉，最后剩下的就是素?cái)?shù)非素?cái)?shù)，就把它挖掉，最后剩下的就是素?cái)?shù). (1)(1)先將先將1 1挖

13、掉挖掉( (因?yàn)橐驗(yàn)? 1不是素?cái)?shù)不是素?cái)?shù)) )。 (2)(2)用用2 2去除它后面的各個(gè)數(shù)，把能被去除它后面的各個(gè)數(shù)，把能被2 2整除的數(shù)挖整除的數(shù)挖 掉，即把掉，即把2 2的倍數(shù)挖掉。的倍數(shù)挖掉。 (3)(3)用用3 3去除它后面各數(shù)，把去除它后面各數(shù)，把3 3的倍數(shù)挖掉。的倍數(shù)挖掉。 (4)(4)分別用分別用4 4、55作為除數(shù)去除這些數(shù)以后的各數(shù)。作為除數(shù)去除這些數(shù)以后的各數(shù)。這個(gè)過程一直進(jìn)行到在除數(shù)后面的數(shù)已全被挖掉為這個(gè)過程一直進(jìn)行到在除數(shù)后面的數(shù)已全被挖掉為止。止。 如果需要找如果需要找1 1n n范圍內(nèi)素?cái)?shù)表，只需進(jìn)行到除數(shù)范圍內(nèi)素?cái)?shù)表，只需進(jìn)行到除數(shù)為為n n1/21/2(

14、(取其整數(shù)取其整數(shù)) )即可。即可。23 (1)(1)挖去挖去1 1； (2)(2)用剛才被挖去的數(shù)的下一個(gè)數(shù)用剛才被挖去的數(shù)的下一個(gè)數(shù)p p去除去除p p后面各后面各 數(shù)，把數(shù)，把p p的倍數(shù)挖掉；的倍數(shù)挖掉； (3)(3)檢查檢查P P是否小于是否小于n n1/21/2 的整敷部分的整敷部分( (如果如果n-1000n-1000， 則檢查則檢查p31)pi當(dāng)當(dāng)ixii+1=i26將去將去x1掉掉 (x1=0)2=i當(dāng)當(dāng)ii如如xi未去掉未去掉,則將則將xi+1到到xn之之間所有是間所有是xi倍數(shù)的數(shù)去掉倍數(shù)的數(shù)去掉27 xi=0 是是 否否則將則將xi+1到到xn之間所有是之間所有是xi倍數(shù)的數(shù)去掉倍數(shù)的數(shù)去掉28i+1=j當(dāng)當(dāng)jj將能被將能被xi整除的整除的xj去掉去掉29是是 xj =0 否否 xj能被能被xi整除整除