算法設(shè)計(jì)與分析習(xí)題答案1-6章

1、習(xí)題13.設(shè)計(jì)算法求數(shù)組中相差最小得兩個(gè)元素(稱為最接近數(shù))得差。要求分別給出偽代 碼與C+描述。/采用分治法/對(duì)數(shù)組先進(jìn)行快速排序/在依次比較相鄰得差#i nclude using n ames pace std; int p arti on s(i nt b,i nt low,i nt high) intp rvotkey=blow; b0=blow; while (lowvhigh) while (low=p rvotkey) -high;blow=bhigh; while (lowhigh&blow=p rvotkey) +low;圖論誕生于七橋問題。出生于瑞士得偉大數(shù)學(xué)家歐拉

2、 提出并解決了該問題。七橋問題就是這樣描述 得：一個(gè)人就是否能在一次步行中穿越哥尼斯 堡(現(xiàn)在叫加里寧格勒，在波羅得海南岸)城 中全部得七座橋后回到起點(diǎn)，且每座橋只經(jīng)過 一次，圖1、7就是這條河以及河上得兩個(gè)島與 七座橋得草圖。請(qǐng)將該問題得數(shù)據(jù)模型抽象出 來，并判斷此問題就是否有解。七橋問題屬于一筆畫問題。輸入：一個(gè)起點(diǎn) 輸出：相同得點(diǎn)1，一次步行2，經(jīng)過七座橋，且每次只經(jīng)歷過一次3，回到起點(diǎn) 該問題無解：能一筆畫得圖形只有兩類：一類就是所有得點(diǎn)都就是偶點(diǎn)。另一類就是只 有二個(gè)奇點(diǎn)得圖形。2.在歐幾里德提出得歐幾里德算法中(即最初得歐幾里德算法)用得不就是除法而就是減法。請(qǐng)用偽代碼描述這個(gè)版本

3、得歐幾里德算法1、r=m-n2、循環(huán)直到r=0123輸出1.2、2、2、3m=nn=rr=m-n(Leonhard Euler ,17071783)bhigh=blow;blow=b0; return low;void qsort(int l,int low,int high)int prvotloc;if(lowhigh)prvotloc=partions(l,low,high);qsort(l,low,prvotloc-1);/qsort(l,prvotloc+1,high); /void quicksort(int l,int n)qsort(l,1,n); /int main()int

4、 a11=0,2,32,43,23,45,36,57,14,27,39;int value=0;/將最小差得值賦值給valuefor (int b=1;b11;b+) coutab ; coutendl;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;coutvalueendl;return 0;4 設(shè)數(shù)組an中得元素均不相等， 設(shè)計(jì)算法找出an中一個(gè)既不就是最大也不就是最 小得元素，并說明最壞情況下得比較次數(shù)。要求分別給出偽代碼與C+描述。#inc

5、lude using namespace std; int main()int a=1,2,3,6,4,9,0;int mid_value=0;/將“既不就是最大也不就是最小得元素”得值賦值給它for(int i=0;i!=4;+i)if(ai+1ai&ai+1ai+2)mid_value=ai+1;將第一次排序得結(jié)果作為樞軸遞歸調(diào)用排序 由low到prvotloc-1遞歸調(diào)用排序 由prvotloc+1到high/第一個(gè)作為樞軸，從第一個(gè)排到第n個(gè)coutmid_valueendl;break;else if(ai+1ai+2)mid_value=ai+1;coutmid_value

6、endl; break;/forreturn 0;5、編寫程序，求#includeusing namespace std;int main()double value=0;for(int n=1;n=10000 ;+n)value=value*10+1;if(value%2013=0)coutn至少為:nendl; break;/forreturn 0;6、計(jì)算n值得問題能精確求解嗎？編寫程序，求解滿足給定精度要求得#include usingnamespace std;int main ()double a,b;double arctan(double x);/聲明a = 16、0*arct

7、an(1/5、0);b = 4、0*arctan(1/239);n至少為多大時(shí)，n個(gè)“1”組成得整數(shù)能被2013整除。cout PI= a-b 1e-15)/定義精度范圍f = e/i;/f就是每次r需要疊加得方程r = (i%4=1)?r+f:r-f;e = e*sqr;/e每次乘于x得平方i+=2;/i每次加2/whilereturn r;7、 圣經(jīng)上說：神6天創(chuàng)造天地萬有，第7日安歇。為什么就是6天呢？任何一個(gè)自然 數(shù)得因數(shù)中都有1與它本身，所有小于它本身得因數(shù)稱為這個(gè)數(shù)得真因數(shù)，如果一個(gè)自然 數(shù)得真因數(shù)之與等于它本身， 這個(gè)自然數(shù)稱為完美數(shù)。 例如，6=1+2+3，因此6就是完美數(shù)。

