計(jì)算機(jī)等級(jí)考試二級(jí)C語(yǔ)言常用的算法

1、計(jì)算機(jī)等級(jí)考試二級(jí)C 語(yǔ)言常用的算法什么是程序？程序= 數(shù)據(jù)結(jié)構(gòu) + 算法。對(duì)于面向?qū)ο蟪绦蛟O(shè)計(jì)，強(qiáng)調(diào)的是數(shù)據(jù)結(jié)構(gòu)，而對(duì)于面向過(guò)程的程序設(shè)計(jì)語(yǔ)言如C、 Pas c a l 、 F O RT R A N 等語(yǔ)言，主要關(guān)注的是算法。掌握算法，也是為面向?qū)ο蟪绦蛟O(shè)計(jì)打下一個(gè)扎實(shí)的基礎(chǔ)。那么，什么是算法呢？人們使用計(jì)算機(jī)，就是要利用計(jì)算機(jī)處理各種不同的問(wèn)題，而要做到這一點(diǎn)，人們就必須事先對(duì)各類(lèi)問(wèn)題進(jìn)行分析，確定解決問(wèn)題的具體方法和步驟，再編制好一組讓計(jì)算機(jī)執(zhí)行的指令即程序，交給計(jì)算機(jī)，讓計(jì)算機(jī)按人們指定的步驟有效地工作。這些具體的方法和步驟，其實(shí)就是解決一個(gè)問(wèn)題的算法。根據(jù)算法，依據(jù)某種規(guī)則編寫(xiě)計(jì)算機(jī)

2、執(zhí)行的命令序列，就是編制程序，而書(shū)寫(xiě)時(shí)所應(yīng)遵守的規(guī)則，即為某種語(yǔ)言的語(yǔ)法。由此可見(jiàn)， 程序設(shè)計(jì)的關(guān)鍵之一， 是解題的方法與步驟， 是算法。 學(xué)習(xí)高級(jí)語(yǔ)言的重點(diǎn)，就是掌握分析問(wèn)題、解決問(wèn)題的方法，就是鍛煉分析、分解，最終歸納整理出算法的能力。與之相對(duì)應(yīng)，具體語(yǔ)言，如C語(yǔ)言的語(yǔ)法是工具，是算法的一個(gè)具體實(shí)現(xiàn)。所以在高級(jí)語(yǔ)言的學(xué)習(xí)中，一方面應(yīng)熟練掌握該語(yǔ)言的語(yǔ)法，因?yàn)樗撬惴▽?shí)現(xiàn)的基礎(chǔ)，另一方面必須認(rèn)識(shí)到算法的重要性，加強(qiáng)思維訓(xùn)練，以寫(xiě)出高質(zhì)量的程序。下面通過(guò)例子來(lái)介紹如何設(shè)計(jì)一個(gè)算法： 例 1-4 輸入三個(gè)數(shù)，然后輸出其中的數(shù)。首先，得先有個(gè)地方裝這三個(gè)數(shù)，我們定義三個(gè)變量A B、C,將三個(gè)數(shù)依次

3、輸入到A、B、C中，另外，再準(zhǔn)備一個(gè)M A X裝數(shù)。由于計(jì)算機(jī)一次只能比較兩個(gè)數(shù)，我們首先把 A與B 比，大的數(shù)放入 M A X 中，再把 M A X 與 C 比，又把大的數(shù)放入 M A X 中。最后，把M A X輸出，此時(shí)M A X中裝的就是A、B、C三數(shù)中的一個(gè)數(shù)。算法可以表示如下：1) 輸入A、 B、 C。2) A與B中大的一個(gè)放入M A X中。3)把C與M A X中大的一個(gè)放入 M A X中。4) 輸出 M A X ， M A X 即為數(shù)。其中的 2 ) 、 3 ) 兩步仍不明確，無(wú)法直接轉(zhuǎn)化為程序語(yǔ)句，可以繼續(xù)細(xì)化：2)把A與B中大的一個(gè)放入 M A X中，若 A B ,則 MAXA

4、;否則 MAXB。3)把C與M A X中大的一個(gè)放入 M A X中，若 C M A X ,則 M A XCo 于是算法最后可以寫(xiě)成：1) 輸入A， B， C。2)若 A B ,則 MAX A;否則M A XB。3)若 C M A X ,則 M A XC。4) 輸出 M A X ， M A X 即為數(shù)。這樣的算法已經(jīng)可以很方便地轉(zhuǎn)化為相應(yīng)的程序語(yǔ)句了。 例 1-5 猴子吃桃問(wèn)題：有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺(jué)得不過(guò)癮，又多吃了一只，第二天照此辦理，吃掉剩下桃子的一半另加一個(gè)，天天如此，到第十天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問(wèn)這堆桃子原來(lái)有多少個(gè)？此題粗看起來(lái)有些無(wú)從著手的感覺(jué)，那么怎

