算法設(shè)計(jì)與分析第 王紅梅 胡明 習(xí)題答案_第1頁
算法設(shè)計(jì)與分析第 王紅梅 胡明 習(xí)題答案_第2頁
算法設(shè)計(jì)與分析第 王紅梅 胡明 習(xí)題答案_第3頁
算法設(shè)計(jì)與分析第 王紅梅 胡明 習(xí)題答案_第4頁
算法設(shè)計(jì)與分析第 王紅梅 胡明 習(xí)題答案_第5頁
已閱讀5頁,還剩36頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、習(xí)題1圖1.7 七橋問題北區(qū)東區(qū)島區(qū)南區(qū)1. 圖論誕生于七橋問題。出生于瑞士的偉大數(shù)學(xué)家歐拉(Leonhard Euler,17071783)提出并解決了該問題。七橋問題是這樣描述的:一個人是否能在一次步行中穿越哥尼斯堡(現(xiàn)在叫加里寧格勒,在波羅的海南岸)城中全部的七座橋后回到起點(diǎn),且每座橋只經(jīng)過一次,圖1.7是這條河以及河上的兩個島和七座橋的草圖。請將該問題的數(shù)據(jù)模型抽象出來,并判斷此問題是否有解。 七橋問題屬于一筆畫問題。 輸入:一個起點(diǎn)輸出:相同的點(diǎn)1, 一次步行2, 經(jīng)過七座橋,且每次只經(jīng)歷過一次3, 回到起點(diǎn)該問題無解:能一筆畫的圖形只有兩類:一類是所有的點(diǎn)都是偶點(diǎn)。另一類是只有二個

2、奇點(diǎn)的圖形。2在歐幾里德提出的歐幾里德算法中(即最初的歐幾里德算法)用的不是除法而是減法。請用偽代碼描述這個版本的歐幾里德算法1.r=m-n2.循環(huán)直到r=02.1  m=n2.2   n=r2.3  r=m-n3 輸出m 3設(shè)計(jì)算法求數(shù)組中相差最小的兩個元素(稱為最接近數(shù))的差。要求分別給出偽代碼和C+描述。/采用分治法/對數(shù)組先進(jìn)行快速排序/在依次比較相鄰的差#include <iostream>using namespace std;int partions(int b,int low,int h

3、igh)int prvotkey=blow;b0=blow;while (low<high) while (low<high&&bhigh>=prvotkey) -high; blow=bhigh; while (low<high&&blow<=prvotkey) +low; bhigh=blow;blow=b0;return low;void qsort(int l,int low,int high)int prvotloc;if(low<high) prvotloc=partions(l,low,high); /將第一次排

4、序的結(jié)果作為樞軸 qsort(l,low,prvotloc-1); /遞歸調(diào)用排序 由low 到prvotloc-1 qsort(l,prvotloc+1,high); /遞歸調(diào)用排序 由 prvotloc+1到 highvoid quicksort(int l,int n)qsort(l,1,n); /第一個作為樞軸 ,從第一個排到第n個int main()int a11=0,2,32,43,23,45,36,57,14,27,39;int value=0;/將最小差的值賦值給valuefor (int b=1;b<11;b+)cout<<ab<<' &

5、#39;cout<<endl;quicksort(a,11);for(int i=0;i!=9;+i) if( (ai+1-ai)<=(ai+2-ai+1) ) value=ai+1-ai; else value=ai+2-ai+1;cout<<value<<endl;return 0;4 設(shè)數(shù)組an中的元素均不相等,設(shè)計(jì)算法找出an中一個既不是最大也不是最小的元素,并說明最壞情況下的比較次數(shù)。要求分別給出偽代碼和C+描述。#include<iostream>using namespace std; int main() int a=1,2

