第2章程序的靈魂---算法2-1算法的概念（理解）2-2簡單算法舉例（理解）2-3算法的特性（理解）2-4怎樣表示一個算法(熟練掌握)2-5結構化程序設計方法（了解）1第2章程序的靈魂-算法第2章程序的靈魂---算法本章要點算法的概念算法的表示結構化程序設計方法

2第2章程序的靈魂-算法2-1算法一.程序的概念

程序，就是一系列的操作步驟，計算機程序就是由人事先規定的計算機完成某項工作的操作步驟。每一步驟的具體內容由計算機能夠理解的指令來描述，這些指令告訴計算機“做什么”和“怎樣做”。二.程序設計語言的概念

編寫計算機程序所使用的語言稱為程序設計語言3第2章程序的靈魂-算法一個程序應包括兩個方面的內容:對數據的描述：數據結構(datastructure)對操作的描述：算法(algorithm)著名計算機科學家沃思提出一個公式:

數據結構+算法=程序

數據結構＋算法＋程序設計方法＋語言工具完整的程序設計應該是:2-1算法4第2章程序的靈魂-算法2-1算法定義：算法是指為解決一個問題而采取的方法和步驟。分類：數值運算算法和非數值運算算法算法有優劣為了有效地進行解題，不僅需要保證算法正確，還要考慮算法的質量，選擇合適的算法。希望方法簡單，運算步驟少。5第2章程序的靈魂-算法2-2簡單算法舉例例1-1計算任意長方形的面積例1-2

計算1x2x3x4x5=？例1-3計算1-1/2+1/3-...+1/99-1/100=？例1-4判斷一個數是否素數算法描述6第2章程序的靈魂-算法計算任意長方形的面積問題分析：輸入長和寬計算面積=長X寬輸出面積數據存放：長-len，寬-wid，面積-area設計算法：輸入len和wid的值；計算area=len×wid；輸出面積area的值；7第2章程序的靈魂-算法求1×2×3×4×5=？步驟1：先求1×2，得到結果2步驟2：將步驟1得到的乘積2再乘以3，得到結果6步驟3：將6再乘以4，得24步驟4：將24再乘以5，得120太繁瑣如果要求1×2×…×1000，則要寫999個步驟8第2章程序的靈魂-算法

S1：使p=1S2：使i=2S3：使p×i，乘積仍放在變量p中，可表示為： p×i=>pS4：使i的值加1，即i+1=>

i。

S5：如果i≤5，返回步驟S3；否則，算法結束。最后得到p的值就是5!的值?？梢栽O兩個變量：一個變量代表被乘數，一個變量代表乘數。不另設變量存放乘積結果，而直接將每一步驟的乘積放在被乘數變量中。設p為被乘數，i為乘數。用循環算法來求結果,算法可改寫：

9第2章程序的靈魂-算法S1：1=>pS2：3=>iS3：p×i=>pS4：i+2=>iS5：若i≤1001，返回S3。否則，結束。

如果題目改為：求1×3×5×……×1001算法只需作很少的改動：算法簡練10第2章程序的靈魂-算法1-1/2+1/3-...+1/99-1/100=？提示：首先考慮實現1+2+3+4+…+100其次考慮實現1/1+1/2+1/3+1/4+...+1/100最后考慮實現1/1-1/2+1/3-1/4+...+1/100思路：S1：SUM=0,I=1S2：SUM=SUM+IS3：I=I+1S4：如果I<=100則轉S2，否則轉S5S5：打印SUM的值1/I,P=1P*1/I,P=-P;11第2章程序的靈魂-算法判斷一個數是否素數分析：本題要點是先搞清楚什么是素數。思路：輸入一個大于3的正整數N定義一個變量I從2~N-1，I每取一個值做：如果N能被I整除則中斷循環，N不是素數；否則I繼續取下一個值；若當I取完所有值都不能整除N，則N是素數一個正整數，若不能被除1和它本身以外的任何整數整除，則是素數。12第2章程序的靈魂-算法2.3算法的特性有窮性指一個算法經過有限步驟后停止（或在合理范圍內）確定性算法的每一步都應當是確定的，無歧義的有效性算法的每一步計算機都能有效執行有0個或多個輸入一個算法可以沒有輸入，即執行時無需輸入信息有1個或多個輸出一個算法必須有輸出，運算過程或運算結果13第2章程序的靈魂-算法2.4怎樣表示一個算法常用的算法描述方法：①帶序號的自然語言描述，易懂卻不直觀，不嚴格。②流程圖：靈活、自由、形象、直觀，可表示任何算法。14第2章程序的靈魂-算法一、結構化程序設計的三種基本結構

