第2章算法程序的靈魂

第2章算法---程序的靈魂一個程序主要包括以下兩方面的信息：(1)對數據的描述。在程序中要指定用到哪些數據以及這些數據的類型和數據的組織形式這就是數據結構(datastructure)(2)對操作的描述。即要求計算機進行操作的步驟也就是算法(algorithm)數據是操作的對象操作的目的是對數據進行加工處理，以得到期望的結果著名計算機科學家沃思(NikiklausWirth)提出一個公式：

算法

+數據結構=程序一個程序除了算法和數據結構這主要要素外，還應當采用結構化程序設計方法進行程序設計，并且用某一種計算機語言表示算法、數據結構、程序設計方法和語言工具是一個程序設計人員應具備的知識算法是解決“做什么”和“怎么做”的問題程序中的操作語句，是算法的體現不了解算法就談不上程序設計2.1什么是算法廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法”對同一個問題，可以有不同的解題方法和步驟為了有效地進行解題，不僅需要保證算法正確，還要考慮算法的質量，選擇合適的算法2.1什么是算法計算機算法可分為兩大類別：數值運算算法非數值運算算法數值運算的目的是求數值解非數值運算包括的面十分廣泛，最常見的是用于事務管理領域2.2簡單的算法舉例例2.1求1×2×3×4×5可以用最原始的方法進行：步驟1：先求1*2，得到結果2。步驟2：將步驟1得到的乘積2再乘以3，得到結果6。步驟3：將6再乘以4，得24。步驟4：將24再乘以5，得120。這就是最后的結果。例2.1求1×2×3×4×5×…×1000太繁瑣2.2簡單的算法舉例改進的算法：設變量p為被乘數變量i為乘數用循環(huán)算法求結果2.2簡單的算法舉例S1：使p=1，或寫成1pS2：使i=2，或寫成2iS3：使p與i相乘，乘積仍放在變量p中，可表示為：p*ipS4：使i的值加1，即i+1iS5：如果i不大于5，返回重新執(zhí)行S3；否則，算法結束最后得到p的值就是5!的值若是1000，求什么？2.2簡單的算法舉例S1：使p=1，或寫成1pS2：使i=2，或寫成2iS3：使p與i相乘，乘積仍放在變量p中，可表示為：p*ipS4：使i的值加1，即i+1iS5：如果i不大于5，返回重新執(zhí)行S3；否則，算法結束最后得到p的值就是5!的值若求1×3×5×7×9×1133221111相當于i≦11

例2.3判定2000—2500年中的每一年是否閏年，并將結果輸出。閏年的條件：(1)能被4整除，但不能被100整除的年份都是閏年，如2008、2012、2048年(2)能被400整除的年份是閏年，如2000年不符合這兩個條件的年份不是閏年例如2009、2100年設year為被檢測的年份。算法表示如下：S1：2000yearS2：若year不能被4整除，則輸出year的值和“不是閏年”。然后轉到S6S3：若year能被4整除，不能被100整除，則輸出year的值和“是閏年”。然后轉到S6S4：若year能被400整除，則輸出year的值和“是閏年”，然后轉到S6S5:其他情況輸出year的值和“不是閏年”S6：year+1yearS7：當year≤2500時，轉S2，否則停止year不能被4整除非閏年year被4整除，但不能被100整除閏年year被100整除，又能被400整除閏年其他非閏年逐漸縮小判斷的范圍2.3算法的特性一個有效算法應該具有以下特點：(1)

有窮性。一個算法應包含有限的操作步驟，而不能是無限的。(2)

確定性。算法中的每一個步驟都應當是確定的，而不應當是含糊的、模棱兩可的。2.3算法的特性一個有效算法應該具有以下特點：(3)

有零個或多個輸入。所謂輸入是指在執(zhí)行算法時需要從外界取得必要的信息。(4)

有一個或多個輸出。算法的目的是為了求解，“解”就是輸出。沒有輸出的算法是沒有意義的。(5)