6、,3,6,4,9,0; int mid_value=0;/將“既不是最大也不是最小的元素”的值賦值給它 for(int i=0;i!=4;+i) if(ai+1>ai&&ai+1<ai+2) mid_value=ai+1; cout<<mid_value<<endl;break;else if(ai+1<ai&&ai+1>ai+2) mid_value=ai+1;cout<<mid_value<<endl;break; /for return 0;5. 編寫程序,求n至少為多大時(shí),n個“1”

7、組成的整數(shù)能被2013整除。#include<iostream>using namespace std;int main() double value=0; for(int n=1;n<=10000 ;+n) value=value*10+1; if(value%2013=0) cout<<"n至少為:"<<n<<endl; break; /for return 0;6. 計(jì)算值的問題能精確求解嗎?編寫程序,求解滿足給定精度要求的值#include <iostream>using namespace std;

8、int main () double a,b; double arctan(double x);/聲明a = 16.0*arctan(1/5.0); b = 4.0*arctan(1/239); cout << "PI=" << a-b << endl;return 0;double arctan(double x) int i=0; double r=0,e,f,sqr;/定義四個變量初 sqr = x*x;e = x;while (e/i>1e-15)/定義精度范圍 f = e/i;/f是每次r需要疊加的方程 r = (i%4=

9、1)?r+f:r-f; e = e*sqr;/e每次乘于x的平方 i+=2;/i每次加2 /while return r;7. 圣經(jīng)上說:神6天創(chuàng)造天地萬有,第7日安歇。為什么是6天呢?任何一個自然數(shù)的因數(shù)中都有1和它本身,所有小于它本身的因數(shù)稱為這個數(shù)的真因數(shù),如果一個自然數(shù)的真因數(shù)之和等于它本身,這個自然數(shù)稱為完美數(shù)。例如,6=1+2+3,因此6是完美數(shù)。神6天創(chuàng)造世界,暗示著該創(chuàng)造是完美的。設(shè)計(jì)算法,判斷給定的自然數(shù)是否是完美數(shù)#include<iostream>using namespace std;int main() int value, k=1; cin>>

10、;value; for (int i = 2;i!=value;+i) while (value % i = 0 ) k+=i;/k為該自然數(shù)所有因子之和 value = value/ i;/for if(k=value) cout<<"該自然數(shù)是完美數(shù)"<<endl; else cout<<"該自然數(shù)不是完美數(shù)"<<endl;return 0;8. 有4個人打算過橋,這個橋每次最多只能有兩個人同時(shí)通過。他們都在橋的某一端,并且是在晚上,過橋需要一只手電筒,而他們只有一只手電筒。這就意味著兩個人過橋后必須有

11、一個人將手電筒帶回來。每個人走路的速度是不同的:甲過橋要用1分鐘,乙過橋要用2分鐘,丙過橋要用5分鐘,丁過橋要用10分鐘,顯然,兩個人走路的速度等于其中較慢那個人的速度,問題是他們?nèi)窟^橋最少要用多長時(shí)間?由于甲過橋時(shí)間最短,那么每次傳遞手電的工作應(yīng)有甲完成甲每次分別帶著乙丙丁過橋例如:第一趟:甲,乙過橋且甲回來第二趟:甲,丙過橋且甲回來第一趟:甲,丁過橋一共用時(shí)19小時(shí)9歐幾里德游戲:開始的時(shí)候,白板上有兩個不相等的正整數(shù),兩個玩家交替行動,每次行動時(shí),當(dāng)前玩家都必須在白板上寫出任意兩個已經(jīng)出現(xiàn)在板上的數(shù)字的差,而且這個數(shù)字必須是新的,也就是說,和白板上的任何一個已有的數(shù)字都不相同,當(dāng)一方再

