1、第九章 程序設計基礎計算機基礎知識19.1 算法與程序設計概述 2022/9/25第九章 程序設計基礎計算機基礎知識19.1 算法與程序設計9.1.1 程序的概念 9.1.2 算法的概念及特征 1)算法的特征 2)算法的評價 9.1.3 算法的表示方法1) 用自然語言表示2) 用傳統流程圖表示3) N-S流程圖4) 用偽代碼表示9.1.4 簡單的程序設計實例 (下一講)9.1 算法與程序設計計算機基礎知識22022/9/259.1.1 程序的概念 9.1 算法與程序設計計算機1、程序 (先看生活中的程序)現實生活中，程序的直觀特征是按事先安排的步驟，一步步完成一系列動作，這種對活動過程的步驟描

2、述就是一個“程序”。在計算機領域，程序是指為讓計算機完成特定的任務而設計的指令序列。它是程序設計人員編寫的、計算機能夠理解并執行的一些命令的集合，是解決問題的具體步驟在計算機中的實現。9.1.1 程序的概念計算機基礎知識32022/9/251、程序 (先看生活中的程序)9.1.1 程序的概念計算計算機中的問題事例：例1：求解一元二次方程4.34651.24X+8=0例2：求解一元二次方程 a bXc=0例3：設a0，b0，c0，若以正數a,b,c為三角的三條邊，求三角形abc的面積？可利用海倫公式：例4：求10以上200以下的整數中，能被3整除但不能被5整除的所有數據之和?9.1.1 程序的概

3、念計算機基礎知識42022/9/25計算機中的問題事例：9.1.1 程序的概念計算機基礎知識計算機中的程序與日常生活中的程序的概念是類似的，只不過執行日常生活程序的主體是人，而執行計算機程序的主體是計算機。計算機程序就是要由計算機進行解釋和執行的程序。它表示的是計算機處理事務的時間順序和處理問題的步驟。程序只能由計算機可以解釋和執行的基本操作組成，組成計算機程序的基本單位一般稱為指令，因此簡單的說，程序就是事先編制好的具有特定功能的指令序列。9.1.1 程序的概念計算機基礎知識52022/9/25計算機中的程序與日常生活中的程序的概念是類似的，只不過執行日2、程序設計既然程序是按一定次序編排的

