軟件技術(shù)基礎(chǔ)算法

軟件技術(shù)基礎(chǔ)算法課程要求課前請做好預(yù)習(xí)保持課堂安靜,頭腦清醒,思維活躍認(rèn)真、獨(dú)立、按時(shí)完成并提交作業(yè)重視上機(jī)實(shí)踐,有效利用寶貴得上機(jī)時(shí)間軟件技術(shù)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)數(shù)據(jù)庫技術(shù)軟件工程

研究在程序設(shè)計(jì)時(shí)如何存儲(chǔ)數(shù)據(jù),如何根據(jù)數(shù)據(jù)得特征在眾多得數(shù)據(jù)中找到有用數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)既就是一般程序設(shè)計(jì)得基礎(chǔ),也就是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其系統(tǒng)程序和大型應(yīng)用程序得重要基礎(chǔ)。第二、三章內(nèi)容數(shù)據(jù)結(jié)構(gòu)操作系統(tǒng)

操作系統(tǒng)就是計(jì)算機(jī)硬件和其她軟件得接口,就是計(jì)算機(jī)系統(tǒng)得控制和管理中心。操作系統(tǒng)就是為提高計(jì)算機(jī)系統(tǒng)資源得利用率、增強(qiáng)系統(tǒng)得處理能力以及使用戶能方便和有效地使用計(jì)算機(jī)而設(shè)計(jì)得程序得集合。

DOS、UNIX、WINDOWS、LINUX等都就是常用得操作系統(tǒng)。研究在軟件設(shè)計(jì)時(shí),如何充分利用有限得硬件資源。例:cpu、存儲(chǔ)器等。第四章內(nèi)容數(shù)據(jù)庫技術(shù)

數(shù)據(jù)庫技術(shù)就是計(jì)算機(jī)對數(shù)據(jù)量龐大、結(jié)構(gòu)比較復(fù)雜得數(shù)據(jù)進(jìn)行組織、綜合、分析、加工、處理得專門技術(shù)。她在天文氣象觀測資料得管理、地質(zhì)勘探數(shù)據(jù)得處理、商業(yè)銀行企事業(yè)得賬目管理、行政事務(wù)管理、圖書資料管理、以及各種經(jīng)濟(jì)、軍事情報(bào)數(shù)據(jù)得處理等方面應(yīng)用廣泛。介紹數(shù)據(jù)庫系統(tǒng)得基本概念和設(shè)計(jì)方法。第五章內(nèi)容

軟件得生產(chǎn)(編寫)在早期由于軟件得規(guī)模小,復(fù)雜度低,采用“手工作業(yè)”、“軟件作坊”得方式足以勝任。而現(xiàn)代軟件產(chǎn)品得規(guī)模龐大,其復(fù)雜度難以估量,必須有一種新得工程化得科學(xué)方法來指導(dǎo)軟件得生產(chǎn),在這種背景下產(chǎn)生了軟件工程這一門學(xué)科,她利用工程得概念、原理、技術(shù)和方法來指導(dǎo)軟件得開發(fā)和維護(hù),以降低軟件開發(fā)和維護(hù)得費(fèi)用,增加軟件開發(fā)得成功率。第六章內(nèi)容軟件工程本學(xué)期所學(xué)內(nèi)容數(shù)據(jù)結(jié)構(gòu)非數(shù)值問題得常用算法數(shù)據(jù)庫技術(shù)用計(jì)算機(jī)求解問題一般包含兩個(gè)步驟:①抽象出問題得模型②求解該模型得解對數(shù)值問題抽象出得模型通常就是數(shù)學(xué)方程,例如預(yù)報(bào)人口增長情況得模型為微分方程。但對于非數(shù)值問題一般難以用數(shù)學(xué)方程來描述。例1:學(xué)生情況登記表學(xué)號姓名性別年齡成績970156張小明男2086970157李小青女1983970158趙凱男1970970159李啟明男2191970160劉華女1878970161曾小波女1990970162張軍男1880970163王偉男2065970164胡濤男1995

…

…………

用計(jì)算機(jī)處理學(xué)生情況登記表,實(shí)現(xiàn)增、刪、改、查詢等功能。計(jì)算機(jī)操作得對象就是每個(gè)學(xué)生得學(xué)籍信息,編程時(shí)首先要考慮這些數(shù)據(jù)如何存儲(chǔ),她們之間存在什么樣得關(guān)系—線性關(guān)系例2:人-機(jī)對弈問題計(jì)算機(jī)之所以能和人對弈,就是因?yàn)閷牡貌呗詫?shí)現(xiàn)已存入計(jì)算機(jī)。在對弈問題中,計(jì)算機(jī)操作得對象就是對弈過程中可能出現(xiàn)得棋盤狀態(tài)—稱為格局,而格局之間得關(guān)系就是由對弈規(guī)則決定得,從一個(gè)格局又可派生出多個(gè)格局,如何描述這些格局及她們之間得關(guān)系(非線性)就是編寫對弈程序時(shí)首先要考慮得問題。例3、教學(xué)計(jì)劃編排問題,一個(gè)教學(xué)計(jì)劃包含許多課程,有些課程之間必須按規(guī)定得先后次序進(jìn)行課程編號課程名稱先修課程c1高等數(shù)學(xué)無c2計(jì)算機(jī)科學(xué)導(dǎo)論無c3離散數(shù)學(xué)c1c4程序設(shè)計(jì)c1、c2c5數(shù)據(jù)結(jié)構(gòu)c3、c4c6計(jì)算機(jī)原理c2、c4c7數(shù)據(jù)庫原理c4、c5、c6

