算法設(shè)計(jì)及分析習(xí)題答案解析1_6章

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

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

3、 (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) 將第一次排序的結(jié)果作為樞軸遞歸調(diào)用排序由low至U prvotloc-1遞歸調(diào)用排序由prvotloc+1 到highprvotloc=parti

4、ons(l,low,high); / qsort(l,low,prvotloc-1); / qsort(l,prvotloc+1,high); / ,從第一個(gè)排到第n個(gè)void quicksort(int l,int n) qsort(l,1,n);/第一個(gè)作為樞軸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<<' 'cout<<endl;quicksort(a,11);f

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

6、”的值賦值給它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;/forreturn 0;5.編寫程序，求n至少為多大時(shí)，n個(gè)“1”組成的整數(shù)能被 2013整除。#include<iostream>using namesp

7、ace 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;/forreturn 0;6.計(jì)算汽值的問題能精確求解嗎？編寫程序，求解滿足給定精度要求的汽值#include <iostream>using namespace std;int main ()double a,b;double arctan(double x); 聲明a = 16.

8、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;定義四個(gè)變量初sqr = x*x;e = x;while (e/i>1e-15)定義精度范圍f = e/i;/f 是每次r需要疊加的方程 r = (i%4=1)?r+f:r-f;e = e*sqr;/e 每次乘于 x的平方i+=2;/i 每次加2/while return r;7 .

9、圣經(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ù)。神6天 創(chuàng)造世界，暗示著該創(chuàng)造是完美的。設(shè)計(jì)算法，判斷給定的自然數(shù)是否是完美數(shù)#include<iostream>using namespace std;int main()int value, k=1;cin>>value;for (int i = 2;i!=value;+i)while (value % i = 0 )k+=i;/k

10、為該自然數(shù)所有因子之和value = value/ i;/forif(k=value)cout<<"該自然數(shù)是完美數(shù)"<<endl;elsecout<<"該自然數(shù)不是完美數(shù)"<<endl;return 0;8 .有4個(gè)人打算過橋，這個(gè)橋每次最多只能有兩個(gè)人同時(shí)通過。他們都在橋的某一端, 并且是在晚上，過橋需要一只手電筒， 而他們只有一只手電筒。 這就意味著兩個(gè)人過橋后必須有一個(gè)人將手電筒帶回來。 每個(gè)人走路的速度是不同的：甲過橋要用1分鐘，乙過橋要用2分鐘，丙過橋要用 5分鐘，丁過橋要用10分鐘，顯然，兩個(gè)

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

12、為factor。則最終能出現(xiàn)的數(shù)包括：factor, factor*2, factor*3,，factor*(a/factor尸a.一共a/factor 個(gè)。如果a/factor 是奇數(shù)，就選擇先行動；否則就后行動。習(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á)到Qn)。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=

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

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

15、n+i)/前半部分if(ai>num_max1)num_max1=ai;for(int j=n/2+1;j<n;+j)/ 后半部分 if(aj>num_max2)num_max2=aj;if(num_max1>=num_max2)cout<<”數(shù)組中的最大元素： "<<num_max1<<endl; elsecout<<” 數(shù)組中的最大元素： "<<num_max2<<endl;return 0;時(shí)間復(fù)雜度：O (n)6 .設(shè)計(jì)分治算法，實(shí)現(xiàn)將數(shù)組A n中所有元素循環(huán)左移k個(gè)位置

16、，要求時(shí)間復(fù)雜性為O( n),空間復(fù)雜性為 Q1)。例如，對 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;aend-i=temp;void Converse(char *a,int

17、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,7,3);return 0;7 .設(shè)計(jì)遞歸算法生成n個(gè)元素的所有排列對象。#inclu

