算法與結構化程序設計

1、1.3 問題求解與算法,1.3.1 問題求解 1.3.2 算法的概念與特點 1.3.3 算法優(yōu)劣的標準 1.3.4 算法的描述,1.3.1問題求解,問題：輸入n,求1+2+n 理解問題特征：“輸入”n,“輸出”1到n間所有正整數(shù)和 設想解決方案： (1)輸入n；初始化變量s為0,逐個將 1到n的正整數(shù)累加到s中；輸出s的值 (2)輸入n；根據(jù)等差數(shù)列求和公式計 算n*(1+n)/2賦值給s；輸出s的值 優(yōu)化解決方案:比較確定最優(yōu)解決方案 解決方案表示:圖形化方法或自然語言描述 編程實現(xiàn)解決方案:選擇適合的語言與開發(fā)環(huán)境編程 測試分析解決方案,1.3.2 算法及其特點,算法:問題求解的具體步驟和

2、方法 特點： 確定性 可行性 0或多個輸入 1或多個輸出 有窮性,漸近時間復雜度指基本操作執(zhí)行次數(shù)函數(shù)的關鍵項,反映算法運行所需時間隨問題規(guī)模增長的增長率,如算法1基本操作執(zhí)行次數(shù)函數(shù)為f(n)=3+2*n+1,時間復雜度T(n)=O(n);算法2中頻度函數(shù)f(n)=3，時間復雜度為T(n)=O(1).關鍵看循環(huán)次數(shù),空間復雜度指所需存儲空間函數(shù)的關鍵項,反映算法運行所需存儲空間隨問題規(guī)模增長的增長率，如算法1需3個變量i、s、n，f(n)=3, S(n)=O(1);算法2需2個變量n與s，f(n)=2,S(n)=O(1)，兩者時間復雜度相同，均為常數(shù)階,1.3.3 算法優(yōu)劣標準,正確性 時間

3、復雜度 空間復雜度 健壯性 可讀性,1.3.4 算法描述,程序流程圖 N-S圖(盒圖) PAD圖 偽碼 判定表和判定樹,程序流程圖,常用符號：起止框 控制流 處理框 選擇框 輸入輸出框 注釋框 連接點等 簡單易懂,但箭頭可隨意轉移控制流，導致復雜算法難以閱讀和維護。 改進:限制箭頭的濫用，不允許流程的隨意轉向，為此提出了三種基本結構，他們各自只有一個入口和出口(比如不允許隨意跳轉到循環(huán)內),i計數(shù)器 S累加器,T,改進的流程圖,N-S圖(盒圖),改進流程圖與盒圖舉例：,優(yōu)點：使用-圖設計出的算法必然是結構化算法，較流程圖清晰直觀易懂，容易表現(xiàn)嵌套關系和模塊的層次結構 缺點：當程序內嵌層數(shù)增多時

4、，內層方框會越來越小，增加畫圖難度，影響清晰度,PAD圖,PAD圖舉例,相比NS圖，PAD圖是一個開放的結構，支持自頂向下、逐步求精的算法設計方法，已被ISO認可為算法圖形描述的標準,偽碼,輸入n; s 0 i 1 while(i=n) s s+i i i+1 輸出s,#include void main() scanf(“%d”, ,判定表與判定樹自學,判定樹(Decision Tree)是用來表示邏輯判斷問題的一種圖形工具。它用“樹”來表達不同條件下的不同處理，比語言、表格的方式更為直觀。判定樹的左側(稱為樹根)為加工名，中間是各種條件，所有的行動都列于最右側 判定表采用表格形式來表達邏輯

