第二章程序的靈魂——算法.ppt

1、第二章是程序的靈魂算法，以及程序設(shè)計概述。程序應(yīng)該包括數(shù)據(jù)描述和數(shù)據(jù)處理描述。1數(shù)據(jù)描述，即數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)的核心課程之一，關(guān)于它有很多專門的工作，所以我們在本課程中不再重復(fù)。在C語言中，系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)以數(shù)據(jù)類型的形式出現(xiàn)。2數(shù)據(jù)處理的描述，即計算機算法。算法是解決問題的方法和步驟，是程序的靈魂。為此，著名的計算機科學(xué)家尼克勞斯沃思提出了一個公式：數(shù)據(jù)結(jié)構(gòu)算法=程序。事實上，除了數(shù)據(jù)結(jié)構(gòu)和算法，程序還必須使用計算機語言，并采用結(jié)構(gòu)化的方法來表達(dá)它。算法：指的是解決特定問題的一組定義明確的步驟。簡而言之，算法是指對解決方案的準(zhǔn)確而完整的描述。從程序的角度來看，也可以說一個算法是

2、一組有限的指令，它決定了解決一個特定類型問題的操作順序。解決同一個問題有不同的方法和步驟，即不同的算法。算法有優(yōu)點也有缺點。一般來說，我們應(yīng)該選擇運算步驟少、運算速度快、內(nèi)存開銷低(算法的時間和空間效率)的簡單算法。2.1算法概念，購買電視機的步驟：選貨，開發(fā)票，付款，拿發(fā)票，提貨，回家，考大學(xué)，填清單，交注冊費，拿準(zhǔn)考證，考試，拿到錄取通知書，報到，2.2，簡單算法示例，示例1這個算法可以先寫：(1)先找到12個，得到結(jié)果2；(2)將步驟1得到的結(jié)果乘以3，得到結(jié)果6；(3)將6乘以4得到24；(4)將24乘以5，得到120。12345，上面的算法太麻煩了，我們找到一個通用的表示方法。S1:

3、讓變量p，被乘數(shù)，p=1；讓變量I代表乘數(shù)，I=2；S3:將pi的乘積放入被乘數(shù)變量p，它可以表示為：p i pS4:將I的值加1，即I 1i；S5:如果I不大于5，則返回并重新執(zhí)行步驟s3以及隨后的步驟s4和S5；否則，算法結(jié)束。最后一個p是5！的價值。2.如果標(biāo)題更改為13579 11，請撥打13579 11。上述算法稍作修改：s 1: 1 p；s 23360 3 I；s3: p i p如果i11，返回S3；否則，結(jié)束。13579 11.由此可見，該方法所表達(dá)的算法具有通用性和靈活性。S3到s5構(gòu)成一個環(huán)路。當(dāng)實現(xiàn)該算法時，步驟s3、s4、s5等。應(yīng)當(dāng)重復(fù)執(zhí)行，直到某個時刻，當(dāng)執(zhí)行步驟s5

4、時，判斷乘數(shù)I已經(jīng)超過指定值，因此不返回步驟S3。用計算機實現(xiàn)這個循環(huán)很容易。13579 11，請仔細(xì)分析循環(huán)結(jié)束的條件，即步驟s5。如果您正在尋找13579 11，將步驟s5寫成：S5；如果I11，返回s3。這有什么問題？結(jié)果會是什么？有50個學(xué)生想打印出那些分?jǐn)?shù)超過80分的。解答：n是學(xué)生證，n1是第一學(xué)生證，ni是第一學(xué)生證。g代表學(xué)生的分?jǐn)?shù)，gi代表第I個學(xué)生的分?jǐn)?shù)，算法表示如下：S2:如果gi80，打印ni和gi，否則不打印。S3: i 1 i如果i50，則返回s2并繼續(xù)執(zhí)行；否則，算法結(jié)束。在這個例子中，變量I被用作下標(biāo)來控制序列號(哪個學(xué)生，哪個年級)。當(dāng)我超過50時，意味著50