三種基本結構：順序、選擇、循環，用這三種基本結構作為表示一種良好算法的基本單元。結構化程序設計方法15第2章程序的靈魂-算法二、相關術語

程序：使用語言給計算機的一組指令序列。

結構化程序：用三種基本結構組成的程序就是結構化程序。

程序設計：為求解特定問題而編寫的正確有效的程序。

程序設計語言：編寫程序所用的語言。結構化程序設計方法16第2章程序的靈魂-算法1、順序結構

例如：a=3;b=4;c=a+b;操作的步驟按照書寫的順序執行AB結構化程序設計方法三、三種基本結構17第2章程序的靈魂-算法2、選擇結構

例如：if(x!=0)y=sin(x)/x;elsey=1;PABYN結構化程序設計方法三、三種基本結構18第2章程序的靈魂-算法3、循環結構:根據條件P決定是否重復執行循環體中的操作

例如：sum=0；

i=1;while(i<=100){sum+=i;i++;}先判斷后執行NAPY結構化程序設計方法三、三種基本結構19第2章程序的靈魂-算法循環結構例如：sum=0；

i=1;do{sum+=i;i++;}while(i<=100)先執行后判斷PNAY結構化程序設計方法三、三種基本結構20第2章程序的靈魂-算法結構化程序設計方法二、三種基本結構特點：只有一個入口和一個出口；結構內每一部分都有機會執行到；結構內不存在“死循環”。注：以上三種基本結構順序組成的算法結構可以解決任何復雜的問題。21第2章程序的靈魂-算法常用的算法描述方法：③N-S圖（盒圖）：特點是完全去掉了帶箭頭的流程線，算法的所有處理步驟都寫在一個大矩形框，表示簡單，符合結構化思想。ATPFAB當P1成立

A

A直到P2成立

處理

判斷

循環22第2章程序的靈魂-算法N-S圖：ABAB順序結構PABYNYPNAB選擇結構23第2章程序的靈魂-算法N-S圖：當型循環直到型循環當P1成立

AAP1Y

A直到P2成立PYANN24第2章程序的靈魂-算法常用的算法描述方法：④偽代碼：用介于自然語言與計算機語言之間的文字及符號來描述算法，特點是方便、易懂、便于向計算機語言過渡。25第2章程序的靈魂-算法學習建議：流程圖和N-S圖一定要熟練掌握，偽代碼表示法在學習完基本的流程控制語句后也經常使用。26第2章程序的靈魂-算法例題：計算s=∑n，寫出其算法

S=0,n=1n<=100輸出SN開始結束S=S+nn=n+1Y100n=1流程圖描述：自然語言描述：1、0S單元2、1n單元3、s+ns4、n+1n5、判斷n≤100？是，轉3；否則轉66、輸出S的值27第2章程序的靈魂-算法例題：計算s=∑n，寫出其算法

100n=1偽代碼描述：N—S圖描述：n≤100？s+nsn+1n輸出S的值0s1nBeginsnwhilen≤100{s+nsn+1n}printsend28第2章程序的靈魂-算法2.5結構化程序設計方法核心思想：自