18、de <iostream> using namespace std;int data100;/在m個(gè)數(shù)中輸出n個(gè)排列數(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) datadepth=j+1;DPpl(num+(1<<j),m,n,depth+1

19、);/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)的最近對問題。參見4.4.1最近對問題的算法分析及算法實(shí)現(xiàn)9 .在有序序列(r1,2,，rn)中，存在序號i (1wiwn),使得c=i。請?jiān)O(shè)計(jì)一個(gè)分 治算法找到這個(gè)元素，要求算法在最壞情況下的時(shí)間性能為Qlog 2n)。/在有序數(shù)組中/采用二分法查找符合條件的元素#include<iostream>using namespace std;void Find

20、num(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ù)是："<<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);return 0;時(shí)間復(fù)雜度為Qlog 2n)。10 .在一個(gè)序列中出現(xiàn)次數(shù)最多的元素稱為眾數(shù)。請?jiān)O(shè)計(jì)算法尋找眾數(shù)并

21、分析算法的時(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 (low<high&&blow<=prvotkey)+low;bhigh=blow;blow=b0

22、;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 至U prvotloc-1qsort(l,prvotloc+1,high); /遞歸調(diào)用排序由 prvotloc+1 到 highvoid quicksort(int l,int n) qsort(l,1,n); /第一個(gè)作為樞軸，從第一個(gè)排到第n個(gè)int main()int a10

23、=123,5,3,3,325,1;int i=0;int count=0;int max=0;/max 表示出現(xiàn)的次數(shù)qsort(a,0,10); while(i<10) int j；j=i+1;if(ai=aj&&i<10)count+;i+；if(count>max)max=count;count=0;/whilecout<<"重復(fù)次數(shù)："<<max<<endl;return 0;時(shí)間復(fù)雜度nlog（n）11 .設(shè)M是一個(gè)nxn的整數(shù)矩陣，其中每一行（從左到右）和每一列（從上到下）的元 素都按升序排列

24、。設(shè)計(jì)分治算法確定一個(gè)給定的整數(shù)x是否在M中，并分析算法的時(shí)間復(fù)雜性。12 .設(shè)S是n （n為偶數(shù)）個(gè)不等的正整數(shù)的集合，要求將集合S劃分為子集S和6,使得| S"=| S2|=n/2,且兩個(gè)子集元素之和的差達(dá)到最大。/先用快速排序進(jìn)行一趟排序/如果s1 （大的數(shù)集）的的個(gè)數(shù)大于n/2/將（i<=n/2-low-1）個(gè)最小的數(shù)排到后面/如果s1 （大的數(shù)集）的的個(gè)數(shù)小于n/2/將s2 （小的數(shù)集）n/2-low-1 排到前面/將排好的數(shù)組的前 n/2個(gè)數(shù)賦值給s1/將排好的數(shù)組的后 n/2個(gè)數(shù)賦值給s2#include<iostream>using namespac

25、e std;const int n=8;void partions(int a,int low,int high)/進(jìn)行一趟快排int prvotkey=alow;a0=alow;while (low<high)while (low<high&&ahigh<=prvotkey)-high；alow=ahigh;while (low<high&&alow>=prvotkey)+low;ahigh=alow;alow=prvotkey;/如果si (大的數(shù)集)的的個(gè)數(shù)大于n/2if(low>=n/2)for(int i=0;i&l

26、t;=n/2-low-1;+i)for(int j=0;j<n-i;+j)if(aj<aj+1)int temp=aj;aj=aj+1；aj+1=temp;/for/if/如果si (大的數(shù)集)的的個(gè)數(shù)小于n/2elsefor(int i=0;i<=n/2-low-1;+i)for(int k=n-1;k<n-i;+k)if(ak>ak-1)int temp1=ak;ak=ak-1;ak-1=temp1;/for int main() int an=135,9,6,0,-11,-8;partions(a,0,n-1);for(int i=0;i<n;+i)i

27、f(i<4) cout<<"屬于子集 si 的："<<endl; cout<<ai<<endl; else cout<<"屬于子集 s2 的："<<endl; cout<<ai<<endl;return 0;13 .設(shè)ai,a2,an是集合1,2,，n的一個(gè)排列,如果 i<j且a>a,則序偶(ai,a)稱為該排列的一個(gè)逆序。例如， 2, 3, 1有兩個(gè)逆序：(3,1)和(2,1)。設(shè)計(jì)算法統(tǒng)計(jì)給定排列中含有逆序的個(gè)數(shù)。/用歸并進(jìn)行排序/當(dāng)一個(gè)

28、子集的一個(gè)數(shù)大于第二個(gè)子集的一個(gè)數(shù)，為逆序，即 ai>aj /則逆序數(shù)為end-j+1;#include<iostream> 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中較小者放入 r1kelse a1k+=aj+;count+=(end-j+1);while(i&l

29、t;=mid) a1k+=ai+; while(j<=end) a1k+=aj+;void MergeSort(int a , int begin, int end)int mid,a11000; if(begin=end) return ;else mid=(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);cout<<count<<e

