1、第二節(jié),算法的編程實現(xiàn),主要內容,1 算法的概念 2 簡單算法舉例 3 算法的特性 4 算法的表示 5 結構化程序設計方法 6 數(shù)值計算算法的收斂與穩(wěn)定性,華羅庚-“燒水泡茶”,“燒水泡茶”有五道工序：1、燒開水 （15分鐘）2、洗茶壺 （2分鐘）3、茶杯 （1分鐘）4、拿茶葉 （1分鐘）5、泡茶 （1分鐘） 燒開水、洗茶壺、茶杯，拿茶葉是泡茶的前提。 問題：請同學們寫出燒水泡茶的具體過程，進行比較和分析，比較的標準是哪個最省時間 。,方法比較,方法1： 第一步：燒水； 第二步：水燒開后，洗刷茶具，拿茶葉； 第三步：沏茶。 方法2： 第一步：燒水； 第二步：燒水過程中，洗刷茶具，拿茶葉； 第三

2、步：水燒開后沏茶。,工序安排不同 甲：燒開水 同時 ，洗茶壺，洗茶杯，拿茶葉 乙：燒開水 之前 ，洗茶壺，洗茶杯，拿茶葉 丙：燒開水 之后 ，洗茶壺，洗茶杯，拿茶葉 花的時間不同， 甲： 16 分鐘 乙： 20 分鐘 丙： 20 分鐘,一個程序應包括兩個方面的內容:,對數(shù)據(jù)的描述：數(shù)據(jù)結構(data structure) 對操作的描述：算法(algorithm) 為解決一個問題而采取的方法和步驟,著名計算機科學家沃思提出一個公式: 數(shù)據(jù)結構 + 算法 = 程序,數(shù)據(jù)結構算法程序設計方法語言工具,完整的程序設計應該是:,1 算法的概念,廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法”。

3、,方法1：1+2，+3，+4，一直加到100 加99次 方法2：100+(1+99)+(2+98)+(49 +51)+50 = 100 + 49100 +50 加51次 方法3：利用等差數(shù)列公式,例： 求,例如,描述太極拳動作的圖解,就是”太極拳的算法”.一首歌曲的樂譜,也可以稱為該歌曲的算法,因為它指定了演奏該歌曲的每一個步驟.設計算法是解決問題的核心。對同一個問題，可有不同的解題方法和步驟,1 算法的概念,為了有效地進行解題，不僅需要保證算法正確，還要考慮算法的質量，選擇合適的算法。希望方法簡單，運算步驟少。,計算機算法可分為兩大類別： 數(shù)值運算算法：求數(shù)值解，例如求方程的根、求函數(shù)的定積

4、分等。 非數(shù)值運算：包括的面十分廣泛，最常見的是用于事務管理領域，例如圖書檢索、人事管理、行車調度管理等。,2 簡單算法舉例,例: 求12345,步驟1：先求12，得到結果2 步驟2：將步驟1得到的乘積2再乘以3，得到結果6 步驟3：將6再乘以4，得24 步驟4：將24再乘以5，得120,太繁瑣,如果要求121000，則要寫999個步驟,S1：使p=1。 S2：使i=2。 S3：使pi，乘積仍放在變量p中，可表示為： pi p S4：使i的值加1，即i+1 i。 S5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否則，算法結束。最后得到p的值就是5!的值。,可以設兩個變量：一

5、個變量代表被乘數(shù)，一個變量代表乘數(shù)。不另設變量存放乘積結果，而直接將每一步驟的乘積放在被乘數(shù)變量中。設p為被乘數(shù)，i為乘數(shù)。用循環(huán)算法來求結果, 算法可改寫：,S1：1p S2：3 i S3：pi p S4：i+2 i S5：若i11，返回S3。否則，結束。,如果題目改為：求13511算法只需作很少的改動：,算法簡練,用這種方法表示的算法具有通用性、靈活性。S3到S5組成一個循環(huán)，在實現(xiàn)算法時 要反復多次執(zhí)行S3，S4，S5等步驟，直到某一時刻，執(zhí)行S5步驟時經過判斷，乘數(shù)i已超過規(guī)定的數(shù)值而不返回S3步驟為止。此時算法結束，變量p的值就是所求結果。,3 算法的特性,有窮性：包含有限的操作步驟

