計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)-王信峰版第2節(jié)-算法

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

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

3、,方法1：1+2，+3，+4，一直加到100 加99次 方法2：100+(1+99)+(2+98)+(49 +51)+50 = 100 + 49100 +50 加51次 方法3：利用等差數(shù)列公式,例： 求,例如,描述太極拳動(dòng)作的圖解,就是”太極拳的算法”.一首歌曲的樂譜,也可以稱為該歌曲的算法,因?yàn)樗付搜葑嘣摳枨拿恳粋€(gè)步驟.設(shè)計(jì)算法是解決問題的核心。對(duì)同一個(gè)問題，可有不同的解題方法和步驟,1 算法的概念,為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。希望方法簡(jiǎn)單，運(yùn)算步驟少。,計(jì)算機(jī)算法可分為兩大類別： 數(shù)值運(yùn)算算法：求數(shù)值解，例如求方程的根、求函數(shù)的定積

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

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

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

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

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

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

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

11、構(gòu)化算法代替，其功能不變 。如果一個(gè)算法不能分解為若干個(gè)基本結(jié)構(gòu)，則它必然不是一個(gè)結(jié)構(gòu)化的算法。,4.6 用計(jì)算機(jī)語言表示算法,概念：用計(jì)算機(jī)實(shí)現(xiàn)算法。計(jì)算機(jī)是無法識(shí)別流程圖和偽代碼的。只有用計(jì)算機(jī)語言編寫的程序才能被計(jì)算機(jī)執(zhí)行。因此在用流程圖或偽代碼描述出一個(gè)算法后，還要將它轉(zhuǎn)換成計(jì)算機(jī)語言程序。 特點(diǎn)：用計(jì)算機(jī)語言表示算法必須嚴(yán)格遵循所用的語言的語法規(guī)則，這是和偽代碼不同的。 用處：要完成一件工作，包括設(shè)計(jì)算法和實(shí)現(xiàn)算法兩個(gè)部分。設(shè)計(jì)算法的目的是為了實(shí)現(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 結(jié)構(gòu)化程序設(shè)計(jì)方法,一個(gè)結(jié)構(gòu)化程序 就是用高級(jí)語言表示的結(jié)構(gòu)化算法。用三種基本結(jié)構(gòu)組成的程序必然是結(jié)構(gòu)化的程序，這種程序便于編寫、便于閱讀、便于修改和維護(hù)。 結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)。 結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思路是：把一個(gè)復(fù)雜問題的求解過程 分階段進(jìn)行，每個(gè)階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。,采取以下方法來保證得到結(jié)構(gòu)化的程序： 自頂向下； 逐步細(xì)化； 模塊化設(shè)計(jì)； 結(jié)構(gòu)化編碼。,兩種不同的方法： 自頂向下，逐步細(xì)化； 自下而上，逐步積累

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

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