30、ndl;return 0;k14 .循環(huán)賽日程安排問題。設(shè)有n=2個(gè)選手要進(jìn)行網(wǎng)球循環(huán)賽，要求設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次。采用分治方法。將2”選手分為2”-1兩組，采用遞歸方法，繼續(xù)進(jìn)行分組，直到只剩下 2個(gè)選手時(shí)，然 后進(jìn)行比賽，回溯就可以指定比賽日程表了15 .格雷碼是一個(gè)長度為 2n的序列，序列中無相同元素，且每個(gè)元素都是長度為n的二進(jìn)制位串，相鄰元素恰好只有 1位不同。例如長度為 23的格雷碼為(000, 001, 011, 010, 110, 111, 101, 100) 。設(shè)計(jì)分治算法對任意的 n值構(gòu)

31、造相應(yīng)的格雷碼。/構(gòu)造格雷碼#include<iostream> using namespace std;int n;char a100;void gelei(int k)if(k=n)cout<<a<<endl; return;gelei(k+1);取反ak='0'?'1':'0'/gelei(k+1);int main()while(cin>>n && n != 0)memset(a,'0',sizeof(a); /初始化，全部置零an ='0'g

32、elei(0);cout<<endl;return 0;16 .矩陣乘法。兩個(gè)n>n的矩陣X和Y的乘積得到另外一個(gè)nxn的矩陣Z,且Z滿足(1 w i , j w n),這個(gè)公式給出了運(yùn)行時(shí)間為O n3)的算法。可以用分治法解決矩陣乘法問題，將矩陣X和Y都劃分成四個(gè)n/2刈/2的子塊，從而X和Y的乘積可WORD格式整理以用這些子塊進(jìn)行表達(dá)，即從而得到分治算法：先遞歸地計(jì)算8個(gè)規(guī)模為n/2的矩陣乘積 AE BG AF、BH CE DGCF DH然后再花費(fèi) O(n2)的時(shí)間完成加法運(yùn)算即可。請?jiān)O(shè)計(jì)分治算法實(shí)現(xiàn)矩陣乘法，并分 析時(shí)間性能。能否再改進(jìn)這個(gè)分治算法？習(xí)題51 .下面這個(gè)

33、折半查找算法正確嗎？如果正確，請給出算法的正確性證明，如果不正確，請 說明產(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) high = mid;else if (k > rmid) low = mid; else return mid;return 0;錯(cuò)誤。正確算法：int BinSearch1(int r , int n, int k) int low =

34、0, high = n - 1;int mid;while (low <= high)mid = (low + high) / 2;if (k < rmid) high =else if (k > rmid) low else return mid;return 0;2 .請寫出折半查找的遞歸算法，并分析時(shí)間性能。/折半查找的遞歸實(shí)現(xiàn)#include<iostream>using namespace std;int digui_search(int a口,int low,int high,int x)if (low > high)return 0;int m

