我們來自五湖四海,不為別的,只因有共同的愛好,為中國互聯網發展出一分力!

算法

2012年10月03日01:18 閱讀: 20761 次
什么是程序?程序= 數據結構+ 算法。

對于面向對象程序設計,強調的是數據結構,而對于面向過程的程序設計語言如C、P a s c a l、F O RT R A N等語言,主要關注的是算法。掌握算法,也是為面向對象程序設計打下一個扎實的基礎。那么,什么是算法呢?

人們使用計算機,就是要利用計算機處理各種不同的問題,而要做到這一點,人們就必須事先對各類問題進行分析,確定解決問題的具體方法和步驟,再編制好一組讓計算機執行的指令即程序,交給計算機,讓計算機按人們指定的步驟有效地工作。這些具體的方法和步驟,其實就是解決一個問題的算法。根據算法,依據某種規則編寫計算機執行的命令序列,就是編制程序,而書寫時所應遵守的規則,即為某種語言的語法。

由此可見,程序設計的關鍵之一,是解題的方法與步驟,是算法。學習高級語言的重點,就是掌握分析問題、解決問題的方法,就是鍛煉分析、分解,最終歸納整理出算法的能力。與之相對應,具體語言,如C語言的語法是工具,是算法的一個具體實現。所以在高級語言的學習中,一方面應熟練掌握該語言的語法,因為它是算法實現的基礎,另一方面必須認識到算法的重要性,加強思維訓練,以寫出高質量的程序。

下面通過例子來介紹如何設計一個算法:

[例1-4] 輸入三個數,然后輸出其中最大的數。

首先,得先有個地方裝這三個數,我們定義三個變量A、B、C,將三個數依次輸入到A、B、C中,另外,再準備一個M A X裝最大數。由于計算機一次只能比較兩個數,我們首先把A與B比,大的數放入M A X中,再把M A X 與C比,又把大的數放入M A X中。最后,把M A X輸出,此時M A X中裝的就是A、B、C三數中最大的一個數。算法可以表

示如下:

1) 輸入A、B、C。

2) A與B中大的一個放入M A X中。

3) 把C與M A X中大的一個放入M A X中。

4) 輸出M A X,M A X即為最大數。

其中的2 )、3 )兩步仍不明確,無法直接轉化為程序語句,可以繼續細化:

2) 把A與B中大的一個放入M A X中,若A > B,則MAX ←A;否則MAX ←B。

3) 把C與M A X中大的一個放入M A X中,若C > M A X,則M A X←C。

于是算法最后可以寫成:

1) 輸入A,B,C。

2) 若A > B,則MAX ←A;

否則M A X←B。

3) 若C > M A X,則M A X←C。

4) 輸出M A X,M A X即為最大數。
這樣的算法已經可以很方便地轉化為相應的程序語句了。

[例1-5] 猴子吃桃問題:有一堆桃子不知數目,猴子第一天吃掉一半,覺得不過癮,又多吃了一只,第二天照此辦理,吃掉剩下桃子的一半另加一個,天天如此,到第十天早上,猴子發現只剩一只桃子了,問這堆桃子原來有多少個?

此題粗看起來有些無從著手的感覺,那么怎樣開始呢?假設第一天開始時有a1只桃子,第二天有a2只,. . .,第9天有a9只,第1 0天是a1 0只,在a1, a2, . . .,a1 0中,只有a1 0= 1是知道的,現要求a1,而我們可以看出,a1, a2, . .,a1 0之間存在一個簡單的關系:

a9= 2 * ( a1 0+ 1 )

a8= 2 * ( a9+ 1 )

a1= 2 * ( a2+ 1 )

也就是:ai= 2 * ( ai + 1+1) i=9,8,7,6,...,1

這就是此題的數學模型。

再考察上面從a9,a8直至a1的計算過程,這其實是一個遞推過程,這種遞推的方法在計算機解題中經常用到。另一方面,這九步運算從形式上完全一樣,不同的只是ai的下標而已。由此,我們引入循環的處理方法,并統一用a0表示前一天的桃子數,a1表示后一天的桃子數,將算法改寫如下:

1) a1=1; {第1 0天的桃子數,a1的初值}

i = 9。{計數器初值為9}

2) a0= 2 * ( a1+ 1 )。{計算當天的桃子數}

3) a1= a0。{將當天的桃子數作為下一次計算的初值}

4) i=i-1。

5) 若i > = 1,轉2 )。

6) 輸出a0的值。

其中2 )~5 )步為循環。



 

這就是一個從具體到抽象的過程,具體方法是:

1) 弄清如果由人來做,應該采取哪些步驟。

2) 對這些步驟進行歸納整理,抽象出數學模型。

3) 對其中的重復步驟,通過使用相同變量等方式求得形式的統一,然后簡練地用循環解決。

算法的描述方法有自然語言描述、偽代碼、流程圖、N - S圖、PA D 圖等。

1.4.1 流程圖與算法的結構化描述

1. 流程圖

流程圖是一種傳統的算法表示法,它利用幾何圖形的框來代表各種不同性質的操作,用流程線來指示算法的執行方向。由于它簡單直觀,所以應用廣泛,特別是在早期語言階段,只有通過流程圖才能簡明地表述算法,流程圖成為程序員們交流的重要手段,直到結構化的程序設計語言出現,對流程圖的依賴才有所降低。

下面介紹常見的流程圖符號及流程圖的例子。
本章例1 - 1的算法的流程圖如圖1 - 2所示。本章例1 - 2的算法的流程圖如圖1 - 3所示。在流程圖中,判斷框左邊的流程線表示判斷條件為真時的流程,右邊的流程線表示條件為假時的流程,有時就在其左、右流程線的上方分別標注“真”、“假”或“T”、“F”或“Y”、“N”。