5、名學(xué)生的分?jǐn)?shù)已經(jīng)被處理，算法結(jié)束。在示例4中，判斷2000-2500年的每一年是否為閏年，并輸出結(jié)果。解決辦法：閏年的條件如下：(1)一年可以被4整除，但不能被100整除，就是閏年；例如，在1996年和2004年(2)，可以用100和400等分的年份是閏年。比如1600，2000。不符合這兩個條件的一年不是閏年。算法如下：以y為檢測年份，并采取以下步驟：s 13360 2000y；S2:如果y不能被4整除，則y輸出為“不是閏年”。然后轉(zhuǎn)到s6。S3:如果y可被100整除，并且可被400整除，則輸出y作為“閏年”；否則，輸出y為“不是閏年”。然后轉(zhuǎn)到s6。S4:如果y可被100整除并且可被400

6、整除，輸出y作為“閏年”，然后轉(zhuǎn)到s6。S5:輸出y“不是閏年”。s 6:y 1y；當(dāng)y2500時，轉(zhuǎn)到s2繼續(xù)執(zhí)行，例如y2500，算法停止。(1)使S=0(S作為累積變量)；(2)讓N=1(N代表分母)；(3)S 1/N S(執(zhí)行迭代，S是迭代變量)；(4)北緯1度；(5)如果N100，轉(zhuǎn)至(3)和后續(xù)步驟；否則，執(zhí)行(6)；(6)打印s的值(即需求的總和)。要找到以下系列的值，您可以編寫以下算法：1。有限性：一個算法應(yīng)該包含有限的步驟，而不是無限的步驟；同時，一個算法應(yīng)該在執(zhí)行一定數(shù)量的步驟后完成，它不能是無止境的。事實上，“貧窮”通常指的是“在合理范圍內(nèi)”的有限步驟。如果一臺計算機被允

7、許執(zhí)行一個需要1000年才能完成的算法，這個算法雖然很差，但是超過了合理的限制，人們認(rèn)為這個算法沒有用。2.確定性：算法中的每一步都應(yīng)該是確定的，而不是模糊不清的。也就是說，不應(yīng)該有歧義。特別是，當(dāng)用自然語言描述算法時，我們應(yīng)該注意這一點。例如，“打印出成績優(yōu)異的學(xué)生名單”就有歧義?！皟?yōu)秀成績”是要求每門課程90分以上，還是平均成績超過90分？不清楚，不明確，不適合描述算法步驟。2.3。算法的特點，3 .有0個或更多輸入(即，可能沒有輸入或可能有輸入)。所謂的輸入是指當(dāng)算法被執(zhí)行時從外部世界獲得必要的信息。(外部世界與算法本身有關(guān)，輸入可以是手動鍵盤輸入的數(shù)據(jù)，也可以是程序其他部分傳輸給算法的

8、數(shù)據(jù)。)例如，您可以計算5！(0個輸入)例如，如果你想計算兩個整數(shù)的最大公約數(shù)，你需要輸入兩個整數(shù)m，n(2個輸入)4。有一個或多個輸出(即算法必須得到結(jié)果)。算法的輸出：算法獲得的結(jié)果。算法必須有結(jié)果，沒有結(jié)果的算法是沒有意義的。(結(jié)果可以顯示在屏幕上，或者結(jié)果數(shù)據(jù)可以傳輸?shù)匠绦虻钠渌糠帧?5 .有效性算法的每一步都應(yīng)得到有效的執(zhí)行，并能得到明確的結(jié)果。例如，如果b=0，執(zhí)行a/b不能有效執(zhí)行。2.4 .如何表示算法？要表示一個算法，可以使用不同的方法。常用的算法表示方法：自然語言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、偽代碼、計算機語言等。(重點：傳統(tǒng)流程圖，N-S流程圖)，2.4.1該算法用人們常

9、用的自然語言表達(dá)，可以是中文、英文或其他語言。用自然語言很容易理解；然而，文本冗長，容易產(chǎn)生“歧義”；此外，用自然語言描述包含分支和循環(huán)的算法也不方便。通常不使用自然語言來描述算法，例如描述計算和輸出z=y/x的過程，可以用自然語言描述如下：(1)輸入X，y。(2)判斷X是否為0:如果X=0，輸出錯誤信息；否則計算y/x z和輸出Z.例如，自然語言描述，算法描述語言：它是一種專門用來解釋程序流程的語言。它通常介于自然語言和編程語言之間。它在自然語言中是靈活的，接近于編程語言的描述。注意：一般來說，算法描述語言描述的過程不能直接作為程序使用，最后需要轉(zhuǎn)換成某種編程語言描述的程序。與編程語言的區(qū)別

