1、習題1圖論誕生于七橋問題。出生于瑞士的偉大數學家歐拉LeonhardEuler, 17071783)提出并解決了該問題。七橋問題是這樣描述的： 一個人是否能在一次步行中穿越哥尼斯堡現在 叫加里寧格勒，在波羅的岸城中全部的七座橋 后回到起點，且每座橋只經過一次，圖1.7是這 條河以及河上的兩個島和七座橋的草圖請將該 問題的數據模型抽第出來,并判斷此問題是否有七橋問題屬于一筆畫問題。輸入：一個起點輸出：一樣的點1, 一次步行2,經過七座橋，且每次只經歷過一次3,回到起點該問題無解：能一筆畫的圖形只有兩類：一類是所有的點都是偶點。另一類是只有二個 號點的圖形。2.在歐幾里德提出的歐幾里德弄法中即茂初

2、的歐幾里德算法用的不是除法而是減法. 請用偽代碼描述這個版本的歐幾里德算法1 .r=m-n2 .循環直到r=()2.1 m=n2.2 n=r2.3 r=m-n3輸出m3.設計算法求數組中相堯最小的兩個元素稱為氏接近數的恚.要求分別給出偽代碼 和C+描述.采用分治法對整組先進展快速排序在依次比擬相鄰的差#includc using namespace std;int partions(int b口,int lowjnt high)int pm)ikcy=bl()w；b0=blow；while (low=prvotkcy)-high;blow=bhigh;while (l()wVhigh&blow