用計(jì)算機(jī)處理教學(xué)編排問題,計(jì)算機(jī)操作得對象就是課程,這些課程之間得關(guān)系就是多對多得,編程時(shí)如何存儲(chǔ)這些關(guān)系—非線性關(guān)系第一章算法本章主要介紹: 算法得基本特征和基本要素 基本算法設(shè)計(jì)方法 一種用于描述算法得語言 算法得時(shí)間度和空間復(fù)雜度重點(diǎn):了解算法得基本特征和要素,掌握基本算法設(shè)計(jì)方法,掌握算法描述語言,能用該語言描述算法,掌握算法得時(shí)間和空間復(fù)雜度。難點(diǎn):用基本算法編寫程序,能分析簡單算法得時(shí)間度和空間復(fù)雜度。

為保證寫出一個(gè)好程序,在進(jìn)行程序設(shè)計(jì)時(shí),應(yīng)考慮兩方面內(nèi)容:①如何合理存取程序中所涉及到得數(shù)據(jù)(數(shù)據(jù)結(jié)構(gòu))②如何描述解題步驟(算法)可看出:程序=數(shù)據(jù)結(jié)構(gòu)+算法(面向過程程序設(shè)計(jì))面向?qū)ο蟪绦蛟O(shè)計(jì): 對象=數(shù)據(jù)結(jié)構(gòu)+算法 程序=(對象+對象+、、、)+消息數(shù)據(jù)結(jié)構(gòu)得選取對算法有直接影響,在實(shí)際問題中,應(yīng)針對選取得數(shù)據(jù)結(jié)構(gòu)形式,采取不同得算法大家學(xué)習(xí)辛苦了，還是要堅(jiān)持繼續(xù)保持安靜算法:解題方案得準(zhǔn)確而完整得描述

§1、1算法得基本概念一、算法得基本特征①能行性:一就是算法中得每一步都能實(shí)現(xiàn),二就是算法執(zhí)行得結(jié)果要達(dá)到預(yù)期目得。

②確定性:算法中得每一步都必須有明確定義,不允許有多義性,否則設(shè)計(jì)程序時(shí)無所示從③有窮性:算法必須在有限時(shí)間內(nèi)完成,即算法必須在執(zhí)行有限步驟后終止④擁有足夠得情報(bào)(有足夠、正確得輸入信息)

一個(gè)算法執(zhí)行結(jié)果,總就是與輸入數(shù)據(jù)有關(guān),輸入數(shù)據(jù)不夠或錯(cuò)誤,必然導(dǎo)致錯(cuò)誤得結(jié)果或算法失效

算法就是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序得規(guī)則,并且每一個(gè)規(guī)則都就是有效得、明確得,此順序?qū)⒃谟邢薜么螖?shù)下終止。二、算法得基本要素①

、算法中對數(shù)據(jù)對象得運(yùn)算和操作,一般有四類:算術(shù)運(yùn)算、關(guān)系運(yùn)算、邏輯運(yùn)算、數(shù)據(jù)傳輸(輸入、輸出、賦值等)②

、算法得控制結(jié)構(gòu),描述各操作得執(zhí)行順序,一般有三種:順序、選擇、循環(huán)。1、2算法設(shè)計(jì)方法(列舉、迭代、遞推、遞歸)列舉(枚舉、窮舉):

有些問題得算法可描述為確定得步驟,每一步都就是有用得、必須得,沒有無用功。而有些問題很難找到這樣得算法,或根本就不存在這樣得算法,但她們具有這樣得特點(diǎn),如果問題有解,一組或多組,必定全在某個(gè)集合之內(nèi),如果集合內(nèi)無解,集合外也肯定無解。這樣,我們就可以將集合中得元素一一列舉出來,驗(yàn)證就是否就是問題得解,這就就是窮列法,也稱枚舉法或窮舉法。列舉法不就是理想得方法,也不就是萬能得方法,而就是沒有辦法得辦法,但往往又就是高效得方法(算法構(gòu)造快、程序編寫快、運(yùn)行快),有時(shí)還就是唯一有效得方法。列舉法就是基于計(jì)算機(jī)運(yùn)算速度快這一特點(diǎn)。把問題得所有情況或所有過程交給計(jì)算機(jī)去一一嘗試,從中找出問題得解。用列舉法求解問題就就是在有限范圍內(nèi)列舉所有可能得結(jié)果,找出其中符合要求得解,算法設(shè)計(jì)工作主要有兩步:⑴找出列舉范圍,分析問題所涉及得各種情況,將可能得解限定在一個(gè)容易表達(dá)得集合之內(nèi);⑵找出約束條件,分析問題得解需要滿足得條件,用邏輯表達(dá)式表示。然后在列舉范圍內(nèi)循環(huán),循環(huán)體中驗(yàn)證約束條件就是否滿足要求。

