軟件技術(shù)專題-課件

軟件技術(shù)基礎(chǔ)1概述2算法3程序設(shè)計4軟件工程軟件技術(shù)基礎(chǔ)1概述11概述1概述2什么是計算機軟件?操作系統(tǒng)、QQ、360……計算機系統(tǒng)=硬件+軟件什么是計算機軟件?操作系統(tǒng)、QQ、360……計算機系統(tǒng)=硬件3程序以及相關(guān)的文檔的集合。程序文檔1文檔2文檔3可執(zhí)行部分不可執(zhí)行部分程序以及相關(guān)的文檔的集合。程序文檔1文檔2文檔3可執(zhí)行部4什么是文檔？文檔：記錄軟件開發(fā)活動和階段性成果，理解軟件所必需的闡述性資料。

–需求分析文檔–軟件設(shè)計文擋等編寫文檔目的

–促進對軟件的開發(fā)、管理和維護；–便于各種人員(用戶、開發(fā)人員)的交流什么是文檔？5什么是程序？程序一詞源于生活。做任何一件事情，都是有程序的。例如，頒獎大會的程序；做菜的程序等等。把做菜的步驟用大家看得懂的方式記錄下來，其他人可以按這些步驟順序?qū)嵤┚屯瓿闪嗽撌虑?。什么是程序？程序一詞源于生活。做任何一件事情，都是有6用計算機完成某事情，就把事先設(shè)計好的計算機處理信息的步驟，用計算機能夠識別的指令編寫出來，送入計算機。計算機按照指令執(zhí)行，就能完成指定的工作。

算法程序設(shè)計語言程序就是用計算機語言表述的算法。用計算機完成某事情，就把事先設(shè)計好的計7

為解決一個問題而采取的方法和步驟，就稱為算法。什么是算法？為解決一個問題而采取的方法和步驟，就稱為算法。什么是8什么是計算機語言？人們想和計算機交流，用符號來表達。怎樣維護交通秩序？音樂是怎樣表示的？什么是計算機語言？人們想和計算機交流，用符號來表達。9用來表達這種關(guān)系的符號系統(tǒng)就是計算機語言，也叫“程序設(shè)計語言”。人與計算機交流使用的是“程序設(shè)計語言”。同人類語言一樣，程序設(shè)計語言也是由字、詞和語法規(guī)則構(gòu)成的一個系統(tǒng)。用來表達這種關(guān)系的符號系統(tǒng)就是計算機語言，也叫“102算法2算法11主要內(nèi)容算法的表示算法的要素算法的特點算法的復(fù)雜度常用算法主要內(nèi)容算法的表示12算法的表示算法一般可以使用下面幾種類型的工具描述：1.自然語言例：求1×2×3×4×5。

算法的表示算法一般可以使用下面幾種類型的工具描述：13

最原始方法：步驟1：先求1×2，得到結(jié)果2。步驟2：將步驟1得到的乘積2乘以3，得到結(jié)果6。步驟3：將6再乘以4，得24。步驟4：將24再乘以5，得120。

14改進的算法：S1:使t=1S2:使i=2S3:使t×i,乘積仍然放在在變量t中，可表示為t×i→tS4:使i的值+1，即i+1→iS5:如果i≤5,返回重新執(zhí)行步驟S3以及其后的S4和S5；否則，算法結(jié)束。

改進的算法：152.專用圖形工具常用的有流程圖、PAD圖和N-S圖等。2.專用圖形工具16流程圖描述流程圖描述173.偽代碼

為了便于轉(zhuǎn)換成某種編程語言，一般采用準程序設(shè)計語言作算法描述語言。3.偽代碼18偽代碼描述：BEGIN(算法開始)1=>t2=>iwhilei<=5[t*i=>ti+1=>i]printtEND(算法結(jié)束)偽代碼描述：BEGIN(算法開始)19算法兩要素算法的兩要素算法由操作與控制結(jié)構(gòu)兩要素組成。1.操作(1)邏輯運算：“與”、“或”、“非”；(2)算術(shù)運算：加、減、乘、除；(3)數(shù)據(jù)比較：大于、小于、等于、不等于；(4)數(shù)據(jù)傳送：輸入、輸出、賦值。算法兩要素算法的兩要素202.控制結(jié)構(gòu)