5、判斷問題，表格分成四個部分：左上角為條件說明；左下角為行動說明；右上角為各種條件的組合說明；右下角為各條件組合下相應的行動。 。,回顧：,理解計算機求解問題的步驟 掌握算法的概念、特性及優(yōu)劣指標，尤其注意漸近時間復雜度的概念和計算 掌握算法的N-S圖和PAD圖表示,了解流程圖和決策樹、決策表 作業(yè)：1.4(1)(3)(4) 課下：務必預習第2章各節(jié)，周二實驗用,上機常見問題說明：,常見error:丟分號、括號和引號,標點或大小寫錯,變量未定義,缺頭文件 常見warning:變量使用前未賦初值,賦值類型不匹配,變量定義后未用 常見運行錯:越界訪問(丟 ,上機實驗：實驗一實驗報告填寫說明,實驗名稱

6、：熟悉C語言的上機環(huán)境 實驗日期：2009.9.22 正文： 一、實驗目的 1. 了解并初步掌握編寫簡單C程序的方法。 2. 熟悉C語言上機環(huán)境Visual C+ 6.0。 3. 初步了解C語言的調試工具。 二、實驗內容 說明：加下劃線者為需要寫入實驗報告的內容,1. 打開VC6，觀察其環(huán)境，記錄下VC6的主要菜單及其功能，如：File、View、Build等。 2. 利用VC6創(chuàng)建一個工程，命名為FirstProject，然后在此工程中新建一個C源程序，命名為：FirstProg.c。記錄操作步驟，之后輸入如下程序： #include /*This is a demo program*/ v

7、oid main() printf(“I am very glad to see you, my first program!n”); 3. 編譯并運行這個程序，輸出結果是什么？ 4. 如下修改上面的程序，簡述修改情況 #include /*This is a demo program*/ void main() printf(“I am very glad to see you, my first program!n”); printf(“Now, I try to compute the sum of two numbers, please input two numbers:”); sc

8、anf(“%d%d”, 5. 編譯這個程序，出現(xiàn)什么錯誤？把錯誤提示記錄下來并加以解釋。注意：這里的錯誤信息是英文的，所以大家一定要熟悉一些常見的錯誤提示，并會據(jù)錯誤信息修改源程序。,6. 再次修改，簡述修改情況 #include /*This is a demo program*/ void main() int a,b,c; printf(“I am very glad to see you, my first program!n”); printf(“Now, I try to compute the sum of two numbers, please input two number

9、s:”); scanf(“%d%d”, 編譯執(zhí)行它，有結果顯示嗎？是什么？記錄下來。,10. 調試下面的程序，使其能夠實現(xiàn)求階乘的功能。注意記錄調試和測試過程 #include int getFactorial(int n) /*返回n的階乘*/ int i; int result; result = n; i=0; while(in) result=result*I; i=i+1; return result; void main() printf(“input an integer please:); scanf(%d, 提示1：C程序是由一個或多個函數(shù)組成的，每個函數(shù)完成一定的功能，且通

10、常返回一定的處理結果，函數(shù)間可以相互調用。如上例中程序由兩個函數(shù)組成，一個是main函數(shù)，該函數(shù)是程序執(zhí)行的入口，函數(shù)的作用是輸入一個整數(shù)n，之后調用getFactorial函數(shù)計算n的階乘并輸出計算結果；getFactorial函數(shù)用以求一個整數(shù)的階乘，被調用執(zhí)行時接受一個整數(shù)參數(shù)，并計算其階乘，之后返回計算結果。 提示2：賦值運算符是=，如i=1含義是為變量i賦值1 ；而=是用以判斷左右兩側的值是否相等，如i=1用以判斷i是否等于1,作業(yè)說明：,補充：正負0、正負32767各種編碼與2字節(jié)補碼表示范圍 1.3：0.125 -33225或-1107296256 95225或231876710

11、40 1.4：兩變量互換 三變量排序 求階乘,兩變量互換（答案略有問題）：,說明：變量存儲空間相當于盒子，定義變量即開辟存儲空間 問題1：通常每個語句單獨占一個處理框 問題2：通常要有輸出,此處輸入實際可略 注意：PAD圖右側各框是分開的,三變量排序（答案略有問題）,問題：Y/N統(tǒng)一用T/F;注意畫法美觀 PAD圖默認上T下F 經典排序算法：選擇法 冒泡法,求階乘（與作業(yè)略有差別，此處求n?。?注:循環(huán)與分支區(qū)別；循環(huán)畫法；當型/直到型,回顧：,計算機解題的步驟 算法的概念和特點 算法的描述：流程圖 N-S圖 PAD圖 C程序的運行步驟與VC6.0的使用,1.4 程序設計與程序設計語言,1.4

12、.1程序質量 1.4.2程序設計語言發(fā)展史 1.4.3 結構化程序設計方法,2-5 結構化程序設計方法,基本思路:本質是功能分解，從代表目標系統(tǒng)整體功能的單個處理著手，自頂向下不斷把復雜的處理分解為子處理，這樣一層一層的分解下去，直到僅剩下若干個容易實現(xiàn)的子處理功能為止。,自頂向下,逐步細化 模塊化設計,結構化編程,用PAD圖表示結構化設計過程：輸入n，求1+n,輸入n,P:計算1到n間正 整數(shù)的和,賦給s,輸出s的值,i=1,s = s+i,i= i+1,P,def,s=0,用PAD圖表示結構化設計過程-輸入n，求n！,用PAD圖表示結構化設計過程：輸入n，求1!+2!+n!,s=0,輸出s的值,while(k=n),k=1,P:計算k!賦給term,s = s+term,輸入n,i=1,term=term*i,i= i+1,P,def,term=1,s=0,輸出s的值,while(k=n),k=1,s= s+term,輸入n,i=1,term=term*i,i= i+1,term=1