8、神6天創(chuàng)造世界，暗示著該創(chuàng)造就是完美得。設(shè)計(jì)算法，判斷給定得自然數(shù)就是否就是完 美數(shù)#includeusing namespace std;int main()int value, k=1;cinvalue;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;elsecout該自然數(shù)不就是完美數(shù)endl;return 0;8、有4個(gè)人打算過橋， 這個(gè)橋每次最多只能有兩個(gè)人同時(shí)通過。她們都在橋得某一端，3、并且就

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

10、新得，也就就是說，與白板上得任何一個(gè)已有得數(shù)字都不相同，當(dāng)一方再 也寫不出新數(shù)字時(shí)，她就輸了。請(qǐng)問，您就是選擇先行動(dòng)還就是后行動(dòng)？為什么？ 設(shè)最初兩個(gè)數(shù)較大得為a,較小得為b,兩個(gè)數(shù)得最大公約數(shù)為factor。則最終能出現(xiàn)得數(shù)包括：factor, factor*2, factor*3,、, factor*(a/factor)=a共a/factor個(gè)。如果a/factor就是奇數(shù)，就選擇先行動(dòng)；否則就后行動(dòng)。習(xí)題21.如果Ti(n) =O(f (n),T2(n)=O(g(n)，解答下列問題：(1)證明加法定理：Ti(n)+T2(n)=max O(f (n), O(g(n);(2)證明乘法定理：T

11、1(n)x T2(n)=O(f (n)x O(g(n);(3)舉例說明在什么情況下應(yīng)用加法定理與乘法定理,1 (1)(2)I(3) 比如在for(f(n)for(g( n)中應(yīng)該用乘法定理如果在“講兩個(gè)數(shù)組合并成一個(gè)數(shù)組時(shí)”，應(yīng)當(dāng)用加法定理2考慮下面得算法，回答下列問題：算法完成什么功能？算法得基本語句就是什么？基 本語句執(zhí)行了多少次？算法得時(shí)間復(fù)雜性就是多少？(1)(1)int完成得就是1-n得平方與 基本語句：s+=i*i，執(zhí)行了n次時(shí)間復(fù)雜度O(n)forint完成得就是n; iffl+得平方基本語S： + i return Q(n -1) + 2 * n-1，執(zhí)行了else次時(shí)t間間復(fù)

12、雜度O(n)return Q(n-1) + 2 * n - 1;分析以下程序段中基本語句得執(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;乙過橋且甲回來丙過橋且甲回來丁過橋甲,甲,甲,(2)int Q(int n)if (n = 1)return 1;(1)基本語句2*i1)return 3*T( n-1);int T(i nt n)if

13、(n=1)return 1;else if(n 1)return 2*T( n/3)+n;、求下列問題得平凡下界，并指出其下界就是否緊密。(1)求數(shù)組中得最大元素；(2)判斷鄰接矩陣表示得無向圖就是不就是完全圖；(3)確定數(shù)組中得元素就是否都就是惟一得；(4)生成一個(gè)具有n個(gè)元素集合得所有子集Q( n)緊密？Q(n*n)Q(logn+n )(先進(jìn)行快排，然后進(jìn)行比較查找)Q(2n)(1)(2)(3)(4)7.畫出在三個(gè)數(shù)a, b, cc合這個(gè)發(fā)achi發(fā)明得,SS&國際象棋就是很久以前由一個(gè)印度人 王很高興，就 糧食：棋盤得第1個(gè)方格內(nèi)只放想要得b賞。1粒麥粒否第2格2粒就以此類推，直

14、到64個(gè)方格全部放滿。這個(gè)獎(jiǎng)賞得最終結(jié)果會(huì)就是什么樣呢bn#in cludeusing n ames pace std;int mai n()long double result=1;double j=1;for(i nt i=1;i=64;+i)哋把該發(fā)明獻(xiàn)給國王時(shí)，國求以這種方式給她一些4粒，否第4格8粒，j=j*2; result+=j; j+;coutresultendl; return 0;using namespace std;int BF(char S, char T)int index = 0;int i = 0, j = 0;while (Si != 0) & (Tj

15、 != 0)if (Si = Tj)i+;j+;else +index; i = index; j = 0;if (Tj = 0)return index + 1;elsereturn 0;int main()char s119=ababcabccabccacbab;char s27=abccac;cout BF( s1, s2) endl;return 0;/KMP算法習(xí)題31 假設(shè)在文本ababcabccabccacbab中查找模式abccac，寫出分別采用BF算法與KMP算法得串匹配過/BF算法#include#include using namespacestd; void GetNe

16、xt(char T , intnext )int i, j, len;next0 = -1;for (j = 1; Tj!=0; j+)for (len = j - 1; len = 1; len-)for (i = 0; i len; i+)if (Ti != Tj-len+i)break; if (i = len)/求模式T得next值/依次求nextj/相等子串得最大長度為j-1/依次比較T0Tlen-1與Tj-lenTj-1nextj = len;break;/forif (len 1)nextj =0;/for/其她情況，無相等子串int KMP(char S , char T )i

17、nt i = 0, j = 0;int next80;GetNext(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()/求T在S中得序號(hào)/假定模式最長為80個(gè)字符/返回本趟匹配得開始位置char s1=ababcabccabccacbab;char s2=abccac; coutKMP(s1,s2)endl;return 0;2、分式化簡。

18、設(shè)計(jì)算法，將一個(gè)給定得真分?jǐn)?shù)化簡為最簡分?jǐn)?shù)形式。例如，將3/4。#include using namespace std; int main()int n;/分子int m;/分母int factor;/最大公因子int factor1;coutnm;int r = m % n; /因?yàn)榫褪钦娣謹(jǐn)?shù) 所以分母一定大于分子factor1=m;factor=n; while (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ì)算法，

19、判斷一個(gè)大整數(shù)能否被11整除。可以通過以下方法：將該數(shù)得十進(jìn)制表示從右端開始，每兩位一組構(gòu)成一個(gè)整數(shù)，然后將這些數(shù)相加，判斷其與能否被11整除。 例如，將562843748分割成5,62,84,37,48，然后判斷(5+62+84+37+48)能否被11整除/將一個(gè)大整數(shù)瞧成一個(gè)數(shù)組/數(shù)組得奇數(shù)位對(duì)應(yīng)數(shù)得10倍加上數(shù)組偶數(shù)對(duì)應(yīng)數(shù)得本身/驗(yàn)證結(jié)果能否被11整除#includeusing 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

20、=0)result+=ai; /i為偶數(shù)位時(shí)，結(jié)果加上其對(duì)應(yīng)數(shù)組數(shù)得本身6/8化簡為endl;if(result%11=0) cout該整數(shù)能被elsecout該整數(shù)不能被return 0;1,2,9這9個(gè)數(shù)字填入以下含有加、減、乘、除得四則運(yùn)算9個(gè)數(shù)字均出現(xiàn)一次且僅出現(xiàn)一次，且數(shù)字1不能出現(xiàn)在乘1得平凡情形) 。X +-= 05、設(shè)計(jì)算法求解anmod m,其中a、n與m均為大于1得整數(shù)。(提示：為了避免an超出int型得表示范圍，應(yīng)該每做一次乘法之后對(duì)n取模)#include using namespace std; int square(int x)return x*x;/用遞歸思想in

21、t resultmod(int a, int n)if(n= 0)return 1;if(n%2 = 0)return square(resultmod(a, n/2);/n為偶數(shù)得時(shí),取n得一半防止溢出elsereturn a*resultmod(a, n-1); /n為奇數(shù)時(shí),取n-1；int main()int a, n, m;cout請(qǐng)輸入a，n, m:anm;coutendl;int result = resultmod(a, n);coutaAn mod m得結(jié)果為： result % mendl; return 0;6、 設(shè)計(jì)算法，在數(shù)組rn中刪除所有元素值為x得元素，要求時(shí)間復(fù)

22、雜性為0(n),空 間復(fù)雜性為O(1)。7.設(shè)計(jì)算法，在數(shù)組rn中刪除重復(fù)得元素，要求移動(dòng)元素得次數(shù)較少并使剩余元素間elseresult+=ai*10;/i為奇數(shù)位時(shí)，結(jié)果加上對(duì)應(yīng)數(shù)組數(shù)得10倍11整除e ndl;11整除e ndl;4、 數(shù)字游戲 。把數(shù)字 式中，使得該等式成立。要求 與除得一位數(shù)中(即排除運(yùn)算式中一位數(shù)為得相對(duì)次序保持不變。#include using namespace std; void deletere(int a,int N)int b100=0;int i,k;k=0;static int j=0; for(i=0;iN;i+) bai+;for(i=0;i10

23、0;i+)if(bi!=0)if(bi=2)k+;aj=i; j+;for(i=0;iN-k;i+)coutaiendl;int main()int a=1,2,1,3,2,4; deletere(a,6); return 0;/在數(shù)組查找相同得元素/把其中一個(gè)相同得數(shù)值得元素位置設(shè)成一個(gè)“特殊數(shù)值”/輸出所求函數(shù)#includeusing namespace std;int main()int a=1,2,1,5,3,2,9,4,5,5,3,5;int i,j;for( i=0;i12;i+)for(j=0;ji;j+)if(aj=ai) ai=64787250;/設(shè)一個(gè)數(shù)組不存在得數(shù)值II

24、forfor(i=0;i12;i+)if(ai!=64787250)coutai ;coutendl;return 0;設(shè)表A=ai, a2,an，將A拆成B與C兩個(gè)表，使A中值大于等于0得元素存 入表B,值小于0得元素存入表C,要求表B與C不另外設(shè)置存儲(chǔ)空間而利用表A得空間。/先對(duì)A進(jìn)行快排II將大于0得元素給B,小于0得元素給C#include using namespace std;int partions(int l,int low,int high)int prvotkey=llow; l0=llow;while (lowhigh)while (low=prvotkey)-high;

25、llow=lhigh;while (lowhigh&llow=prvotkey) +low;lhigh=llow;llow=l0;return low;void qsort(int l,int low,int high)int prvotloc;if(lowhigh)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到high8、void quicksort(in

26、t l,int n)qsort(l,1,n); /第一個(gè)作為樞軸，從第一個(gè)排到第n個(gè)int main()int a11=-2,2,32,43,-23,45,36,-57,14,27,-39; quicksort(a,11);for(int i=1;i11;i+)if(ai0)coutC: ai ;elsecoutB: ai ;coutendl;return 0;9、荷蘭國旗問題。要求重新排列一個(gè)由字符R, W, B(R代表紅色，W代表白色，B代表蘭色，這都就是荷蘭國旗得顏色)構(gòu)成得數(shù)組，使得所有得R都排在最前面，W排在其次，B排在最后。為荷蘭國旗問題設(shè)計(jì)一個(gè)算法，其時(shí)間性能就是O(n)。/0代

27、表紅；1代表白；2代表藍(lán)#include using namespace std;const int N = 20;void s ( int *p , int *q )int tmp = *p; *p = *q;*q = tmp;void process ( 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) )s ( q, q-1 );-q; /q指針后移 /if+P； /whileint mai n()int aN = 0

28、, 2, 1,2, 0, 1,0, 2, 2, 1,0, 1,2, 1, 1, 0, 0, 1, 1,2; /待處理得數(shù)組cout 處理后得數(shù)組序列:endl; p rocess ( a, N );for (i nt i=0; i N; +i )cout ai ;cout en dl;return 0;10、設(shè)最近對(duì)問題以k維空間得形式出現(xiàn)，k維空間得兩個(gè)點(diǎn)P1=(X1, X2,Xk)與p2=(y1, y2,yk)得歐幾里德距離定義為：。對(duì)k維空間得最近對(duì)問題設(shè)計(jì)蠻力算法，并分析其時(shí)間性能。11設(shè)計(jì)蠻力算法求解小規(guī)模得線性規(guī)劃問題。假設(shè)約束條件為：x+3y0且y0;使目標(biāo)函數(shù)3x+5y取得極大

29、值。#in clude using n ames pace std;int mai n()int x,y,xO,yO;int summax=0,te mp=0;for(x0=0;x0=4;+x0)for(y0=0;(x0+y0=4) &(x0+3*y0=summax)summax=te mp;x=x0;/符合sum最大值得xy=y0;/符合sum最大值得y/forcoutx= x y= y summax= summax0得元素進(jìn)行判斷循環(huán)變量i從1n重復(fù)進(jìn)行下述操作：1、1計(jì)算矩陣i次方，如果矩陣對(duì)角線上有0得元素，則跳轉(zhuǎn)到1、21、2否則+i;如果矩陣對(duì)角線有0得元素，則輸出該回路2

30、輸出無解信息；13找詞游戲。要求游戲者從一張?zhí)顫M字符得正方形表中，找出包含在一個(gè)給定集合中得 所有單詞。這些詞在正方形表中可以橫著讀、豎著讀、或者斜著讀。為這個(gè)游戲設(shè)計(jì)一個(gè) 蠻力算法14、變位詞。給定兩個(gè)單詞，判斷這兩個(gè)單詞就是否就是變位詞。如果兩個(gè)單詞得字母完全相同，只就是位置有所不同，則這兩個(gè)單詞稱為變位詞。例如，eat與tea就是變位詞。/判斷qwer與rewq就是否就是變位詞#in clude#in cludeusing n ames pace std;int mai n()char s5=qwer; char t5=rewq; for(i nt i=0;i!=4;+i) if(si!

31、=t3-i)coutqwer與rewq不就是變位詞endl; return 0;break;coutqwer與rewq就是變位詞endl; return 0;15.在美國有一個(gè)連鎖店叫7-11店，因?yàn)檫@個(gè)商店以前就是早晨7點(diǎn)開門，晚上點(diǎn)關(guān)門。有一天，一個(gè)顧客在這個(gè)店挑選了四樣?xùn)|西，然后到付款處去交錢。營業(yè)員拿起計(jì)算器，按了一些鍵，然后說：“總共就是$7、11?！边@個(gè)顧客開了個(gè)玩笑說：“哦？難道因?yàn)槟鷤兊玫昝?-11,所以我就要付$7、11嗎？”營業(yè)員沒有聽出這就是個(gè)玩笑，回答說：“當(dāng)然不就是，我已經(jīng)把這四樣?xùn)|西得價(jià)格相乘才得出這個(gè)結(jié)果 得！”顧客一聽非常吃驚，“您怎么把她們相乘呢？您應(yīng)該把她