1）算法的控制結(jié)構(gòu)，決定了各操作的執(zhí)行次序。用流程圖可以形象地表示出算法的控制結(jié)構(gòu)。2）任何復(fù)雜的算法都可以用順序、選擇、循環(huán)三種控制結(jié)構(gòu)組合而成。2.控制結(jié)構(gòu)1）算法的控制結(jié)構(gòu)，決定了各操作的執(zhí)行次21FTFT22我們在構(gòu)造一個算法的時候，也只能以這三種基本結(jié)構(gòu)作為“建筑單元”，遵守三種基本結(jié)構(gòu)的規(guī)范。基本結(jié)構(gòu)之間可以并列、可以相互包含，但不允許交叉。正因為整個算法都由這三種基本結(jié)構(gòu)構(gòu)成，所以結(jié)構(gòu)清晰，易于驗證，易于糾錯。這種方法就是結(jié)構(gòu)化方法。我們在構(gòu)造一個算法的時候，也只能以這三種基本結(jié)構(gòu)23算法的特征有窮性一個算法必須總是在執(zhí)行有窮步后結(jié)束，且每一步都可在有窮時間內(nèi)完成；確定性算法中的每一個指令必須有明確的含義，不能有二義性；例：武松打死老虎手舉過頭頂單手?雙手？舉多高？算法的特征有窮性一個算法必須總是在執(zhí)行有窮步后結(jié)束，且每一24可行性(有效性)算法中描述的操作都是可通過已經(jīng)實現(xiàn)的基本運算、執(zhí)行有限次實現(xiàn)的；例：a/b若b=0則無效輸入一個算法應(yīng)有0個或多個輸入；輸出一個算法應(yīng)有1個或多個輸出。可行性(有效性)算法中描述的操作都是可通過已經(jīng)實現(xiàn)的基本25算法的復(fù)雜度評價算法的標準：–執(zhí)行算法所耗費的時間，即時間復(fù)雜度；–執(zhí)行算法所耗費的存貯空間，主要是輔助空間，即空間復(fù)雜度。算法的復(fù)雜度評價算法的標準：26思考：給出一組數(shù)12、13、26、27、38、49、55、60、67、86，查找某一個數(shù)x是否在這組數(shù)中的算法？算法1：順序查找算法2：二分法查找比較：的時間復(fù)雜度？思考：給出一組數(shù)12、13、26、27、38、49、27算法的設(shè)計要求正確性滿足需求可讀性有助于算法的理解、調(diào)試和修改健壯性容錯高效率與低存儲量算法的設(shè)計要求正確性滿足需求28常用算法常用算法29

先依據(jù)題目的部分條件確定答案的大致范圍，在此范圍內(nèi)對所有可能的情況逐一驗證，直到全部情況驗證完。若某個情況使驗證符合題目的條件，則為本題的一個答案；若全部情況驗證完后均不符合題目的條件，則問題無解。1.枚舉法先依據(jù)題目的部分條件確定答案的大致范圍，30例：公雞每只五元，母雞每只三元，小雞三只一元，問一百元錢買一百只雞有幾種買法？假設(shè)公雞數(shù)為x，母雞數(shù)為y，則小雞數(shù)是z，也就有了下面的方程式：x+y+z=1005x+3x+z/3=100例：公雞每只五元，母雞每只三元，小雞三31算法：算法：322.遞推法順推法和倒推法例：猴子分食桃子一天，一只猴子采得一堆桃子，當(dāng)天它吃掉一半多一個，第二天又吃了一半多一個…一直到第七天，它就剩一個桃子了。那么那天它共采了多少個桃子呢？2.遞推法順推法和倒推法例：猴子分食桃子33算法：S1:使s=1S2:使t=7S3:使(s+1)×2,結(jié)果仍然放在變量s中，可表示為(s+1)×2→sS4:使t的值-1，即t-1→tS5:如果t>=1,返回重新執(zhí)行步驟S3以及其后的S4和S5；否則，算法結(jié)束。算法：343.遞歸法如果一個過程直接或間接地調(diào)用它自身，則稱該過程是遞歸的。例：求階乘。n!=1n=1n(n-1)!n>03.遞歸法如果一個過程直接或間接地調(diào)用它自身，則例：35算法：FunctionFactorial(nAsLong)AsLongIfn=1ThenFactorial=1ElseFactorial=n*Factorial(n-1)EndFunction算法：FunctionFactorial(36例：有一個n×m的棋盤(2<=n<=50，2<=m<=50)，在棋盤上有一個馬，馬走的規(guī)則為：馬走日字且只能向右走。當(dāng)n，m給出之后，同時給出馬起始的位置和終點的位置，找出從起點到終點的所有路徑的數(shù)目。

4.回溯法回溯算法：從一條路往前走，能進則進，不能進則退回來，換一條路再試。例：有一個n×m的棋盤(2<=n<=50，2<=m<373程序設(shè)計基礎(chǔ)程序設(shè)計的一般步驟：模型算法程序結(jié)果實際問題

解決問題的核心：算法及算法的處理對象。3程序設(shè)計基礎(chǔ)程序設(shè)計的一般步驟：模型算法程序結(jié)果實際問題38一個程序應(yīng)包括：對操作的描述。即操作步驟，也就是算法(algorithm)。對數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)(datastructure)。NikiklausWirth提出的公式：

數(shù)據(jù)結(jié)構(gòu)+算法=程序一個程序應(yīng)包括：39程序設(shè)計語言1.發(fā)展的過程程序設(shè)計語言分類：機器語言、匯編語言、高級語言機器語言匯編語言高級語言程序設(shè)計語言1.發(fā)展的過程機器語言匯編語言高級語言40機器語言機器語言是一種CPU指令系統(tǒng),是該CPU可以識別的一組組由0和1序列組成的指令碼。最初的語言是機器語言，二進制編碼，機器可直接執(zhí)行，執(zhí)行速度快。機器語言4100000001000000001000數(shù)據(jù)裝入寄存器000000001000100001010數(shù)據(jù)裝入寄存器100000101000000000001寄存器0與1的數(shù)據(jù)乘00000001000100001001數(shù)據(jù)裝入寄存器100000100000000000001寄存器0與1的數(shù)據(jù)加00000010000000001110保存寄存器0里的數(shù)編程困難、可讀性差、容易出錯、可移植性差00000001000000001000數(shù)據(jù)裝入寄存42匯編語言用一些簡潔的英文字母、符號串來替代一個特定的指令的二進制串，比如，用“ADD”代表加法，“MOV”代表數(shù)據(jù)傳遞等等。例：load0,a將單元a的數(shù)據(jù)裝入寄存器0load1,b將單元b的數(shù)據(jù)裝入寄存器1mult0,1寄存器0與1的數(shù)據(jù)乘load1,c將單元c的數(shù)據(jù)裝入寄存器1add0,1寄存器0與1的數(shù)據(jù)加save0,d將寄存器0里的數(shù)存入單元d匯編語言43計算機無法直接執(zhí)行匯編語言程序，執(zhí)行前需要翻譯為機器指令。最早是人自己翻譯，后來人們開發(fā)出“匯編系統(tǒng)”，讓計算機去完成這項工作。匯編語言細節(jié)太多，程序無結(jié)構(gòu)，缺乏組織手段，寫程序仍然很困難。計算機無法直接執(zhí)行匯編語言程序，執(zhí)行前需要翻譯為44高級語言具有類似文字的表現(xiàn)形式；用類似數(shù)學(xué)的表達式形式描述基本計算；用變量等概念取代低級的存儲概念，人們擺脫了繁瑣的存儲安排工作；提供高級流程控制手段和程序組織手段。

例：d=a*b+c高級語言45高級語言程序必須經(jīng)過翻譯變成機器語言程序。翻譯有兩種做法：編譯和解釋，相應(yīng)的翻譯工具分別叫做編譯器和解釋器。高級語言程序必須經(jīng)過翻譯變成機器語言程序。翻譯有46匯編語言VS高級語言DATASEGMENTXXDBXYYDB？DATAENDSCODESEGMENTASSUMECS：CODE，DS：DATASTART：MOVAX，DATAMOVDS，AXMOVAL，XXCMPAL，0JGEBLGRMOVAL0FFHAL，MOVYY，ALHLTBLGR：JEEQUTMOVAL01HAL，MOVYY，ALHLTEQUT:MOVEYY，ALHLTCODEENDSENDSTARTIfx>0theny=1elseifx=0theny=0elsey=-1endifPrintx,y匯編語言VS高級語言DATASEGMENTIfx>047常用高級程序語言目前，使用較廣泛的高級語言有C、C++、VisualBasic、VisualFoxpro、VisualC++、PowerBuilder、Java、Delphi、ASP、JSP、PHP等。常用高級程序語言目前，使用較廣泛的高級語言有C、C482.常見的程序控制結(jié)構(gòu)2.常見的程序控制結(jié)構(gòu)49程序設(shè)計方法程序設(shè)計方法50面向過程的程序設(shè)計面向過程的程序設(shè)計強調(diào)模塊化和結(jié)構(gòu)化。采用自頂向下、逐步求精的程序設(shè)計方法；使用三種基本控制結(jié)構(gòu)構(gòu)造程序。遵循這種方法的程序設(shè)計就是面向過程的程序設(shè)計。

常用軟件：C，F(xiàn)ORTRAN，PASCAL等。面向過程的程序設(shè)計面向過程的程序設(shè)計強調(diào)模塊化和51程序分解實例：程序分解實例：52面向?qū)ο蟮某绦蛟O(shè)計什么是對象？現(xiàn)實世界中,比如書、人、車都是對象。我們怎么區(qū)分它們呢？從外觀特征以及他們的動作行為。比如：人

