計算機軟件技術(shù)基礎(chǔ) 第3版 課件 第1章 計算機軟件技術(shù)基礎(chǔ)概論

第1章

計算機軟件技術(shù)基礎(chǔ)概論

目錄1.1計算機基礎(chǔ)1.2計算機軟件基礎(chǔ)1.3計算機軟件技術(shù)的發(fā)展1.4軟件的設(shè)計方法1.5程序設(shè)計的一些基本算法1.1計算機基礎(chǔ)1.1.1計算機的發(fā)展概況1.1.2計算機的基本組成1.1.3計算機的應(yīng)用科學(xué)計算、數(shù)據(jù)處理、過程控制、計算機輔助系統(tǒng)、人工智能、辦公自動化1.2.1計算機軟件的基本概念計算機軟件是計算機程序、程序所使用的數(shù)據(jù)以及有關(guān)的文檔資料的集合，即軟件=程序+數(shù)據(jù)+文檔。1.2計算機軟件基礎(chǔ)分類：系統(tǒng)軟件、應(yīng)用軟件系統(tǒng)軟件：直接控制和協(xié)調(diào)計算機、通信設(shè)備及其他外部設(shè)備的軟件，這類軟件一般緊靠硬件，是用戶與計算機之間的第一層界面。最典型的系統(tǒng)軟件是操作系統(tǒng)，另外還有語言處理程序、服務(wù)性程序和數(shù)據(jù)庫管理系統(tǒng)等。

應(yīng)用軟件：指用戶借助系統(tǒng)軟件而開發(fā)編制的用來解決各種實際問題的軟件。

常用的應(yīng)用軟件有工程計算軟件、文字處理軟件、實時過程控制軟件、輔助設(shè)計軟件、智能處理軟件計算機語言

機器語言、匯編語言、高級語言

1.2.2計算機語言程序設(shè)計（1946-1955）軟件時代（1955-1970）軟件工程（1970-）軟件特點邏輯產(chǎn)品、質(zhì)量保證靈活、生命周期不定、動靜結(jié)合1.3計算機軟件技術(shù)的發(fā)展程序設(shè)計時代這個時代計算機硬件的特點是：邏輯電路是由電子管組成的，計算機內(nèi)存容量比較小，運行速度慢，外部設(shè)備少，系統(tǒng)穩(wěn)定性差。系統(tǒng)設(shè)計與實現(xiàn)是以硬件為中心，而不是程序設(shè)計，編程只是處于從屬地位，程序設(shè)計的工具是機器語言、匯編語言及服務(wù)性程序。軟件時代這一時期硬件已經(jīng)廣泛采用了晶體管和小規(guī)模的集成電路，計算機容量增大，運算速度增大，運算速度加快，外部設(shè)備也比較齊全，運行穩(wěn)定性高；計算機產(chǎn)量也大幅度上升，程序員需求量猛增，使軟件人員極缺。這時已經(jīng)提出了軟件的概念，軟件工具已經(jīng)使用了第二代語言，如FORTRAN，COBOL等編譯系統(tǒng)。軟件工程時代在20世紀60年代中后期，計算機硬件迅速發(fā)展，而傳統(tǒng)的軟件開發(fā)方法不能適應(yīng)大型軟件的生產(chǎn)，導(dǎo)致軟件危機。于是人們想到了用工程化的思想來生產(chǎn)軟件，主要是研究軟件開發(fā)的方法、技術(shù)和原理，由此軟件生產(chǎn)開始進入了軟件工程時代。軟件工程時代人們開始重點關(guān)注軟件的設(shè)計方法，提出了諸如自頂向下、逐步求精的結(jié)構(gòu)程序設(shè)計方法、面向?qū)ο蟮姆椒ǖ刃碌某绦蛟O(shè)計方法。軟件工程正是從管理和技術(shù)兩方面來研究和解決如何更好地開發(fā)和維護計算機軟件的一門新興的工程學(xué)科。面向數(shù)據(jù)流的軟件設(shè)計方法

以需求分析階段產(chǎn)生的數(shù)據(jù)流圖為基礎(chǔ)，按一定的步驟映射成的軟件結(jié)構(gòu)。這個方法與結(jié)構(gòu)化分析銜接，構(gòu)成了完整的結(jié)構(gòu)化分析與設(shè)計技術(shù)，是目前使用最廣泛的軟件設(shè)計方法之一。