5、樣開(kāi)始呢？假設(shè)第一天開(kāi)始時(shí)有a1 只桃子，第二天有 a2 只， . . . ，第 9 天有 a9 只，第 1 0 天是 a1 0 只，在 a1, a2, . . .， a1 0 中，只有al 0= 1是知道的，現(xiàn)要求 al,而我們可以看出，a1, a2, . ., al 0之間存在一個(gè)簡(jiǎn)單的關(guān)系：a9= 2 * ( a1 0+ 1 )a8= 2 * ( a9+ 1 ) 1 Ia1= 2 * ( a2+ 1 )也就是： ai= 2 * ( ai + 1+1) i=9,8,7,6,.,1這就是此題的數(shù)學(xué)模型。再考察上面從a9 ， a8 直至 a1 的計(jì)算過(guò)程，這其實(shí)是一個(gè)遞推過(guò)程，這種遞推的方法在

6、計(jì)算機(jī)解題中經(jīng)常用到。 另一方面， 這九步運(yùn)算從形式上完全一樣， 不同的只是ai 的下標(biāo)而已。由此，我們引入循環(huán)的處理方法，并統(tǒng)一用 a0 表示前一天的桃子數(shù)， a1 表示后一天的桃子數(shù)，將算法改寫(xiě)如下：a1=1; 第1 0天的桃子數(shù)，al的初值i = 9 。計(jì)數(shù)器初值為9a0= 2 * ( a1+ 1 )。計(jì)算當(dāng)天的桃子數(shù)a1= a0 。 將當(dāng)天的桃子數(shù)作為下一次計(jì)算的初值i=i-1。若 i = 1 ，轉(zhuǎn) 2 ) 。輸出a0 的值。其中2 )5 )步為循環(huán)。這就是一個(gè)從具體到抽象的過(guò)程，具體方法是：弄清如果由人來(lái)做，應(yīng)該采取哪些步驟。對(duì)這些步驟進(jìn)行歸納整理，抽象出數(shù)學(xué)模型。對(duì)其中的重復(fù)步驟，

7、 通過(guò)使用相同變量等方式求得形式的統(tǒng)一， 然后簡(jiǎn)練地用循環(huán)解決。算法的描述方法有自然語(yǔ)言描述、偽代碼、流程圖、 N - S 圖、 PA D 圖等。1.4.1 流程圖與算法的結(jié)構(gòu)化描述流程圖流程圖是一種傳統(tǒng)的算法表示法，它利用幾何圖形的框來(lái)代表各種不同性質(zhì)的操作，用流程線(xiàn)來(lái)指示算法的執(zhí)行方向。由于它簡(jiǎn)單直觀，所以應(yīng)用廣泛，特別是在早期語(yǔ)言階段，只有通過(guò)流程圖才能簡(jiǎn)明地表述算法，流程圖成為程序員們交流的重要手段，直到結(jié)構(gòu)化的程序設(shè)計(jì)語(yǔ)言出現(xiàn)，對(duì)流程圖的依賴(lài)才有所降低。下面介紹常見(jiàn)的流程圖符號(hào)及流程圖的例子。本章例 1 - 1 的算法的流程圖如圖 1 - 2 所示。本章例 1 - 2 的算法的流程圖如圖 1 - 3所示。在流程圖中，判斷框左邊的流程線(xiàn)表示判斷條件為真時(shí)的流程，右邊的流程線(xiàn)表示條件為假時(shí)的流程，有時(shí)就在其左、右流程線(xiàn)的上方分別標(biāo)注真、假或T、F或Y、N。另外還規(guī)定，流程線(xiàn)是從下往上或從右向左時(shí)，必須帶箭頭，除此以外，都不畫(huà)箭頭，流程線(xiàn)的走向總是從上向下或從左向右。算法的結(jié)構(gòu)化描述早期的非結(jié)構(gòu)化語(yǔ)言中都有g(shù) o t o 語(yǔ)句，它允許程序從一個(gè)地方直接跳轉(zhuǎn)到另一個(gè)地方去。執(zhí)行這樣做的好處是程序設(shè)計(jì)十分方便靈活，減少了人工復(fù)雜度，但其缺點(diǎn)也是