外觀：一個腦袋,兩條腿,兩個胳臂…

動作行為：說話,吃飯,跑步,流淚…面向?qū)ο蟮某绦蛟O(shè)計什么是對象？現(xiàn)實世界中,比如書、人53在面向?qū)ο缶幊讨校绦虮豢醋魇窍嗷f(xié)作的對象集合，通過消息來實現(xiàn)對象間的通訊。類是對象的集合，每個對象都是某個類的實例，所有的類構(gòu)成一個通過繼承關(guān)系相聯(lián)系的層次結(jié)構(gòu)。常用語言：Java、c++、VB.Net等。在面向?qū)ο缶幊讨校绦虮豢醋魇窍嗷f(xié)作的對象集合，通54在結(jié)構(gòu)化程序設(shè)計中可以用下面的式子表示程序：程序=數(shù)據(jù)結(jié)構(gòu)+算法在面向?qū)ο蟪绦蛟O(shè)計中可以用下面的式子表示程序：程序=對象+對象+…+對象對象=算法+數(shù)據(jù)結(jié)構(gòu)在結(jié)構(gòu)化程序設(shè)計中可以用下面的式子表示程序：55面向過程：分析出解決問題所需要的步驟，用函數(shù)把這些步驟一步一步實現(xiàn)，使用的時候一個一個依次調(diào)用。面向?qū)ο螅喊褬?gòu)成問題事務(wù)分解成各個對象，建立對象的目的不是為了完成一個步驟，而是為了描敘某個事物在解決問題中的行為。面向過程：分析出解決問題所需要的步驟，用函數(shù)把這56例1：有一臺如下流程的演出：主持人開場—演員1表演—演員2表演—主持人總結(jié)。用面向過程的思想來分析，就是先完成主持人開場，再完成演員1的表演，再完成演員2的表演，最后完成主持人的總結(jié)。如果用面向?qū)ο蟮乃枷雭矸治?，就是：這個演出由兩大部分組成：主持人、演員。與主持人相關(guān)的：開場、總結(jié)。與演員相關(guān)的：演員編號、所演的節(jié)目。然后這臺演出就可以這樣策劃：需要一個主持人a，需要兩個演員b、c。演出的事情可以表示為：a的開場——>b、c的編號和節(jié)目——>a的總結(jié)。