4、指令序列，那么編寫指令序列的過程就是程序設計。用什么來編寫指令序列？由于指令序列是給計算機執行的，因此這些指令應該是以計算機能夠理解的語言表示的，這種語言就是程序設計語言。現在能夠充當人和計算機之間的交流工具的，就是計算機語言，包括各種命令語言和程序設計語言，主要是程序設計語言。9.1.1 程序的概念計算機基礎知識62022/9/252、程序設計9.1.1 程序的概念計算機基礎知識6202*例1的 FoxPro 程序A=4.346B=-51.24C=8X1=(-B+SQRT(B*B-4*A*C)/(2*A)X2=(-B-SQRT(B*B-4*A*C)/(2*A)? X1=,X1? X2=,X2

5、9.1.1 程序的概念計算機基礎知識72022/9/25*例1的 FoxPro 程序9.1.1 程序的概念計算機*例2的 FoxPro 程序INPUT 輸入數據到A TO AINPUT 輸入數據到B TO BINPUT 輸入數據到C TO CIF B*B-4*A*C=0 X1=(-B+SQRT(B*B-4*A*C)/(2*A) X2=(-B-SQRT(B*B-4*A*C)/(2*A) ? X1=,X1 ? X2=,X2ELSE ? 無實數解!ENDIF9.1.1 程序的概念計算機基礎知識82022/9/25*例2的 FoxPro 程序9.1.1 程序的概念計算機*例3的 C語言程序#inclu

6、demain() float a,b,c,p,area; scanf(%f,%f,%f,&a,&b,&c); if (a+bc) &(a+cb)&(b+ca) p=(a+b+c)/2.0; area=sqrt(p*(p-a)*(p-b)(p-c); printf(a=%7.2f,b=%7.2f,c=%7.2f,p=%7.2fn,a,b,c,p); printf(area=%7.2fn,area); else printf(abc不能構成三角形!);9.1.1 程序的概念計算機基礎知識92022/9/25*例3的 C語言程序9.1.1 程序的概念計算機基礎知識*例4的 FoxPro程序sum=0

7、n=10do while n200 if mod(n,3)=0 and int(n/5)n/5 s=s+n endif stor n+1 to nenddo 5,10 say 10200內被3整除但不能被5整除的所有數據之和為: +str(s,5)9.1.1 程序的概念計算機基礎知識102022/9/25*例4的 FoxPro程序9.1.1 程序的概念計算機基1、算法的概念所謂算法是指解題方案的準確而完整的描述。算法是程序的靈魂，計算機程序設計的實質是算法的設計。自從計算機廣泛用于解決現實問題以來，人們積累了大量的算法，這些算法是前人思想的結晶，也是新算法產生的基礎。學習和研究這些算法，對解決

8、實際問題，以及研究新的算法都是極為必要的。 每個算法實際上是按解題要求從所有的指令系統操作中選擇合適的操作所組成的一組指令序列。因此，計算機算法就是計算機能處理的操作所組成的指令序列。9.1.2 算法的概念及特征計算機基礎知識112022/9/251、算法的概念9.1.2 算法的概念及特征計算機基礎知識11一個算法的功能不僅取決于所選用的操作，而且還與各操作之間的執行順序有關。算法中各操作間的執行順序稱為算法的控制結構2、算法的基本要素一個算法通常由兩種基本要素組成，一是對數據對象的運算和操作，二是算法的控制結構。一個算法的運算操作或控制結構無論是簡單還是復雜，一般必須滿足以下五個重要特性：有

9、窮性、確定性、可行性、輸入、輸出9.1.2 算法的概念及特征計算機基礎知識122022/9/25一個算法的功能不僅取決于所選用的操作，而且還與各操作之間的執1）有窮性對于任意一組合法輸入值，在執行有窮步驟之后一定能結束，即：算法中的每個步驟都能在有限時間內完成。2）確定性對于每種情況下所應執行的操作，在算法中都有確切的規定，使算法的執行者或閱讀者都能明確其含義及如何執行。并且在任何條件下，算法都只有一條執行路徑。 3）可行性算法中的所有操作都必須足夠基本，都可以通過已經實現的基本操作運算有限次實現之。4）輸入一個算法有零個或多個輸入。5）輸出一個算法有一個或多個有效信息的輸出。9.1.2 算法

10、的概念及特征計算機基礎知識132022/9/251）有窮性對于任意一組合法輸入值，在執行有窮步驟之后一定能3、算法的評價（算法復雜度）解決同一個問題的算法可以有多種，不同人員的設計不盡相同，其效率也存在差別，一個不好算法可能導致程序要運行幾天、幾個月甚至幾年，一個好的算法可能只要幾分種、幾秒鐘就可以完成。在設計算法時，應當遵循以下原則:首先是保證算法的正確性其次要具有良好的可讀性第三，算法應具有健壯性第四，算法執行時間的高效性第五，降低對存儲空間的需求9.1.2 算法的概念及特征計算機基礎知識142022/9/253、算法的評價（算法復雜度）9.1.2 算法的概念及特征計算一般而言，方法有優劣

11、之分，算法的優劣可以有多種不同的評價標準。例如，可以從時間上來評價，也可以從空間上來評價，或者從其他的角度來評價。人們當然愿意選擇較優的算法。因此，為了有效解題，不僅需要保證算法的正確性，還要考慮算法的質量，選擇合適的算法。從時間上來評價算法的優劣，即執行時間短的算法效率高,用算法的時間復雜度來度量。所謂算法的時間復雜度是指執行算法所需要的計算工作量。可以用算法在執行過程中所需基本運算的執行次數來度量算法的工作量。9.1.2 算法的概念及特征計算機基礎知識152022/9/25一般而言，方法有優劣之分，算法的優劣可以有多種不同的評價標準例如，求1+2+100的結果，有人是先求1+2，再把和加上

12、3，再加4，一直加到100；而高斯采取的辦法是，先將這100個數分為若干個組：(100)、(1, 99)、(2, 98)、(49, 51)、(50)，前面50個組每個組的和都是100，因此結果為50*100+50。當然還有其他的方法。從空間上來評價即為算法所需輔助空間越少越好,用算法的空間復雜度來度量。一個算法的空間復雜度，一般是指執行這個算法所需要的內存空間。一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數據所占的存儲空間以及算法執行過程中所需要的額外空間。9.1.2 算法的概念及特征計算機基礎知識162022/9/25例如，求1+2+100的結果，有人是先求1+2，再把和加1)

13、 用自然語言表示（教材中有例）2) 用傳統流程圖表示3) N-S流程圖4) 用偽代碼表示【例】求1+2+100的和，算法描述如下。 將1賦值給x。 將2賦值給y。 將x與y相加，結果存放在x中。 將y加1，結果存放在y中。 若y大于100，則輸出結果x，算法結束，否則轉步驟，算法繼續執行。9.1.3 算法的表示方法計算機基礎知識172022/9/251) 用自然語言表示（教材中有例）9.1.3 算法的表示方【例】求1+2+100的和，算法描述二： i1，sum0（即將1賦值給i，0賦值給sum）。 sumsum + i（即將sum + i的結果保存到sum中）。 ii+1。 判斷是否i100，

