算法與結(jié)構(gòu)化程序設(shè)計(jì)

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

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

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

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

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

6、：熟悉C語言的上機(jī)環(huán)境 實(shí)驗(yàn)日期：2009.9.22 正文： 一、實(shí)驗(yàn)?zāi)康?1. 了解并初步掌握編寫簡單C程序的方法。 2. 熟悉C語言上機(jī)環(huán)境Visual C+ 6.0。 3. 初步了解C語言的調(diào)試工具。 二、實(shí)驗(yàn)內(nèi)容 說明：加下劃線者為需要寫入實(shí)驗(yàn)報(bào)告的內(nèi)容,1. 打開VC6，觀察其環(huán)境，記錄下VC6的主要菜單及其功能，如：File、View、Build等。 2. 利用VC6創(chuàng)建一個(gè)工程，命名為FirstProject，然后在此工程中新建一個(gè)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. 編譯并運(yùn)行這個(gè)程序，輸出結(jié)果是什么？ 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. 編譯這個(gè)程序，出現(xiàn)什么錯(cuò)誤？把錯(cuò)誤提示記錄下來并加以解釋。注意：這里的錯(cuò)誤信息是英文的，所以大家一定要熟悉一些常見的錯(cuò)誤提示，并會(huì)據(jù)錯(cuò)誤信息修改源程序。,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í)行它，有結(jié)果顯示嗎？是什么？記錄下來。,10. 調(diào)試下面的程序，使其能夠?qū)崿F(xiàn)求階乘的功能。注意記錄調(diào)試和測試過程 #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程序是由一個(gè)或多個(gè)函數(shù)組成的，每個(gè)函數(shù)完成一定的功能，且通

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

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

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