12、也寫不出新數(shù)字時(shí),他就輸了。請問,你是選擇先行動還是后行動?為什么?設(shè)最初兩個數(shù)較大的為a, 較小的為b,兩個數(shù)的最大公約數(shù)為factor。則最終能出現(xiàn)的數(shù)包括: factor, factor*2, factor*3, ., factor*(a/factor)=a. 一共a/factor個。如果a/factor 是奇數(shù),就選擇先行動;否則就后行動。習(xí)題21如果T1(n)=O(f (n),T2(n)=O(g(n),解答下列問題:(1)證明加法定理:T1(n)T2(n)=maxO(f (n), O(g(n);(2)證明乘法定理:T1(n)×T2(n)=O(f (n)×O(g(n

13、);(3)舉例說明在什么情況下應(yīng)用加法定理和乘法定理。,(1)(2)(3)比如在 for(f(n))for(g(n)中應(yīng)該用乘法定理如果在“講兩個數(shù)組合并成一個數(shù)組時(shí)”,應(yīng)當(dāng)用加法定理(1)int Stery(int n) int S = 0; for (int i = 1; i <= n; i+) S = S + i * i; return S;(2)int Q(int n) if (n = 1) return 1; else return Q(n-1) + 2 * n - 1;2考慮下面的算法,回答下列問題:算法完成什么功能?算法的基本語句是什么?基本語句執(zhí)行了多少次?算法的時(shí)間復(fù)雜

14、性是多少?(1) 完成的是1-n的平方和基本語句:s+=i*i,執(zhí)行了n次時(shí)間復(fù)雜度O(n)(2) (2)完成的是n的平方基本語句:return Q(n-1) + 2 * n 1,執(zhí)行了n次時(shí)間復(fù)雜度O(n)3. 分析以下程序段中基本語句的執(zhí)行次數(shù)是多少,要求列出計(jì)算公式。(1)for (i = 1; i <= n; i+)if (2*i <= n) for (j = 2*i; j <= n; j+) y = y + i * j;(2)m = 0;for (i = 1; i <= n; i+) for (j = 1; j <= 2*i; j+) m=m+1; (1

15、) 基本語句2*i<n執(zhí)行了n/2次基本語句y = y + i * j執(zhí)行了2/n次一共執(zhí)行次數(shù)=n/2+n/2=O(n)(2) 基本語句m+=1執(zhí)行了(n/2)*n=O(n*n)4. 使用擴(kuò)展遞歸技術(shù)求解下列遞推關(guān)系式:(1) (2)(1) int T(int n) if(n=1)return 4;else if(n>1)return 3*T(n-1);(2)int T(int n) if(n=1)return 1;else if(n>1)return 2*T(n/3)+n;5. 求下列問題的平凡下界,并指出其下界是否緊密。(1)求數(shù)組中的最大元素; (2)判斷鄰接矩陣表示

16、的無向圖是不是完全圖;(3)確定數(shù)組中的元素是否都是惟一的;(4)生成一個具有n個元素集合的所有子集(1) (n) 緊密?(2) (n*n)(3) (logn+n)(先進(jìn)行快排,然后進(jìn)行比較查找)(4) (2n)7畫出在三個數(shù)a, b, c中求中值問題的判定樹。a<ba<b<c是是是否否否a<cb<cb<a<cb<cC<b<ab<c<aa<cC<a<ba<c<b否否是是8國際象棋是很久以前由一個印度人Shashi發(fā)明的,當(dāng)他把該發(fā)明獻(xiàn)給國王時(shí),國王很高興,就許諾可以給這個發(fā)明人任何他想要的獎賞

17、。Shashi要求以這種方式給他一些糧食:棋盤的第1個方格內(nèi)只放1粒麥粒,第2格2粒,第3格4粒,第4格8粒,以此類推,直到64個方格全部放滿。這個獎賞的最終結(jié)果會是什么樣呢?#include<iostream>using namespace std;int main() long double result=1; double j=1; for(int i=1;i<=64;+i) j=j*2; result+=j; j+; cout<<result<<endl; return 0;習(xí)題31 假設(shè)在文本"ababcabccabccacbab&

18、quot;中查找模式"abccac",寫出分別采用BF算法和KMP算法的串匹配過/BF算法#include<iostream>using namespace std;int BF(char S, char T) int index = 0; int i = 0, j = 0; while (Si != '0') && (Tj != '0') if (Si = Tj) i+; j+; else +index; i = index; j = 0; if (Tj = '0') return index +

19、 1; else return 0;int main()char s119="ababcabccabccacbab"char s27="abccac" cout<< BF( s1, s2) <<endl;return 0;/KMP算法#include<iostream>using namespace std;void GetNext(char T , int next ) /求模式T的next值int i, j, len;next0 = -1; for (j = 1; Tj!='0' j+) /依次求n

20、extjfor (len = j - 1; len >= 1; len-) /相等子串的最大長度為j-1 for (i = 0; i < len; i+) /依次比較T0Tlen-1與Tj-lenTj-1 if (Ti != Tj-len+i) break; if (i = len) nextj = len; break;/forif (len < 1) nextj = 0; /其他情況,無相等子串/forint KMP(char S , char T ) /求T在S中的序號int i = 0, j = 0;int next80; /假定模式最長為80個字符 GetNext(

21、T, next); while (Si != '0' && Tj != '0') if (Si = Tj) i+; j+; else j = nextj; if (j = -1) i+; j+; if (Tj = '0') return (i - strlen(T) +1); /返回本趟匹配的開始位置else return 0;int main()char s1="ababcabccabccacbab"char s2="abccac"cout<<KMP(s1,s2)<<

22、;endl; return 0; 2.分式化簡。設(shè)計(jì)算法,將一個給定的真分?jǐn)?shù)化簡為最簡分?jǐn)?shù)形式。例如,將6/8化簡為3/4。#include<iostream>using namespace std;int main() int n;/分子 int m;/分母 int factor;/最大公因子 int factor1; cout<<"輸入一個真分?jǐn)?shù)的分子與分母: "<<endl; cin>>n>>m; int r = m % n;/因?yàn)槭钦娣謹(jǐn)?shù) 所以分母一定大于分子 factor1=m;factor=n;whil

23、e (r != 0) factor1 =factor; factor = r; r = factor1% factor;cout<<"輸出該真分?jǐn)?shù)的最簡分?jǐn)?shù): "<<(n/factor)<<"/"<<(m/factor)<<endl;return 0;3. 設(shè)計(jì)算法,判斷一個大整數(shù)能否被11整除??梢酝ㄟ^以下方法:將該數(shù)的十進(jìn)制表示從右端開始,每兩位一組構(gòu)成一個整數(shù),然后將這些數(shù)相加,判斷其和能否被11整除。例如,將562843748分割成5,62,84,37,48,然后判斷(5+62+84+3

24、7+48)能否被11整除/將一個大整數(shù)看成一個數(shù)組/數(shù)組的奇數(shù)位對應(yīng)數(shù)的10倍加上數(shù)組偶數(shù)對應(yīng)數(shù)的本身/驗(yàn)證結(jié)果能否被11整除 #include<iostream>using namespace std;int main()int a9=5,6,2,8,4,3,7,4,8;int result=0; /result為題目要求的各位之和for(int i=0;i!=9;+i) if(i%2=0) result+=ai; /i 為偶數(shù)位時(shí),結(jié)果加上其對應(yīng)數(shù)組數(shù)的本身 else result+=ai*10; /i 為奇數(shù)位時(shí),結(jié)果加上對應(yīng)數(shù)組數(shù)的10倍 if(result%11=0)co

25、ut<<"該整數(shù)能被11整除"<<endl;else cout<<"該整數(shù)不能被11整除"<<endl;return 0;4. 數(shù)字游戲。把數(shù)字 1,2,9這9個數(shù)字填入以下含有加、減、乘、除的四則運(yùn)算式中,使得該等式成立。要求9個數(shù)字均出現(xiàn)一次且僅出現(xiàn)一次,且數(shù)字1不能出現(xiàn)在乘和除的一位數(shù)中(即排除運(yùn)算式中一位數(shù)為1的平凡情形)。 ¨¨×¨¨¨¨÷¨¨¨ = 05. 設(shè)計(jì)算法求解an mod m,

26、其中a、n和m均為大于1的整數(shù)。(提示:為了避免an超出int型的表示范圍,應(yīng)該每做一次乘法之后對n取模)#include<iostream>using namespace std;int square(int x) return x*x;/用遞歸思想int resultmod(int a, int n) if(n= 0)return 1; if(n%2 = 0)return square(resultmod(a, n/2);/n為偶數(shù)的時(shí),取n的一半防止溢出 else return a*resultmod(a, n-1);/n為奇數(shù)時(shí),取n-1;int main() int a,

27、 n, m; cout<<"請輸入a,n, m: "<<" " cin>>a>>n>>m;cout<<endl; int result = resultmod(a, n); cout<<"an mod m的結(jié)果為:"<< result % m<<endl; return 0; 6. 設(shè)計(jì)算法,在數(shù)組rn中刪除所有元素值為x的元素,要求時(shí)間復(fù)雜性為O(n),空間復(fù)雜性為O(1)。7. 設(shè)計(jì)算法,在數(shù)組rn中刪除重復(fù)的元素,要求移動

28、元素的次數(shù)較少并使剩余元素間的相對次序保持不變。#include <iostream>using namespace std;void deletere(int a,int N)int b100=0;int i,k;k=0;static int j=0;for(i=0;i<N;i+)bai+;for(i=0;i<100;i+) if(bi!=0)if(bi=2)k+;aj=i;j+;for(i=0;i<N-k;i+)cout<<ai<<endl;int main()int a=1,2,1,3,2,4;deletere(a,6);return

29、 0;/在數(shù)組查找相同的元素/把其中一個相同的數(shù)值的元素位置設(shè)成一個“特殊數(shù)值”/輸出所求函數(shù)#include<iostream>using namespace std;int main() int a=1,2,1,5,3,2,9,4,5,5,3,5;int i,j; for( i=0;i<12;i+) for(j=0;j<i;j+)if(aj=ai) ai=64787250;/設(shè)一個數(shù)組不存在的數(shù)值/for for(i=0;i<12;i+)if(ai!=64787250) cout<<ai<<" " cout<&

30、lt;endl; return 0;8. 設(shè)表A=a1, a2, , an,將A拆成B和C兩個表,使A中值大于等于0的元素存入表B,值小于0的元素存入表C,要求表B和C不另外設(shè)置存儲空間而利用表A的空間。 /先對A進(jìn)行快排/將大于0的元素給B,小于0的元素給C#include <iostream>using namespace std;int partions(int l,int low,int high)int prvotkey=llow;l0=llow;while (low<high) while (low<high&&lhigh>=prvot

31、key) -high; llow=lhigh; while (low<high&&llow<=prvotkey) +low; lhigh=llow;llow=l0;return low;void qsort(int l,int low,int high)int prvotloc;if(low<high) prvotloc=partions(l,low,high); /將第一次排序的結(jié)果作為樞軸 qsort(l,low,prvotloc-1); /遞歸調(diào)用排序 由low 到prvotloc-1 qsort(l,prvotloc+1,high); /遞歸調(diào)用排序

32、由 prvotloc+1到 highvoid quicksort(int l,int n)qsort(l,1,n); /第一個作為樞軸 ,從第一個排到第n個int main()int a11=-2,2,32,43,-23,45,36,-57,14,27,-39;quicksort(a,11);for(int i=1;i<11;i+)if(ai<0) cout<<"C: "<<ai<<' 'elsecout<<"B: "<<ai<<' ' c

33、out<<endl;return 0;9. 荷蘭國旗問題。要求重新排列一個由字符R, W, B(R代表紅色,W代表白色,B代表蘭色,這都是荷蘭國旗的顏色)構(gòu)成的數(shù)組,使得所有的R都排在最前面,W排在其次,B排在最后。為荷蘭國旗問題設(shè)計(jì)一個算法,其時(shí)間性能是O(n)。/0代表紅;1代表白;2代表藍(lán)#include <iostream> using namespace std; const int N = 20; void swap_ab ( int *p , int *q ) int tmp = *p; *p = *q; *q = tmp; void process (

34、int a, int n ) int *p, *q; p = q = a; while ( p != a+n-1 ) /p向前遍歷,直到便利完畢 if ( *(p+1) < *p ) q = p+1; while ( *q < *(q-1) ) swap_ab ( q, q-1 ); -q; /q指針后移 /if+p; /while int main() int aN = 0, 2, 1, 2, 0, 1, 0, 2, 2, 1, 0, 1, 2, 1, 1, 0, 0, 1, 1, 2; /待處理的數(shù)組 cout << "處理后的數(shù)組序列: " &

35、lt;<endl; process ( a, N ); for (int i=0; i< N; +i ) cout << ai <<" " cout << endl; return 0; 10. 設(shè)最近對問題以k維空間的形式出現(xiàn),k維空間的兩個點(diǎn)p1=(x1, x2, , xk)和p2=(y1, y2, , yk)的歐幾里德距離定義為:。對k維空間的最近對問題設(shè)計(jì)蠻力算法,并分析其時(shí)間性能。11設(shè)計(jì)蠻力算法求解小規(guī)模的線性規(guī)劃問題。假設(shè)約束條件為:(1)x+y4;(2)x+3y6;(3)x0且y0;使目標(biāo)函數(shù)3x+5y取得極大

36、值。#include<iostream>using namespace std;int main() int x,y,x0,y0; int summax=0,temp=0; for(x0=0;x0<=4;+x0) for(y0=0;(x0+y0<=4)&&(x0+3*y0<=6);+y0) temp=3*x0+5*y0; if(temp>=summax) summax=temp; x=x0;/符合sum最大值的x y=y0;/符合sum最大值得y /for cout<<"x= "<<x<<

37、;" y= "<<y<<" summax= "<<summax<<endl; return 0;12設(shè)計(jì)算法,判定一個以鄰接矩陣表示的連通圖是否具有歐拉回路。算法描述:輸入:鄰接矩陣(n*n)輸出:如有證明有歐拉回路,則輸出該回路,否則,輸出無解信息1 對矩陣的對角線是否有>0的元素進(jìn)行判斷 1.1 循環(huán)變量i從1n重復(fù)進(jìn)行下述操作: 計(jì)算矩陣i次方,如果矩陣對角線上有>0的元素,則跳轉(zhuǎn)到1.2 否則+i; 1.2 如果矩陣對角線有>0的元素,則輸出該回路2 輸出無解信息;13找詞游戲。要

38、求游戲者從一張?zhí)顫M字符的正方形表中,找出包含在一個給定集合中的所有單詞。這些詞在正方形表中可以橫著讀、豎著讀、或者斜著讀。為這個游戲設(shè)計(jì)一個蠻力算法14. 變位詞。給定兩個單詞,判斷這兩個單詞是否是變位詞。如果兩個單詞的字母完全相同,只是位置有所不同,則這兩個單詞稱為變位詞。例如,eat和tea是變位詞。/判斷qwer和rewq是否是變位詞#include<iostream>#include<string>using namespace std;int main()char s5="qwer"char t5="rewq"for(i

