程序设计与算法课件

*

程式設計與演算法

*1.1.1 程式與程式設計為了解決某個實際問題而編排的指令序列稱之為程式。程式是由多條指令按照一定的順序組合而成的。在程式中使用哪些指令？這些指令出現和執行應該按怎樣的順序？程式是基於某種指令系統來實現的。對於電腦程式設計而言，就是要基於某種具體的電腦程式設計語言來編寫程式。*1.1.2 程式設計的過程和特性程式設計過程問題分析、確定演算法、編碼實現演算法問題輸入指令(computer)輸出*程式設計的特性構造性構造性決定了不能用統一的標準來衡量程式的品質。構造性決定了難以用形式化的方法來證明程式的正確性。嚴謹性編制程式所使用的程式設計語言是上下文無關的形式語言，需要程式員具有認真的工作作風和縝密的邏輯思維能力等基本素質。

抽象性要讓電腦來求解現實世界中的某一實際問題，程式員必須將該問題的求解方法和步驟進行歸納和抽象，用電腦能夠理解和執行的操作指令來實現每一個解題步驟，將這些指令合理地進行編排和控制，從而形成電腦程式。這就需要程式員具有較強的概括和抽象能力。*1.1.3 程式設計語言組合語言高級語言通用語言比如，BASIC/VisualBASIC，C/C++/VisualC++，PASCAL等等專用語言APL是為數組和向量運算設計的簡潔而又功能很強的語言；BLISS是為開發編譯程序和操作系統而設計的語言；FORTH是為開發微處理機軟體而設計的語言；LISP語言和PROLOG語言特別適合於編寫人工智慧領域的應用程式。資料庫管理系統目前常用的資料庫管理系統有，SQLServer，Oracle，VisualFoxPro等等。*圖1.1解釋型語言根源程式的執行過程這種翻譯方式執行速度較慢，因為它不產生可執行檔，每次運行都要重新解釋一次。根源程式和數據電腦解釋程式目標程式運行結果*圖1.2編譯型語言根源程式的編譯和執行過程編譯生成了可執行檔之後，就不再需要根源程式了，而且執行速度較快。源程序電腦編譯程式目標程式（檔）運行結果電腦目標程式（檔）數據*程式設計語言的發展（1）機器語言（2）組合語言（3）高級語言（4）第四代程式設計語言*1.1.4 程式設計方法結構化分析與設計的方法主要採用功能分解的方法，利用模組分解和功能抽象，自頂向下、分而治之。面向對象程式設計技術可以將解決某個問題的全套解決方案作為一個對象來進行分析，也可以將問題中涉及到的具體事物作為對象。對象是一個容器，其中包括數據和處理該數據的代碼，其內部的具體工作過程常常是與外部隔離的。模組僅包含代碼，數據是游離在外的。對象的操作是由向對象發消息引起。*面向對象程式設計技術中的基本概念1、對象對象可以表現為一個窗口、窗口中的一個按鈕、一個圖畫框、一個表格等可視的程式組件，還可以表現為變數、檔等不可視的程式元素。2、類類是對象的原型，它描述該類任一對象的共同行為特徵，是對一組性質相同對象的電腦語言描述，概括了對象的共同的數據結構和操作。例如，在程式實現時的一個窗口對象，就是窗口類的一個實例。*圖1.3對象、實體、與類之間的關係對象類實體抽象數據類人腦電腦現實世界映射電腦邏輯的實現*面向對象程式設計技術中的基本概念3、屬性對象中描述實體靜態特性的數據稱為（對象的）屬性。4、方法對象中用以模擬實體動態行為的“對數據施加的操作”稱為（對象的）方法。例如，對於對象“學生成績表”，增加一條記錄、刪除一條記錄、求最大值、求平均值、求前十名等等都是方法。方法是封裝在對象之中的特定的程式段，叫做方法過程。在程式中，使某個方法執行稱為調用該方法。*面向對象程式設計技術中的基本概念5、事件導致某個對象的“操作”被執行的過程稱為事件。某個事件發生時，對象所執行的操作稱為事件回應。面向對象的程式設計語言為每一個對象都預先定義了許多事件，一個事件發生時系統要作何回應，需要由程式員根據具體功能來編寫相應的回應代碼，該代碼稱做事件過程。*1.1.5 程式的品質標準正確性易讀性有效性可維護性適應性此外，程式設計必須盡力達到的四個目標是：可檢驗的、可修正的、可重複使用的、可移植的……。*1.2 演算法及演算法的描述工具1.2.1 演算法和演算法設計1.2.2 演算法描述工具1.2.3 演算法的基本特性*1.2.1 演算法和演算法設計什麼是演算法？演算法是一組（有限個）規則，它提供瞭解決某個特定問題的運算序列。程式和演算法是怎樣的一種關係呢？程式是演算法用電腦語言實現的形式。程式＝數據結構＋演算法*1.2.3演算法的基本特性和性質演算法的基本特性有窮性確定性能行性有輸入和輸出

評價演算法根據其：正確性可讀性健壯性較高的時空效率**基本數據結構和經典演算法簡介基本數據結構線性數據結構、圖、樹、集合與字典重要的經典演算法排序查找串處理圖問題:圖的遍曆、拓撲排序、旅行商問題、圖填色問題組合問題:旅行商問題（最短路徑問題）、圖填色問題幾何問題:凸包問題數值問題:解方程和方程組、演算法定積分、求函數的解………