3、v=prvotkuy)+low；bhigh二 blow；bp(w=b();return low；void qsort(int 10,int kwjnt high)int prvotloc;if(l(whigli)prTotloc=partions(l,low,high); 將第一次排序的結果作為樞軸 qsort(l,low,prvotloc-1); 遞歸調用排序 由 low 到 prvotloc-1 qsort(l,prvotloc+l,high); 遞歸調用排序 由 pryotloc+l 到 highvoid quicksort(int IQ,int n)qsort(l,l,n); 第一個作

4、為樞軸，從第一個排到第n個int mainQint al 1=0,2,32,43,23,45,36,57J4R,39;int valuc=0;將戢小差的值賦值給valuefor (int b=l ;b 11 ;b十十)coutab* *;couKcndl;quicksort(a,l 1);for(int i=0u!=9;+i)if(ai+1-ai)=(ai+2-ai+l) valuc=ai+l-ai;elsevaluc=ai+2-ai+1;coutvaluccndl;return 0;4.設數如La回中的元素均不相等，設計算法找出an中一個既不是最大也不是我小的元 素，并說明最壞情況下的比擬次

5、數。要求分別給出偽代碼和C+描述。#includcusing namespace std;int mainQint aQ=ai&ai+lai+2)mid_vakiu=ai+1;coutmid_valuccndl;break;else if(ai+ lai+2)mid_x-aluc=ai+l;coutm!d_valuccndl;break;|)fbr.word zl-return 0;5 .編寫程序，求22至少為多大時，Z2個T”組成的整數能被2013排除。#includc using namespace std;int main。double valuc=0;f()r(ini n=lm=100

6、00 ;+n)value二value* 10+1;if(valuc%2013=0)coutHn 至少為:nvcndl;break;/forreturn 0;6 .計算k值的問題能準確求解嗎？編寫程序，求解滿足給定精度要求的燈值#includc using namespace std;int main 0double a,b;double arc tan (double x);/ 聲明a = 16.0*arctan(1/5.0);b = 4.0* arc tan( 1/239);cout MPI=H a-b Ciidl;return 0;double arctan(doublc x)(int i

7、=0;double r=0,c,f,sqr;定義四個變量初sqr = x*x；while (c/ilc-15)定義精度圍f=c/i；/f是每次r需要兌加的方程r = (i%4=l)?r-l-f:r-f;c = c*sqr;/c每次乘于x的平方i+=2;i每次加2/whilereturn r;7 .圣經上說：神6天創造天地萬有，第7日安欹為什么是6天呢？任何一個自然教的 因數中都有1和它本身，所有小于它本身的因數稱為這個數的真因數，如果一個自然數的真 因數之和等于它本身，這個自然數稱為完美數.例如，6=1+2+3,因此6是完美數.神6天 創造世界，暗示著該創造是完美的.設計算法，判斷給定的自然數

8、是否是完美數#includcusing namespace std;int main()int value, k=l;cinvaluc；for (int i = 2;i!=valuc；+i)while (value %i=0)(k+=i;/k為該自然數所有因子之和value = value/ i;/forif(k二二 value)couYV”該自然數是完美數“vvedl;elseccutv”該自然數不是完美數“Wendi;return 0;|8 .有4個人打算過橋，這個橋每次最多只能有兩個人同時埴過。他們都在橋的某一端， 并且是在晚上，過橋需要一只手電筒，而他們只有一只手電筒。這就意味著兩個人

9、過橋后必 須有一個人將手電筒帶兇來.每個人走路的速度是不同的：甲過橋旻用1分鐘，乙過橋要用 2分鐘，丙過橋要用5分鐘，丁過橋要用10分鐘，顯然，兩個人走路的速度等于其中校慢 那個人的速度，問題是他們全部過橋最少要用多長時間？由于甲過橋時間武短，那么每次傳遞手電的工作應有甲完成甲每次分別帶著乙丙丁過橋例如：第一趟：甲，乙過橋且甲凹來第二趟：甲，丙過橋且甲回來第一越：甲，丁過橋一共用時19小時9 .歐幾里德游戲：開場的時候，白板上有兩個不相等的正接數，兩個玩家交替行動，毒 次行動時，當前玩家都必須在白板上寫出任意兩個巳經出現在板上的數字的要，而且這個數 字必須是新的，也就是說，和白板上的任何一個已

10、有的數字都不一樣，當一方再也寫不出新 數字時，他就輸了.請問，你是選擇先行動還是后行動？為什么？設最初兩個數較大的為n較小的為b,兩個數的敢大公約數為factor。那么最終能出現的數包括:factor, factor*2, factor*3,. factor*(a/factor)=a. 一共 a/factor 個。如果a/factor是才數，就選擇先行動；否那么就后行動。習題41 .分治法的時間性能與直接計算最小問題的時間、合并于問題解的時間以及于問題的 個數有關，試說明這幾個參數與分治法時間復雜性之間的關系。2 .證明：如果分治法的合并可以在線性時間完成，那么當于問題的規模之和小于原問 題的

11、規模時，算法的時間復雜性可到達。(刀)。O(N)=2*O(N/2)+xO(N)+x=2*O(N/2)+2*xa+O(N)+x=a*(2*O(N/2)+x)+x=2*a*O(N/2)+(a+l)*x由此可知，時間發雜度可到達O(n);3 .分治策略一定導致遞歸嗎？如果是，請解釋原因。如果不是，給出一個不包含遢歸的 分治例于，并闡述這種分治和包含遞歸的分治的主要不同。不一定導致遞歸。如非遞歸的二叉樹中序遍歷。這種分治方法與遞歸的二叉樹中序遍歷主要區別是：應用了棧這個數據構造。4對于待排序序列(5,3,1,9),分別離出歸并排序和快速排序的遞歸運行軌跡.歸并排序：第一趟：5,31,9；第二趟：3,5

12、,1,9；第三趟：1,359；快速排序：第一趟：5，3,1,9； 5為哨兵,比擬9和5第二趟：51,3,9； 比擬1和5,將1挪到相應位置；第三越：5 (1,3, ,91;比擬3和5;第四趟：1,3,5,9);5.設計分治算法求一個數組中的最大元素，并分析時間性能.簡單的分治問題將教姐均衡的分為“前：后”兩局部分別求出這兩局部最大值，然后再比擬這兩個最大值#includcusing namespace std;extern const iiit n=6;/ 聲 明int an= (),6,1,2,3,5 ; 初始化int mid=n/2;int num_maxl=0,num_

13、max2=0;fbiQit i=0;iv=n/2;+i)/前半局部i f(ai num_max 1) num_maxl=ai;for(int j=n/2+l;jvn;+j) 后半局部if(ajnum_max2) num_max2=aj;if(num_maxl =num_max2)cqirvv”數組中的最大元素：ftnum_max1cndl;elsecoutvv”數組中的最大元素：Hnum_max2cndl;return 0;時間復雜度：。56 .設計分治算法，實現將數組4囪中所有元素循環左移k個位置，要求時間復雜性為 。(甘，空間復雜性為。(1).例如，對如c國儂板環左移3位得到也磔血采用分治

14、法將數組分為。*-1和k-n-1兩塊將這兩塊分別左移然后再合并左移#includc using namespace std;void LcftRcxxrsc(char int begin, int end)fbr(int i=0;iv(sdbugin+1)/2;i+) 交換移動int tcmp=abcgin+i; abcgin+i=acnd-i; acnd-i=tcmp;void Convcrsc(char *a,int njnt k)LcftRcvcrsc(a, 0, k-1);LcftRcvcrsc(% k, n-1);LcftRcvcrsc(a, 0, n-1); &)r(int i=(

15、);ivn;i+) coutaiH coutcndl;int mainOchMaP=C,E,c；d,Vf7g;Convcrsc(aJ,3);return 0;7 .設計遞歸算法生成A個元素的所有排列對象.#includc using namespace std;int d；ua100;在m個數中輸出n個排列數n二m void DPpl(iiit num,illt mjnt n,int depth) if(dcpth=n)fi)r(int i=0pn;i+)coutdataiH n；coutcndl;f()r(int j=O;jm;j+)if(num&(l )=() datadcpth=j+l;