10、：前者是免費的，不像后者，后者受語法的限制，只要它是以人們可以理解的方式描述的，而不考慮計算機處理應(yīng)該遵循的規(guī)則或其他細(xì)節(jié)。算法描述語言，在編程過程中，一般不可能一開始就用某一種編程語言來編譯一個計算機程序，而是要用一種簡單、直觀、靈活的描述工具來描述處理問題的過程。方案確定后，這個過程被轉(zhuǎn)換成計算機程序。這種轉(zhuǎn)換通常是機械的，不涉及功能的重新設(shè)計或控制過程的改變，而只需要考慮語法要求和編程語言指定的詳細(xì)問題。1.過程描述；2.4.2算法用流程圖表示；流程圖：一些約定的幾何圖形被用來描述算法。用特定的框架表示操作，用箭頭表示算法流程，以及流程圖(符號和含義)。美國標(biāo)準(zhǔn)化協(xié)會的ANSI規(guī)定了一些

11、常用的流程圖符號，這些符號已被世界各地的程序員廣泛采用：起止框、輸入輸出框、判斷選擇框、處理框、流程線、連接點、注釋框、l起止框：表示算法的開始和結(jié)束。通常，內(nèi)部只寫“開始”或“結(jié)束”。l處理框：表示算法的一個處理步驟，賦值操作通常在里面填寫。l輸入/輸出框：表示算法請求輸入所需的數(shù)據(jù)或算法輸出一些結(jié)果。一般來說，“輸入”和“打印/顯示”L菱形框(判斷框)是內(nèi)部填寫的，主要用于判斷給定的條件，并根據(jù)給定的條件是否為真來決定如何進(jìn)行后續(xù)操作。它有一個入口和兩個出口。l連接點：用于連接不同位置繪制的流線。相同數(shù)字的點是相互聯(lián)系的。事實上，相同數(shù)字的點是相同的點，但它們不能分開畫。連接點的使用還可以

12、避免流線的交叉或過長，使流程圖更加清晰。評論框：評論框不是流程圖的重要部分，也不能反映流程和操作。它只是對流程圖中一些方框的操作做了必要的補充說明，以幫助讀者更好地理解流程圖的功能。例子：要求5英鎊！t=1，i=2，t=t*i，i=i 1，i5，end，N，Y，start，傳統(tǒng)的流程圖使用流程線來指示每個塊的執(zhí)行順序，并且對流程線的使用沒有嚴(yán)格的限制。因此，用戶可以不受限制地改變流程，使流程圖不規(guī)則。人們改進(jìn)這個流程圖，規(guī)定幾個基本結(jié)構(gòu)，然后由這些基本結(jié)構(gòu)按照一定的規(guī)則形成算法結(jié)構(gòu)。整個算法結(jié)構(gòu)按照從上到下的順序排列基本結(jié)構(gòu)。這可以在一定程度上提高算法的質(zhì)量。三種基本結(jié)構(gòu)如下：(1)順序結(jié)構(gòu)按

13、照指令的順序執(zhí)行；(2)判斷選擇結(jié)構(gòu)：根據(jù)判斷條件有選擇地改變執(zhí)行流程；(3)循環(huán)結(jié)構(gòu)：有條件地重復(fù)執(zhí)行某個程序塊；(2.4.3)三個基本結(jié)構(gòu)和改進(jìn)的流程圖；(1)順序結(jié)構(gòu)編程，依次執(zhí)行程序語句、塊A、塊B和塊A。a=5；b=10(2)判別和選擇結(jié)構(gòu)化程序，首先判斷條件，如果條件滿足，程序執(zhí)行方框A，否則執(zhí)行方框B；例如，找出a和b的最大值；滿足條件否、滿足、不滿足、執(zhí)行塊A、執(zhí)行塊B、條件成立嗎？執(zhí)行塊A、執(zhí)行塊B、是、否、B最大值？Max=a；max=b；(3)循環(huán)結(jié)構(gòu)的編程。該循環(huán)分為“當(dāng)型循環(huán)”和“直到型循環(huán)”，并計算1100的累積和。int i，sum=0；而(I=100)sum=s