例1：有一臺如下流程的演出：主持人開場—演員1表57例2：下五子棋

面向過程的設(shè)計思路就是首先分析問題的步驟：1、開始游戲，2、黑子先走，3、繪制畫面，4、判斷輸贏，5、輪到白子，6、繪制畫面，7、判斷輸贏，8、返回步驟2，9、輸出最后結(jié)果。把上面每個步驟用分別的函數(shù)來實現(xiàn)，問題就解決了。例2：下五子棋58面向?qū)ο蟮脑O(shè)計思路是，整個五子棋可以分為：1、黑白雙方，這兩方的行為是一模一樣的，2、棋盤系統(tǒng)，負責(zé)繪制畫面，3、規(guī)則系統(tǒng)，負責(zé)判定諸如犯規(guī)、輸贏等。第一類對象（玩家對象）負責(zé)接受用戶輸入，并告知第二類對象（棋盤對象）棋子布局的變化，棋盤對象接收到了棋子的變化就要負責(zé)在屏幕上面顯示出這種變化，同時利用第三類對象（規(guī)則系統(tǒng)）來對棋局進行判定。可以明顯地看出，面向?qū)ο笫且怨δ軄韯澐謫栴}，而不是步驟。面向?qū)ο蟮脑O(shè)計思路是，整個五子棋可以分為：59功能上的統(tǒng)一保證了面向?qū)ο笤O(shè)計的可擴展性。比如我要加入悔棋的功能，如果要改動面向過程的設(shè)計，那么從輸入到判斷到顯示這一連串的步驟都要改動，甚至步驟之間的順序都要進行大規(guī)模調(diào)整。如果是面向?qū)ο蟮脑?，只用改動棋盤對象就行了，棋盤系統(tǒng)保存了黑白雙方的棋譜，簡單回溯就可以了，而顯示和規(guī)則判斷則不用顧及，同時整個對對象功能的調(diào)用順序都沒有變化，改動只是局部的。功能上的統(tǒng)一保證了面向?qū)ο笤O(shè)計的可擴展性。60再比如：把五子棋游戲改為圍棋游戲，如果是面向?qū)ο蟮?，只需要改寫?guī)則對象就可以了；如果是面向過程的，五子棋的規(guī)則分布在程序的每個角落，要改動還不如重寫。再比如：把五子棋游戲改為圍棋游戲，如果是面向?qū)ο?1面向過程方法的特點優(yōu)點：–這種程序設(shè)計方法算法描述準確。–對每一子過程模塊容易進行程序正確性證明。缺點：–程序代碼可重用性差。程序中除少數(shù)標準庫函數(shù)外，每設(shè)計一個程序時，程序員幾乎從零做起。即使重用代碼，通常也是通過拷貝或編輯重新生成一份。–維護程序的一致性困難。前一步修改了導(dǎo)致以后步驟的修改。面向過程方法的特點優(yōu)點：62OOP方法的特點OOP以“對象”或“數(shù)據(jù)”為中心。由于對象自然地反映了應(yīng)用領(lǐng)域的模塊性，因此具有相對穩(wěn)定性，可以被用作一個組件去構(gòu)成更復(fù)雜的應(yīng)用，又由于對象一般封裝的是某一實際需求的各種成分，因此，某一對象的改變對整個系統(tǒng)幾乎沒有影響。引入了“類”的概念。類與類以層次結(jié)構(gòu)組織，屬于某個類的對象除具有該類所描述的特性外，還具有層次結(jié)構(gòu)中該類上層所有類描述的全部性質(zhì)，OOP中稱這種機制為繼承。OOP方法的模塊性與繼承性，保證了新的應(yīng)用程序設(shè)計可在原有對象的數(shù)據(jù)類型和功能的基礎(chǔ)上通過重用、擴展和細化來進行，而不必從頭做起或復(fù)制原有代碼，這樣，大大減少了重新編寫新代碼的工作量。OOP方法的特點OOP以“對象”或“數(shù)據(jù)”為中心。由于對象自634軟件工程落后的軟件生產(chǎn)方式無法滿足迅速增長的計算機軟件需求，從而導(dǎo)致軟件開發(fā)與維護過程中出現(xiàn)一系列嚴重問題的現(xiàn)象。

軟件工程源于軟件危機。4軟件工程落后的軟件生產(chǎn)方式無法滿足迅速增長的計算64軟件危機--軟件危機的表現(xiàn)軟件成本日益增長

軟件和硬件費用比不斷增加。軟件危機--軟件危機的表現(xiàn)軟件成本日益增長

軟件和硬件65軟件質(zhì)量得不到保證開發(fā)進度難以控制維護非常困難軟件質(zhì)量得不到保證66產(chǎn)生軟件危機的根源規(guī)模越來越大復(fù)雜性越來越高缺乏有效、系統(tǒng)原理、原則、方法和工具的指導(dǎo)和輔助產(chǎn)生軟件危機的根源規(guī)模越來越大67如何克服軟件危機人們面臨的不光是技術(shù)問題，更重要的是管理問題。管理不善必然導(dǎo)致失敗。人們開始探索用工程的方法進行軟件生產(chǎn)的可能性，即用現(xiàn)代工程的概念、原理、技術(shù)和方法進行計算機軟件的開發(fā)、管理和維護。如何克服軟件危機人們面臨的不光是技術(shù)問題，更重要68要建一座橋梁。我們會怎么做？了解橋梁的要求、用途—設(shè)計—維護開發(fā)大型軟件：定義—開發(fā)—維護于是，計算機科學(xué)技術(shù)的一個新領(lǐng)域—軟件工程誕生了。要建一座橋梁。我們會怎么做？于是，計算機科學(xué)技術(shù)的一69軟件工程強調(diào)使用生存周期方法學(xué)和各種結(jié)構(gòu)分析及結(jié)構(gòu)設(shè)計技術(shù)。

