程序邏輯與C語言：第2章 算法---程序的靈魂

1、第2章 算法-程序的靈魂,一個程序主要包括以下兩方面的信息： (1) 對數據的描述。在程序中要指定用到哪些數據以及這些數據的類型和數據的組織形式 這就是數據結構(data structure) (2) 對操作的描述。即要求計算機進行操作的步驟 也就是算法(algorithm),數據是操作的對象 操作的目的是對數據進行加工處理，以得到期望的結果 著名計算機科學家沃思(Nikiklaus Wirth)提出一個公式： 算法 + 數據結構 = 程序,一個程序除了算法和數據結構這主要要素外，還應當采用結構化程序設計方法進行程序設計，并且用某一種計算機語言表示 算法、數據結構、程序設計方法和語言工具是一個

2、程序設計人員應具備的知識,算法是解決“做什么”和“怎么做”的問題 程序中的操作語句，是算法的體現(xiàn) 不了解算法就談不上程序設計,2.1 什么是算法 2.2 簡單的算法舉例 2.3 算法的特性 2.4 怎樣表示一個算法 2.5 結構化程序設計方法,2.1 什么是算法,廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法” 對同一個問題，可以有不同的解題方法和步驟 為了有效地進行解題，不僅需要保證算法正確，還要考慮算法的質量，選擇合適的算法,2.1 什么是算法,計算機算法可分為兩大類別： 數值運算算法 非數值運算算法 數值運算的目的是求數值解 非數值運算包括的面十分廣泛，最常見的是用于事務管理領

3、域,2.2簡單的算法舉例,例2.1 求12345 可以用最原始的方法進行： 步驟1：先求1*2，得到結果2。 步驟2：將步驟1得到的乘積2再乘以3，得到結果6。 步驟3：將6再乘以4，得24。 步驟4：將24再乘以5，得120。這就是最后的結果。,例2.1 求12345 1000,太繁瑣,2.2簡單的算法舉例,改進的算法： 設變量p為被乘數 變量i為乘數 用循環(huán)算法求結果,2.2簡單的算法舉例,S1：使p=1，或寫成1p S2：使i=2，或寫成2i S3：使p與i相乘，乘積仍放在變量p中，可表示為：p*ip S4：使i的值加1，即i+1 i S5：如果i不大于5，返回重新執(zhí)行S3；否則，算法結

4、束 最后得到p的值就是 5!的值,若是1000，求什么？,2.2簡單的算法舉例,S1：使p=1，或寫成1p S2：使i=2，或寫成2i S3：使p與i相乘，乘積仍放在變量p中，可表示為：p*ip S4：使i的值加1，即i+1 i S5：如果i不大于5，返回重新執(zhí)行S3；否則，算法結束 最后得到p的值就是 5!的值,若求1357911,3,3,2,2,11,11,相當于i 11,例2.2 有50個學生，要求將成績在80分以上的學生的學號和成績輸出。 用ni代表第i個學生學號，gi表示第i個學生成績 S1：1i S2：如果gi80， 則輸出ni和gi，否則不輸出 S3：i+1i S4：如果i50，

5、返回到步驟S2，繼續(xù)執(zhí)行，否則，算法結束,例2.3 判定20002500年中的每一年是否閏年，并將結果輸出。 閏年的條件： (1)能被4整除，但不能被100整除的年份都是閏年，如2008、2012、2048年 (2)能被400整除的年份是閏年，如2000年 不符合這兩個條件的年份不是閏年 例如2009、2100年,設year為被檢測的年份。算法表示如下： S1：2000year S2：若year不能被4整除，則輸出year 的值和“不是閏年”。然后轉到S6 S3：若year能被4整除，不能被100整除，則輸出year的值和“是閏年”。然后轉到S6 S4：若year能被400整除，則輸出year

6、的值和“是閏年” ，然后轉到S6 S5: 其他情況輸出year的值和“不是閏年” S6：year+1year S7：當year2500時，轉S2，否則停止,year不能被4整除,非閏年,year被4整除，但不能被100整除,閏年,year被100整除，又能被400整除,閏年,其他,非閏年,逐漸縮小判斷的范圍,例2.4 求 規(guī)律： 第1項的分子分母都是1 第2項的分母是2，以后每一項的分母子都是前一項的分母加1 笫2項前的運算符為“-”，后一項前面的運算符都與前一項前的運算符相反,例2.4 求 S1：sign=1 S2：sum=1 S3：deno=2 S4：sign=(-1)*sign S5：t

