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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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