軟件工程在完成生存周期每個階段的任務(wù)時，采用適合該階段任務(wù)特點的系統(tǒng)化的技術(shù)方法──結(jié)構(gòu)分析或結(jié)構(gòu)設(shè)計技術(shù)。生存周期方法學(xué)就指從時間角度對軟件開發(fā)和維護的復(fù)雜問題進行分解，把軟件生存的漫長周期依次劃分為若干個階段，每個階段有相對獨立的任務(wù)，然后逐步完成每個階段的任務(wù)。軟件工程強調(diào)使用生存周期方法學(xué)和各種結(jié)構(gòu)分析及結(jié)70軟件生命周期某一軟件從被提出并著手開始實現(xiàn)，直到軟件完成其使命為止的全過程被劃分為一些階段，并稱這一全過程為軟件生命周期。通常，軟件生命周期分三個階段：軟件定義、軟件開發(fā)、運行維護。軟件生命周期某一軟件從被提出并著手開始實現(xiàn)，直到軟件71(1)可行性研究與計劃制定：確定開發(fā)目標和總的要求，給出功能、可靠性等可能方案，制定實施計劃。

(2)需求分析：對軟件需求進行分析并給出詳細定義，編寫軟件規(guī)格說明書及初步的用戶手冊，提交評審。

1軟件定義---軟件要“做什么”(1)可行性研究與計劃制定：確定開發(fā)目標和總的要求，給出功72(3)系統(tǒng)設(shè)計：概要設(shè)計和詳細設(shè)計，給出軟件的結(jié)構(gòu)、模塊和功能的劃分等。編寫概要設(shè)計、詳細設(shè)計說明書和測試計劃初稿。

(4)詳細設(shè)計：源程序編碼，把軟件設(shè)計轉(zhuǎn)換成計算機可以接受的程序代碼。編寫用戶手冊、操作手冊和單元測試計劃。(5)編碼：(6)測試：設(shè)計測試用例，檢驗軟件各個組成部分。編寫測試分析報告。

2軟件開發(fā)—軟件要“怎么做”(3)系統(tǒng)設(shè)計：概要設(shè)計和詳細設(shè)計，給出軟件的結(jié)構(gòu)、模塊和733軟件運行和維護

(7)軟件投入運行，維護(進行擴充和刪改)。

3軟件運行和維護74實驗實驗75軟件技術(shù)基礎(chǔ)1概述2算法3程序設(shè)計4軟件工程軟件技術(shù)基礎(chǔ)1概述761概述1概述77什么是計算機軟件?操作系統(tǒng)、QQ、360……計算機系統(tǒng)=硬件+軟件什么是計算機軟件?操作系統(tǒng)、QQ、360……計算機系統(tǒng)=硬件78程序以及相關(guān)的文檔的集合。程序文檔1文檔2文檔3可執(zhí)行部分不可執(zhí)行部分程序以及相關(guān)的文檔的集合。程序文檔1文檔2文檔3可執(zhí)行部79什么是文檔？文檔：記錄軟件開發(fā)活動和階段性成果，理解軟件所必需的闡述性資料。

–需求分析文檔–軟件設(shè)計文擋等編寫文檔目的

–促進對軟件的開發(fā)、管理和維護；–便于各種人員(用戶、開發(fā)人員)的交流什么是文檔？80什么是程序？程序一詞源于生活。做任何一件事情，都是有程序的。例如，頒獎大會的程序；做菜的程序等等。把做菜的步驟用大家看得懂的方式記錄下來，其他人可以按這些步驟順序?qū)嵤┚屯瓿闪嗽撌虑?。什么是程序？程序一詞源于生活。做任何一件事情，都是有81用計算機完成某事情，就把事先設(shè)計好的計算機處理信息的步驟，用計算機能夠識別的指令編寫出來，送入計算機。計算機按照指令執(zhí)行，就能完成指定的工作。

算法程序設(shè)計語言程序就是用計算機語言表述的算法。用計算機完成某事情，就把事先設(shè)計好的計82

為解決一個問題而采取的方法和步驟，就稱為算法。什么是算法？為解決一個問題而采取的方法和步驟，就稱為算法。什么是83什么是計算機語言？人們想和計算機交流，用符號來表達。怎樣維護交通秩序？音樂是怎樣表示的？什么是計算機語言？人們想和計算機交流，用符號來表達。84用來表達這種關(guān)系的符號系統(tǒng)就是計算機語言，也叫“程序設(shè)計語言”。人與計算機交流使用的是“程序設(shè)計語言”。同人類語言一樣，程序設(shè)計語言也是由字、詞和語法規(guī)則構(gòu)成的一個系統(tǒng)。用來表達這種關(guān)系的符號系統(tǒng)就是計算機語言，也叫“852算法2算法86主要內(nèi)容算法的表示算法的要素算法的特點算法的復(fù)雜度常用算法主要內(nèi)容算法的表示87算法的表示算法一般可以使用下面幾種類型的工具描述：1.自然語言例：求1×2×3×4×5。