7、erm=sign*(1/deno) S6：sum=sum+term S7：deno=deno+1 S8：若deno100返回S4；否則算法結束,sign當前項符號 term當前項的值 sum當前各項的和 deno當前項分母,-1,-1/2,1-1/2,3,滿足，返回S4,例2.4 求 S1：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：若deno100返回S4；否則算法結束,sign當前項符號 term當前項的值 sum當前各項的和 deno

8、當前項分母,1,1/3,1-1/2+1/3,4,滿足，返回S4,例2.4 求 S1：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：若deno100返回S4；否則算法結束,99次循環(huán)后sum的值就是所要求的結果,例2.5 給出一個大于或等于3的正整數，判斷它是不是一個素數。 所謂素數(prime)，是指除了1和該數本身之外，不能被其他任何整數整除的數 例如，13是素數，因為它不能被2，3，4，12整除。,判斷一個數n(n3)是否素數：將n作為被

9、除數，將2到(n-1)各個整數先后作為除數，如果都不能被整除，則n為素數 S1：輸入n的值 S2：i=2 （i作為除數） S3：n被i除，得余數r S4：如果r=0，表示n能被i整除，則輸出n“不是素數”，算法結束；否則執(zhí)行S5 S5：i+1i S6：如果in-1，返回S3；否則輸出n “是素數”，然后結束。,可改為n/2,2.3算法的特性,一個有效算法應該具有以下特點： (1) 有窮性。一個算法應包含有限的操作步驟，而不能是無限的。 (2) 確定性。算法中的每一個步驟都應當是確定的，而不應當是含糊的、模棱兩可的。,2.3算法的特性,一個有效算法應該具有以下特點： (3) 有零個或多個輸入。所

10、謂輸入是指在執(zhí)行算法時需要從外界取得必要的信息。 (4) 有一個或多個輸出。算法的目的是為了求解，“解” 就是輸出。 沒有輸出的算法是沒有意義的。 (5) 有效性。算法中的每一個步驟都應當能有效地執(zhí)行，并得到確定的結果。,2.3算法的特性,對于一般最終用戶來說: 他們并不需要在處理每一個問題時都要自己設計算法和編寫程序 可以使用別人已設計好的現(xiàn)成算法和程序 只需根據已知算法的要求給予必要的輸入，就能得到輸出的結果,輸入3個數,黑箱子,3個數中最大數,求3個數的最大數,2.4怎樣表示一個算法,常用的方法有： 自然語言 傳統(tǒng)流程圖 結構化流程圖 偽代碼 ,2.4怎樣表示一個算法,2.4.1 用自然

11、語言表示算法 2.4.2 用流程圖表示算法 2.4.3 三種基本結構和改進的流程圖 2.4.4 用N-S流程圖表示算法 2.4.5 用偽代碼表示算法 2.4.6 用計算機語言表示算法,2.4.1 用自然語言表示算法,2.2節(jié)介紹的算法是用自然語言表示的 用自然語言表示通俗易懂，但文字冗長，容易出現(xiàn)歧義性 用自然語言描述包含分支和循環(huán)的算法，不很方便 除了很簡單的問題外，一般不用自然語言,2.4.2用流程圖表示算法,流程圖是用一些圖框來表示各種操作 用圖形表示算法，直觀形象，易于理解,起止框,輸入輸出框,處理框,判斷框,流程線,連接點,注釋框,x0,Y,N,一個入口,兩個出口,2.4.2用流程圖

12、表示算法,流程圖是用一些圖框來表示各種操作 用圖形表示算法，直觀形象，易于理解,起止框,輸入輸出框,處理框,判斷框,流程線,連接點,注釋框,位置不夠,防止交叉,例2.6 將例2.1的算法用流程圖表示。 求12345 如果需要將最后結果輸出:,1t,i5,開始,2i,t*it,i+1i,結束,N,Y,例2.6 將例2.1的算法用流程圖表示。 求12345 如果需要將最后結果輸出:,1t,輸出t,i5,開始,2i,t*it,i+1i,結束,N,Y,例2.7 例2.2的算法用流程圖表示。有50個學生，要求將成績在80分以上的學生的學號和成績輸出。,1i,i50,開始,i+1i,結束,N,Y,輸入ni

13、、gi,1i,開始,gi80,輸出ni、gi,i+1i,i50,N,Y,Y,N,如果包括輸入數據部分,1i,i50,開始,i+1i,結束,N,Y,輸入ni、gi,1i,gi80,輸出ni、gi,i+1i,i50,N,Y,Y,N,如果包括輸入數據部分,例2.8 例2.3判定閏年的算法用流程圖表示。判定20002500年中的每一年是否閏年，將結果輸出。,N,Y,N,Y,Y,N,Y,N,例2.9 將例2.4的算法用流程圖表示。求,1sum 2deno 1sign,(-1)*signsign sign*(1/deno)term sum+termsum deno+1deno,N,Y,例2.10 例2.5