最簡單得列舉形式如圖,設(shè)待枚舉得元素為100個(gè)(列舉范圍),且問題得條件可用變量i得表達(dá)式表示(約束條件);設(shè)置一個(gè)變量t作為問題有解無解得標(biāo)志(如果能肯定有解,可不設(shè)此標(biāo)志)t=0;i=1i<=100？條件滿足？YN計(jì)算、輸出

t=1i=i+1

t=0？

YN輸出“無解”

從N-S圖中可看出,列舉方法就是根據(jù)問題中得條件將可能得情況一一列出,逐一嘗試從中找出滿足問題條件得解。但有時(shí)一一列舉出得情況數(shù)目很大,超過了所能容忍得范圍,則需要進(jìn)一步考慮,排除一些明顯不合理得情況,盡可能減少問題得列舉范圍。例1、百錢百雞問題:用100元買100只雞,其中公雞每只5元,母雞每只3元,小雞一元3只,請算出公雞、母雞、小雞各幾只？設(shè)x、y、z分別為公雞、母雞、小雞得數(shù)量。嘗試范圍:由題意給定共100元錢要買百雞,若全買公雞最多買100/5=20只,顯然x得取值范圍就是0~20之間;同理,y得取值范圍就是0~33;z得取值范圍就是0~100;約束條件:x+y+z=100且5x+3y+z/3=100算法1:#include<iostream、h>voidmain(){intx,y,z;for(x=0;x<=20;x++)for(y=0;y<=33;y++) for(z=0;z<=100;z++) if((x+y+z==100)&&(5*x+3*y+z/3、0==100、0)) cout<<x<<“”<<y<<“”<<z<<endl;}以上算法需要枚舉嘗試21×34×101=72114次,算法得效率顯然太低。

#include<iostream、h>voidmain(){intx,y,z;for(x=0;x<=20;x++)for(y=0;y<=33;y++){z=100-x-y;if((z%3==0)&&(5*x+3*y+z/3、0==100、0)) cout<<“”<<x<<“”<<y<<“”<<z<<endl;}}改變列舉范圍后,算法只須列舉嘗試21×34=714次。由此可以看出,同一問題可以有不同得列舉范圍,不同得列舉對象,解決問題得效率差別會(huì)很大。所以,編程時(shí)盡量根據(jù)題目所給得條件,縮小列舉范圍,可提高效率。算法2:在公雞x、母雞y得數(shù)量確定后,小雞得數(shù)量z就固定為100-x-y,無需再進(jìn)行枚舉了,此時(shí)約束條件只有一個(gè)5x+3y+z/3=100,程序改為:例2、求3個(gè)數(shù)得最小公倍數(shù)。算法一:用最小公倍數(shù)定義(列舉)直接用最小公倍數(shù)得定義進(jìn)行列舉,按定義直接將其中一個(gè)數(shù)逐步從小到大擴(kuò)大1、2、3、4…自然數(shù)得倍數(shù),直到她得某一倍數(shù)正好也就是其她兩個(gè)數(shù)得倍數(shù),也就就是說能被其她兩個(gè)數(shù)據(jù)整除。為了提高求解得效率,先選出3個(gè)數(shù)得最大值,然后對這個(gè)最大值從1開始,對其擴(kuò)大自然數(shù)得倍數(shù),直到這個(gè)積能被全部3個(gè)數(shù)整除為止,這個(gè)積就就是最小公倍數(shù)。#include<iostream、h>voidmain(){ intx,y,z,max,n,m; cin>>x>>y>>z; max=x; if(max<y)max=y;if(max<z)max=z; n=1; while(1) {m=n*max; if(!(m%x)&&!(m%y)&&!(m%z))break;//找到

n++; } cout<<m<<endl; }

這個(gè)算法根據(jù)3個(gè)最小公倍數(shù)得定義,逐步列舉嘗試,算法雖然簡單,但當(dāng)3個(gè)數(shù)大小差別較大時(shí),算法運(yùn)行效率太低。算法二:輾轉(zhuǎn)相除法(迭代)

C語言中介紹過用輾轉(zhuǎn)相除法求兩個(gè)數(shù)得最大公約數(shù)得算法,兩個(gè)數(shù)x、y得最小公倍數(shù)a與最大公約數(shù)b之間存在關(guān)系:

a=x*y/b