32、們相加才對(duì)！”營業(yè)員答道：“噢，對(duì)不起，我今天非常頭疼，所以把鍵按錯(cuò)了?！比缓?，營業(yè)員將結(jié)果重算了一遍，將這四樣?xùn)|西得價(jià)格加在一起，然而，令她倆更為吃驚得就是總與也就是11”設(shè)計(jì)蠻力算法找出這四樣?xùn)|西得價(jià)格各就是多少？ 該算法為：1、11、1、1、211int $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)for(int m=0;m!=n;+m)if(ai+bj+ck+dm)=7、11 & a i*bj*ck*dm=7、11)

33、coutaibjckdmendl;return 0;return 0;習(xí)題41、 分治法得時(shí)間性能與直接計(jì)算最小問題得時(shí)間、合并子問題解得時(shí)間以及子問題得個(gè)數(shù)有關(guān)，試說明這幾個(gè)參數(shù)與分治法時(shí)間復(fù)雜性之間得關(guān)系 。2、 證明：如果分治法得合并可以在線性時(shí)間內(nèi)完成，則當(dāng)子問題得規(guī)模之與小于原 問題得規(guī)模時(shí)，算法得時(shí)間復(fù)雜性可達(dá)到O(N)=2*O(N/2)+x O(N)+x=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)致遞歸嗎？如果就是，請(qǐng)解釋原因。如果不就是，給出一個(gè)不包含