算法的表示算法一般可以使用下面幾種類型的工具描述：88

最原始方法：步驟1：先求1×2，得到結(jié)果2。步驟2：將步驟1得到的乘積2乘以3，得到結(jié)果6。步驟3：將6再乘以4，得24。步驟4：將24再乘以5，得120。

89改進的算法：S1:使t=1S2:使i=2S3:使t×i,乘積仍然放在在變量t中，可表示為t×i→tS4:使i的值+1，即i+1→iS5:如果i≤5,返回重新執(zhí)行步驟S3以及其后的S4和S5；否則，算法結(jié)束。

改進的算法：902.專用圖形工具常用的有流程圖、PAD圖和N-S圖等。2.專用圖形工具91流程圖描述流程圖描述923.偽代碼

為了便于轉(zhuǎn)換成某種編程語言，一般采用準程序設(shè)計語言作算法描述語言。3.偽代碼93偽代碼描述：BEGIN(算法開始)1=>t2=>iwhilei<=5[t*i=>ti+1=>i]printtEND(算法結(jié)束)偽代碼描述：BEGIN(算法開始)94算法兩要素算法的兩要素算法由操作與控制結(jié)構(gòu)兩要素組成。1.操作(1)邏輯運算：“與”、“或”、“非”；(2)算術(shù)運算：加、減、乘、除；(3)數(shù)據(jù)比較：大于、小于、等于、不等于；(4)數(shù)據(jù)傳送：輸入、輸出、賦值。算法兩要素算法的兩要素952.控制結(jié)構(gòu)

1）算法的控制結(jié)構(gòu)，決定了各操作的執(zhí)行次序。用流程圖可以形象地表示出算法的控制結(jié)構(gòu)。2）任何復(fù)雜的算法都可以用順序、選擇、循環(huán)三種控制結(jié)構(gòu)組合而成。2.控制結(jié)構(gòu)1）算法的控制結(jié)構(gòu)，決定了各操作的執(zhí)行次96FTFT97我們在構(gòu)造一個算法的時候，也只能以這三種基本結(jié)構(gòu)作為“建筑單元”，遵守三種基本結(jié)構(gòu)的規(guī)范。基本結(jié)構(gòu)之間可以并列、可以相互包含，但不允許交叉。正因為整個算法都由這三種基本結(jié)構(gòu)構(gòu)成，所以結(jié)構(gòu)清晰，易于驗證，易于糾錯。這種方法就是結(jié)構(gòu)化方法。我們在構(gòu)造一個算法的時候，也只能以這三種基本結(jié)構(gòu)98算法的特征有窮性一個算法必須總是在執(zhí)行有窮步后結(jié)束，且每一步都可在有窮時間內(nèi)完成；確定性算法中的每一個指令必須有明確的含義，不能有二義性；例：武松打死老虎手舉過頭頂單手?雙手？舉多高？算法的特征有窮性一個算法必須總是在執(zhí)行有窮步后結(jié)束，且每一99可行性(有效性)算法中描述的操作都是可通過已經(jīng)實現(xiàn)的基本運算、執(zhí)行有限次實現(xiàn)的；例：a/b若b=0則無效輸入一個算法應(yīng)有0個或多個輸入；輸出一個算法應(yīng)有1個或多個輸出?？尚行?有效性)算法中描述的操作都是可通過已經(jīng)實現(xiàn)的基本100算法的復(fù)雜度評價算法的標準：–執(zhí)行算法所耗費的時間，即時間復(fù)雜度；–執(zhí)行算法所耗費的存貯空間，主要是輔助空間，即空間復(fù)雜度。算法的復(fù)雜度評價算法的標準：101思考：給出一組數(shù)12、13、26、27、38、49、55、60、67、86，查找某一個數(shù)x是否在這組數(shù)中的算法？算法1：順序查找算法2：二分法查找比較：的時間復(fù)雜度？思考：給出一組數(shù)12、13、26、27、38、49、102算法的設(shè)計要求正確性滿足需求可讀性有助于算法的理解、調(diào)試和修改健壯性容錯高效率與低存儲量算法的設(shè)計要求正確性滿足需求103常用算法常用算法104