面向數(shù)據(jù)結(jié)構(gòu)的軟件設(shè)計方法

是用數(shù)據(jù)結(jié)構(gòu)作為程序設(shè)計的基礎(chǔ)。這種方法的最終目標是得出對程序處理過程的描述，最適合于在詳細設(shè)計階段使用，在完成了軟件結(jié)構(gòu)設(shè)計之后，可以使用面向數(shù)據(jù)結(jié)構(gòu)的方法來設(shè)計每個模塊的處理過程。面向?qū)ο蟮能浖O(shè)計方法

是一種支持模塊化設(shè)計和軟件重用的編程方法，把程序設(shè)計的主要活動集中在建立對象和對象之間的聯(lián)系上，所以一個面向?qū)ο蟮某绦蚓褪窍嗷リP(guān)聯(lián)的對象的集合。1.4軟件的設(shè)計方法1.5.1迭代法：方程求根1.5.2遞推法：斐波那契數(shù)列1.5.3遞歸法：斐波那契數(shù)列1.5.4窮舉法：百錢買百雞1.5.5回朔法：填字游戲1.5.6貪婪法：裝箱問題

1.5.7分治法：

循環(huán)賽日程表

1.5程序設(shè)計中常見的算法思想迭代法是一種不斷用變量的舊值遞推新值的過程，跟迭代法相對應(yīng)的是直接法（或者稱為一次解法），即一次性解決問題。比較典型的迭代法如“二分法”和“牛頓迭代法”1.5.1迭代法與應(yīng)用（1）確定迭代變量。（2）建立迭代關(guān)系式。（3）對迭代過程進行控制。一種是所需的迭代次數(shù)是個確定的值;一種是所需的迭代次數(shù)無法確定。運用迭代法的基本步驟是：利用迭代法來求方程或方程的根是迭代法的一個重要的應(yīng)用。例如設(shè)方程為f(x)=0，用某種數(shù)學(xué)方法導(dǎo)出等價的形式x=g(x)，然后按以下步驟執(zhí)行：（1）選方程的一個近似根，賦給變量x0。（2）將x0的值保存于變量x1，然后計算g(x1)，將結(jié)果存于變量x0。（3）當x0與x1差的絕對值小于指定的精度的要求時，重復(fù)步驟（2）的計算。

