




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 能源統(tǒng)計報表培訓課件
- 抖音商戶直播樣品回收再利用登記制度
- 抖音商戶主播直播狀態(tài)穩(wěn)定管理制度
- 公交優(yōu)先與城市交通擁堵治理:2025年政策效果與優(yōu)化策略研究
- 公交優(yōu)先策略在2025年城市交通擁堵治理中的實踐探索報告
- 公眾參與在2025年環(huán)境影響評價中的實際操作案例報告
- 湖南汽車工程職業(yè)學院《醫(yī)學影像診斷學B》2023-2024學年第一學期期末試卷
- 陜西機電職業(yè)技術學院《社會調查方法》2023-2024學年第一學期期末試卷
- 遼寧省興城市紅崖子滿族鄉(xiāng)初級中學2025屆化學九年級第一學期期末調研模擬試題含解析
- 吉林建筑大學《導游俄語視聽說》2023-2024學年第一學期期末試卷
- 手電筒產品課程設計報告書
- 《優(yōu)質客戶服務技巧》
- TL4型彈性套柱銷聯(lián)軸器零件工藝規(guī)程及加工柱銷孔液動夾具設計
- 05-衣之鏢-輔行訣湯液經法用藥圖釋義
- LS/T 3240-2012湯圓用水磨白糯米粉
- GB/T 15298-1994電子設備用電位器第一部分:總規(guī)范
- 2023高中學業(yè)水平合格性考試歷史重點知識點歸納總結(復習必背)
- 自然指數(shù)NatureIndex(NI)收錄的68種自然科學類期刊
- 手術報告審批單
- 《專業(yè)導論光電信息科學與工程》教學大綱
- 少兒美術國畫- 少兒希望 《紫藤課件》
評論
0/150
提交評論