先依據(jù)題目的部分條件確定答案的大致范圍，在此范圍內(nèi)對所有可能的情況逐一驗證，直到全部情況驗證完。若某個情況使驗證符合題目的條件，則為本題的一個答案；若全部情況驗證完后均不符合題目的條件，則問題無解。1.枚舉法先依據(jù)題目的部分條件確定答案的大致范圍，105例：公雞每只五元，母雞每只三元，小雞三只一元，問一百元錢買一百只雞有幾種買法？假設(shè)公雞數(shù)為x，母雞數(shù)為y，則小雞數(shù)是z，也就有了下面的方程式：x+y+z=1005x+3x+z/3=100例：公雞每只五元，母雞每只三元，小雞三106算法：算法：1072.遞推法順推法和倒推法例：猴子分食桃子一天，一只猴子采得一堆桃子，當(dāng)天它吃掉一半多一個，第二天又吃了一半多一個…一直到第七天，它就剩一個桃子了。那么那天它共采了多少個桃子呢？2.遞推法順推法和倒推法例：猴子分食桃子108算法：S1:使s=1S2:使t=7S3:使(s+1)×2,結(jié)果仍然放在變量s中，可表示為(s+1)×2→sS4:使t的值-1，即t-1→tS5:如果t>=1,返回重新執(zhí)行步驟S3以及其后的S4和S5；否則，算法結(jié)束。算法：1093.遞歸法如果一個過程直接或間接地調(diào)用它自身，則稱該過程是遞歸的。例：求階乘。n!=1n=1n(n-1)!n>03.遞歸法如果一個過程直接或間接地調(diào)用它自身，則例：110算法：FunctionFactorial(nAsLong)AsLongIfn=1ThenFactorial=1ElseFactorial=n*Factorial(n-1)EndFunction算法：FunctionFactorial(111例：有一個n×m的棋盤(2<=n<=50，2<=m<=50)，在棋盤上有一個馬，馬走的規(guī)則為：馬走日字且只能向右走。當(dāng)n，m給出之后，同時給出馬起始的位置和終點的位置，找出從起點到終點的所有路徑的數(shù)目。

4.回溯法回溯算法：從一條路往前走，能進則進，不能進則退回來，換一條路再試。例：有一個n×m的棋盤(2<=n<=50，2<=m<1123程序設(shè)計基礎(chǔ)程序設(shè)計的一般步驟：模型算法程序結(jié)果實際問題

解決問題的核心：算法及算法的處理對象。3程序設(shè)計基礎(chǔ)程序設(shè)計的一般步驟：模型算法程序結(jié)果實際問題113一個程序應(yīng)包括：對操作的描述。即操作步驟，也就是算法(algorithm)。對數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)(datastructure)。NikiklausWirth提出的公式：

數(shù)據(jù)結(jié)構(gòu)+算法=程序一個程序應(yīng)包括：114程序設(shè)計語言1.發(fā)展的過程程序設(shè)計語言分類：機器語言、匯編語言、高級語言機器語言匯編語言高級語言程序設(shè)計語言1.發(fā)展的過程機器語言匯編語言高級語言115機器語言機器語言是一種CPU指令系統(tǒng),是該CPU可以識別的一組組由0和1序列組成的指令碼。最初的語言是機器語言，二進制編碼，機器可直接執(zhí)行，執(zhí)行速度快。機器語言11600000001000000001000數(shù)據(jù)裝入寄存器000000001000100001010數(shù)據(jù)裝入寄存器100000101000000000001寄存器0與1的數(shù)據(jù)乘00000001000100001001數(shù)據(jù)裝入寄存器100000100000000000001寄存器0與1的數(shù)據(jù)加00000010000000001110保存寄存器0里的數(shù)編程困難、可讀性差、容易出錯、可移植性差00000001000000001000數(shù)據(jù)裝入寄存117匯編語言用一些簡潔的英文字母、符號串來替代一個特定的指令的二進制串，比如，用“ADD”代表加法，“MOV”代表數(shù)據(jù)傳遞等等。例：load0,a將單元a的數(shù)據(jù)裝入寄存器0load1,b將單元b的數(shù)據(jù)裝入寄存器1mult0,1寄存器0與1的數(shù)據(jù)乘load1,c將單元c的數(shù)據(jù)裝入寄存器1add0,1寄存器0與1的數(shù)據(jù)加save0,d將寄存器0里的數(shù)存入單元d匯編語言118計算機無法直接執(zhí)行匯編語言程序，執(zhí)行前需要翻譯為機器指令。最早是人自己翻譯，后來人們開發(fā)出“匯編系統(tǒng)”，讓計算機去完成這項工作。匯編語言細節(jié)太多，程序無結(jié)構(gòu)，缺乏組織手段，寫程序仍然很困難。計算機無法直接執(zhí)行匯編語言程序，執(zhí)行前需要翻譯為119高級語言具有類似文字的表現(xiàn)形式；用類似數(shù)學(xué)的表達式形式描述基本計算；用變量等概念取代低級的存儲概念，人們擺脫了繁瑣的存儲安排工作；提供高級流程控制手段和程序組織手段。

例：d=a*b+c高級語言120高級語言程序必須經(jīng)過翻譯變成機器語言程序。翻譯有兩種做法：編譯和解釋，相應(yīng)的翻譯工具分別叫做編譯器和解釋器。高級語言程序必須經(jīng)過翻譯變成機器語言程序。翻譯有121匯編語言VS高級語言DATASEGMENTXXDBXYYDB？DATAENDSCODESEGMENTASSUMECS：CODE，DS：DATASTART：MOVAX，DATAMOVDS，AXMOVAL，XXCMPAL，0JGEBLGRMOVAL0FFHAL，MOVYY，ALHLTBLGR：JEEQUTMOVAL01HAL，MOVYY，ALHLTEQUT:MOVEYY，ALHLTCODEENDSENDSTARTIfx>0theny=1elseifx=0theny=0elsey=-1endifPrintx,y匯編語言VS高級語言DATASEGMENTIfx>0122常用高級程序語言目前，使用較廣泛的高級語言有C、C++、VisualBasic、VisualFoxpro、VisualC++、PowerBuilder、Java、Delphi、ASP、JSP、PHP等。常用高級程序語言目前，使用較廣泛的高級語言有C、C1232.常見的程序控制結(jié)構(gòu)2.常見的程序控制結(jié)構(gòu)124程序設(shè)計方法程序設(shè)計方法125面向過程的程序設(shè)計面向過程的程序設(shè)計強調(diào)模塊化和結(jié)構(gòu)化。采用自頂向下、逐步求精的程序設(shè)計方法；使用三種基本控制結(jié)構(gòu)構(gòu)造程序。遵循這種方法的程序設(shè)計就是面向過程的程序設(shè)計。

常用軟件：C，F(xiàn)ORTRAN，PASCAL等。面向過程的程序設(shè)計面向過程的程序設(shè)計強調(diào)模塊化和126程序分解實例：程序分解實例：127面向?qū)ο蟮某绦蛟O(shè)計什么是對象？現(xiàn)實世界中,比如書、人、車都是對象。我們怎么區(qū)分它們呢？從外觀特征以及他們的動作行為。比如：人