39、nt i=0;i!=4;+i)if(si!=t3-i)cout<<"qwer和rewq不是變位詞"<<endl; return 0; break; cout<<"qwer和rewq是變位詞"<<endl; return 0;15在美國有一個連鎖店叫7-11店,因?yàn)檫@個商店以前是早晨7點(diǎn)開門,晚上11點(diǎn)關(guān)門。有一天,一個顧客在這個店挑選了四樣?xùn)|西,然后到付款處去交錢。營業(yè)員拿起計(jì)算器,按了一些鍵,然后說:“總共是$7.11?!边@個顧客開了個玩笑說:“哦?難道因?yàn)槟銈兊牡昝?-11,所以我就要付$7.11嗎?

40、”營業(yè)員沒有聽出這是個玩笑,回答說:“當(dāng)然不是,我已經(jīng)把這四樣?xùn)|西的價(jià)格相乘才得出這個結(jié)果的!”顧客一聽非常吃驚,“你怎么把他們相乘呢?你應(yīng)該把他們相加才對!”營業(yè)員答道:“噢,對不起,我今天非常頭疼,所以把鍵按錯了?!比缓螅瑺I業(yè)員將結(jié)果重算了一遍,將這四樣?xùn)|西的價(jià)格加在一起,然而,令他倆更為吃驚的是總和也是$7.11。設(shè)計(jì)蠻力算法找出這四樣?xùn)|西的價(jià)格各是多少?該算法為:int $7.11(float a,float b,float c,float d,int n) for(int i=0;i!=n;+i) for(int j=0;j!=n;+j) for(int k=0;k!=n;+k) f