34、遞歸得分治例子，并闡述這種分治與包含遞歸得分治得主要不同。不一定導(dǎo)致遞歸。 如非遞歸得二叉樹中序遍歷。 這種分治方法與遞歸得二叉樹中序遍歷主要區(qū)別就是：應(yīng)用了棧這個(gè)數(shù)據(jù)結(jié)構(gòu)。4、對(duì)于待排序序列(5, 3, 1, 9)，分別畫出歸并排序與快速排序得遞歸運(yùn)行軌跡。 歸并排序：第一趟： 第二趟： 第三趟：快速排序：第一趟：第二趟：第三趟：第四趟：O(n)。5,3)(1,9)；3,5,1,9)；1,3,5,9)；5(,3,1,9)；/5為哨兵，比較9與55(1,3, ,9)；/比較1與5，將1挪到相應(yīng)位置；1,3, ,9);/比較3與5；51,3,5,9);5、設(shè)計(jì)分治算法求一個(gè)數(shù)組中得最大元素，并分

35、析時(shí)間性能。/簡單得分治問題/將數(shù)組均衡得分為“前” ，“后”兩部分/分別求出這兩部分最大值，然后再比較這兩個(gè)最大值#includeusing namespace std; externconst int n=6;/聲明intmain()int an=0,6,1,2,3,5;/初始化int mid=n/2;int num_max1=0,num_max2=0;for(int i=0;inum_max1)num_max1=ai;for(int j=n/2+1;jnum_max2)num_max2=aj;if(num_max1=num_max2) cout數(shù)組中得最大元素：else cout數(shù)組中得

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

