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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上習(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)

2、都是偶點(diǎn)。另一類是只有二個奇點(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,

3、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;return low;void qsort(int l,int low,int high)int prvotloc;if(low<high) prvotloc=partions(l,low,

4、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 a11=0,2,32,43,23,45,36,57,14,27,39;int value=0;/將最小差的值賦值給valuefor (int b=1;b<11;b+)cout<<ab&l

5、t;<' '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 mai

6、n() int a=1,2,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. 編寫程序，求

7、n至少為多大時，n個“1”組成的整數(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 n

8、amespace std;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需要疊加

9、的方程 r = (i%4=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=

10、1; cin>>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個人打算過橋，這個橋每次最多只能有兩個人同時通過。他們都在橋的某一端，并且是在晚上，過橋需要一只手電筒，而他們只有一只手電筒。這

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

12、有的數(shù)字都不相同，當(dāng)一方再也寫不出新數(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í)題41. 分治法的時間性能與直接計(jì)算最小問題的時間、合并子問題解的時間以及子問題的個數(shù)有關(guān)，試說明這幾個參數(shù)與分治法時間復(fù)雜性之間的關(guān)系。2. 證明：如果分治法的合并可以在線性時間內(nèi)完成，則當(dāng)子問題的規(guī)模之和小于原問題的規(guī)

13、模時，算法的時間復(fù)雜性可達(dá)到O(n)。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+1)*x由此可知，時間復(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,

14、9）；第二趟：（3,5,1,9）；第三趟：（1,3,5,9）；快速排序： 第一趟：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ù)組均衡的分為“前”，“后”兩部分/分別求出這兩部分最大值，然后再比較這兩個最大值#include<iostream>using namespace std;extern const int n=6;/聲明int main()int an=0

15、,6,1,2,3,5;/初始化int mid=n/2;int num_max1=0,num_max2=0;for(int i=0;i<=n/2;+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;else cout<<"數(shù)組中的最大元素： &q

16、uot;<<num_max2<<endl;return 0;時間復(fù)雜度：O（n）6. 設(shè)計(jì)分治算法，實(shí)現(xiàn)將數(shù)組An中所有元素循環(huán)左移k個位置, 要求時間復(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)

17、/2;i+)/交換移動int temp=abegin+i;abegin+i=aend-i;aend-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'

18、,'e','f','g'Converse(a,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(

19、int j=0;j<m;j+) if(num&(1<<j)=0) 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)的最近對問題。參見4.4.1最近對問題的算法分析及算法實(shí)現(xiàn)9. 在有序序列(r1, r2, , rn)中，存在序號i（1in），使得ri=i。請?jiān)O(shè)計(jì)一個分治算法找到這個元素

20、，要求算法在最壞情況下的時間性能為O(log2n)。/在有序數(shù)組中/采用二分法查找符合條件的元素#include<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=mi

21、d+1; int main()int a7=1,0,2,5,6,7,9; Findnum(a,7);return 0;時間復(fù)雜度為O(log2n)。10. 在一個序列中出現(xiàn)次數(shù)最多的元素稱為眾數(shù)。請?jiān)O(shè)計(jì)算法尋找眾數(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&&

22、amp;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); /將第一次排序的結(jié)果作為樞軸 qsort(l,low,prvotloc-1); /遞歸調(diào)用排序 由low 到prvotloc-1 qsort(l,prvotlo

23、c+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;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; /while

24、 cout<<"重復(fù)次數(shù)："<<max<<endl; return 0;時間復(fù)雜度nlog(n)11. 設(shè)M是一個n×n的整數(shù)矩陣，其中每一行（從左到右）和每一列（從上到下）的元素都按升序排列。設(shè)計(jì)分治算法確定一個給定的整數(shù)x是否在M中，并分析算法的時間復(fù)雜性。 12. 設(shè)S是n（n為偶數(shù)）個不等的正整數(shù)的集合，要求將集合S劃分為子集S1和S2，使得| S1|=| S2|=n/2，且兩個子集元素之和的差達(dá)到最大。/先用快速排序進(jìn)行一趟排序/如果s1（大的數(shù)集）的的個數(shù)大于n/2/將（i<=n/2-low-1）個最小的數(shù)排到

25、后面/如果s1（大的數(shù)集）的的個數(shù)小于n/2/將s2（小的數(shù)集）n/2-low-1排到前面/將排好的數(shù)組的前n/2個數(shù)賦值給s1/將排好的數(shù)組的后n/2個數(shù)賦值給s2#include<iostream>using namespace 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; wh

26、ile (low<high&&alow>=prvotkey) +low; ahigh=alow;alow=prvotkey;/如果s1（大的數(shù)集）的的個數(shù)大于n/2if(low>=n/2) for(int i=0;i<=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/如果s1（大的數(shù)集）的的個數(shù)小于n/2else for(int i=0;i<=n/2-low-1;+i) for(int k=n-1;k<

27、n-i;+k) if(ak>ak-1)int temp1=ak; ak=ak-1; ak-1=temp1; /for int main()int an=1,3,5,9,6,0,-11,-8;partions(a,0,n-1);for(int i=0;i<n;+i) if(i<4) cout<<"屬于子集s1的："<<endl; cout<<ai<<endl; else cout<<"屬于子集s2的："<<endl; cout<<ai<<end

28、l; return 0;13. 設(shè)a1, a2, an是集合1, 2, , n的一個排列，如果i<j且ai>aj，則序偶(ai, aj)稱為該排列的一個逆序。例如，2, 3, 1有兩個逆序：(3, 1)和(2, 1)。設(shè)計(jì)算法統(tǒng)計(jì)給定排列中含有逆序的個數(shù)。/用歸并進(jìn)行排序/當(dāng)一個子集的一個數(shù)大于第二個子集的一個數(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)/合并子序

29、列 int i=begin,j=mid+1,k=end; while(i<=mid&&j<=end) if(ai<=aj) a1k+=ai+;/取ai和aj中較小者放入r1k else a1k+=aj+; count+=(end-j+1); while(i<=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; Mer

30、geSort(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<<endl;return 0;14. 循環(huán)賽日程安排問題。設(shè)有n=2k個選手要進(jìn)行網(wǎng)球循環(huán)賽，要求設(shè)計(jì)一個滿足以下要求的比賽日程表：（1）每個選手必須與其他n-1個選手各賽一次；（2）每個選手一天只能賽一次。 采用分治方法。 將2k選手分為2k-1兩組，采用遞歸方法，繼續(xù)進(jìn)行分組，直到只剩下2個選

31、手時，然后進(jìn)行比賽，回溯就可以指定比賽日程表了15. 格雷碼是一個長度為2n的序列，序列中無相同元素，且每個元素都是長度為n的二進(jìn)制位串，相鄰元素恰好只有1位不同。例如長度為23的格雷碼為(000, 001, 011, 010, 110, 111, 101, 100)。設(shè)計(jì)分治算法對任意的n值構(gòu)造相應(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=

32、9;0'?'1':'0' /取反 gelei(k+1);int main() while(cin>>n && n != 0) memset(a,'0',sizeof(a); /初始化，全部置零 an ='0' gelei(0); cout<<endl; return 0;16. 矩陣乘法。兩個n×n的矩陣X和Y的乘積得到另外一個n×n的矩陣Z，且Zij滿足 （1i, jn），這個公式給出了運(yùn)行時間為O(n3)的算法?？梢杂梅种畏ń鉀Q矩陣乘法問題，將矩陣X和Y都劃分

33、成四個n/2×n/2的子塊，從而X和Y的乘積可以用這些子塊進(jìn)行表達(dá)，即從而得到分治算法：先遞歸地計(jì)算8個規(guī)模為n/2的矩陣乘積AE、BG、AF、BH、CE、DG、CF、DH，然后再花費(fèi)O(n2)的時間完成加法運(yùn)算即可。請?jiān)O(shè)計(jì)分治算法實(shí)現(xiàn)矩陣乘法，并分析時間性能。能否再改進(jìn)這個分治算法？習(xí)題51. 下面這個折半查找算法正確嗎？如果正確，請給出算法的正確性證明，如果不正確，請說明產(chǎn)生錯誤的原因。int BinSearch(int r , int n, int k) int low = 0, high = n - 1;int mid;while (low <= high) mid =

34、 (low + high) / 2;if (k < rmid)high = mid;elseif (k > rmid) low = mid; else return mid; return 0;錯誤。正確算法：int BinSearch1(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 - 1;elseif (k > rmid) low = mid + 1; els

35、e return mid; return 0; 2. 請寫出折半查找的遞歸算法，并分析時間性能。/折半查找的遞歸實(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 mid = (low+high)/2; if (amid = x) return mid; else if (amid < x) digui_search(a,low,mid-1,x); else digui_search(a,m

36、id+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之間的所有元素（ab）修改第二題算法并實(shí)現(xiàn)：/折半查找算法使之能夠進(jìn)行范圍查找#include <iostream>using namespace std;/折半進(jìn)行范圍查找函數(shù)：void digui_search(int min, int max, int a, int

37、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); else for(int i=mid; ai>=min && i>=low; i-) cout<<ai<<" " cout<<endl; for(int j=mid+1; aj<=max &&a

38、mp; 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<<"請輸入查找范圍最小值min和最大值max："<<" "cin>>min>>max; digui_search(min,

39、 max, r, 0, 5); cout<<endl;4. 求兩個正整數(shù)m和n的最小公倍數(shù)。（提示：m和n的最小公倍數(shù)lcm(m, n)與m和n的最大公約數(shù)gcd(m, n)之間有如下關(guān)系：lcm(m, n)=m×n/gcd(m, n)）/求兩個數(shù)的最小公倍數(shù)#include<iostream>using namespace std;int main (void) int a,b; int i=1; cin>>a>>b; while(i%a!=0)|(i%b!=0) +i; cout<<"a,b最小公倍數(shù)為：&qu

40、ot;<<i<<endl;return 0;(該算法比較直接，要使其改進(jìn)，可用歐幾里得算法求得兩個數(shù)的最大公約數(shù)，然后套用上面的公式再求最小公倍數(shù))5. 插入法調(diào)整堆。已知（k1, k2, , kn）是堆，設(shè)計(jì)算法將（k1, k2, , kn, kn+1）調(diào)整為堆（假設(shè)調(diào)整為大根堆）。參照： void SiftHeap(int r , int k, int n)int i, j, temp;i = k; j = 2 * i + 1; /置i為要篩的結(jié)點(diǎn)，j為i的左孩子while (j < n) /篩選還沒有進(jìn)行到葉子if (j < n-1 &&

41、; rj < rj+1) j+; /比較i的左右孩子，j為較大者if (ri > rj) /根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者 break; else temp = ri; ri = rj; rj = temp; /將被篩結(jié)點(diǎn)與結(jié)點(diǎn)j交換 i = j; j = 2 * i + 1; /被篩結(jié)點(diǎn)位于原來結(jié)點(diǎn)j的位置進(jìn)行調(diào)堆！6. 設(shè)計(jì)算法實(shí)現(xiàn)在大根堆中刪除一個元素，要求算法的時間復(fù)雜性為O(log2n)。/將要刪除的ak與最后一個元素an-1交換/然后進(jìn)行調(diào)堆void de_SiftHeap(int r , int k, int n)int i, j, temp,temp1;i = k

42、; j = 2 * i + 1; if(i<0|i>n-1)return error;else if(i=n-1)free(ai);else /置i為要篩的結(jié)點(diǎn)，j為i的左孩子while (j < n) /篩選還沒有進(jìn)行到葉子temp1=ai; /將an-1與ak交換；ai=an-1;an-1= temp1;if (j < n-1 && rj < rj+1) j+; /比較i的左右孩子，j為較大者if (ri > rj) /根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者 break; else temp = ri; ri = rj; rj = temp;

43、/將被篩結(jié)點(diǎn)與結(jié)點(diǎn)j交換 i = j; j = 2 * i + 1; /被篩結(jié)點(diǎn)位于原來結(jié)點(diǎn)j的位置n m50 6525 130 13012 260 6 5203 1040 10401 2080 2080 3250圖5.15 俄式乘法+7. 計(jì)算兩個正整數(shù)n和m的乘積有一個很有名的算法稱為俄式乘法，其思想是利用了一個規(guī)模是n的解和一個規(guī)模是n/2的解之間的關(guān)系：n×mn/2×2m（當(dāng)n是偶數(shù)）或：n×m(n-1)/2×2mm（當(dāng)n是奇數(shù)），并以1×mm作為算法結(jié)束的條件。例如，圖5.15給出了利用俄式乘法計(jì)算50×65的例子。據(jù)說十九

44、世紀(jì)的俄國農(nóng)夫使用該算法并因此得名，這個算法也使得乘法的硬件實(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)/2; temp=n;/記錄倒數(shù)第二個n的值 return sum+n;int main() int a,b

45、; while(cin>>a>>b) cout<<fun(a,b)<<endl; 8. 拿子游戲?？紤]下面這個游戲：桌子上有一堆火柴，游戲開始時共有n根火柴，兩個玩家輪流拿走1，2，3或4根火柴，拿走最后一根火柴的玩家為獲勝方。請為先走的玩家設(shè)計(jì)一個制勝的策略（如果該策略存在）。 如果桌上有小于4根的火柴，先手必勝，如果是5根，先手必輸；依次類推，同理15、20、25.都是必輸狀態(tài)；所有每次把對手逼到15、20、25.等必輸狀態(tài)，就可以獲勝。9. 競賽樹是一棵完全二叉樹，它反映了一系列“淘汰賽”的結(jié)果：葉子代表參加比賽的n個選手，每個內(nèi)部結(jié)點(diǎn)代表

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

47、有假幣；如果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ì)算各個子問題的解并填表。2. 對于圖6.26所示多段圖，用動態(tài)規(guī)劃法求從頂點(diǎn)0到頂點(diǎn)12的最短路徑，寫出求解過程。883510234101112圖6.26 第2題圖567891367683533463552643 將該多段圖分為四段；首先求解初始子問題，可直接獲得：d(0, 1)=c015(01)d(0, 2)=c023(01)再求解下一個階段的子問題，有：d(0,3)= d(0, 1)+ c13 =6(13)d(0,4)=mind(0,1)+ c14 ,d(0,2)+ c24=8(14)。（以此類推）最短路徑為：013811123用動態(tài)規(guī)劃法求如下0/1背包問題的最優(yōu)解：有5個物品，其重量分別為(3, 2, 1, 4,5)，價值分別為(25, 20, 15, 40, 50)，背包容量為6。寫出求解過程。