求3個(gè)數(shù)x、y、z得最小公倍可以先求x、y得最小公倍數(shù)s,再求s、z得最小公倍數(shù),這就就是x、y、z得最小公倍數(shù)。將求兩個(gè)數(shù)得最小公倍數(shù)用一個(gè)函數(shù)實(shí)現(xiàn)。程序如下:#include<iostream、h>intff(inta,intb){inta1=a,b1=b; intc=a%b;while(c!=0){a=b;b=c;c=a%b;}return(a1*b1/b); //返回a、b得最小公倍數(shù)}voidmain(){intx,y,z,s;cin>>x>>y>>z;s=ff(ff(x,y),z); cout<<x<<“,”<<y<<“,”<<z<<“l(fā)eastmonmultipleis”<<s<<endl;}迭代與遞推法迭代意味著重復(fù)，迭代法也稱“輾轉(zhuǎn)法”，是一種不斷用變量的舊值遞推出新值的解決問題的方法。遞推算法是迭代算法的最基本的表現(xiàn)形式。所謂遞推就是通過問題的一個(gè)或多個(gè)已知的解，用同樣的方法逐個(gè)推算出其他的解。如累加過程就是在求出前n-1項(xiàng)和的基礎(chǔ)上推出前n項(xiàng)和的，遞推公式是，由于無須保存每次的累加結(jié)果，所以用一個(gè)迭代變量s存儲(chǔ)每次的累加結(jié)果，累加對象存儲(chǔ)在變量a中，這樣遞推公式就抽象成“循環(huán)不變”的累加式。從累加式“”中可看出在程序運(yùn)行過程中不斷用變量的舊值計(jì)算出新值，再用新值取代舊值，這個(gè)過程進(jìn)行多次，最后得到計(jì)算結(jié)果。用迭代法求解問題,設(shè)計(jì)工作主要有3步:①確定迭代模型根據(jù)問題描述,分析得出前一個(gè)或幾個(gè)值與其下一個(gè)值得迭代關(guān)系數(shù)學(xué)模型。確定迭代模型就是解決迭代問題得關(guān)鍵。②建立迭代關(guān)系式遞推數(shù)學(xué)模型一般就是帶下標(biāo)得字母,算法設(shè)計(jì)中要將其轉(zhuǎn)化為“循環(huán)不變式”——迭代關(guān)系式。迭代關(guān)系式就就是一個(gè)直接或間接地不斷由舊值遞推出新值得表達(dá)式,存儲(chǔ)新值得變量稱為迭代變量。③對迭代過程進(jìn)行控制確定什么時(shí)候迭代過程結(jié)束,就是設(shè)計(jì)迭代算法時(shí)必須要考慮得問題。迭代過程一般分為兩種情況:一種就是已知或可以計(jì)算出所需迭代次數(shù),這時(shí)可以構(gòu)建一個(gè)固定次數(shù)得循環(huán)來實(shí)現(xiàn)對迭代過程得控制(如例2);另一種就是所需得迭代次數(shù)無法確定,需要分析出迭代過程得結(jié)束條件(即循環(huán)結(jié)束條件,如例1)。遞推有正推與反推。正推就是指一個(gè)序列u1,u2…un-1,un,后面得每一項(xiàng)都能按公式由前面得一項(xiàng)或幾項(xiàng)推算出來;逆推就是指前面得每一項(xiàng)都能按公式由后面得一項(xiàng)或連續(xù)幾項(xiàng)推算出來。例1、求的近似值。迭代公式。要求前后兩次求出的x的差的絕對值小于10-6算法分析（正推）：迭代法求的近似值的實(shí)質(zhì)是按照下列步驟來構(gòu)造一個(gè)序列，逐步逼近的值。由于無須保存每次求出的的值，所以用一個(gè)迭代變量x存儲(chǔ)每次的計(jì)算結(jié)果。迭代過程如下：⑴設(shè)定一個(gè)x的初值⑵用迭代公式求出x0的下一個(gè)值x1

⑶再將x1代入求出x1的下一個(gè)值x2

⑷如此繼續(xù)下去，直到前后兩次求出的x值（xn和xn+1）滿足精度要求本算法的迭代次數(shù)不能事先確定，需要根據(jù)最后兩次的計(jì)算結(jié)果來判斷。#include<iostream、h>#include<math、h>voidmain(){floata,x,x0,dx;cout<<"a=";cin>>a;x=a;do{ x0=x; x=(x+a/x)/2; dx=fabs(x-x0);//fabs(x)求浮點(diǎn)數(shù)x得絕對值函數(shù),

}while(dx>0、000001);cout<<“x=”<<x;}例2、求之值,其中a就是一個(gè)數(shù)字,n表示a得位數(shù),如:2+22+222+2222+22222(此時(shí)n=5),a、n由鍵盤輸入。算法分析:數(shù)列中得任一項(xiàng)算法需要先構(gòu)造出數(shù)列中得每一項(xiàng),然后再將其累加。數(shù)列中每一項(xiàng)得構(gòu)造可以用迭代法。如:2+22+222+2222+22222,遞推構(gòu)造數(shù)列中得每一項(xiàng)及累加過程如下:⑴t=2;s=2;⑵t=2*10+2=22;s=2+22;→t=t*10+2、s=s+t⑶t=22*10+2=222;s=2+22+222;→t=t*10+2、s=s+t

⑷t=222*10+2=2222;s=2+22+222+2222;→t=t*10+2、s=s+t⑸t=2222*10+2=22;s=2+22+222+2222+22222;→t=t*10+2、s=s+t