37、begin+i=aend-i;aend-i=temp;交換移動(dòng)void Converse(char *a,int n,intk)LeftReverse(a, 0, k-1);LeftReverse(a, k, n-1);LeftReverse(a, 0, n-1);for(int i=0;in;i+) coutai ; coutendl;int main()char a7=a,b,c,d,e,f,g;Converse(a,7,3);return 0;設(shè)計(jì)遞歸算法生成n個(gè)元素得所有排列對(duì)象。#include using namespace std;int data100;/在m個(gè)數(shù)中輸出n個(gè)排列

38、數(shù)(n=m)void DPpl(int num,int m,int n,int depth)if(depth=n)for(int i=0;in;i+) coutdatai ; coutendl;for(int j=0;jm;j+)if(num&(1j)=0) datadepth=j+1; DPpl(num+(1j),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個(gè)點(diǎn)得最近對(duì)問題。 參見4

39、、4、1最近對(duì)問題得算法分析及算法實(shí)現(xiàn)7、9、在有序序列(門，2,rn)中，存在序號(hào)i(K in),使得ri=i。請(qǐng)?jiān)O(shè)計(jì)一個(gè)分治算 法找到這個(gè)元素，要求算法在最壞情況下得時(shí)間性能為O(log2n)。/在有序數(shù)組中/采用二分法查找符合條件得元素#include 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這個(gè)數(shù)就是：amidmid) high=mid-1;else low=mid+1;int m