………**演算法的設計和分析過程決定：計算方法；精確和近似的解法；數據結構；演算法設計技術理解問題設計演算法正確性證明分析演算法根據演算法寫代碼*1.2.2演算法描述工具目前廣泛使用的演算法描述工具有：程式流程圖、N-S圖、PAD圖、偽碼、自然語言等等。圖1.4求一元二次方程根的演算法輸入:a,b,c開始計算:d=b*b-4*a*c計算根:x1,x2輸出:”無解”輸出:x1,x2結束d>=0？是否*程式流程圖的基本符號*三種基本結構S1S2C是否S1C是否圖1.6分支（選擇）結構(a)(b)S1S2S3圖1.5順序結構*三種基本結構（續）圖1.8迴圈結構(a)(b)SC是否SC是否*圖1.7使用多次判斷的部分流程圖計算:y=xX<=1？是否X<10？是否計算:y=x3-17計算:y=x2-1Ifx<=1theny=xElseifx<10theny=x^2-1elsey=x^3-17endifEndif*1.3 演算法設計舉例[例1.1]統計10個數中，有多少個數為3的整數倍數。[例1.2]找出2～100間的素數。[例1.3]求Fibonacci數列的第n項值（n>2）。[例1.4]求n！。*[例1.1]統計10個數中，有多少個數為3的整數倍數。⑴T=0；⑵I=1；⑶如果I>10則轉到⑹；⑷-1輸入X；⑷-2如果X不是3的整數倍數，則轉⑸；⑷-3T加1；⑸I加1，然後轉⑶；⑹輸出T；⑺結束。圖1.9例1.1的流程圖開始T=0，I=1T=T+1I>10是是3的倍數I=I+1結束否否輸入:X輸出:T*[例1.2]找出2~100間的素數。演算法框架：⑴

n=2；⑵如果n>100則轉到⑸；⑶判斷n是否為素數；⑷n加1，然後轉⑵；⑸結束。開始n=2IsPrime=0n>100是否I>=nI=I+1結束否是圖1.10例1.2的流程圖IsPrime=1輸出:不是素數I=2否除不盡是IsPrime=1輸出:是素數否是*詳細演算法⑴n=2；⑵如果n>100則轉到⑸，否則執行下一步；⑶-1IsPrime=1；⑶-2-1I=2；⑶-2-2如果I>=n，則轉⑶-3，否則執行下一步；⑶-2-3如果nMODI<>0，則轉⑶-2-5，否則執行下一步；⑶-2-4IsPrime=0，轉⑶-3；⑶-2-5I加1，轉⑶-2-2；⑶-3如果IsPrime=1，則輸出“n是素數”,否則輸出“n不是素數”；⑷n加1，然後轉⑵；⑸結束。*[例1.3]求Fibonacci數列的第n項值（n>2）。⑴輸入n；⑵fa=0；⑶fb=1；⑷I=3；⑸fc=fa+fb；⑹如果I>=n則轉到⑾；開始fa=0,fb=1否I>=nI=I+1結束圖1.11例1.3的流程圖I=3fc=fa+fb是輸出:fcfa=fbfb=fc輸入:n⑺I=I+1；⑻fa=fb；⑼fb=fc；⑽轉⑸；⑾輸出fc；⑿結束。*[例1.4]求n！。最容易理解的遞推算法如下：⑴輸入n；⑵f=1；⑶I=1；⑷如果I>n則轉到⑻；⑸f=f×I；⑹I=I+1；⑺轉⑷；⑻輸出f；⑼結束。*遞歸遞歸演算法一般具有如下形式：⑴若問題的規模滿足邊界條件，則計算並返回結果；⑵否則，遞歸求解。計算m的階乘的fact函數可定義如下：⑴接受參數m；⑵如果m=0，fact=1,轉⑷；⑶否則，fact=m*fact(m-1)，注意:自己調用自己；⑷返回函數值fact。*求n！的演算法如下：⑴輸入n；⑵f=fact(n)；注意：在此調用了前面定義的遞歸函數fact(m）；⑶輸出f；⑷結束。*以上通過四個例子簡單介紹了幾類常用的演算法窮舉遞推遞歸其他：迭代法、回溯法、貪心演算法、動態規劃……*習題11.1什麼是程式？什麼是程式設計？1.2程式設計過程主要包括哪些步驟？各步驟的主要任務是什麼？1.3程式設計工作具有哪些特性？1.4怎樣評價一個程式品質的好壞？1.5什麼是解釋型程式設計語言？什麼是編譯型程式設計語言？1.6解釋下列概念：對象，屬性，方法，事件。1.7什麼是演算法？1.8簡述演算法與程式有什麼關係？*習題1-續1.9演算法有哪些基本特性？1.10設計計算s=1+2+3+…+100的演算法。1.11設計計算s=1+(1+2)+(1+2+3)+…+(1+2+…+100)的演算法。1.12設計求n個數的平均值的演算法。1.13設計求n個數中最小值的演算法。1.14一個n位數，如果其各位數字的n次方之和等於該數，則稱之為Armstrong數。例如，3位數153是Armstrong數（153=13+53+33）。試用枚舉的思想設計找出3位數中所有Armstrong數的演算法。*習題1-續1.15觀察下列數列Pn（n=1,2,3,…），找出遞推關係式，並設計計算其第20項的演算法：⑴1,2,4,7,11,16,…。⑵0,1