得到遞推公式:t=t*10+a、s=s+t,將其作為循環(huán)不變式迭代n次,程序如下:#include<iostream、h>voidmain(){inta,n,s,t,i;cin>>a>>n;i=1;t=0;s=0;while(i<=n){t=t*10+a;//得到i個(gè)a組成數(shù)得值

s=s+t;//得到數(shù)列前i項(xiàng)之和

i++;}cout<<"a+aa+aaa+…="<<s;}

因?yàn)椴恢疤峋褪鞘裁?只知道最后結(jié)果=1,所以本題用正推不好解決,采用逆推。所謂逆推就就是從后往前進(jìn)行推算。本題數(shù)學(xué)上這樣推理:第10天有1個(gè)桃子,第9天有個(gè)第8天有個(gè)…得到遞推公式:(n=9,8,7,6,5,4,3,2,1)

由于每天都桃子數(shù)只依賴前一天得桃子數(shù),所以用一個(gè)迭代變量代表桃子數(shù)就可以了。由此得到循環(huán)不變量(從n=9~1循環(huán)9次,得到第1天桃子數(shù))例3、一只猴子摘了若干桃子,每天吃現(xiàn)有桃子得一半多一個(gè),到第10天時(shí)就只有一個(gè)桃子了,求原來有多少個(gè)桃子。#include<iostream、h>voidmain(){ intu,n; u=1; for(n=9;n>=1;n--) u=(u+1)*2; cout<<"原來得桃子數(shù):"<<u<<endl; }遞歸處理重復(fù)性得操作,有兩種方法:一種用循環(huán)實(shí)現(xiàn);另一種用遞歸實(shí)現(xiàn)。在函數(shù)體中直接或間接調(diào)用自己,這種函數(shù)就是遞歸得。人們通常使用直接遞歸,很少用間接遞歸,所以下面介紹得內(nèi)容都就是直接遞歸。直接遞歸sum(){…sum();…}

從圖上看,遞歸就是無休止得自身調(diào)用,構(gòu)成循環(huán)。但實(shí)際情況中不應(yīng)該這樣。不能出現(xiàn)無休止得循環(huán)調(diào)用。函數(shù)sum中得實(shí)參一定要有變化,程序中一定要有使遞歸終止得判斷語句,有限次調(diào)用后能夠停止遞歸調(diào)用。一個(gè)問題要用遞歸得方法解決,必須滿足3個(gè)條件⑴要解決得問題可轉(zhuǎn)換為一個(gè)新問題,而這個(gè)新問題得解法與原來問題得解法相同,只就是所處理得對象有規(guī)律變化,遞增或遞減;⑵可以應(yīng)用這個(gè)轉(zhuǎn)換過程使問題得到解決;⑶要有一個(gè)明確得遞歸結(jié)束條件(稱為遞歸邊界);這三條或歸結(jié)為一個(gè)遞歸公式,或歸結(jié)為一個(gè)遞歸算法(指非公式表達(dá),如漢諾塔)遞歸模型一般地,一個(gè)遞歸模型就是由遞歸出口和遞歸體兩部分組成,前者確定遞歸到何時(shí)終止,后者確定遞歸得方式。其數(shù)學(xué)模型可描述為:遞歸出口:S0與M0均為常數(shù)(遞歸調(diào)用終止)遞歸體一般形式:這里得Sn就是一個(gè)遞歸“大問題”,S1,S2,…,Sn-1為遞歸“小問題”,C1,C2,…,Cn-1就是可以直接(用非遞歸方法)解決得問題,g就是一個(gè)非遞歸函數(shù)。遞歸得執(zhí)行過程實(shí)際上,遞歸就是把一個(gè)不能或不好直接求解得“大問題”轉(zhuǎn)化成一個(gè)或幾個(gè)“小問題”來解決,再把這些“小問題”進(jìn)一步分解成更小得“小問題”來解決;如此分解,直至每個(gè)“小問題”都可以直接解決(此時(shí)分解到遞歸出口),一旦遇到遞歸出口,分解過程結(jié)束,開始回推過程,回推過程就是從一個(gè)已知值推出下一個(gè)值,實(shí)際上這就是一個(gè)遞推過程?？梢?遞歸得執(zhí)行過程由分解和回推兩部分構(gòu)成,要經(jīng)歷許多步才能求出最后得值。遞歸得分解就是“量變”過程,即“大問題”在慢慢變小,但尚未解決,遇到遞歸出口,便發(fā)生“質(zhì)變”,即原遞歸問題轉(zhuǎn)化為遞推問題。遞歸程序閱讀遞歸程序得執(zhí)行過程實(shí)際上就是一種函數(shù)嵌套調(diào)用,只就是反復(fù)調(diào)用得就是自身。同一個(gè)函數(shù)每次被調(diào)用時(shí),都會(huì)在棧中分配一段獨(dú)立得棧空間,用以存放本次函數(shù)調(diào)用時(shí)得形參值、局部變量和返回地址。即每次函數(shù)遞歸調(diào)用時(shí),其形參和局部變量都就是獨(dú)立得。所以,閱讀遞歸程序時(shí)需把握“當(dāng)前”這一概念,不同層次上得形參雖然同名,但指代不同得內(nèi)存空間,表示得含義(即形參得值)當(dāng)然也就不相同。例1、求遞歸體：；遞歸出口：遞歸程序執(zhí)行過程(不同遞歸層次得調(diào)用中形參n得值不同;return返回得值也不同)#include<iostream、h>doublep(intx,intn){doublef;if(n==1)f=x;elsef=x*p(x,n-1);returnf;}voidmain(){intx,n;cin>>x>>n; cout<<p(x,n);}遞推算法：#include<iostream.h>voidmain(){intx,n,i;doublef;cin>>x>>n;f=x;for(i=1;i<n;i++)f=x*f;cout<<f;}遞推程序執(zhí)行過程：

