




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、1.3 問(wèn)題求解與算法,1.3.1 問(wèn)題求解 1.3.2 算法的概念與特點(diǎn) 1.3.3 算法優(yōu)劣的標(biāo)準(zhǔn) 1.3.4 算法的描述,1.3.1問(wèn)題求解,問(wèn)題:輸入n,求1+2+n 理解問(wè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)解決方案 解決方案表示:圖形化方法或自然語(yǔ)言描述 編程實(shí)現(xiàn)解決方案:選擇適合的語(yǔ)言與開(kāi)發(fā)環(huán)境編程 測(cè)試分析解決方案,1.3.2 算法及其特點(diǎn),算法:問(wèn)題求解的具體步驟和
2、方法 特點(diǎn): 確定性 可行性 0或多個(gè)輸入 1或多個(gè)輸出 有窮性,漸近時(shí)間復(fù)雜度指基本操作執(zhí)行次數(shù)函數(shù)的關(guān)鍵項(xiàng),反映算法運(yùn)行所需時(shí)間隨問(wèn)題規(guī)模增長(zhǎng)的增長(zhǎng)率,如算法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ǔ)空間隨問(wèn)題規(guī)模增長(zhǎng)的增長(zhǎng)率,如算法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圖 偽碼 判定表和判定樹(shù),程序流程圖,常用符號(hào):起止框 控制流 處理框 選擇框 輸入輸出框 注釋框 連接點(diǎn)等 簡(jiǎ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ì)越來(lái)越小,增加畫(huà)圖難度,影響清晰度,PAD圖,PAD圖舉例,相比NS圖,PAD圖是一個(gè)開(kāi)放的結(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”, ,判定表與判定樹(shù)自學(xué),判定樹(shù)(Decision Tree)是用來(lái)表示邏輯判斷問(wèn)題的一種圖形工具。它用“樹(shù)”來(lái)表達(dá)不同條件下的不同處理,比語(yǔ)言、表格的方式更為直觀。判定樹(shù)的左側(cè)(稱為樹(shù)根)為加工名,中間是各種條件,所有的行動(dòng)都列于最右側(cè) 判定表采用表格形式來(lái)表達(dá)邏輯
5、判斷問(wèn)題,表格分成四個(gè)部分:左上角為條件說(shuō)明;左下角為行動(dòng)說(shuō)明;右上角為各種條件的組合說(shuō)明;右下角為各條件組合下相應(yīng)的行動(dòng)。 。,回顧:,理解計(jì)算機(jī)求解問(wèn)題的步驟 掌握算法的概念、特性及優(yōu)劣指標(biāo),尤其注意漸近時(shí)間復(fù)雜度的概念和計(jì)算 掌握算法的N-S圖和PAD圖表示,了解流程圖和決策樹(shù)、決策表 作業(yè):1.4(1)(3)(4) 課下:務(wù)必預(yù)習(xí)第2章各節(jié),周二實(shí)驗(yàn)用,上機(jī)常見(jiàn)問(wèn)題說(shuō)明:,常見(jiàn)error:丟分號(hào)、括號(hào)和引號(hào),標(biāo)點(diǎn)或大小寫(xiě)錯(cuò),變量未定義,缺頭文件 常見(jiàn)warning:變量使用前未賦初值,賦值類型不匹配,變量定義后未用 常見(jiàn)運(yùn)行錯(cuò):越界訪問(wèn)(丟 ,上機(jī)實(shí)驗(yàn):實(shí)驗(yàn)一實(shí)驗(yàn)報(bào)告填寫(xiě)說(shuō)明,實(shí)驗(yàn)名稱
6、:熟悉C語(yǔ)言的上機(jī)環(huán)境 實(shí)驗(yàn)日期:2009.9.22 正文: 一、實(shí)驗(yàn)?zāi)康?1. 了解并初步掌握編寫(xiě)簡(jiǎn)單C程序的方法。 2. 熟悉C語(yǔ)言上機(jī)環(huán)境Visual C+ 6.0。 3. 初步了解C語(yǔ)言的調(diào)試工具。 二、實(shí)驗(yàn)內(nèi)容 說(shuō)明:加下劃線者為需要寫(xiě)入實(shí)驗(yàn)報(bào)告的內(nèi)容,1. 打開(kāi)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. 如下修改上面的程序,簡(jiǎn)述修改情況 #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ò)誤提示記錄下來(lái)并加以解釋。注意:這里的錯(cuò)誤信息是英文的,所以大家一定要熟悉一些常見(jiàn)的錯(cuò)誤提示,并會(huì)據(jù)錯(cuò)誤信息修改源程序。,6. 再次修改,簡(jiǎn)述修改情況 #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é)果顯示嗎?是什么?記錄下來(lái)。,10. 調(diào)試下面的程序,使其能夠?qū)崿F(xiàn)求階乘的功能。注意記錄調(diào)試和測(cè)試過(guò)程 #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è)說(shuō)明:,補(bǔ)充:正負(fù)0、正負(fù)32767各種編碼與2字節(jié)補(bǔ)碼表示范圍 1.3:0.125 -33225或-1107296256 95225或231876710
11、40 1.4:兩變量互換 三變量排序 求階乘,兩變量互換(答案略有問(wèn)題):,說(shuō)明:變量存儲(chǔ)空間相當(dāng)于盒子,定義變量即開(kāi)辟存儲(chǔ)空間 問(wèn)題1:通常每個(gè)語(yǔ)句單獨(dú)占一個(gè)處理框 問(wèn)題2:通常要有輸出,此處輸入實(shí)際可略 注意:PAD圖右側(cè)各框是分開(kāi)的,三變量排序(答案略有問(wèn)題),問(wèn)題:Y/N統(tǒng)一用T/F;注意畫(huà)法美觀 PAD圖默認(rèn)上T下F 經(jīng)典排序算法:選擇法 冒泡法,求階乘(與作業(yè)略有差別,此處求n?。?注:循環(huán)與分支區(qū)別;循環(huán)畫(huà)法;當(dāng)型/直到型,回顧:,計(jì)算機(jī)解題的步驟 算法的概念和特點(diǎn) 算法的描述:流程圖 N-S圖 PAD圖 C程序的運(yùn)行步驟與VC6.0的使用,1.4 程序設(shè)計(jì)與程序設(shè)計(jì)語(yǔ)言,1.4
12、.1程序質(zhì)量 1.4.2程序設(shè)計(jì)語(yǔ)言發(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ì)過(guò)程:輸入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ì)過(guò)程-輸入n,求n!,用PAD圖表示結(jié)構(gòu)化設(shè)計(jì)過(guò)程:輸入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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 壽險(xiǎn)職場(chǎng)出勤管理辦法
- 監(jiān)管平臺(tái)考核管理辦法
- 征地拆遷補(bǔ)償管理辦法
- 徐州市奢侈品管理辦法
- 如何實(shí)施課程管理辦法
- 學(xué)?;顒?dòng)管理辦法細(xì)則
- 監(jiān)督抽檢管理辦法復(fù)檢
- 媒體公司素材管理辦法
- 咨詢公司職級(jí)管理辦法
- 醫(yī)藥原材料進(jìn)場(chǎng)計(jì)劃及保證措施
- 2024年小區(qū)地下車位租賃合同
- 高含鹽廢水深度治理及綜合利用提升改造項(xiàng)目環(huán)評(píng)報(bào)告
- 教師食品安全知識(shí)
- 《網(wǎng)絡(luò)故障及處理》課件
- 輔導(dǎo)員素質(zhì)能力大賽基礎(chǔ)知識(shí)試題題庫(kù)
- 裝飾裝修工程主要質(zhì)量通病防治措施
- 深圳航空公司招聘筆試真題
- bopp消光膜及其生產(chǎn)工藝
- 離婚協(xié)議書(shū)(完整版)WORDx(二篇)
- 巖棉外墻保溫系統(tǒng)
- 波譜分析復(fù)習(xí)資料
評(píng)論
0/150
提交評(píng)論