另外還規定,流程線是從下往上或從右向左時,必須帶箭頭,除此以外,都不畫箭頭,流程線的走向總是從上向下或從左向右。

2. 算法的結構化描述

早期的非結構化語言中都有g o t o語句,它允許程序從一個地方直接跳轉到另一個地方去。執行這樣做的好處是程序設計十分方便靈活,減少了人工復雜度,但其缺點也是十分突出的,一大堆跳轉語句使得程序的流程十分復雜紊亂,難以看懂也難以驗證程序的正確性,如果有錯,排起錯來更是十分困難。這種轉來轉去的流程圖所表達的混亂與復雜,正是軟件危機中程序人員處境的一個生動寫照。而結構化程序設計,就是要把這團亂麻理清。

經過研究,人們發現,任何復雜的算法,都可以由順序結構、選擇(分支)結構和循環結構這三種基本結構組成,因此,我們構造一個算法的時候,也僅以這三種基本結構作為“建筑單元”,遵守三種基本結構的規范,基本結構之間可以并列、可以相互包含,但不允許交叉,不允許從一個結構直接轉到另一個結構的內部去。正因為整個算法都是由三種基本結構組成的,就像用模塊構建的一樣,所以結構清晰,易于正確性驗證,易于糾錯,這種方法,就是結構化方法。遵循這種方法的程序設計,就是結構化程序設計。

相應地,只要規定好三種基本結構的流程圖的畫法,就可以畫出任何算法的流程圖。

(1) 順序結構

順序結構是簡單的線性結構,各框按順序執行。其流程圖的基本形態如圖1 - 4所示,語句的執行順序為:A→B→C。

(2) 選擇(分支)結構

這種結構是對某個給定條件進行判斷,條件為真或假時分別執行不同的框的內容。其基本形狀有兩種,如圖1-5 a)、b)所示。圖1-5 a)的執行序列為:當條件為真時執行A,否則執行B;圖1 - 5 b)的執行序列為:當條件為真時執行A,否則什么也不做。

1 、(3) 循環結構循環結構有兩種基本形態:w h i l e型循環和d o - w h i l e型循環。
2、a. while 型循環如圖1 - 6所示。其執行序列為:當條件為真時,反復執行A,一旦條件為假,跳出循環,執行循環緊后的 語句。



 

b. do-while型循環如圖1 - 7所示。

執行序列為:首先執行A,再判斷條件,條件為真時,一直循環執行A,一旦條件為假,結束循環,執行循環緊后的下一條語句。

在圖1 - 6、圖1 - 7中,A被稱為循環體,條件被稱為循環控制條件。要注意的是:

1) 在循環體中,必然對條件要判斷的值進行修改,使得經過有限次循環后,循環一定能結束,如圖1 - 3中的i = i - 1。2) 當型循環中循環體可能一次都不執行,而直到型循環則至少執行一次循環體。3) 直到型循環可以很方便地轉化為當型循環,而當型循環不一定能轉化為直到型循環。

例如,圖1 - 7可以轉化為圖1 - 8。

2 用N-S圖描述算法

N - S圖是另一種算法表示法,是由美國人I . N a s s i和B . S h n e i d e r m a n共同提出的,其根據是:既然任何算法都是由前面介紹的三種結構組成,所以各基本結構之間的流程線就是多余的,因此,N - S圖也是算法的一種結構化描述方法。

N - S圖中,一個算法就是一個大矩形框,框內又包含若干基本的框,三種基本結構的N - S 圖描述如下所示:

1. 順序結構如圖1 - 9所示,執行順序先A后B。
2. 選擇結構
對應于圖1 - 5的N - S圖為圖1 - 1 0。圖1-10 a)條件為真時執行A,條件為假時執行B。圖1 - 1 0 b )條件為真時執行A,為假時什么都不做。


3. 循環結構
1) while型循環的N - S圖如圖1 - 11所示,條件為真時一直循環執行循環體A,直到條件為假時才跳出循環。
2) do-while型循環的N - S圖如圖1 - 1 2,一直循環執行循環體A,直到條件為假時才跳出循環。
本章例1 - 1的N - S圖如圖1 - 1 3,例1 - 2的N - S圖如圖1 - 1 4。應該說,N - S圖比流程圖更直觀易懂,而且相對簡練一些。



3 用PAD圖描述算法
PA D(Problem Analysis Diagram),是近年來在軟件開發中被廣泛使用的一種算法的圖形表示法,與前述的流程圖、N - S圖相比,流程圖、N - S圖都是自上而下的順序描述,而PA D圖除了自上而下以外,還有自左向右的展開,所以,如果說流程圖、N - S圖是一維的算法描述的話,則PA D圖就是二維的,它能展現算法的層次結構,更直觀易懂。
下面是PA D圖的幾種基本形態:
1. 順序結構:
如圖1 - 1 5所示。
2. 選擇結構
(1) 單分支選擇,條件為真執行A,如圖1-16 a)。
(2) 兩分支選擇,如圖1-16 b),條件為真執行A,為假執行B。
(3) 多分支選擇,如圖1-16 c),當I = I1時執行A,I= I2時執行B,I = I3時執行C,I = I4時執行D。

3. 循環結構
如圖1 - 1 7所示。圖1-17 a)為w h i l e型循環,圖1-17 b)為d o - w h i l e型循環。

本章例1 . 1的PA D圖如圖1 - 1 8,例1 - 2的PA D圖如圖1 - 1 9。

分享到: 更多
藍客門戶
©2001-2019 中國藍客聯盟 版權所有.
關于藍客聯盟歷史宗旨章程技術服務聯系我們藍客社區

女校剑道部闯关