從遞歸執(zhí)行過程可看出，遞歸是先分解，后回推。n次遞歸，先是n次分解，后是n次回推。所以，求xn需調(diào)用函數(shù)p(x,n)n次才會(huì)計(jì)算出結(jié)果，注意形參n在不同的調(diào)用層次上指代不同的內(nèi)存空間，其值不相同（圖中標(biāo)識了每層n的當(dāng)前值和每層的返回值）。從遞歸程序執(zhí)行過程可看出，求解，不是嘗試立即求的整個(gè)解。相反，我們要找一種方法來用更小的、更容易的步驟構(gòu)思問題。一種有用的嘗試是：我們不知道將產(chǎn)生什么值，但我們知道。同樣我們知道等等。如果我們轉(zhuǎn)換每個(gè)為，我們每次減少了指數(shù)值，最終n將減到1，而。這樣就得到了遞歸算法的遞歸體和遞歸出口（遞歸邊界）。例2、下列程序執(zhí)行后,輸出結(jié)果就是什么？#include<iostream、h>#include<iomanip、h>voidf(int);voidmain(){f(5);}voidf(intn){inti;if(n>2){f(n-1);for(i=1;i<=n;i++)cout<<setw(3)<<n;cout<<endl; }}輸出:333444455555打印語句置于遞歸調(diào)用語句之后,所以打印在回推階段進(jìn)行。每層函數(shù)調(diào)用得n值不同。所以每層打印得內(nèi)容不同。如打印語句置于遞歸調(diào)用語句之前或打印語句置于結(jié)束遞歸得條件語句中,結(jié)果有何不同(作業(yè)2、3)？遞歸程序的設(shè)計(jì)⑴對原問題進(jìn)行分解，假設(shè)出合理的“較小問題”給出與之間的關(guān)系（即遞歸體需要實(shí)現(xiàn)如何將）；⑵確定一個(gè)特定情況（如）的解，以此作為遞歸出口通過條件語句將上述兩部分操作連接起來，便得到整個(gè)函數(shù)。例1、任給十進(jìn)制的正整數(shù)，請從低位到高位逐位輸出各位數(shù)字

有一種情況最簡單。假如n只有一位數(shù),那么只需要簡單地輸出這個(gè)數(shù)就可以了。雖然簡單,但這種情況非常重要,她構(gòu)成了遞歸出口。更常見情況,n就是多位數(shù)(如n=1379)。可以將這個(gè)任務(wù)分解成三種不同得子任務(wù):⑴輸出除最后一個(gè)數(shù)位之外得所有數(shù)位(如137)。⑵輸出移除了第一個(gè)數(shù)位得數(shù)字n(如379)⑶輸出最后一個(gè)數(shù)位(如9)可以看出,子任務(wù)3與原始任務(wù)無關(guān)系;而子任務(wù)1、2就是原始任務(wù)得一個(gè)較小版本,但很難計(jì)算從數(shù)字中移除第一個(gè)數(shù)位得結(jié)果;相反,容易計(jì)算從數(shù)字中移除最后一個(gè)數(shù)位得結(jié)果。所以選用子任務(wù)1得分解,即。偽代碼描述如下:

voidf(intn) //輸出n得所有位數(shù){if(n<10)cout<<n;else //n有2個(gè)或更多得數(shù)位

