




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1算法的設計與描述認識程序設計
(C)任務介紹必備知識任務拓展
算法的概念和特征算法的復雜度算法的表示為了解決一個現實問題,我們首先需要在計算機中將問題描述出來。比如我們要找到某個班的成績最好的學生,就首先需要在程序中描述這個班每個學生的成績,而這就是程序的第一個任務———描述數據,
它回答了“是什么”的問題。算法的概念為解決一個問題而采取的步驟和方法,稱為算法。從程序設計的角度來看,每個問題都包含了兩個方面的內容:數據結構和算法。數據結構包括了數據的類型、數據的組織形式和數據之間的相互關系;
算法則是為解決一個問題而采取的方法和步驟。一個程序僅僅能夠描述數據,并不能解決問題,重要的是對數據進行處理,也就是找出程序所表示的所有學生成績當中最優秀的一個,這才是我們想要的最終結果。這就構成了程序的第二個任務———處理數據,它回答的是“怎么做”
的問題。而一個程序中對于數據的處理,就是算法。算法的概念和特征為了解決一個問題,會有多種解決方案。以生活中常見的地圖導航為例。假設某人在杭州西湖文化廣場的環球中心寫字樓下出發要到杭州索菲特西湖大酒店會客,他選擇公共交通工具前往。那么地圖會給出哪些方案呢?算法的概念和特征算法的概念計算機算法可分為兩大類別:數值運算算法和非數值運算算法。數值運算就是求數值解,例如常見的數學問題,目標一般為具體數值,而非事務性問題。而非數值運算的涉及面就很廣泛了,也是現階段計算機程序設計關注的熱點,最為常見的就是事務性管理領域,例如后序項目中提到的學生基本信息管理,學生成績管理等。數值運算往往有現成的模型,可以用數值分析方法,因此在數值運算的算法的研究比較深人,算法大都成熟。人們在程序設計中往往把這些算法匯編成庫,供用戶進行調用。但非數值運算種類繁多,要求各異,很難一次性做成相應的程序庫供開發者調用。算法的概念和特征算法的特征有窮性:一個算法應包含有限的操作步驟,而不能是無限的。事實上,“有窮性”往往指“在合理的范圍之內”。究竟什么算“合理限度”,并無嚴格標準,由人們的常識和需要而定。確定性:算法中的每一個步驟都應當是確定的,而不應當是含糊的、模棱兩可的。有零個或多個輸入:所謂輸入是指在執行算法時需要從外界取得必要的信息。一個算法也可以沒有輸入。有一個或多個輸出:算法的目的是為了求解,“解”就是輸出。沒有輸出的算法是沒有意義的。有效性:算法中的每一個步驟都應當能有效地執行,并得到確定的結果。算法的概念和特征有藍和黑兩個墨水瓶,規格相同,現在錯把藍墨水裝在黑墨水瓶中,黑墨水裝在藍墨水瓶中,要求將其互換。01比較3位學生的數學成績,將較高成績輸出到屏幕上。02對一個大于或等于2的正整數,判斷它是不是一個素數。03以下有三個案例,試用算法解決下列問題:算法的概念和特征1算法的設計與描述認識程序設計
(C)任務介紹必備知識任務拓展
算法的概念和特征算法的復雜度算法的表示自然語言就是人們日常使用的語言,用自然語言描述算法顯然很有吸引力,但是自然語言固有的不嚴密性使得要簡單清晰的描述算法變得很困難,并且一般篇幅較冗長,除了很簡單的問題,一般不用自然語言描述算法。用自然語言描述算法描述是指對設計出的算法,用一種方式進行詳細的描述,以便與人交流。描述可以使用自然語言、偽代碼,也可使用程序流程圖,但描述的結果必須滿足算法的五個特征。算法的表示流程圖是用一組規定的圖形符號、流程線和文字說明來表示各種操作、算法的方法,用流程圖表示算法,直觀形象,易于理解。ANSI規定了一些常用的流程圖符號:用流程圖描述算法的表示理論已經證明,任何復雜的算法都可以用順序結構、選擇結構和循環結構組合、嵌套來描述。下面針對程序的三種基本結構(順序結構、選擇結構、循環結構)用流程圖的形式進行算法表示。順序結構的程序設計是最簡單的,只要按照解決問題的順序寫出相應的語句就行,它的執行順序是自上而下,依次執行。順序結構可以獨立使用構成一個簡單的完整程序,常見的輸入、計算、輸出三部曲的程序就是順序結構。例如計算圓的面積,
其程序的語句順序就是輸入圓的半徑r,
計算s=3.14159×r×r,輸出圓的面積s。大多數情況下順序結構都是作為程序的一部分,與其他結構一起構成一個復雜的程序,例如分支結構中的復合語句、循環結構中的循環體等。算法的表示選擇程序結構用于判斷給定的條件,根據判斷的結果來控制程序的流程。在選擇結構中,要根據邏輯條件成立與否,分別選擇不同的處理。P代表邏輯條件,當條件為真時,執行處理A,否則執行處理B,選擇結構又稱為分支結構。算法的表示循環結構可以減少源程序重復書寫的工作量,用來描述重復執行某段算法的問題。循環結構一般可以分為當型循環和直到型循環。,當型循環結構:先判斷所給條件P是否成立若P成立,則執行A(步驟);再判斷條件P是否成立,若P成立,則又執行A,若此反復,直到某一次條件P不成立時為止。直到型循環結構:先執行A,再判斷所給條件P是否成立,若P不成立,則再執行A,如此反復,直到P成立,該循環過程結束。算法的表示如何繪制流程圖:通過Word自帶的繪圖工具,或者使用專業的繪圖工具,這里推薦MicrosoftVisio,用起來比較簡單,而且容易上手。算法的表示為了輸出2015年至2500年之間所有的閏年,請畫出流程圖。算法的表示使用偽代碼,不用拘泥于具體實現。相比程序語言它更接近自然語言。用偽代碼寫算法并無固定﹑嚴格的語法規則,可以用英文,也可以中英文混用。只要將意思表達清楚就可以,便于書寫和閱讀即可。偽代碼編寫時,一般考慮的相應規則是:每一條指令占一行(else
if除外);指令后不跟任何符號,也就是不用以分號結尾;書寫上的“縮進”表示程序中的分支程序結構。這種縮進風格也適用于if-then-else語句。用偽代碼表示偽代碼可以被看作是一種算法描述語言,介于自然語言與編程語言之間。使用偽碼的目的是使被描述的算法可以容易地以任何一種編程語言實現。因此,偽代碼必須結構清晰、代碼簡單、可讀性好,并且類似自然語言。算法的表示偽代碼舉例,求5!
。該算法的偽代碼如下:(算法開始)begin1=>
t2=>
iwhile
i≤5{t*i=>ti+1=>i}print
tend(算法結束)用偽代碼表示算法的表示1算法的設計與描述認識程序設計
(C)任務介紹必備知識任務拓展
算法的概念和特征算法的復雜度算法的表示算法的時間復雜度是指執行算法所需要的計算工作量,反映了程序執行時間隨輸入規模增長而增長的量級。一個算法執行所耗費的時間,從理論上是不能算出來的,必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試,只需知道哪個算法花費的時間多,哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執行次數成正比例,哪個算法中語句執行次數多,它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度,記為T(n)。時間復雜度同一問題可用不同算法解決,而一個算法的質量優劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進算法。一個算法的評價主要從時間復雜度和空間復雜度來考慮。算法的復雜度在各種不同算法中,若算法中語句執行次數為一個常數,則時間復雜度為O(1),另外,在時間頻度不相同時,時間復雜度有可能相同,如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同,但時間復雜度相同,都為O(n2)。請分析以下程序的時間復雜度。for(i=1;i<n;++i){for(
j=0;j<n;++j){A[i][
j]=i*j; ①}}該程序段中語句①的頻度為n*n,則程序段的時間復雜度為T(n)=O(n2)。時間復雜度若有某個輔助函數f(n),使得當n趨近于無窮大時,T(n)/f
(n)的極限值為不等于零的常數,則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n))為算法的漸進時間復雜度。算法的復雜度有兩個算法A1和A2求解同一問題,時間復雜度分別是T1(n)=100n2
,T2(n)=5n3。①當輸入量n<20時,有T1(n)>T2(n),后者花費的時間較少。②隨著問題規模n的增大,兩個算法的時間開銷將接近,然后有T1(n)<T2(n)。也就是當問題規模較大時,算法A1比算法A2要有效地多。它們的漸近時間復雜度O(n2)和O(n3)從宏觀上評價了這兩個算法在時間方面的質量。時間復雜度算法的復雜度空間復雜度與時間復雜度類似,空間復雜度是指算法在計算機內執行時所需存儲空間的度量。記作:S(n)=O(f(n))。一個算法所需的存儲空間用f(n)表示。其中n為問題的規模,S(n)表示空間復雜度。算法執行期間所需要的存儲空間包括3個部分:算法程序所占的空間輸入的初始數據所占的存儲空間(3)算法執行過程中所需要的額外空間在許多實際問題中,為了減少算法所占的存儲空間,通常采用壓縮存儲技術。空間復雜度算法的復雜度排序精講程序設計競賽排序講解2冒泡排序1計數排序排序題在程序設計競賽和面試中經常出現。經典的排序有計數排序、冒泡排序、選擇排序等。計數排序一種不是基于比較的排序算法,其核心在于將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中以達到排序的效果給定一組取值范圍為0到9的無序序列:1、7、4、9、0、5、2、4、7、3、4,建立一個長度為10的計數數組,值初始化為0遍歷無序序列,將每個序列元素值對應的計數數組下標的元素加1如:第一個序列元素為1,則計數數組中下標為1的元素加1繼續遍歷序列,當序列遍歷完畢,計數數組的最終狀態如下:計數排序遍歷計數數組,輸出計數數組下標值,元素的值是多少,就輸出幾次。輸出結果如下:0、1、2、3、4、4、4、5、7、7、9計數排序冒泡排序有一個無序數列:1、5、4、2、6、3,我們要將它按從小到大排序。按照冒泡排序的思想,我們要把相鄰的元素兩兩比較,根據大小來交換元素的位置冒泡排序是排序算法里面比較簡單的一個排序。它重復地走訪要排序的數列,一次比較兩個數據元素,如果順序不對則進行交換,并一直重復這樣的走訪操作,直到沒有要交換的數據元素為止。冒泡排序首先開始第一輪比較第一步:比較1和5,1比5小,順序正確,元素位置不變第二步:比較5和4,5比4大,順序錯誤,交換元素位置冒泡排序經過一輪比較后,6作為最大的元素到了序列的最右側。第二輪結束后,如下所示。.......第五輪結束后,如下所示冒泡排序1程序設計競賽遞推和遞歸《程序設計基礎》2f()X0 O1 X2 O3f() f() f()O0 X1 O2 X3遞推人類思維中自底向上、從小到大的正向思維,稱為“遞推思維”。也就是從積累的「先驗知識」出發,試圖從「已知」推導「未知」。可用遞推算法求解的問題一般有以下兩個特點:問題可以劃分成多個狀態;除初始狀態外,其它各個狀態都可以用固定的遞推關系式來表示。當然,在實際問題中,大多數時候不會直接給出遞推關系式,而是需要通過分析各種狀態,找出遞推關系式。3有一對兔子,從出生后第3個月起每個月都生一對兔子,小兔子長到第三個月后每個月又生一對兔子假如兔子都不死,問每個月的兔子總數為多少?表中1,1,2,3,5,8,13.....構成一個序列,這個數列有一個特點就是前兩項之和等于后一項兔子問題4遞歸在遞推中,是逐次對問題進行推導直到獲得最終解。而在遞歸中,則是逐次回歸迭代,直到跳出回歸。主要思想是利用分解法和合并法在方法定義中調用方法本身。用遞歸算法求解的問題一般步驟:確定遞歸初值;確定遞歸中止條件確定遞歸表達式1認識程序設計
(C)程序設計模式任務介紹必備知識任務拓展面向過程編程特征與方法面向對象編程特征與方法程序設計模式可以被看作是一套被反復使用、為多數人知曉的、經過分類編目、代碼設計經驗的總結。面向對象編程面向對象編程(Object-oriented
programming,OOP)是一種以類和對象為核心的程序設計模式。萬物皆對象,類是一群對象的所具有的共性的抽象,而對象則是類的實例。面向對象編程可以看作一種在程序中包含各種獨立而又互相調用的對象的思想,這與面向過程的思想剛好相反:面向過程的程序設計主張將程序看作一系列函數的集合,或者直接就是一系列對計算機下達的指令。面向對象程序設計中的每一個對象都應該能夠接受數據、處理數據并將數據傳達給其他對象,因此它們都可以被看作一個小型的“機器”,即對象。以五子棋游戲為例,了解面向對象編程的特點。當采用面向對象的設計時,整個五子棋可以分為以下幾個部分:①黑白雙方,這兩方的行為是一模一樣的;②棋盤系統,負責繪制畫面;③規則系統,負責判定諸如犯規輸贏等。面向對象編程模式具有典型的三大基本特征:封裝、繼承和多態。123封裝性:將類作為程序繼承性:子類自動共享多態性:相同的操作或函的基本單元,封裝數據和操作。父類數據結構和方法。數可作用于多種類型的對象上并獲得不同的結果。當我們遇到一個實際待解決的問題時,面向對象模式(OOP)首先針對問題要處理的數據特征找出相應的數據結構,然后設計解決問題的各種算法,并將數據結構和算法融入一個有機的整體——對象,該模式認為程序是由許多對象組成,對象是程序的基本實體,這個實體包含了對該對象屬性的描述(數據結構)和對該對象進行的操作(算法),即對象=數據結構+算法;程序=對象+對象。123可重用性:是指一可擴展性:要求應可管理性:采用類個軟件項目中所開發的用軟件能夠很方便、容作為構建系統的部件,模塊可以重復地使用在其他項目中。易地進行擴充和修改。整個項目的組織更加合理、方便。1認識程序設計
(C)程序設計模式任務介紹必備知識任務拓展面向過程編程特征與方法面向對象編程特征與方法設計模式是前人總結出來的開發經驗,就像是我們日常所說的管理模式一樣,通過對設計模式的運用可以讓我們更高效和更安全更正確的進行項目開發,同時具有更好的擴展性。面向過程編程模式(ProcedureOriented
Programming,簡稱POP)采用的是以過程為中心的編程思想,先分析解決問題的步驟,然后用函數把這些步驟一步一步地實現,接著在使用的時候調用。以五子棋游戲為例,了解面向過程編程的特點。① 開始游戲② 黑子先走③ 繪制畫面④ 判斷輸贏⑤ 輪到白子⑥ 繪制畫面⑦ 判斷輸贏⑧ 返回步驟2⑨ 輸出最后結果面向過程編程面向過程是一種直接的編程方法,它是按照編程語言的思路考慮問題,也是最為實際的一種
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 危險品事故調查案例分析考核試卷
- 服務質量評估與反饋系統考核試卷
- 保健品品牌宣傳策略的口碑營銷策略考核試卷
- 志愿者服務心理素質培養方案考核試卷
- 技能鑒定試題及答案
- 荊州日報面試題及答案
- 設施維護綠色節能技術應用考核試卷
- 系統集成方案設計考核試卷
- 兒科出科試題及答案
- 外事實務試題及答案
- 校長競聘筆試題目及答案
- 2025-2030“一帶一路”背景下甘肅省區域經濟發展分析及投資前景報告
- 2025五級應急救援員職業技能精練考試題庫及答案(濃縮400題)
- 反恐知識宣傳主題班會
- 基礎護理技能實訓 課件 模塊一項目四任務三血壓的測量
- 貴州省2024年12月普通高中學業水平合格性考試數學試卷(含答案)
- 北京市西城區2022-2023學年三年級上學期英語期末試卷(含聽力音頻)
- 海洋機器人與人工智能知到智慧樹章節測試課后答案2024年秋哈爾濱工程大學
- 2024-2025學年人教新目標英語八年級下冊期末綜合檢測卷(含答案)
- 涼糕擺攤技術培訓課件
- 幕墻清洗安全培訓
評論
0/150
提交評論