41、or(int m=0;m!=n;+m) if(ai+bj+ck+dm)=7.11 && a i*bj*ck*dm=7.11) cout<<ai<<bj<<ck<<dm<<endl; return 0; return 0;習(xí)題41. 分治法的時(shí)間性能與直接計(jì)算最小問題的時(shí)間、合并子問題解的時(shí)間以及子問題的個數(shù)有關(guān),試說明這幾個參數(shù)與分治法時(shí)間復(fù)雜性之間的關(guān)系。2. 證明:如果分治法的合并可以在線性時(shí)間內(nèi)完成,則當(dāng)子問題的規(guī)模之和小于原問題的規(guī)模時(shí),算法的時(shí)間復(fù)雜性可達(dá)到O(n)。O(N)=2*O(N/2)+xO(N)+x

42、=2*O(N/2)+2*xa*O(N)+x=a*(2*O(N/2)+x)+x=2*a *O(N/2)+(a+1)*x由此可知,時(shí)間復(fù)雜度可達(dá)到O(n);3.分治策略一定導(dǎo)致遞歸嗎?如果是,請解釋原因。如果不是,給出一個不包含遞歸的分治例子,并闡述這種分治和包含遞歸的分治的主要不同。不一定導(dǎo)致遞歸。如非遞歸的二叉樹中序遍歷。 這種分治方法與遞歸的二叉樹中序遍歷主要區(qū)別是:應(yīng)用了棧這個數(shù)據(jù)結(jié)構(gòu)。4. 對于待排序序列(5, 3, 1, 9),分別畫出歸并排序和快速排序的遞歸運(yùn)行軌跡。 歸并排序: 第一趟:(5,3)(1,9);第二趟:(3,5,1,9);第三趟:(1,3,5,9);快速排序: 第一趟