16、DPpl(num+(l j),m4i,dcpth+1);/fcr int main。DPpl(0,5,l,0);DPpl(0,5,0);DPpl(O,5,3,O);DPpl(0,5,4,0);DPpl(O,5,5,O);return 0;)8 .設計分治算法求解一維空間上a個點的最近對問題。參見441最近對問題的算法分析及算法實現9 .在有序序列(小色，W中，存在序號/11田間，使得正人請設計一個分治算法 找到這個元素，要求算法在最壞情況下的時間性能為803功。在由序教組中采用二分法查找符合條件的元素.word zl-#includc using namespace std;void Find

17、num (int * n)int kw=O;int high=n-l;whilc(l()wmid) high=mid-l;elsel)w=mid+l;int mainQint a口二1,025,6,7,9;Findnum (a,7);return 0;時間發雜度為10 .在一個序列中出現次數最多的元素稱為眾數.請設計算法尋找眾數并分析算法的時 間發雜性.先對序列進展快速排序/再進展一次遍歷輸出眾數的重發次數#includc using namespace std;iiit partions(int b Jnthigh)int pnrotkcy=blow;b()=bp()w；while

18、 (k)whij)(while (low=pn*otkcy)-hi即blw=b|higji;whilehigh&blow=pn-otkey)+bw；bhigh=blow；blow=b();return low；void qsort(int IQJnt lowjnt high)int prvotloc;if(lowhigh)pm)tloc=parti()ns0,l)w,higli); 將第一次排序的結果作為樞軸 qsort(Uow,prvodoc-l);/遞歸調用排序 由 low 到 prvotloc-1 qsort(l,prvovloc+l,high); /遞歸調用排序 由 prvoHoc+1

19、 到 highvoid quicksort(int IQ,int n)qgort(l,l,n); 第一個作為樞軸,從第一個排到第n個int mainOint 1,2,3,5,3,3,32,5,1;int i=0;int count=0;int max=O;/max表亦出現的次數 qsort(a,(),10);whilc(i10)ini j；j=i+l； if(aH=aj&imax) max=count;count=();/whilecoutvv”重更次數：Hmaxcndl;return 0;時間笑雜度nlog（n）11 .設M是一個AXA的整數矩陣，其中每一行從左到右和每一列從上到下的 元素都

20、按升序排列。設計分治算法確定一個給定的整數x是否在M中，并分析算法的時間 復雜性。12 .設S是a S為偶數個不等的正繁數的集合，要求將集合S劃分為于集S和2, 使得I Sl = l &Ima/2,且兩個子集元素之和的差到達武大.先用快速排序進展一趟排序如果si大的教集的的個數大于n/2將ti=n/2-low-l）個最小的數排到后面如果4大的教集的的個數小于n/2將s2小的教集n/2-low-l排到前面將排好的數組的前n/2個數賦值洽si將排好的數組的后n/2個數賦值給s2#includeusing namespace std;const int n=8;void partions（int 旬

21、皿 low皿 hi 的）進展一趟快排int prvotkey=aQovd；a0=alow；while (lowhii)while (Lowhii&a|hii =prvotkey)-hi 也；aQo|=ahii;while 0ow =ptvotkey) +low;a 次=aQE);)aLol=prvotkey;如果si大的教集的的個數大于n/2if(low=n/2)(forint i=04=n/2-low-l;+i)(forint j=On-i;+j)if(a0aO+U)(int temp=aj;affl=ag+l;a(j+l=temp;)/for)/if如果si大的數集的的個數小于n/2els