14、判斷素數的算法用流程圖表示。對一個大于或等于3的正整數，判斷它是不是一個素數。,N,Y,2i,n%ir,i+1i,Y,N,通過以上幾個例子可以看出流程圖是表示算法的較好的工具 一個流程圖包括以下幾部分： (1) 表示相應操作的框 (2) 帶箭頭的流程線 (3) 框內外必要的文字說明 流程線不要忘記畫箭頭，否則難以判定各框的執(zhí)行次序,2.4.3 三種基本結構和改進的流程圖,1.傳統(tǒng)流程圖的弊端 傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴格限制 使用者可以毫不受限制地使流程隨意地轉來轉去，使人難以理解算法的邏輯,2.4.3 三種基本結構和改進的流程圖,2.三種基本結構 (1) 順

15、序結構,A,B,2.4.3 三種基本結構和改進的流程圖,2.三種基本結構 (2) 選擇結構,A,B,Y,N,A,Y,N,2.4.3 三種基本結構和改進的流程圖,2.三種基本結構 (3) 循環(huán)結構 當型循環(huán)結構,A,Y,N,Y,N,0 x,x+1x,輸出1,2,3,4,5,2.4.3 三種基本結構和改進的流程圖,2.三種基本結構 (3) 循環(huán)結構 直到型循環(huán)結構,A,Y,N,Y,N,0 x,x+1x,輸出1,2,3,4,5,以上三種基本結構，有以下共同特點： (1) 只有一個入口 (2) 只有一個出口 一個判斷框有兩個出口 一個選擇結構只有一個出口 (3) 結構內的每一部分都有機會被執(zhí)行到。也就

16、是說，對每一個框來說，都應當有一條從入口到出口的路徑通過它 (4) 結構內不存在“死循環(huán)”,由三種基本結構派生出來的結構：,A,N,Y,B,根據表達式p 的值進行選擇,A,B,p=p1,p=p2,M,N,p=pm,p=pn,2.4.4 用N-S流程圖表示算法,N-S流程圖用以下的流程圖符號：,順序結構,選擇結構,循環(huán)結構 （當型）,循環(huán)結構（直到型）,例2.11將例2.1的求5!算法用N-S圖表示。,直到i5,1t,輸出t,2i,t*it,i+1i,例2.12 將例2.2的算法用N-S圖表示。將50名學生中成績高于80分者的學號和成績輸出。,直到i50,1t,1i,i+1i,輸入ni、gi,i

17、+1i,直到i50,gi80,否,是,輸出ni,gi,例2.13 將例2.3判定閏年的算法用N-S圖表示,直到y(tǒng)ear2500,2000year,year+1year,否,是,year%4為0,否,是,輸出 year 非閏年,year%100不為0,year%400為0,是,否,輸出year 非閏年,輸出year 閏年,輸出 year 閏年,例2.14 將例2.4的算法用N-S圖表示。求,直到deno100,deno+1deno,輸出sum,1sum,1sign,2deno,(-1)*signsign,sign*(1/deno)term,sum+termsum,例2.15 將例2.5判別素數的

18、算法用N-S流程圖表示。 例2.10的流程圖不是由三種基本結構組成的 循環(huán)有兩個出口，不符合基本結構的特點 無法直接用N-S流程圖的三種基本結構的符號來表示 先作必要的變換,輸入n,r=0,是,否,0w,2i,n%ir,1w,i+1i,直到i 或w 0,w=0,是,否,輸出n是素數,輸出n不是素數,一個結構化的算法是由一些基本結構順序組成的 在基本結構之間不存在向前或向后的跳轉，流程的轉移只存在于一個基本結構范圍之內 一個非結構化的算法可以用一個等價的結構化算法代替，其功能不變 如果一個算法不能分解為若干個基本結構，則它必然不是一個結構化的算法,2.4.5用偽代碼表示算法,偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法 用偽代碼寫算法并無固定的、嚴格的語法規(guī)則，可以用英文，也可以中英文混用,例2.16 求5!。 begin (算法開始) 1 t 2 i while i5 t*i t i+1 i print t end (算法結束),例2.17 求 begin 1 sum 2 deno 1 sign while deno 100 (-1)*sign sign sign*1/deno term sum+term sum de