43、:5( ,3,1,9);/5為哨兵,比較9和5 第二趟:5(1,3, ,9);/比較1和5,將1挪到相應(yīng)位置; 第三趟:5(1,3, ,9);/比較3和5; 第四趟:(1,3,5,9); 5. 設(shè)計(jì)分治算法求一個數(shù)組中的最大元素,并分析時(shí)間性能。/簡單的分治問題/將數(shù)組均衡的分為“前”,“后”兩部分/分別求出這兩部分最大值,然后再比較這兩個最大值#include<iostream>using namespace std;extern const int n=6;/聲明int main()int an=0,6,1,2,3,5;/初始化int mid=n;int num_max1=0,

44、num_max2=0;for(int i=0;i<=n;+i)/前半部分 if(ai>num_max1) num_max1=ai;for(int j=n+1;j<n;+j)/后半部分if(aj>num_max2) num_max2=aj;if(num_max1>=num_max2)cout<<"數(shù)組中的最大元素: "<<num_max1<<endl;else cout<<"數(shù)組中的最大元素: "<<num_max2<<endl;return 0;時(shí)間復(fù)雜

45、度:O(n)6. 設(shè)計(jì)分治算法,實(shí)現(xiàn)將數(shù)組An中所有元素循環(huán)左移k個位置, 要求時(shí)間復(fù)雜性為O(n),空間復(fù)雜性為O(1)。例如,對abcdefgh循環(huán)左移3位得到defghabc。 /采用分治法/將數(shù)組分為0-k-1和k-n-1兩塊/將這兩塊分別左移/然后再合并左移#include <iostream>using namespace std;void LeftReverse(char *a, int begin, int end)for(int i=0;i<(end-begin+1)/2;i+)/交換移動int temp=abegin+i;abegin+i=aend-i;a