40、ain()int a7=1,0,2,5,6,7,9;Findnum(a,7);return 0;時(shí)間復(fù)雜度為O(log2n)。10、 在一個(gè)序列中出現(xiàn)次數(shù)最多得元素稱為眾數(shù)。請(qǐng)?jiān)O(shè)計(jì)算法尋找眾數(shù)并分析算法得 時(shí)間復(fù)雜性。/先對(duì)序列進(jìn)行快速排序/再進(jìn)行一次遍歷/輸出眾數(shù)得重復(fù)次數(shù)#include using namespace std;int partions(int b,int low,int high)int prvotkey=blow;b0=blow;while (lowhigh)while (low=prvotkey) -high;blow=bhigh;while (lowhigh&

41、;blow=prvotkey) +low;bhigh=blow;blow=b0;return low;void qsort(int l,int low,int high)int prvotloc;if(lowhigh)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); /第一個(gè)作為樞

42、軸 ，從第一個(gè)排到第n個(gè)int main()int a10=1,2,3,5,3,3,3,2,5,1;int i=0;int count=0;int max=0;/max表示出現(xiàn)得次數(shù)qsort(a,0,10);while(i10)int j;j=i+1;if(ai=aj&imax)max=count;count=0;/while cout重復(fù)次數(shù)：maxendl;return 0;時(shí)間復(fù)雜度nlog（n）11、設(shè)M就是一個(gè)n X n得整數(shù)矩陣，其中每一行（從左到右）與每一列（從上到下） 得元素都按升序排列。設(shè)計(jì)分治算法確定一個(gè)給定得整數(shù)x就是否在M中，并分析算法得 時(shí)間復(fù)雜性。12、

43、設(shè)S就是n（n為偶數(shù)）個(gè)不等得正整數(shù)得集合，要求將集合S2,使得I Si|=| S2|= n/2,且兩個(gè)子集元素之與得差達(dá)到最大。/先用快速排序進(jìn)行一趟排序如果si（大得數(shù)集）得得個(gè)數(shù)大于n/2 /將（i=n/2-low-1）個(gè)最小得數(shù)排到后面 如果si（大得數(shù)集）得得個(gè)數(shù)小于/將s2（小得數(shù)集）/將排好得數(shù)組得前/將排好得數(shù)組得后#includeusing namespace std;const int n=8;void partions（int a,int low,int high）/進(jìn)行一趟快排int prvotkey=alow; a0=alow; while （lowhigh）whil

44、e (lowhigh&ahigh=prvotkey) -high;alow=ahigh;while (low=prvotkey) +low;ahigh=alow;alow=prvotkey;如果s1(大得數(shù)集)得得個(gè)數(shù)大于n/2if(low=n/2)for(int i=0;i=n/2-low-1;+i)for(int j=0;jn-i;+j)if(ajaj+1)S劃分為子集S1與n/2n/2-low-1排到前面n/2個(gè)數(shù)賦值給s1 n/2個(gè)數(shù)賦值給s2/if/如果elsefor(int i=0;i=n/2-low-1;+i)for(int k=n-1;kak-1)int temp1=a

45、k;ak=ak-1; ak-1=temp1;/forint main()int an=1,3,5,9,6,0,-11,-8; partions(a,0,n-1);for(int i=0;in;+i)if(i4)cout屬于子集s1得：endl; coutaiendl;elsecout屬于子集s2得：endl; coutaiendl;return 0;設(shè)ai, 32,an就是集合1,2,n得一個(gè)排列，如果iaj,則序偶，aj)稱為該排列得一個(gè)逆序。例如，2, 3, 1有兩個(gè)逆序：(3, 1)與(2, 1)。設(shè)計(jì)算法統(tǒng)計(jì)給定排列中含有逆序得個(gè)數(shù)。/fointtemp=aj;aj=aj+1;aj+1

46、=temp;s1(大得數(shù)集)得得個(gè)數(shù)小于n/213、/用歸并進(jìn)行排序/當(dāng)一個(gè)子集得一個(gè)數(shù)大于第二個(gè)子集得一個(gè)數(shù)，為逆序，即/則逆序數(shù)為end-j+1;#include using namespace std; int count;void Merge(int a,int a1,int begin,int mid,int end)/int i=begin,j=mid+1,k=end; while(i=mid&j=end)if(ai=aj) a1k+=ai+;/取ai與aj中較小者放入r1k elsea1k+=aj+;count+=(end-j+1);while(i=mid)a1k+=ai

47、+;while(j=end)a1k+=aj+;void MergeSort(int a , int begin, int end)int mid,a11000;if(begin=end)return ;elsemid=(begin+end)/2;MergeSort(a,begin,mid);MergeSort(a,mid+1,end);Merge(a,a1,begin,mid,end);int main()int a6=6,5,4,3,2,1; count=0;MergeSort(a,0,6);coutcountaj合并子序列將2你選手分為2你-1兩組，采用遞歸方法，繼續(xù)進(jìn)行分組，直到只剩下后