有效性。算法中的每一個步驟都應當能有效地執(zhí)行，并得到確定的結果。2.3算法的特性對于一般最終用戶來說:他們并不需要在處理每一個問題時都要自己設計算法和編寫程序可以使用別人已設計好的現成算法和程序只需根據已知算法的要求給予必要的輸入，就能得到輸出的結果輸入3個數黑箱子3個數中最大數求3個數的最大數2.4怎樣表示一個算法常用的方法有：自然語言傳統流程圖結構化流程圖偽代碼……2.4怎樣表示一個算法2.4.1用自然語言表示算法2.4.2用流程圖表示算法2.4.3三種基本結構和改進的流程圖2.4.4用N-S流程圖表示算法2.4.6用計算機語言表示算法2.4.1用自然語言表示算法2.2節(jié)介紹的算法是用自然語言表示的用自然語言表示通俗易懂，但文字冗長，容易出現歧義性用自然語言描述包含分支和循環(huán)的算法，不很方便除了很簡單的問題外，一般不用自然語言2.4.2用流程圖表示算法流程圖是用一些圖框來表示各種操作用圖形表示算法，直觀形象，易于理解起止框輸入輸出框處理框判斷框流程線連接點注釋框x≧0Y……N……一個入口兩個出口2.4.2用流程圖表示算法流程圖是用一些圖框來表示各種操作用圖形表示算法，直觀形象，易于理解起止框輸入輸出框處理框判斷框流程線連接點注釋框③①②①③②③位置不夠防止交叉

例2.6將例2.1的算法用流程圖表示。

求1×2×3×4×5如果需要將最后結果輸出:p=1i>5開始i=2p=p*ii=i+1結束NY

例2.6將例2.1的算法用流程圖表示。

求1×2×3×4×5如果需要將最后結果輸出:p=1輸出ti>5開始i=2t=t*ii=i+1結束NY

例2.8例2.3判定閏年的算法用流程圖表示。判定2000—2500年中的每一年是否閏年，將結果輸出。NYN開始year=2000year不能被4整除year是閏年year不能被100整除year=year+1year>2500結束Yyear不能被400整除year不是閏年year是閏年year不是閏年YNYN通過以上幾個例子可以看出流程圖是表示算法的較好的工具一個流程圖包括以下幾部分：(1)表示相應操作的框(2)帶箭頭的流程線(3)框內外必要的文字說明流程線不要忘記畫箭頭，否則難以判定各框的執(zhí)行次序2.4.3三種基本結構和改進的流程圖2.三種基本結構(1)順序結構AB2.4.3三種基本結構和改進的流程圖2.三種基本結構(2)選擇結構ABYpNAYpN2.4.3三種基本結構和改進的流程圖2.三種基本結構(3)循環(huán)結構①當型循環(huán)結構AYp1NYx<5N0x輸出x的值x+1x輸出1,2,3,4,52.4.3三種基本結構和改進的流程圖2.三種基本結構(3)循環(huán)結構②直到型循環(huán)結構AYp2NYx≧5N0x輸出x的值x+1x輸出1,2,3,4,5以上三種基本結構，有以下共同特點：(1)只有一個入口(2)只有一個出口一個判斷框有兩個出口一個選擇結構只有一個出口(3)結構內的每一部分都有機會被執(zhí)行到。也就是說，對每一個框來說，都應當有一條從入口到出口的路徑通過它(4)結構內不存在“死循環(huán)”由三種基本結構派生出來的結構：ANp2YB根據表達式p的值進行選擇ABp=p1p=p2…MNp=pmp=pn2.4.4用N-S流程圖表示算法N-S流程圖用以下的流程圖符號：ABABYNpA當p1成立A直到p2成立順序結構選擇結構循環(huán)結構（當型）循環(huán)結構（直到型）例2.11將例2.1的求5!算法用N-S圖表示。直到i>5p=1輸出pi=2p=p*ii=i+1例2.13將例2.3判定閏年的算法用N-S圖表示直到year>25002000yearyear+1year否是year%4為0否是輸出year非閏年year%100不為0year%400為0是否輸出year非閏年輸出year閏年輸出year閏年2.4.6用計算機語言表示算法要完成一項工作，包括設計算法和實現算法兩個部分。設計算法的目的是為了實現算法。不僅要考慮如何設計一個算法，也要考慮如何實現一個算法。2.5結構化程序設計方法結構化程序設計強調程序設計風格和程序結構的規(guī)范化，提倡清晰的結構。結構化程序設計方法的基本思路是：把一個復雜問題的求解過程分階段進行，每個階段處理的問題都控制在人們容易理解和處理的范圍內。2.5結構化程序設計方法采取以下方法保證得到結構化的程序：（1）自頂向下；（2）逐步細化；（3）模塊化設計；（4）結構化編碼。2.5結構化程序設計方法三種基本結構（1）順序結構；（2）分支結構（選擇結構）；（3）循環(huán)結構。1、算法的有窮性是指

A）算法程序的運行時間是有限的B）算法程序所處理的數據量是