35、id = (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 main()int a6=0,1,2,9,5,3;int result=digui_search(a,0,5,5);cout<<aresult<<endl;return 0;3 .修改折半查找算法使之能夠進(jìn)行范圍查找。所謂范圍查找是要找出在給定值a和b之間的所有元素(awb)修改第二題算法并實(shí)現(xiàn)：/折半查找算法使之能夠

36、進(jìn)行范圍查找#include <iostream>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(amid<min)digui_search(min, max, a, mid, high);else if(amid>max)digui_search(min, max, a, low, mid);elsefor(int i=mid; ai>=min && i&

37、gt;=low; i-)cout<<ai<<""cout<<endl;for(int j=mid+1; aj<=max && j<=high; j+)cout<<aj<<""cout<<endl;void main()int r6, min, max;cout<<"請輸入數(shù)組元素："<<endl;for(int i=0; i<6; i+)cin>>ri;cout<<"請輸入

38、查找范圍最小值min和最大值 max "<<""cin>>min>>max;digui_search(min, max, r, 0, 5); cout<<endl;4 .求兩個(gè)正整數(shù)m和n的最小公倍數(shù)。(提示：m和n的最小公倍數(shù)lcm( mn)與m和n的最大公約數(shù) gcd( m n)之間有如下關(guān)系：lcm( m n)=mn/gcd( m n)/求兩個(gè)數(shù)的最小公倍數(shù)#include<iostream>using namespace std;int main (void) int a,b;專業(yè)資料值得擁有in

39、t i=1;cin>>a>>b;while(i%a!=0)|(i%b!=0)+i；cout<<"a,b最小公倍數(shù)為："<<i<<endl;return 0;（該算法比較直接，要使其改進(jìn)，可用歐幾里得算法求得兩個(gè)數(shù)的最大公約數(shù)，然后套用上 面的公式再求最小公倍數(shù)）5.插入法調(diào)整堆。已知（ 調(diào)整為堆（假設(shè)調(diào)整為大根堆）ki, k2,，kn）是堆，設(shè)計(jì)算法將（kl,k2,，kn,kn+1)參昭八、void SiftHeap(int r , int k, int n)int i, j, temp;i = k; j = 2

40、* i + 1;/子while (j < n)/if (j < n-1 && rj < 巾+1) j+;/if (ri > rj)者break;else temp = ri; ri = rj; rj = temp; / i = j; j = 2 * i + 1;/進(jìn)行調(diào)堆！置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的位置6.設(shè)計(jì)算法實(shí)現(xiàn)在大根堆中刪除一個(gè)元素，要求算法的時(shí)間復(fù)雜性為qiog 2n）o/將要刪除的ak與最后一個(gè)元素an-1交換/然

41、后進(jìn)行調(diào)堆void de_SiftHeap(int r , int k, int n) int i, j, temp,temp1;i = k; j = 2 * i + 1;if(i<0|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交換;temp1=ai; / ai=an-1； an-1= tempi;/if (j < n-1 && rj < 巾+1) j+;/ if (ri > rj)比較i的左右

42、孩子，j為較大者 根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大i = j; j = 2 * i + 1;/break;else temp = ri; ri = rj; rj = temp; /將被篩結(jié)點(diǎn)與結(jié)點(diǎn)j交換被篩結(jié)點(diǎn)位于原來結(jié)點(diǎn)j的位置nm50652513013012260652031040104012080+ 20803250圖5.15俄式乘法7 .計(jì)算兩個(gè)正整數(shù)n和m的乘積有一個(gè)很有名的算法 稱為俄式乘法，其思想是利用了一個(gè)規(guī)模是n的解和一個(gè)規(guī)模是n/2的解之間的關(guān)系：n>mH n/2>2m （當(dāng)n是偶數(shù)） 或：n>fnF （n-1）/2 >2m m（當(dāng) n 是奇數(shù)），并以

43、 1 >mF m作 為算法結(jié)束的條件。 例如，圖5.15給出了利用俄式乘法計(jì) 算50>65的例子。據(jù)說十九世紀(jì)的俄國農(nóng)夫使用該算法并 因此得名，這個(gè)算法也使得乘法的硬件實(shí)現(xiàn)速度非?？?， 因?yàn)橹皇褂靡莆痪涂梢酝瓿啥M(jìn)制數(shù)的折半和加倍。請?jiān)O(shè) 計(jì)算法實(shí)現(xiàn)俄式乘法。/俄式乘法#include<iostream>using namespace std;int fun(int m,int n)int sum=0;int temp=n;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

