## 1內容介紹： 算法 一個程序應包括： l 對數據的描述。在程序中要指定數據的類型和數據的組織形式，即數據結構（data structure）。 l 對操作的描述。即操作步驟，也就是算法（algorithm）。Nikiklaus Wirth提出的公式： 數據結構+算法\=程序 程序\=算法+數據結構+程序設計方法+語言工具和環境 這4個方面是一個程序涉及人員所應具備的知識。 本課程的目的是使同學知道怎樣編寫一個C程序，進行編寫程序的初步訓練，因此，只介紹算法的初步知識。 ## 2.1 算法的概念 做任何事情都有一定的步驟。為解決一個問題而采取的方法和步驟，就稱為算法。 l 計算機算法：計算機能夠執行的算法。 l 計算機算法可分為兩大類： n 數值運算算法：求解數值； n 非數值運算算法：事務管理領域。 ## 2.2簡單算法舉例 【例2.1】求1×2×3×4×5。 最原始方法： 步驟1：先求1×2，得到結果2。 步驟2：將步驟1得到的乘積2乘以3，得到結果6。 步驟3：將6再乘以4，得24。 步驟4：將24再乘以5，得120。 這樣的算法雖然正確，但太繁。 改進的算法： S1: 使t=1 S2: 使i=2 S3: 使t×i, 乘積仍然放在在變量t中，可表示為t×i→t S4: 使i的值+1，即i+1→i S5: 如果i≤5, 返回重新執行步驟S3以及其后的S4和S5；否則，算法結束。 如果計算100！只需將S5:若i≤5改成i≤100即可。 如果該求1×3×5×7×9×11，算法也只需做很少的改動： S1: 1→t S2: 3→i S3: t×i→t S4: i+2→t S5:若i≤11, 返回S3，否則，結束。 該算法不僅正確，而且是計算機較好的算法，因為計算機是高速運算的自動機器，實現循環輕而易舉。 思考：若將 S5寫成：S5:若i＜11, 返回S3;否則，結束。 【例2.2】有50個學生，要求將他們之中成績在80分以上者打印出來。 如果，n表示學生學號，ni表示第i個學生學號；g表示學生成績，gi表示第i個學生成績； 則算法可表示如下： S1: 1→i S2: 如果gi≥80，則打印ni和gi，否則不打印 S3: i+1→i S4:若i≤50, 返回S2，否則，結束。 【例2.3】判定2000 — 2500年中的每一年是否閏年，將結果輸出。 潤年的條件： 1) 能被4整除，但不能被100整除的年份； 2) 能被100整除，又能被400整除的年份； 設y為被檢測的年份，則算法可表示如下： S1: 2000→y S2:若y不能被4整除，則輸出y“不是閏年”，然后轉到S6 S3:若y能被4整除，不能被100整除，則輸出y“是閏年”，然后轉到S6 S4:若y能被100整除，又能被400整除，輸出y“是閏年” 否則輸出y“不是閏年”，然后轉到S6 S5:輸出y“不是閏年”。 S6:y+1→y S7:當y≤2500時, 返回S2繼續執行，否則，結束。  ## 2.3 算法的特性 1 有窮性：一個算法應包含有限的操作步驟而不能是無限的。 2 確定性：算法中每一個步驟應當是確定的，而不能應當是含糊的、模棱兩可的。 3 有零個或多個輸入。 4 有一個或多個輸出。 5 有效性：算法中每一個步驟應當能有效地執行，并得到確定的結果。 對于程序設計人員，必須會設計算法，并根據算法寫出程序。 ## 2.4 怎樣表示一個算法 ### 2.4.1 用自然語言表示算法 除了很簡單的問題，一般不用自然語言表示算法。 ### 2.4.2 用流程圖表示算法 流程圖表示算法，直觀形象，易于理解。  【例2.6】將例2.1求5!的算用流程圖表示。  【例2.7】將例2.2的算用流程圖表示。  【例2.8】將例2.3判定閏年的算用流程圖表示。  ### 2.4.3 三種基本結構和改進的流程圖 1. 順序結構： 從算法開始至算法結束，每個步驟依次順序執行。  2. 選擇結構：在算法的執行過程中，需要根據條件的不同而執行不同的執行路徑。   3. 循環結構：在算法的執行過程中，根據條件需要重復執行某些步驟。 下面是 “當型”循環 和 “直到型”循環示意圖：   三種基本結構的共同特點： 1 只有一個入口； 2 只有一個出口； 3 結構內的每一部分都有機會被執行到；（請注意：一個菱形判斷框有兩個出口，而一個選擇結構只有一個出口。不要將菱形框的出口和選擇結構的出口混淆。） 4 結構內不存在“死循環”（無終止的循環）。 ### 2.4.4 用N-S流程圖表示算法 1973年美國學者提出了一種新型流程圖：N-S流程圖。 順序結構：  選擇結構：  循環結構：   ### 2.4.5 用偽代碼表示算法 偽代碼使用介于自然語言和計算機語言之間的文字和符號來描述算法。 ### 2.4.6 用計算機語言表示算法 1 我們的任務是用計算機解題，就是用計算機實現算法； 2 用計算機語言表示算法必須嚴格遵循所用語言的語法規則。 【例2.20】求1×2×3×4×5用C語言表示。 ``` #include <stdio.h> #include <stdlib.h> main(){ int i,t; t=1; i=2; while(i<=5) { t=t\*i; i=i+1; } //輸出結果信息 printf("%d",t); } ``` ## 2.5 結構化程序設計方法 1 自頂向下； 2 逐步細化； 3 模塊化設計； 4 結構化編碼；