外觀：一個腦袋,兩條腿,兩個胳臂…

動作行為：說話,吃飯,跑步,流淚…面向?qū)ο蟮某绦蛟O(shè)計什么是對象？現(xiàn)實世界中,比如書、人128在面向?qū)ο缶幊讨?，程序被看作是相互協(xié)作的對象集合，通過消息來實現(xiàn)對象間的通訊。類是對象的集合，每個對象都是某個類的實例，所有的類構(gòu)成一個通過繼承關(guān)系相聯(lián)系的層次結(jié)構(gòu)。常用語言：Java、c++、VB.Net等。在面向?qū)ο缶幊讨?，程序被看作是相互協(xié)作的對象集合，通129在結(jié)構(gòu)化程序設(shè)計中可以用下面的式子表示程序：程序=數(shù)據(jù)結(jié)構(gòu)+算法在面向?qū)ο蟪绦蛟O(shè)計中可以用下面的式子表示程序：程序=對象+對象+…+對象對象=算法+數(shù)據(jù)結(jié)構(gòu)在結(jié)構(gòu)化程序設(shè)計中可以用下面的式子表示程序：130面向過程：分析出解決問題所需要的步驟，用函數(shù)把這些步驟一步一步實現(xiàn)，使用的時候一個一個依次調(diào)用。面向?qū)ο螅喊褬?gòu)成問題事務(wù)分解成各個對象，建立對象的目的不是為了完成一個步驟，而是為了描敘某個事物在解決問題中的行為。面向過程：分析出解決問題所需要的步驟，用函數(shù)把這131例1：有一臺如下流程的演出：主持人開場—演員1表演—演員2表演—主持人總結(jié)。用面向過程的思想來分析，就是先完成主持人開場，再完成演員1的表演，再完成演員2的表演，最后完成主持人的總結(jié)。如果用面向?qū)ο蟮乃枷雭矸治?，就是：這個演出由兩大部分組成：主持人、演員。與主持人相關(guān)的：開場、總結(jié)。與演員相關(guān)的：演員編號、所演的節(jié)目。然后這臺演出就可以這樣策劃：需要一個主持人a，需要兩個演員b、c。演出的事情可以表示為：a的開場——>b、c的編號和節(jié)目——>a的總結(jié)。

例1：有一臺如下流程的演出：主持人開場—演員1表132例2：下五子棋

面向過程的設(shè)計思路就是首先分析問題的步驟：1、開始游戲，2、黑子先走，3、繪制畫面，4、判斷輸贏，5、輪到白子，6、繪制畫面，7、判斷輸贏，8、返回步驟2，9、輸出最后結(jié)果。把上面每個步驟用分別的函數(shù)來實現(xiàn)，問題就解決了。例2：下五子棋133面向?qū)ο蟮脑O(shè)計思路是，整個五子棋可以分為：1、黑白雙方，這兩方的行為是一模一樣的，2、棋盤系統(tǒng)，負責(zé)繪制畫面，3、規(guī)則系統(tǒng)，負責(zé)判定諸如犯規(guī)、輸贏等。第一類對象（玩家對象）負責(zé)接受用戶輸入，并告知第二類對象（棋盤對象）棋子布局的變化，棋盤對象接收到了棋子的變化就要負責(zé)在屏幕上面顯示出這種變化，同時利用第三類對象（規(guī)則系統(tǒng)）來對棋局進行判定。可以明顯地看出，面向?qū)ο笫且怨δ軄韯澐謫栴}，而不是步驟。面向?qū)ο蟮脑O(shè)計思路是，整個五子棋可以分為：134功能上的統(tǒng)一保證了面向?qū)ο笤O(shè)計的可擴展性。比如我要加入悔棋的功能，如果要改動面向過程的設(shè)計，那么從輸入到判斷到顯示這一連串的步驟都要改動，甚至步驟之間的順序都要進行大規(guī)模調(diào)整。如果是面向?qū)ο蟮脑?，只用改動棋盤對象就行了，棋盤系統(tǒng)保存了黑白雙方的棋譜，簡單回溯就可以了，而顯示和規(guī)則判斷則不用顧及，同時整個對對象功能的調(diào)用順序都沒有變化，改動只是局部的。功能上的統(tǒng)一保證了面向?qū)ο笤O(shè)計的可擴展性。135再比如：把五子棋游戲改為圍棋游戲，如果是面向?qū)ο蟮?，只需要改寫?guī)則對象就可以了；如果是面向過程的，五子棋的規(guī)則分布在程序的每個角落，要改動還不如重