22、eforint i=04ak-l)(int tempi =ak;ak=ak-l;ak-l=templ;)/for)int mainQ intan=13,5,9,6,0,-ll,-8);partions(a0/i-l);forint i=0n；+j)if$4) cout”屬于于集 si 的：”vVendl; coutaiendl;) else cout%那么序偶(馬稱為 該排列的一個逆序。例如，2,3,1有兩個逆序：(3,1)和(2,1)。設計算法統計給定排列中含有 逆序的個數./用歸并進展排序當一個子集的一個數大于第二個子集的一個數，為逆序，即玨 那么逆序數為end-j+1;#includc

23、using namespace std;int count;void Mcrgc(int aQ jnt alQ,int bugin,int midjm end)/ 合并子序列int i=bugin,j二mid+ l*=und;while(i=mid& j =cnd)if(ai=aj)tdk+=ai+;/取 ai和 aj中較小者放入 rlk elseal k+=aj+;count+=(cnd-j+1);whilc(i=mid)al k+=ai+;whilc(j=cnd)alk+4-=aG+；void McrgcSort(ini a, ini begin, int end)ini mid,all

24、()()();if(bcgin=cnd)return ;elsemid=(bcgin+cnd)/2;McrgcSort(a,bcgin,mid);McrgcSort(a,mid+1 ,cnd);Mcrgc(a,a l,bcgin,mid,cnd);int mainQint -=6,5,4,32；count=();McrgcSort(a,0,6);coutcouiitciidl;return 0;14 .我環賽日程安排問題.設有G乃個選手要進展網球加環賽，奏求設計一個滿足以下 要求的比賽日程表：(1)每個選手必須與其他力1個選手各賽一次；2每個選手一天只能套一次.采用分治方法O將2人k選手分為2

25、人卜-1兩組，采用遞歸方法，繼續進展分組，宜到只剩下2個選手時，然 后進展比賽，回溯就可以指定比賽日程表了15 .格雷碼是一個長度為乃的序列，序列中無一樣元素，且每個元素都是長度為X2的二 進制位奉，相鄰元素恰好只有1位不同。例如長度為25的格雷瑪為(000,001,011,010,110,111, 101,100)0設計分治算法對任意的與值構造相應的格雷馬。構造格雷碼#includc using namespace std;int n；char a100;void gclci(int k)if(k=n)coutan & n != 0)(mcmsct(a,0,sizcof(a); 初始化，全部

26、 S.零an=(T；gplci(0);coutcndl;return 0;16矩陣乘法。兩個AXA的矩陣*和y的乘積得到另外一個AXA的矩陣z,且Z,滿足這個公式給出了運行時間為a)的算法。可以用分治法解決矩陣乘法問題，將矩陣、和V都劃分成四個W2XA/2的于塊，從而X和的乘 積可以用這些子塊進辰表達，即.word zl-從而得到分治算法：先遞歸地計算8個規模為n/2的矩陣乘積AE. BG、AF. BH、CE、 DG、CF、/7”，然后再花費力的時間完成加法運算即可。請設計分治算法實現矩陣乘法, 并分析時間性能O能否再改良這個分治算法？習題51.下面這個折半查找算稀嗎？如果正稿，請給出算法的正

27、確性證明，如果不正確，請說明 產生錯誤的原因。int BinScarch(int r, int n, int k)int l()w= 0, high=n - 1;inv mid;while (1oviY=high)mid=0ow+high)/2;if (krmid) low=mid;else return mid;return 0;錯誤。正確算法：inv BinScarchl(inv r, int n, int k)int low= 0, high=n - 1;int mid;while (low 二high)mid=(low+high)/2;if (krmid) low=tnid+l；els

28、e return mid;return 0;2請寫出折半查找的遞歸算法，并分析時間性能。折半查找的遞歸實現#includc using namespace std;int digui_scarch(int a jnt lowjnt highjnt x) if (low high) return 0;int mid = (low+high)/2;if amid = x) return mid;else if (amid 05,5)coutarcsukcndl;return 0;3.修改折半查找算法使之能夠進展國查找所謂圖查找是要找出在給定值a和b之間的所 有元素aVb修改第二題算法并實現：/折半