46、end-i=temp;void Converse(char *a,int n,int k) LeftReverse(a, 0, k+1);LeftReverse(a, k, n+1);LeftReverse(a, 0, n-1);for(int i=0;i<n;i+)cout<<ai<<" "cout<<endl;int main()char a7='a','b','c','d','e','f','g'Converse(a

47、,7,3);return 0;7. 設(shè)計(jì)遞歸算法生成n個元素的所有排列對象。#include <iostream>using namespace std;int data100;/在m個數(shù)中輸出n個排列數(shù)(n<=m)void DPpl(int num,int m,int n,int depth) if(depth=n) for(int i=0;i<n;i+) cout<<datai<<" " cout<<endl; for(int j=0;j<m;j+) if(num&(1<<j)=0)

48、datadepth=j+1; DPpl(num+(1<<j),m,n,depth+1); /forint main() DPpl(0,5,1,0); DPpl(0,5,2,0); DPpl(0,5,3,0);DPpl(0,5,4,0); DPpl(0,5,5,0); return 0;8. 設(shè)計(jì)分治算法求解一維空間上n個點(diǎn)的最近對問題。參見最近對問題的算法分析及算法實(shí)現(xiàn)9. 在有序序列(r1, r2, , rn)中,存在序號i(1in),使得ri=i。請?jiān)O(shè)計(jì)一個分治算法找到這個元素,要求算法在最壞情況下的時(shí)間性能為O(log2n)。/在有序數(shù)組中/采用二分法查找符合條件的元素#in