48、進(jìn)行比賽，回溯就可以指定比賽日程表了15、格雷碼就是一個(gè)長度為2n得序列，序列中無相同元素，且每個(gè)元素都就是長度為n得二進(jìn)制位串， 相鄰元素恰好只有1位不同。 例如長度為23得格雷碼為(000, 001,011,010, 110, 111, 101,100)。設(shè)計(jì)分治算法對(duì)任意得n值構(gòu)造相應(yīng)得格雷碼。/構(gòu)造格雷碼#in cludeusing n ames pace std;int n;char a100;void gelei (int k)if(k=n)coutan & n != 0)memset(a,0,sizeof(a);/初始化，全部置零a n =0;gelei(0);coute

49、 ndl;return 0;伺、矩陣乘法。兩個(gè)nxn得矩陣X與丫得乘積得到另外一個(gè)nX n得矩陣Z,且Zij(1i, j w n),這個(gè)公式給出了運(yùn)行時(shí)間為O(n3)得算法?？梢杂梅种畏ń鉀Q矩陣乘法問題，將矩陣X與丫都劃分成四個(gè)n/2 X n/2得子塊，從而X與丫得乘積 可以用這些子塊進(jìn)行表達(dá)，即2個(gè)選手時(shí)，然/取反滿足從而得到分治算法： 先遞歸地計(jì)算8個(gè)規(guī)模為n/2得矩陣乘積AE、BG、AF、BH、CE、DG、CF、DH，然后再花費(fèi)0(n2)得時(shí)間完成加法運(yùn)算即可。請(qǐng)?jiān)O(shè)計(jì)分治算法實(shí)現(xiàn)矩陣乘法，并 分析時(shí)間性能。能否再改進(jìn)這個(gè)分治算法？習(xí)題51.下面這個(gè)折半查找算法正確嗎？如果正確，請(qǐng)給出算法

50、得正確性證明，如果不正確，請(qǐng) 說明產(chǎn)生錯(cuò)誤得原因。int BinSearch(int r , int n, int k)int low = 0, high = n - 1;int mid;while (low = high)mid = (low + high) / 2;if (k rmid) low = mid;else return mid;return 0;錯(cuò)誤。 正確算法：int BinSearch1(int r , int n, intint low = 0, high = n - 1;int mid;while (low =high)mid = (low + high) / 2;if

51、 (k rmid)low = else return mid;return 0;2.請(qǐng)寫出折半查找得遞歸算法，并分析時(shí)間性能。/折半查找得遞歸實(shí)現(xiàn)#include using namespace std;int digui_search(int a,int low,int high,int x)if (low high)return 0;int mid = (low+high)/2;=if (amid = x) return mid;else if (amid x) digui_search(a,low,mid-1,x);elsedigui_search(a,mid+1,high,x);int

52、 main()int a6=0,1,2,9,5,3;int result=digui_search(a,0,5,5);coutaresultendl; return 0;3.修改折半查找算法使之能夠進(jìn)行范圍查找。所謂范圍查找就是要找出在給定值a與b之間得所有元素(ab)修改第二題算法并實(shí)現(xiàn)：/折半查找算法使之能夠進(jìn)行范圍查找#include using namespace std;/折半進(jìn)行范圍查找函數(shù)：void digui_search(int min, int max, int a, int low, int high)int mid; mid=(low+high)/2; if(amidm

53、ax) digui_search(min, max, a, low, mid);elsefor(int i=mid; ai=min & i=low; i-) coutai ; coutendl;for(int j=mid+1; aj=max & j=high; j+) coutaj ;coutendl;void main()int r6, min, max; cout請(qǐng)輸入數(shù)組元素：endI;for(int i=0; iri;coutminmax;digui_search(min, max, r, 0, 5); coutendI;4、 求兩個(gè)正整數(shù)m與n得最小公倍數(shù)。與n得最大

54、公約數(shù)gcd(m, n)之間有如下關(guān)系：/求兩個(gè)數(shù)得最小公倍數(shù)#incIude using namespace std;int main (void)int a,b;int i=1;cinab;whiIe(i%a!=0)|(i%b!=0)+i;couta,b最小公倍數(shù)為：iendI;return 0;(該算法比較直接，要使其改進(jìn)，可用歐幾里得算法求得兩個(gè)數(shù)得最大公約數(shù)，然后套用上 面得公式再求最小公倍數(shù))5、 插入法調(diào)整堆。已知(ki,k2,kn)就是堆，設(shè)計(jì)算法將(ki,k2,kn,kn+1)調(diào)整為堆(假設(shè)調(diào)整為大根堆) 。參照：max：H H.提示：m與n得最小公倍數(shù)lcm( m, n)與

55、mIcm(m, n)=mxn/gcd(m, n)void SiftHeap(int r , int k, intn)int i, j, temp;i = k; j = 2 * i + 1;whiIe (j n)if (j n-1 & rj rj)break;eIse temp = ri; ri = rj; rj =temp;i = j; j = 2 * i + 1;/置i為要篩得結(jié)點(diǎn)，j為i得左孩子/篩選還沒有進(jìn)行到葉子/比較i得左右孩子，j為較大者/根結(jié)點(diǎn)已經(jīng)大于左右孩子中得較大者/將被篩結(jié)點(diǎn)與結(jié)點(diǎn)j交換/被篩結(jié)點(diǎn)位于原來結(jié)點(diǎn)j得位置計(jì)算兩個(gè)正整數(shù)n與m得乘積有一個(gè)很有名得算 法稱為

56、俄式乘法，其思想就是利用了一個(gè)規(guī)模就是n得解與一個(gè)規(guī)模就是n/2得解之間得關(guān)系：n X m=nI2 x 2m(當(dāng)n就是偶數(shù))或：n X m=(n- 1)/2 x 2m+m(當(dāng)n就是奇數(shù))， 并以1 X m=m作為算法結(jié)束得條件。例如，圖5、15給出了利用俄式乘法計(jì)算50 X 65得例子。據(jù)說十九世紀(jì)得俄國農(nóng)夫使用該算法并因此得名，這個(gè)算法也使得乘法得硬件 實(shí)現(xiàn)速度非?？?，因?yàn)橹皇褂靡莆痪涂梢酝瓿啥M(jìn)制數(shù)得 折半與加倍。請(qǐng)?jiān)O(shè)計(jì)算法實(shí)現(xiàn)俄式乘法。/俄式乘法#in cludeusing n ames pace std;int fun (i nt m,i nt n)int sum=0;int temp