29、查找算法使之能夠進展圍查找#includc using namespace std;折半進展圍查找函數：void digui_scarch(int min, int max, int 分口，int low, int high)int mid;mid=(k)w+hi J】)/2;if(amidmax)digui_scarch(min, max, a, low, mid);elsefbr(int i=mid; ai=min & i=low； i) coutaiH coutciidl;fbr(int j=mid+l; aj=max & j=high; j+) coutajn H;coutciidl;

30、void main。(int r6, min, max;coutvv”請輸入數組元素：Hcndl;forfint i=0; imax；diguLscarch(min, max, r, 0, 5); coutcndl;4 .求兩個正整數ZD和22的最小公倍數。提示：ZD和22的最小公倍數lcm(m,0與。和 n的最大公約數gcd(zn,0之間有如下關系：km(fl?,0=mXzj/gcd(m,0求兩個數的最小公倍數#includcusing namespace std;int main (void)(int a,b;int i=l;cinab;whilc(i%a!=O) | |(i%b!=O)+

31、i；couina,b 最小公倍數為：Hicndl;return 0;（該其法比擬立按，妥使其改良，可用歐幾里得算法求得兩個數的最大公約數，然后套用上 面的公式再求最小公倍數）5 .插入法調整堆七魚,左是埴，設計算法將七入,調掛為堆假設調 接為大根堆。參照：void SiftHcap(int r, int k, int n)int i, j, temp;i = k;j = 2*i+ 1；while (j n)if (j n-1 & rQ rQ) break;else temp = ri; ri = rj; rj = temp; i = j；j = 2*i+ 1;置i為要篩的結點，j為i的左孩子篩

32、選還沒有進展到葉子比擬i的左右孩子，i為較大者根結點已經大于左右孩子中的較大者將被篩結點與結點i交換被押結點位于原來結點j的位競進展調堆!6 .設計算法實現在大根堆中副除一個元素，關求算法的時間復雜性為將妥刪除的 小與最后一個元素 由-1交換然后進展調堆void dc_SiftHcap(int r, int k, int n) ini i, j, temp,tempi;i = k;j = 2*i+l；if(in-l)return error;else if0=n-l)frcc(a0);.word zl-else置i為妥，肺的結點，j為i的左孩子while (j n)篩選還沒有進展到葉子temp

33、i =a0； 將 anl與 ak交換；afl=an-l;an-l= tempi;if(j n-1 & rj rG)根結點已經大于左右孩子中的較大者break;else temp = ri; ri = rj; rj = temp; / 將被篩結點與結點 j 交換i = i；j = 2*i+l;被州結點位于原來結點i的位置nni50652513013012260652031040104012080 -卜 20803250圖5.15俄式乘法7 .計算兩個正筌數4和m的柬積有一個很有名的算法 稱為儻式柬法，其思想是利用了一個規模是A的解和一個 規模是Z1/2的解之間的關系：nXm=n/2X2m當a是偶

34、 數或：AXm=g4)/2X2n+zn當 zz 是寺教，并以 IX作為算法完畢的條件。例如，圖5.15給出了利用俄 式乘法計算50 X 65的例子。據說十九世紀的俄國農夫使用 該算法并因此得名，這個算法也使得柬法的硬件實現速度 非常快，因為只使用移位就可以完成二進制數的折率和加 倍.請設計算法實現俄式柬法俄式乘法#iiicludcusing namespace std;int fun(int n)int sum=0;int icmp=n;whilc(m! 1)if(m%2=0)/如果n是偶數n=n+2;m=m/2;else如果n是號教n=n*2;sum+=tcmp;m=(m-1)/2;icmp=n;/記錄倒數第二個n的值return sum+n;ini a,b;while(ciiiab)cout 1)d。, 2)=02=3(0-1)再求解下一個階段的子問題，有：d(0,3)=成0,1)+ Q3 =的-3)d(0,4)=mind(0,l)+ c14 ,d(0)+ =8(1 -4) oooooooo以此類推戰短路徑為：01 38-11 123 .用動態規劃法求如下0/1背也問題的最優解：有5個物品，其重量分別為(3,2,1,45), 價值分別為(25,20,15,40,50),背包容量為6寫出求解過程。(xl,x2,x3,