49、clude<iostream>using namespace std;void Findnum(int *a,int n) int low=0; int high=n-1; while(low<=high) int mid=(low+high)/2;if(amid=mid)cout<<"這個數(shù)是: "<<amid<<endl; break;else if(amid>mid)high=mid-1;elselow=mid+1; int main()int a7=1,0,2,5,6,7,9; Findnum(a,7);r

50、eturn 0;時(shí)間復(fù)雜度為O(log2n)。10. 在一個序列中出現(xiàn)次數(shù)最多的元素稱為眾數(shù)。請?jiān)O(shè)計(jì)算法尋找眾數(shù)并分析算法的時(shí)間復(fù)雜性。 /先對序列進(jìn)行快速排序/再進(jìn)行一次遍歷/輸出眾數(shù)的重復(fù)次數(shù)#include <iostream>using namespace std;int partions(int b,int low,int high)int prvotkey=blow;b0=blow;while (low<high) while (low<high&&bhigh>=prvotkey) -high; blow=bhigh; while (l

51、ow<high&&blow<=prvotkey) +low; bhigh=blow;blow=b0;return low;void qsort(int l,int low,int high)int prvotloc;if(low<high) prvotloc=partions(l,low,high); /將第一次排序的結(jié)果作為樞軸 qsort(l,low,prvotloc-1); /遞歸調(diào)用排序 由low 到prvotloc-1 qsort(l,prvotloc+1,high); /遞歸調(diào)用排序 由 prvotloc+1到 highvoid quicksort(int l,int n)qsort(l,1,n); /第一個作為樞軸 ,從第一個排到第n個int main()int a10=1,2,3,5,3,3,3,2,5,1;

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論