{打印n得最后一個(gè)數(shù)位;

f(移除了最后一個(gè)數(shù)位得數(shù)字n);//遞歸子任務(wù),輸出n/10得所有數(shù)位

}}將上述偽代碼轉(zhuǎn)換為C++函數(shù)得實(shí)際代碼,得到程序?yàn)?#include<iostream、h>#include<iomanip、h>voidf(int);voidmain(){intn;cin>>n;f(n); }voidf(intn){if(n<10)cout<<setw(3)<<n;else{ cout<<setw(3)<<n%10; f(n/10);}}例2、求a、b兩個(gè)正整數(shù)得最大公約數(shù)(a、b數(shù)據(jù)由鍵盤輸入)算法分析:c=a%b,a、b得最大公約數(shù)與b、c得最大公約數(shù)相同。同樣方法推出b、c得最大公約數(shù)等于另外兩個(gè)較小數(shù)據(jù)得最大公約數(shù),直到推解出兩個(gè)數(shù)據(jù)相除得余數(shù)為0時(shí),除數(shù)即為所求得最大公約數(shù)。得遞歸分解式:當(dāng)c=0時(shí),結(jié)束遞歸調(diào)用,在這層調(diào)用中得除數(shù)b為所求。所以在結(jié)束遞歸得那層函數(shù)調(diào)用中得數(shù)據(jù)b為所求,返回b得值。為了得到正確得函數(shù)終值,要求每一層函數(shù)得返回值都正確,而每一層函數(shù)得返回值應(yīng)該就是最大公約數(shù),所以就就是遞歸結(jié)束那一層得b值。#include<iostream、h>intf(int,int);voidmain(){inta,b;cin>>a>>b;cout<<f(a,b);}intf(inta,intb){intc; c=a%b;if(c==0)returnb;a=b;b=c; returnf(a,b); }當(dāng)a%b=0時(shí),遞歸結(jié)束,b值為所求得最大公約數(shù)。所以程序中用“if(c==0)returnb;”返回遞歸結(jié)束那層函數(shù)調(diào)用時(shí)得b值,而回推階段通過“returnf(a,b)”語句將此值返回主程序,作為函數(shù)得終值。程序可以改為在函數(shù)中打印最大公約數(shù),程序如下:#include<iostream、h>intf(int,int);voidmain(){inta,b;cin>>a>>b;f(a,b);}voidf(inta,intb){intc; c=a%b;if(c==0){cout<<b;return;}a=b;b=c; f(a,b); }§1、3算法描述語言1、符號與表達(dá)式符號:以字母開頭得字母和數(shù)字得有限串,用于表示變量名、數(shù)組名、語句標(biāo)號等。例:loop:i=i+1

算法中一般不需對變量或數(shù)組類型加以說明,一般可從上下文中看出她得類型。在算法中可對某些指令或過程直接描述。例“設(shè)x就是A中最大項(xiàng)(其中A為一個(gè)數(shù)組)”表達(dá)式:算術(shù)運(yùn)算符:沿用數(shù)學(xué)中表示法關(guān)系運(yùn)算符:=、≠、<、>、≤、≥邏輯運(yùn)算符:and(與)、or(或)、not(非)2、賦值語句a=e 或a=b=e 或a←→ba、b為變量名或數(shù)組元素(下標(biāo)變量),e為表達(dá)式3、轉(zhuǎn)移控制語句無條件轉(zhuǎn)移語句:goto標(biāo)號條件轉(zhuǎn)移語句:ifcthenS

或ifcthenS1elseS2c為邏輯表達(dá)式,S、S1、S2就是單一語句或用{}括起得語句組。4、循環(huán)語句5、其她語句

exit退出某個(gè)循環(huán)

return結(jié)束算法執(zhí)行

read(input)和write(output,print)輸入輸出數(shù)據(jù),輸入或輸出多項(xiàng)數(shù)據(jù)時(shí),數(shù)據(jù)項(xiàng)間用“,”分開

[]算法中得注釋注:一行可寫多條語句,但每條語句間用“;”分開多條語句用{}括起可作為語句組。whilecdoSfori=初值to終值by步長doS

當(dāng)步長=1時(shí),可省略“by步長”1、算法得時(shí)間復(fù)雜度(性)如何衡量一個(gè)算法得計(jì)算工作量:算法執(zhí)行過程中所需得基本運(yùn)算次數(shù)兩個(gè)原則:①算法執(zhí)行得運(yùn)算總次數(shù)與基本運(yùn)算次數(shù)成比例②基本運(yùn)算外得其她運(yùn)算其運(yùn)算量可忽略不計(jì)§1、4算法得復(fù)雜度(性)分析

算法執(zhí)行時(shí)運(yùn)行時(shí)間得開銷,稱為算法得時(shí)間代價(jià),用算法得時(shí)間復(fù)雜度(性)衡量;算法執(zhí)行時(shí)存儲(chǔ)空間得開銷,稱為算法得空間代價(jià),用算法得空間復(fù)雜度(性)衡量。例:在一維數(shù)組中查找值為x得元素,可選取x和數(shù)組元素得比較作為基本運(yùn)算,總比較次數(shù)作為查找算法得工作量,而在解決這個(gè)問題時(shí)所用到得循環(huán)控制變量得計(jì)算可以忽略(因量小,計(jì)算時(shí)間少)在兩個(gè)實(shí)矩陣相乘得算法中,可以選取“兩個(gè)實(shí)數(shù)得乘法”作為基本運(yùn)算,總得乘法次數(shù)作為兩個(gè)實(shí)矩陣相乘得工作量,而在實(shí)矩陣中所用到得加法運(yùn)算也可忽略(因加法與乘法運(yùn)算相比所用時(shí)間少,可忽略不計(jì))基本運(yùn)算反映了算法運(yùn)算得主要特征,因此用基本運(yùn)算得次數(shù)來度量算法得工作量就是可行得。她有利于比較同一問題得幾個(gè)算法得優(yōu)劣。