44、)/2;temp=n;/ 記錄倒數(shù)第二個(gè) n的值return sum+n;int main()int a,b;while(cin>>a>>b) cout<<fun(a,b)<<endl;8 .拿子游戲?？紤]下面這個(gè)游戲：桌子上有一堆火柴，游戲開始時(shí)共有n根火柴，兩個(gè)玩家輪流拿走1,2, 3或4根火柴，拿走最后一根火柴的玩家為獲勝方。請為先走的玩家設(shè)計(jì)一個(gè)制勝的策略(如果該策略存在) 。如果桌上有小于4根的火柴，先手必勝，如果是5根，先手必輸；依次類推，同理15、 20、25.都是必輸狀態(tài)；所有每次把對手逼到15、20、25.等必輸狀態(tài)，就可以獲勝

45、。9 .競賽樹是一棵完全二叉樹，它反映了一系列“淘汰賽”的結(jié)果：葉子代表參加比賽 的n個(gè)選手，每個(gè)內(nèi)部結(jié)點(diǎn)代表由該結(jié)點(diǎn)的孩子結(jié)點(diǎn)所代表的選手中的勝者，顯然，樹的根結(jié)點(diǎn)就代表了淘汰賽的冠軍。請回答下列問題：(1)這一系列的淘汰賽中比賽的總場數(shù)是多少？(2)設(shè)計(jì)一個(gè)高效的算法，它能夠利用比賽中產(chǎn)生的信息確定亞軍。(1)因?yàn)閚人進(jìn)行淘汰賽，要淘汰 n-1人，所有要進(jìn)行 n-1場比賽。 10.在120枚外觀相同的硬幣中， 有一枚是假幣，并且已知假幣與真幣的重量不同，但不知道假幣與真幣相比較輕還是較重?？梢酝ㄟ^一架天平來任意比較兩組硬幣，最壞情況下，能不能只比較5次就檢測出這枚假幣？將120枚平均分為三

46、組，記為： A, B, C;先將A,B比較，如果 A,B重量不同(假如 B比A 重)，再將B與C比較，如果B, C相同，則A有假幣；如果B,C不同，再將A,C比較，如果 A,C相同，則B有假幣；如果 A,C不同，則B有假幣；如果 A,B相同，則C有假幣；習(xí)題61.動態(tài)規(guī)劃法為什么都需要填表？如何設(shè)計(jì)表格的結(jié)構(gòu)?在填寫表格過程中，不僅可以使問題更加清晰，更重要的是可以確定問題的存儲結(jié)構(gòu)； 設(shè)計(jì)表格，以自底向上的方式計(jì)算各個(gè)子問題的解并填表。2.對于圖6.26 解過程。所示多段圖，用動態(tài)規(guī)劃法求從頂點(diǎn)0到頂點(diǎn)12的最短路徑，寫出求將該多段圖分為四段；首先求解初始子問題，可直接獲得：d(0, 1)=

47、 coi= 5(0 一 1)d(0, 2)= Co2= 3(0 - 1)再求解下一個(gè)階段的子問題，有：d(0,3)= d(0, 1)+ C13 =6(1 - 3) d(0,4)=mind(0,1)+ c 14 ,d(0,2)+ 00000000 (以此類推)最短路徑為：0一 1 一 3一 8一 11 一12C24=8（1 一 4）3 .用動態(tài)規(guī)劃法求如下0/1背包問題的最優(yōu)解：有5個(gè)物品，其重量分別為(3, 2, 1,4,5),價(jià)值分別為(25, 20,15, 40, 50),背包容量為6。寫出求解過程。(x1, x2,x3,x4,x5) 一 (1,1,1,0,0)(過程略)4 .用動態(tài)規(guī)劃法求兩個(gè)字符串A="xzyz