57、=n;進(jìn)行調(diào)堆！6、設(shè)計(jì)算法實(shí)現(xiàn)在大根堆中刪除一個(gè)元素，要求算法得時(shí)間復(fù)雜性為 將要?jiǎng)h除得ak與最后一個(gè)元素an-1交換然后進(jìn)行調(diào)堆void de_SiftHea p(int r , i nt k, i nt n)int i, j, temp ,te mp1;i = k; j = 2 * i + 1;if(i n-1)return error;else if(i=n-1)free(ai);elsewhile (j n)置i為要篩得結(jié)點(diǎn)，j為i得左孩子/篩選還沒有進(jìn)行到葉子將an-1與ak交換;temp 1=ai;ai=a n-1;an-1= temp1;if (j n-1 & rj r

58、j)break;else temp = ri; ri = rj; rj= temp;i = j; j = 2 * i + 1;O(log2n)。/比較i得左右孩子，j為較大者II根結(jié)點(diǎn)已經(jīng)大于左右孩子中得較大將被篩結(jié)點(diǎn)與結(jié)點(diǎn)j交換II被篩結(jié)點(diǎn)位于原來結(jié)點(diǎn)j得位置7、nm50652513013012260652031040104012080+ 20803250圖 5、 15俄式乘法while(m!=1)if(m%2=0)/如果n就是偶數(shù)n=n*2;m=m/2;else/如果n就是奇數(shù)n=n*2;sum+=temp; m=(m-1)/2;temp=n;/記錄倒數(shù)第二個(gè)n得值return sum+n

59、;int main()int a,b;while(cinab)coutfun(a,b)endl;8、拿子游戲?？紤]下面這個(gè)游戲：桌子上有一堆火柴，游戲開始時(shí)共有n根火柴，兩個(gè)玩家輪流拿走1，2，3或4根火柴，拿走最后一根火柴得玩家為獲勝方。請(qǐng)為先走得 玩家設(shè)計(jì)一個(gè)制勝得策略(如果該策略存在) 。如果桌上有小于4根得火柴，先手必勝，如果就是15、20、25、都就是必輸狀態(tài)；所有每次把對(duì)手逼到 就可以獲勝。9、競賽樹就是一棵完全二叉樹，它反映了一系列“淘汰賽”得結(jié)果：葉子代表參加 比賽得n個(gè)選手，每個(gè)內(nèi)部結(jié)點(diǎn)代表由該結(jié)點(diǎn)得孩子結(jié)點(diǎn)所代表得選手中得勝者，顯然， 樹得根結(jié)點(diǎn)就代表了淘汰賽得冠軍。請(qǐng)回答下列問題：(1)這一系列得淘汰賽中比賽得總場數(shù)就是多少？(2)設(shè)計(jì)一個(gè)高效得算法，它能夠利用比賽中產(chǎn)生得信息確定亞軍(1)因?yàn)閚人進(jìn)行淘汰賽，要淘汰n-1人，所有要進(jìn)行n-1場比賽。(2)10、 在120枚外觀相同得硬幣中， 有一枚就是假幣， 并且已知假幣與真幣得重量不同， 但不知道假幣與真幣相比較輕還就是較重?？梢酝ㄟ^一架天平來任意比較兩組硬幣，最壞 情況下，能不能只比較