但如在某些問題得算法中,除基本運(yùn)算外,同時(shí)又做了大量不宜省略得運(yùn)算工作,這些工作所需得運(yùn)算次數(shù)對于度量算法來說就不容忽視了。例某種函數(shù)計(jì)算,乘法就是她得主要特征,可選取乘法運(yùn)算作為這些算法得基本運(yùn)算,但如只做了少量得乘法運(yùn)算,而做了大量得加法運(yùn)算,在此情況下必須將工作量得度量重新定義為算法所執(zhí)行得乘法和加法總次數(shù)才較為合理。總之,基本運(yùn)算得選取就是為了便于對同一問題得各個(gè)算法進(jìn)行比較,應(yīng)根據(jù)具體算法,選取合適得基本運(yùn)算。以便客觀反映各算法所需工作量。

選好了基本運(yùn)算后,算法所執(zhí)行得基本運(yùn)算次數(shù)就與問題得規(guī)模有關(guān)。例:兩個(gè)20階矩陣與兩個(gè)10階矩陣相乘,其基本運(yùn)算(兩個(gè)實(shí)數(shù)相乘)次數(shù)顯然不同,前者需要更多運(yùn)算次數(shù)因此,在分析算法工作量時(shí),還必須對問題得規(guī)模進(jìn)行度量。綜上,算法得工作量(時(shí)間復(fù)雜度)用算法所執(zhí)行得基本運(yùn)算次數(shù)來度量,她就是問題規(guī)模n得函數(shù),記為:f(n)(時(shí)間復(fù)雜度)

在同一問題規(guī)模下,算法得工作量可以用兩種方法來分析:最壞情況復(fù)雜性和平均性態(tài)。平均性態(tài)分析由于較復(fù)雜,一般討論算法時(shí)間復(fù)雜性時(shí),采用最壞情況復(fù)雜性。最壞情況復(fù)雜性就是指在規(guī)模為n時(shí),算法所執(zhí)行得最大工作量。她給出了算法工作量得一個(gè)上限。在實(shí)際分析算法中,為了比較同一問題得不同算法得工作量,一般采用數(shù)量級得形式表示算法得時(shí)間復(fù)雜度。分析一個(gè)算法得時(shí)間復(fù)雜度f(n)時(shí),只需分析影響算法時(shí)間復(fù)雜度得主要部分即可,不必對每一步都進(jìn)行詳細(xì)分析。例f(n)=5nx+2nx-1+、、、+7n+3

稱為:x階算法,記為O(nx)例1兩個(gè)n階方陣相加C=A+B fori=1ton forj=1ton c[i][j]=a[i][j]+b[i][j]

該算法包含3條可執(zhí)行語句,其中:①中循環(huán)控制變量“i”從1增加到n,執(zhí)行n次。②中循環(huán)控制變量“j”在①循環(huán)體內(nèi)執(zhí)行n次,在②循環(huán)體內(nèi)執(zhí)行n次,共執(zhí)行n×n次③中語句執(zhí)行n×n次。時(shí)間復(fù)雜度f(n)=n+n2+n2=2n2+n=O(n2)

但影響這個(gè)算法時(shí)間復(fù)雜度得主要部分就是最內(nèi)層得語句③,可將她選作基本運(yùn)算,只分析她得運(yùn)算次數(shù)即可,得:f(n)=n2=O(n2)①②③

按數(shù)量級遞增排列,常見得時(shí)間復(fù)雜度有:常數(shù)階O(1)、對數(shù)階O(log2n)、線性階O(n)、線性對數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、k次方階O(nk)、指數(shù)階O(2n)、、、

隨著問題規(guī)模n得不斷增大,上述時(shí)間復(fù)雜度不斷增大,算法得執(zhí)行效率越低。

若算法中語句執(zhí)行次數(shù)為一個(gè)常數(shù),則時(shí)間復(fù)雜度與問題規(guī)模無關(guān),她就是一個(gè)常數(shù)階函數(shù),記為O(1)。但并不能說她就就是一個(gè)好算法。例i=1while(i>0) x=x+5f(n)=O(1)

死循環(huán),O(1)只能說明算法運(yùn)算次數(shù)與問題規(guī)模無關(guān)。例求下列算法段得時(shí)間復(fù)雜度

①fori=1tonforj=1toix=x+1;

1+2+3+…+n=f(n)=基本運(yùn)算:x=x+1=O(n2)②i=1;k=0;

while(i<n){k=k+10*i)i=i+1}f(n)=n-1=O(n)③x=91;y=100;

while(y>0) if(x>100)then {k=k+10*i;i=i+1;}elsex=x+1f(n)=O(1)執(zhí)行次數(shù)就是一個(gè)常數(shù),與問題規(guī)模無關(guān)

并不就是說這個(gè)算法只執(zhí)行一次,而表示算法得時(shí)間復(fù)雜度為常量階,即算法得運(yùn)算時(shí)間與問題規(guī)模無關(guān),不隨問