6、。 確定性：算法中的每一個步驟都應當是確定的。 有零個或多個輸入：輸入是指在執(zhí)行算法時需要從外界取得必要的信息。 有一個或多個輸出：算法的目的是為了求解，“解” 就是輸出。 有效性：算法中的每一個步驟都應當能有效地執(zhí)行，并得到確定的結果 。,一個算法應該具有以下特點：,4 算法的表示,可以用不同的方法表示算法，常用的有： 自然語言 傳統(tǒng)流程圖 NS流程圖 偽代碼 PAD圖,4.1 用自然語言表示算法,自然語言就是人們日常使用的語言，可以是漢語或英語或其它語言。用自然語言表示通俗易懂，但文字冗長，容易出現(xiàn)“歧義性”。自然語言表示的含義往往不大嚴格，要根據(jù)上下文才能判斷其正確含義，描述包含分支和循

7、環(huán)的算法時也不很方便。因此，除了那些很簡單的問題外，一般不用自然語言描述算法。,4.2 用流程圖表示算法,美國國家標準化協(xié)會ANSI(American National Standard Institute)規(guī)定了一些常用的流程圖符號：,例 將求5!的算法用流程圖表示,如果需要將最后結果打印出來，可在菱形框的下面加一個輸出框。,小結：,流程圖是表示算法的較好的工具。一個流程圖包括以下幾部分 ： (1)表示相應操作的框； (2)帶箭頭的流程線； (3)框內外必要的文字說明。,三種基本結構 順序結構、選擇結構、循環(huán)結構 用這三種基本結構作為表示一個良好算法的基本單元。,4.3 三種基本結構和N-S

8、流程圖,三種基本結構的圖示：,順序結構,選擇結構,循環(huán)結構的圖示：,當型(While型)循環(huán)結構,直到型(Until型)循環(huán),三種基本結構的共同特點： (1)只有一個入口。 (2)只有一個出口。（請注意：一個菱形判斷框有兩個出口，而一個選擇結構只有一個出口。不要將菱形框的出口和選擇結構的出口混淆。） (3)結構內的每一部分都有機會被執(zhí)行到。 (4)結構內不存在“死循環(huán)”(無終止的循環(huán))。,圖中沒有一條從入口到出口的路徑通過A框,不正確的流程表示：,流程內的死循環(huán),小結：,由三種基本結構順序組成的算法結構，可以解決任何復雜的問題。由基本結構所構成的算法屬于“結構化”的算法，它不存在無規(guī)律的轉向，

9、只在本基本結構內才允許存在分支和向前或向后的跳轉。,4.4 用N-S流程圖表示算法,1973年美國學者I.Nassi和B.Shneiderman提出了一種新的流程圖形式。在這種流程圖中，完全去掉了帶箭頭的流程線。全部算法寫在一個矩形框內，在該框內還可以包含其它的從屬于它的框，或者說，由一些基本的框組成一個大的框。這種流程圖又稱N-S結構化流程圖。,N-S流程圖用以下的流程圖符號：,(1)順序結構,(2)選擇結構,(3)循環(huán)結構,用三種N-S流程圖中的基本框，可以組成復雜的N-S流程圖。圖中的A框或B框，可以是一個簡單的操作，也可以是三個基本結構之一。,A框可以是一個選擇結構,B框可以是一個循環(huán)

10、結構,例 將求5!算法用N-S圖表示,例 將打印50名學生中成績高于80分的學號和成績）算法用N-S圖表示。,沒有輸入數(shù)據(jù),N-S圖表示算法的優(yōu)點,比文字描述直觀、形象、 易于理解；比傳統(tǒng)流程圖緊湊易畫。尤其是它廢除了流程線，整個算法結構是由各個基本結構按順序組成的，N-S流程圖中的上下順序就是執(zhí)行時的順序。用N-S圖表示的算法都是結構化的算法，因為它不可能出現(xiàn)流程無規(guī)律的跳轉，而只能自上而下地順序執(zhí)行。,小結：,一個結構化的算法是由一些基本結構順序組成的。在基本結構之間不存在向前或向后的跳轉，流程的轉移只存在于一個基本結構范圍之內(如循環(huán)中流程的跳轉)；一 個非結構化的算法可以用一個等價的結