14、um I；I=I 1；在循環(huán)中執(zhí)行指令，直到滿足條件。當(dāng)條件滿足時，在循環(huán)中執(zhí)行指令。i=100？sum=sum I；I=I 1；Y，和=0；三個基本結(jié)構(gòu)有以下共同之處：l只有一個入口：不允許從結(jié)構(gòu)外部隨意轉(zhuǎn)移到結(jié)構(gòu)中的某一點。只有一個出口：不允許從建筑的某個位置隨意轉(zhuǎn)身(跳出來)。l結(jié)構(gòu)的每個部分都有被執(zhí)行的機會。(沒有“死語句”)在L結(jié)構(gòu)中沒有“死循環(huán)”(循環(huán))。已經(jīng)證明，由三個基本結(jié)構(gòu)序列組成的算法結(jié)構(gòu)可以解決任何復(fù)雜的問題。由基本結(jié)構(gòu)組成的算法屬于“結(jié)構(gòu)化”算法。2.4.4算法用N-S流程圖表示，基本結(jié)構(gòu)的順序組合可以表示任何復(fù)雜的算法結(jié)構(gòu)，因此基本結(jié)構(gòu)之間的流程線是多余的，因此美國學(xué)

15、者I . Nasii和B.shneiderman在1973年提出了一種新的流程圖形式。所有算法都寫在一個矩形框中，帶有箭頭的流線被完全去除。這個流程圖被稱為南北結(jié)構(gòu)流程圖(箱線圖)。N-S流程圖適用于結(jié)構(gòu)化編程、序列結(jié)構(gòu)編程、執(zhí)行塊A、執(zhí)行塊B、順序執(zhí)行程序語句、先執(zhí)行操作A、后執(zhí)行操作B、判斷和選擇結(jié)構(gòu)化編程、條件是否滿足、滿足、不滿足、執(zhí)行塊A、執(zhí)行塊B、條件為真時執(zhí)行操作A、條件不為真時執(zhí)行操作B。a、b操作允許空操作，即不做任何事情。注意選擇結(jié)構(gòu)作為一個整體，代表一個基本結(jié)構(gòu)。循環(huán)結(jié)構(gòu)編程，循環(huán)分為“當(dāng)-型循環(huán)”和“直到-型循環(huán)”，當(dāng)條件p滿足時，執(zhí)行循環(huán)中的指令直到條件p滿足，例如：

16、ask for 5！該算法由N-S圖表示、1 t、2 I、t * I t、I I、直到i5、打印t，當(dāng)類型循環(huán)：當(dāng)條件p成立時，重復(fù)執(zhí)行循環(huán)中的指令，直到條件p不成立。當(dāng)類型循環(huán)在決定是否執(zhí)行循環(huán)體之前進(jìn)行判斷時，如果條件p不滿足一次，則循環(huán)體可能不會執(zhí)行一次，當(dāng)條件p滿足時，執(zhí)行循環(huán)中的指令，直到類型循環(huán)：當(dāng)條件p不為真時，重復(fù)執(zhí)行循環(huán)體中的指令，直到條件p成立。直到類型循環(huán)首先執(zhí)行循環(huán)體，然后判斷條件p，所以循環(huán)體至少執(zhí)行一次。直到滿足條件p，執(zhí)行循環(huán)中的指令，2.4.5使用偽代碼來表示算法，這通常用于算法設(shè)計。該算法采用傳統(tǒng)的流程圖和N-S圖表示，直觀易懂，但繪制起來比較麻煩。設(shè)計算法時，可能需要反復(fù)修改，但修改流程圖很麻煩。因此，流程圖適于表示算法，但是為了方便設(shè)計算法，通常使用偽代碼工具。偽代碼用自然語言和計算機語言之間的單詞和符號來描述算法。偽碼不使用圖形符號，書寫方便，格式緊湊，便于向計算機語言算法過渡。用某種編程語言編寫的程序本質(zhì)上是對問題解決方案的描述和最終描述。在一般的編程過程中，不建議一開始就編寫程序，尤其是對于大規(guī)模的程序。程序是程序設(shè)計的最終產(chǎn)品，它需要每一步的精心