14、如果是，轉到步驟，否則，轉到步驟。 輸出sum的值，算法結束。9.1.3 算法的表示方法計算機基礎知識182022/9/25【例】求1+2+100的和，算法描述二：9.1.3 算2) 用傳統流程圖表示傳統流程圖是用規定的一組圖形符號、流程線和文字說明來表示各種操作的算法表示方法。9.1.3 算法的表示方法計算機基礎知識192022/9/25處理框判斷框輸入輸出框連接點流程線起止框2) 用傳統流程圖表示9.1.3 算法的表示方法計算機基礎2) 用傳統流程圖表示在算法設計中常用到三種基本流程控制結構，即順序、分支和循環結構。 順序結構。每一個基本的處理單位順序地被執行，9.1.3 算法的表示方法計

15、算機基礎知識202022/9/25FT條件AB 分支結構。又稱作選擇結構，根據邏輯條件的成立與否，選擇執行不同的處理，當邏輯條件成立時，執行處理A，否則執行處理B。2) 用傳統流程圖表示9.1.3 算法的表示方法計算機基礎2) 用傳統流程圖表示 循環結構。當邏輯條件成立時，反復執行處理A，直到邏輯條件不成立時結束（左）。9.1.3 算法的表示方法計算機基礎知識212022/9/25FTA條件TFTA條件2) 用傳統流程圖表示9.1.3 算法的表示方法計算機基礎2) 用傳統流程圖表示求1到100的自然數的和流程圖9.1.3 算法的表示方法計算機基礎知識222022/9/25FT開始sum0，i1

16、sumsum + ii100?輸出sum結束2) 用傳統流程圖表示9.1.3 算法的表示方法計算機基礎4) 用偽代碼表示 賦值給一個變量賦值 變量名表達式 例 s12 xs*6.2+8給多個變量賦相同的值 變量名，變量名，變量名表達式例 x,y,z3.5 s,tx+y9.1.3 算法的表示方法計算機基礎知識232022/9/254) 用偽代碼表示9.1.3 算法的表示方法計算機基礎知識4) 用偽代碼表示從鍵盤上輸入數據到一個變量input “數據類型” to 變量名例 INPUT “姓名” TO XM INPUT “數值數據” TO S輸出一個或多個結果值output “結果提示”, 表達式，

17、表達式例 OUTPUT “二次方程式的根為：”, X,Y output “1100的數據和S=：” ,s OUTPUT S9.1.3 算法的表示方法計算機基礎知識242022/9/254) 用偽代碼表示9.1.3 算法的表示方法計算機基礎知識4) 用偽代碼表示分支9.1.3 算法的表示方法計算機基礎知識252022/9/25單分支if 語句組endif雙分支if 語句組Aelse 語句組Bendif4) 用偽代碼表示9.1.3 算法的表示方法計算機基礎知識4) 用偽代碼表示分支9.1.3 算法的表示方法計算機基礎知識262022/9/25多分支（可省略）DO CASE CASE 語句組1 CA

18、SE 語句組2 CASE 語句組N OTHER 語句組N+1 ENDCASE【注】邏輯運算符3個： NOT AND OR4) 用偽代碼表示9.1.3 算法的表示方法計算機基礎知識4) 用偽代碼表示循環9.1.3 算法的表示方法計算機基礎知識272022/9/25 DO WHILE/ENDDO結構(當條件為真時執行循環體)DO WHILE 循環體ENDDO FOR/NEXT結構(不超越終值時執行循環體)FOR 循環控制變量=初值(表達式) TO 終值(表達式) STEP 步長值(表達式) 循環體NEXT4) 用偽代碼表示9.1.3 算法的表示方法計算機基礎知識綜合舉例：【例1】求數列1,1,2,3,5,8,13,21前30項的數據和。X，Y1N，S2DO WHILE N30 GX+Y XY YG SS+Y NN+1ENDDOOUTPUT “數列1,1,2,3,5,8,13,21前30項的數據和S=”,S OUTPUT “數列當前項為”,N9.1.3 算法的表示方法計算機基礎知識282022/9/25綜合舉例：9.1.3 算法的表示方法計算機基礎知識28