11、構化算法代替，其功能不變 。如果一個算法不能分解為若干個基本結構，則它必然不是一個結構化的算法。,4.6 用計算機語言表示算法,概念：用計算機實現(xiàn)算法。計算機是無法識別流程圖和偽代碼的。只有用計算機語言編寫的程序才能被計算機執(zhí)行。因此在用流程圖或偽代碼描述出一個算法后，還要將它轉換成計算機語言程序。 特點：用計算機語言表示算法必須嚴格遵循所用的語言的語法規(guī)則，這是和偽代碼不同的。 用處：要完成一件工作，包括設計算法和實現(xiàn)算法兩個部分。設計算法的目的是為了實現(xiàn)算法。,#include void main( ) int i,t; t=1; i=2; while(i=5) t=t*i; i=i+1;

12、 printf(%dn,t); ,例 2.20 將例2.16表示的算法（求5!）用C語言表示。,5 結構化程序設計方法,一個結構化程序 就是用高級語言表示的結構化算法。用三種基本結構組成的程序必然是結構化的程序，這種程序便于編寫、便于閱讀、便于修改和維護。 結構化程序設計強調程序設計風格和程序結構的規(guī)范化，提倡清晰的結構。 結構化程序設計方法的基本思路是：把一個復雜問題的求解過程 分階段進行，每個階段處理的問題都控制在人們容易理解和處理的范圍內。,采取以下方法來保證得到結構化的程序： 自頂向下； 逐步細化； 模塊化設計； 結構化編碼。,兩種不同的方法： 自頂向下，逐步細化； 自下而上，逐步積累

13、。,用這種方法逐步分解，直到作者認為可以直接將各小段表達為文字語句為止。這種方法就叫 做“自頂向下，逐步細化”。,自頂向下，逐步細化方法的優(yōu)點： 考慮周全，結構清晰，層次分明，作者容易寫，讀者容易看。如果發(fā)現(xiàn)某一部分中有一段內容不妥，需要修改，只需找出該部分修改有關段落即可，與其它部分無關。我們提倡用這種方法設計程序。這就是用工程的方法設計程序。,1.2.2 算法的數(shù)值穩(wěn)定性,用一個算法進行計算，如果初始數(shù)據(jù)誤差在計算中傳播 使計算結果的誤差增長很快，這個算法就是數(shù)值不穩(wěn)定的.,計算 并估計誤差.,由分部積分可得計算 的遞推公式,若計算出 ，,代入（3.2），可逐次求出 的值.,（3.2）,例

14、5,而要算出 就要先計算 .,并取 ，,則得 ，,計算過程中小數(shù)點后第5位的數(shù)字按四舍五入原則舍入.,若用泰勒多項式展開部分和,用4位小數(shù)計算，,截斷誤差,當初值取為 時，用（3.2）遞推的計 算公式為,計算結果見表1-1的 列.,用 近似 產生的誤差 就是初值誤差，,它對后面計算結果是有影響的.,從表中看到 出現(xiàn)負值，,這與一切 相矛盾.,因此，當 較大時，用 近似 顯然是不正確的.,（3.3）,實際上，由積分估值得,計算公式與每步計算都是正確的，計算結果錯誤的原因,主要就是初值 有誤差 ，由此引起以后各步 計算的誤差 滿足關系,容易推得,這說明 有誤差 ，則 就是 的 倍誤差.,例如， ，,若 ，,這就說明 完全不能近似 了. 它表明計算公式（A）,若換一種計算方案.,由（3.3）取 ，,取,則,是數(shù)值不穩(wěn)定的.,由,將公式(3.2)倒過來算，,即由 算出 ，公式為,計算結果見表1-1的 列.,可以看出 與 的誤差不超過 .,反之，當用方案（A）計算時，盡管初值 相當準確，,此例說明，數(shù)值不穩(wěn)