{x0=初始近似根；

do{

x1=x0；

x0=g(x1)；/*按特定的方程計算新的近似根*/

}while(fabs(x0-x1)>Epsilon)；

printf(“方程的近似根是%f\n”，x0)；}（1）如果方程無解，算法求出的近似根序列就不會收斂，迭代過程會變成死循環(huán)，因此在使用迭代算法前應(yīng)先考察方程是否有解，并在程序中對迭代的次數(shù)給予限制。（2）方程雖然有解，但若迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導(dǎo)致迭代失敗。利用牛頓迭代法求方程的根。方程為ax3+bx2+cx+d=0，系數(shù)a,b,c,d由主函數(shù)輸入。求x在1附近的一個實根，求出根后由主函數(shù)輸出。分析：對于方程f(x)=ax3+bx2+cx+d=0，通過牛頓迭代公式：xk+1=xk-f(xk)/f’(xk)，可以推出迭代公式為x=x-(ax3+bx2+cx+d)/(3ax2+2bx+c)，其中f’(x)=3ax2+2bx+c。1.5.2遞推法與應(yīng)用遞推法是利用問題本身所具有的一種遞推關(guān)系求問題解的一種方法。問題規(guī)模為N的解，當N=0或1時解已知得到問題規(guī)模為i-1的解后，由遞推性質(zhì)，能從已求得的規(guī)模為1，2，…，i-1的一系列解，構(gòu)造出問題規(guī)模為i的解。從i=0或i=1出發(fā)，由已知至i-1規(guī)模的解，通過遞推，獲得規(guī)模為i的解，直至得到N的解?！斑f推”法來輸出Fibonacci數(shù)列的前20項值。Fibonacci系列是：第0個元素為0，第1個元素為1，后面每一個元素都是前面兩個元素值的和，即{0,1,1,2,3,5,8,13,21,34,55,…}這個數(shù)列利用遞推過程可以得到如下公式：f(0)=0；f(1)=1；f(n)=f(n-2)+f(n-1)（n>1）。intf[20]；f[0]=0;f[1]=1;for(inti=0;i<20;i++){if(i>1)f[i]=f[i-2]+f[i-1];/*遞推公式*/printf(“Fibonacci[%d]=%d\n”,i,f[i]);}1.5.3遞歸法與應(yīng)用遞歸法是設(shè)計和描述算法的一種有力的工具，它在復(fù)雜算法的描述中被經(jīng)常采用規(guī)模為N的問題，分解成規(guī)模較小的問題,從這些小問題的解方便地構(gòu)造出大問題的解.規(guī)模較小的問題也能采用同樣方法，分解成規(guī)模更小的問題,并從這些更小問題的解構(gòu)造出規(guī)模較大問題的解當規(guī)模N=1時，能直接得解。編寫計算斐波那契（Fibonacci）數(shù)列的第n項函數(shù)fib（n）。intfib(intn){ if(n==0) return0; if(n==1) return1; if(n>1) returnfib(n-1)+fib(n-2);}遞推和回歸兩個階段遞推階段，把較復(fù)雜的問題（規(guī)模為n）的求解推到比原問題簡單一些的問題（規(guī)模小于n）的求解。求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。遞推階段，必須要有終止遞歸的情況。例如n為1和0的情況。回歸階段，獲得最簡單情況的解后，逐級返回，依次得到稍復(fù)雜問題的解，得到fib(1)和fib(0)后，返回得到fib(2)的結(jié)果，……，在得到了fib(n-1)和fib(n-2)的結(jié)果后，返回得到fib(n)的結(jié)果。遞歸引起一系列的函數(shù)調(diào)用，并且可能會有一系列的重復(fù)計算，遞歸算法的執(zhí)行效率相對較低。當某個遞歸算法能較方便地轉(zhuǎn)換成遞推算法時，通常按遞推算法編寫程序。1.5.4窮舉法與應(yīng)用窮舉搜索法是對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，并從眾找出那些符合要求的候選解作為問題的解。實例4：百錢買百雞問題——一百個銅錢買了一百只雞，其中公雞一只5錢、母雞一只3錢，小雞一錢3只，問一百只雞中公雞、母雞、小雞各多少）設(shè)公雞、母雞、小雞分別為x，y，z這里x,y,z為正整數(shù)，且z是3的倍數(shù)；由于雞和錢的總數(shù)都是100，可以確定x,y,z的取值范圍：x的取值范圍為1～20y的取值范圍為1～33z的取值范圍為3～99，步長為3用窮舉的方法，遍歷x,y,z的所有可能組合，最后得到問題的解。1.5.5回溯法與應(yīng)用回溯法也稱為試探法將問題的候選解按某種順序逐一枚舉和檢驗。當前候選解不可能是解時，就選擇下一個候選解當前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探。候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。填字游戲在3×3個方格的方陣中要填入數(shù)字1到N（N≥10）內(nèi)的某9個數(shù)字，每個方格填一個整數(shù)，使得的所有相鄰兩個方格內(nèi)的兩個整數(shù)之和為質(zhì)數(shù)。試求出所有滿足這個要求的各種數(shù)字填法。用試探法找到問題的解，即從第一個方格開始，為當前方格尋找一個合理的整數(shù)填入，并在當前位置正確填入后，為下一方格尋找可填入的合理整數(shù)。如不能為當前方格找到一個合理的可填，就要回退到前一方格，調(diào)整前一方格的填入數(shù)。當?shù)诰艂€方格也填入合理的整數(shù)后，就找到了一個解，將該解輸出，并調(diào)整第九個的填入的整數(shù)，尋找下一個解。1.5.6貪婪法與應(yīng)用貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。平時購物找錢時裝箱問題裝箱問題可簡述如下：設(shè)有n種物品，體積分別為v0、v1、…、vn-1。將這n種物品裝到容量都為V的若干箱子里。約定這n種物品的體積均不超過V。裝箱問題要求使裝盡這n種物品的箱子數(shù)要少。對裝箱問題采用非常簡單的近似算法，即貪婪法。該算法依次將物品放到它第一個能放進去的箱子中設(shè)n件物品的體積是按從大到小排好序的，即有v0≥v1≥…≥vn-1。該算法不一定能找到最優(yōu)解1.5.7分治法與應(yīng)用任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模N有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問