算法設計及分析習題答案解析1-6章

..習題1圖1.7七橋問題北區(qū)東區(qū)島區(qū)南區(qū)圖論誕生于七橋問題。出生于瑞士的偉大數(shù)學家歐拉〔LeonhardEuler,1707—1783提出并解決了該問題。七橋問題是這樣描述的：一個人是否能在一次步行中穿越圖1.7七橋問題北區(qū)東區(qū)島區(qū)南區(qū)七橋問題屬于一筆畫問題。輸入：一個起點輸出：相同的點一次步行經(jīng)過七座橋,且每次只經(jīng)歷過一次回到起點該問題無解：能一筆畫的圖形只有兩類：一類是所有的點都是偶點。另一類是只有二個奇點的圖形。2．在歐幾里德提出的歐幾里德算法中〔即最初的歐幾里德算法用的不是除法而是減法。請用偽代碼描述這個版本的歐幾里德算法1.r=m-n2.循環(huán)直到r=0

2.1

m=n

2.2

n=r

2.3

r=m-n

3

輸出m3．設計算法求數(shù)組中相差最小的兩個元素〔稱為最接近數(shù)的差。要求分別給出偽代碼和C++描述。//采用分治法//對數(shù)組先進行快速排序//在依次比較相鄰的差#include<iostream>usingnamespacestd;intpartions<intb[],intlow,inthigh>{intprvotkey=b[low];b[0]=b[low];while<low<high>{while<low<high&&b[high]>=prvotkey>--high;b[low]=b[high];while<low<high&&b[low]<=prvotkey>++low;b[high]=b[low];}b[low]=b[0];returnlow;}voidqsort<intl[],intlow,inthigh>{intprvotloc;if<low<high>{prvotloc=partions<l,low,high>;//將第一次排序的結果作為樞軸qsort<l,low,prvotloc-1>;//遞歸調用排序由low到prvotloc-1qsort<l,prvotloc+1,high>;//遞歸調用排序由prvotloc+1到high}}voidquicksort<intl[],intn>{qsort<l,1,n>;//第一個作為樞軸,從第一個排到第n個}intmain<>{inta[11]={0,2,32,43,23,45,36,57,14,27,39};intvalue=0;//將最小差的值賦值給valuefor<intb=1;b<11;b++>cout<<a[b]<<'';cout<<endl;quicksort<a,11>;for<inti=0;i!=9;++i>{if<<a[i+1]-a[i]><=<a[i+2]-a[i+1]>> value=a[i+1]-a[i];elsevalue=a[i+2]-a[i+1];}cout<<value<<endl;return0;}4．設數(shù)組a[n]中的元素均不相等,設計算法找出a[n]中一個既不是最大也不是最小的元素,并說明最壞情況下的比較次數(shù)。要求分別給出偽代碼和C++描述。#include<iostream>usingnamespacestd;intmain<>{ inta[]={1,2,3,6,4,9,0};intmid_value=0;//將"既不是最大也不是最小的元素"的值賦值給它 for<inti=0;i!=4;++i> { if<a[i+1]>a[i]&&a[i+1]<a[i+2]> { mid_value=a[i+1]; cout<<mid_value<<endl; break; } elseif<a[i+1]<a[i]&&a[i+1]>a[i+2]> { mid_value=a[i+1]; cout<<mid_value<<endl; break; } }//for return0;}5.編寫程序,求n至少為多大時,n個"1"組成的整數(shù)能被2013整除。#include<iostream>usingnamespacestd;intmain<>{doublevalue=0;for<intn=1;n<=10000;++n>{ value=value*10+1;if<value%2013==0>{ cout<<"n至少為:"<<n<<endl; break;}}//forreturn0;}6.計算π值的問題能精確求解嗎？編寫程序,求解滿足給定精度要求的π值#include<iostream>usingnamespacestd;intmain<>{doublea,b;doublearctan<doublex>;//聲明a=16.0*arctan<1/5.0>;b=4.0*arctan<1/239>;cout<<"PI="<<a-b<<endl;return0；}doublearctan<doublex>{inti=0;doubler=0,e,f,sqr;//定義四個變量初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}//whilereturnr;}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ù)是否是完美數(shù)#include<iostream>usingnamespacestd;intmain<>{intvalue,k=1;cin>>value;for<inti=2;i!=value;++i>{while<value%i==0>{k+=i;//k為該自然數(shù)所有因子之和value=value/i; }}//forif<k==value>cout<<"該自然數(shù)是完美數(shù)"<<endl; elsecout<<"該自然數(shù)不是完美數(shù)"<<endl; return0;}8.有4個人打算過橋,這個橋每次最多只能有兩個人同時通過。他們都在橋的某一端,并且是在晚上,過橋需要一只手電筒,而他們只有一只手電筒。這就意味著兩個人過橋后必須有一個人將手電筒帶回來。每個人走路的速度是不同的：甲過橋要用1分鐘,乙過橋要用2分鐘,丙過橋要用5分鐘,丁過橋要用10分鐘,顯然,兩個人走路的速度等于其中較慢那個人的速度,問題是他們全部過橋最少要用多長時間？由于甲過橋時間最短,那么每次傳遞手電的工作應有甲完成甲每次分別帶著乙丙丁過橋例如：第一趟：甲,乙過橋且甲回來第二趟：甲,丙過橋且甲回來第一趟：甲,丁過橋一共用時19小時9．歐幾里德游戲：開始的時候,白板上有兩個不相等的正整數(shù),兩個玩家交替行動,每次行動時,當前玩家都必須在白板上寫出任意兩個已經(jīng)出現(xiàn)在板上的數(shù)字的差,而且這個數(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ù),就選擇先行動；否則就后行動。習題41.分治法的時間性能與直接計算最小問題的時間、合并子問題解的時間以及子問題的個數(shù)有關,試說明這幾個參數(shù)與分治法時間復雜性之間的關系。2.證明：如果分治法的合并可以在線性時間內完成,則當子問題的規(guī)模之和小于原問題的規(guī)模時,算法的時間復雜性可達到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由此可知,時間復雜度可達到O<n>;3.分治策略一定導致遞歸嗎？如果是,請解釋原因。如果不是,給出一個不包含遞歸的分治例子,并闡述這種分治和包含遞歸的分治的主要不同。不一定導致遞歸。如非遞歸的二叉樹中序遍歷。這種分治方法與遞歸的二叉樹中序遍歷主要區(qū)別是：應用了棧這個數(shù)據(jù)結構。4.對于待排序序列<5,3,1,9>,分別畫出歸并排序和快速排序的遞歸運行軌跡。歸并排序：第一趟：〔5,3〔1,9；第二趟：〔3,5,1,9；第三趟：〔1,3,5,9；快速排序：第一趟：5〔,3,1,9；//5為哨兵,比較9和5第二趟：5〔1,3,,9；//比較1和5,將1挪到相應位置；第三趟：5〔1,3,,9;//比較3和5；第四趟：〔1,3,5,9;5.設計分治算法求一個數(shù)組中的最大元素,并分析時間性能。//簡單的分治問題//將數(shù)組均衡的分為"前","后"兩部分//分別求出這兩部分最大值,然后再比較這兩個最大值#include<iostream>usingnamespacestd;externconstintn=6;//聲明intmain<>{ inta[n]={0,6,1,2,3,5};//初始化 intmid=n/2; intnum_max1=0,num_max2=0; for<inti=0;i<=n/2;++i>//前半部分 { if<a[i]>num_max1> num_max1=a[i]; } for<intj=n/2+1;j<n;++j>//后半部分 { if<a[j]>num_max2> num_max2=a[j]; } if<num_max1>=num_max2> cout<<"數(shù)組中的最大元素："<<num_max1<<endl; elsecout<<"數(shù)組中的最大元素："<<num_max2<<endl; return0;}時間復雜度：O〔n6.設計分治算法,實現(xiàn)將數(shù)組A[n]中所有元素循環(huán)左移k個位置,要求時間復雜性為O<n>,空間復雜性為O<1>。例如,對abcdefgh循環(huán)左移3位得到defghabc。//采用分治法//將數(shù)組分為0-k-1和k-n-1兩塊//將這兩塊分別左移//然后再合并左移#include<iostream>usingnamespacestd;voidLeftReverse<char*a,intbegin,intend>{for<inti=0;i<<end-begin+1>/2;i++>//交換移動{inttemp=a[begin+i];a[begin+i]=a[end-i];a[end-i]=temp;}}voidConverse<char*a,intn,intk>{LeftReverse<a,0,k-1>;LeftReverse<a,k,n-1>;LeftReverse<a,0,n-1>;for<inti=0;i<n;i++>cout<<a[i]<<"";cout<<endl;}intmain<>{chara[7]={'a','b','c','d','e','f','g'};Converse<a,7,3>;return0;}7.設計遞歸算法生成n個元素的所有排列對象。#include<iostream>usingnamespacestd;intdata[100];//在m個數(shù)中輸出n個排列數(shù)〔n<=mvoidDPpl<intnum,intm,intn,intdepth>{if<depth==n>{for<inti=0;i<n;i++>cout<<data[i]<<"";cout<<endl;}for<intj=0;j<m;j++>{if<<num&<1<<j>>==0>{data[depth]=j+1;DPpl<num+<1<<j>,m,n,depth+1>;}}//for}intmain<>{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>;return0;}8.設計分治算法求解一維空間上n個點的最近對問題。參見最近對問題的算法分析及算法實現(xiàn)9.在有序序列<r1,r2,…,rn>中,存在序號i〔1≤i≤n,使得ri=i。請設計一個分治算法找到這個元素,要求算法在最壞情況下的時間性能為O<log2n>。//在有序數(shù)組中//采用二分法查找符合條件的元素#include<iostream>usingnamespacestd;voidFindnum<int*a,intn>{intlow=0;inthigh=n-1;while<low<=high>{intmid=<low+high>/2; if<a[mid]==mid> { cout<<"這個數(shù)是："<<a[mid]<<endl;break; } elseif<a[mid]>mid> high=mid-1; else low=mid+1;}}intmain<>{ inta[7]={1,0,2,5,6,7,9};Findnum<a,7>; return0;}時間復雜度為O<log2n>。10.在一個序列中出現(xiàn)次數(shù)最多的元素稱為眾數(shù)。請設計算法尋找眾數(shù)并分析算法的時間復雜性。//先對序列進行快速排序//再進行一次遍歷//輸出眾數(shù)的重復次數(shù)#include<iostream>usingnamespacestd;intpartions<intb[],intlow,inthigh>{intprvotkey=b[low];b[0]=b[low];while<low<high>{while<low<high&&b[high]>=prvotkey>--high;b[low]=b[high];while<low<high&&b[low]<=prvotkey>++low;b[high]=b[low];}b[low]=b[0];returnlow;}voidqsort<intl[],intlow,inthigh>{intprvotloc;if<low<high>{prvotloc=partions<l,low,high>;//將第一次排序的結果作為樞軸qsort<l,low,prvotloc-1>;//遞歸調用排序由low到prvotloc-1qsort<l,prvotloc+1,high>;//遞歸調用排序由prvotloc+1到high}}voidquicksort<intl[],intn>{qsort<l,1,n>;//第一個作為樞軸,從第一個排到第n個}intmain<>{ inta[10]={1,2,3,5,3,3,3,2,5,1}; inti=0; intcount=0; intmax=0;//max表示出現(xiàn)的次數(shù) qsort<a,0,10>;while<i<10> { intj; j=i+1; if<a[i]=a[j]&&i<10> { count++; i++; } if<count>max> { max=count; count=0; } }//whilecout<<"重復次數(shù)："<<max<<endl;return0;}時間復雜度nlog<n>11.設M是一個n×n的整數(shù)矩陣,其中每一行〔從左到右和每一列〔從上到下的元素都按升序排列。設計分治算法確定一個給定的整數(shù)x是否在M中,并分析算法的時間復雜性。12.設S是n〔n為偶數(shù)個不等的正整數(shù)的集合,要求將集合S劃分為子集S1和S2,使得|S1|=|S2|=n/2,且兩個子集元素之和的差達到最大。//先用快速排序進行一趟排序//如果s1〔大的數(shù)集的的個數(shù)大于n/2//將〔i<=n/2-low-1個最小的數(shù)排到后面//如果s1〔大的數(shù)集的的個數(shù)小于n/2//將s2〔小的數(shù)集n/2-low-1排到前面//將排好的數(shù)組的前n/2個數(shù)賦值給s1//將排好的數(shù)組的后n/2個數(shù)賦值給s2#include<iostream>usingnamespacestd;constintn=8;voidpartions<inta[],intlow,inthigh>{ //進行一趟快排intprvotkey=a[low];a[0]=a[low];while<low<high>{while<low<high&&a[high]<=prvotkey>--high;a[low]=a[high];while<low<high&&a[low]>=prvotkey>++low;a[high]=a[low];}a[low]=prvotkey;//如果s1〔大的數(shù)集的的個數(shù)大于n/2if<low>=n/2>{for<inti=0;i<=n/2-low-1;++i>{for<intj=0;j<n-i;++j> { if<a[j]<a[j+1]> { inttemp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } }//for}}//if//如果s1〔大的數(shù)集的的個數(shù)小于n/2elsefor<inti=0;i<=n/2-low-1;++i>{for<intk=n-1;k<n-i;++k> { if<a[k]>a[k-1]> { inttemp1=a[k]; a[k]=a[k-1]; a[k-1]=temp1; } }//for}}intmain<>{ inta[n]={1,3,5,9,6,0,-11,-8}; partions<a,0,n-1>;for<inti=0;i<n;++i>{if<i<4>{cout<<"屬于子集s1的："<<endl;cout<<a[i]<<endl;}else{cout<<"屬于子集s2的："<<endl;cout<<a[i]<<endl;}} return0;}13.設a1,a2,…,an是集合{1,2,…,n}的一個排列,如果i<j且ai>aj,則序偶<ai,aj>稱為該排列的一個逆序。例如,2,3,1有兩個逆序：<3,1>和<2,1>。設計算法統(tǒng)計給定排列中含有逆序的個數(shù)。//用歸并進行排序//當一個子集的一個數(shù)大于第二個子集的一個數(shù),為逆序,即a[i]>a[j]//則逆序數(shù)為end-j+1;#include<iostream>usingnamespacestd;intcount;voidMerge<inta[],inta1[],intbegin,intmid,intend>//合并子序列{inti=begin,j=mid+1,k=end;while<i<=mid&&j<=end>{if<a[i]<=a[j]> a1[k++]=a[i++];//取a[i]和a[j]中較小者放入r1[k] else { a1[k++]=a[j++]; count+=<end-j+1>; }}while<i<=mid> a1[k++]=a[i++];while<j<=end> a1[k++]=a[j++];}voidMergeSort<inta[],intbegin,intend>{intmid,a1[1000];if<begin==end> return;else{ mid=<begin+end>/2;MergeSort<a,begin,mid>; MergeSort<a,mid+1,end>; Merge<a,a1,begin,mid,end>; }}intmain<>{ inta[6]={6,5,4,3,2,1}; count=0; MergeSort<a,0,6>; cout<<count<<endl; return0;}14.循環(huán)賽日程安排問題。設有n=2k個選手要進行網(wǎng)球循環(huán)賽,要求設計一個滿足以下要求的比賽日程表：〔1每個選手必須與其他n-1個選手各賽一次；〔2每個選手一天只能賽一次。采用分治方法。將2^k選手分為2^k-1兩組,采用遞歸方法,繼續(xù)進行分組,直到只剩下2個選手時,然后進行比賽,回溯就可以指定比賽日程表了15.格雷碼是一個長度為2n的序列,序列中無相同元素,且每個元素都是長度為n的二進制位串,相鄰元素恰好只有1位不同。例如長度為23的格雷碼為<000,001,011,010,110,111,101,100>。設計分治算法對任意的n值構造相應的格雷碼。//構造格雷碼#include<iostream>usingnamespacestd;intn;chara[100];voidgelei<intk>{if<k==n>{cout<<a<<endl; return;}gelei<k+1>;a[k]='0'?'1':'0';//取反gelei<k+1>;}intmain<>{while<cin>>n&&n!=0>{ memset<a,'0',sizeof<a>>;//初始化,全部置零a[n]='\0'; gelei<0>; cout<<endl;}return0;}16.矩陣乘法。兩個n×n的矩陣X和Y的乘積得到另外一個n×n的矩陣Z,且Zij滿足〔1≤i,j≤n,這個公式給出了運行時間為O<n3>的算法?？梢杂梅种畏ń鉀Q矩陣乘法問題,將矩陣X和Y都劃分成四個n/2×n/2的子塊,從而X和Y的乘積可以用這些子塊進行表達,即從而得到分治算法：先遞歸地計算8個規(guī)模為n/2的矩陣乘積AE、BG、AF、BH、CE、DG、CF、DH,然后再花費O<n2>的時間完成加法運算即可。請設計分治算法實現(xiàn)矩陣乘法,并分析時間性能。能否再改進這個分治算法？習題5下面這個折半查找算法正確嗎？如果正確,請給出算法的正確性證明,如果不正確,請說明產(chǎn)生錯誤的原因。intBinSearch<intr[],intn,intk>{intlow=0,high=n-1;intmid;while<low<=high>{mid=<low+high>/2;if<k<r[mid]> high=mid;else if<k>r[mid]>low=mid;elsereturnmid;}return0;}錯誤。正確算法：intBinSearch1<intr[],intn,intk>{intlow=0,high=n-1;intmid;while<low<=high>{mid=<low+high>/2;if<k<r[mid]> high=mid-1;else if<k>r[mid]>low=mid+1;elsereturnmid;}return0;}請寫出折半查找的遞歸算法,并分析時間性能。//折半查找的遞歸實現(xiàn)#include<iostream>usingnamespacestd;intdigui_search<inta[],intlow,inthigh,intx>{if<low>high>return0;intmid=<low+high>/2;if<a[mid]==x>returnmid;elseif<a[mid]<x>digui_search<a,low,mid-1,x>;elsedigui_search<a,mid+1,high,x>;}intmain<>{ inta[6]={0,1,2,9,5,3};intresult=digui_search<a,0,5,5>;cout<<a[result]<<endl; return0;}修改折半查找算法使之能夠進行范圍查找。所謂范圍查找是要找出在給定值a和b之間的所有元素〔a≤b修改第二題算法并實現(xiàn)：//折半查找算法使之能夠進行范圍查找#include<iostream>usingnamespacestd;//折半進行范圍查找函數(shù)：voiddigui_search<intmin,intmax,inta[],intlow,inthigh>{intmid;mid=<low+high>/2;if<a[mid]<min>digui_search<min,max,a,mid,high>;elseif<a[mid]>max>digui_search<min,max,a,low,mid>;else{for<inti=mid;a[i]>=min&&i>=low;i-->cout<<a[i]<<""; cout<<endl;for<intj=mid+1;a[j]<=max&&j<=high;j++>cout<<a[j]<<""; cout<<endl;}}voidmain<>{intr[6],min,max;cout<<"請輸入數(shù)組元素："<<endl;for<inti=0;i<6;i++>cin>>r[i];cout<<"請輸入查找范圍最小值min和最大值max："<<"";cin>>min>>max;digui_search<min,max,r,0,5>;cout<<endl;}4.求兩個正整數(shù)m和n的最小公倍數(shù)?！蔡崾荆簃和n的最小公倍數(shù)lcm<m,n>與m和n的最大公約數(shù)gcd<m,n>之間有如下關系：lcm<m,n>=m×n/gcd<m,n>//求兩個數(shù)的最小公倍數(shù)#include<iostream>usingnamespacestd;intmain<void>{inta,b;inti=1;cin>>a>>b;while<<i%a!=0>||<i%b!=0>> ++i;cout<<"a,b最小公倍數(shù)為："<<i<<endl;return0;}<該算法比較直接,要使其改進,可用歐幾里得算法求得兩個數(shù)的最大公約數(shù),然后套用上面的公式再求最小公倍數(shù)>5.插入法調整堆。已知〔k1,k2,…,kn是堆,設計算法將〔k1,k2,…,kn,kn+1調整為堆〔假設調整為大根堆。參照：voidSiftHeap<intr[],intk,intn>{inti,j,temp;i=k;j=2*i+1;//置i為要篩的結點,j為i的左孩子while<j<n>//篩選還沒有進行到葉子{if<j<n-1&&r[j]<r[j+1]>j++;//比較i的左右孩子,j為較大者 if<r[i]>r[j]>//根結點已經(jīng)大于左右孩子中的較大者break; else{ temp=r[i];r[i]=r[j];r[j]=temp;//將被篩結點與結點j交換 i=j;j=2*i+1;//被篩結點位于原來結點j的位置 }}}進行調堆！6.設計算法實現(xiàn)在大根堆中刪除一個元素,要求算法的時間復雜性為O<log2n>。//將要刪除的a[k]與最后一個元素a[n-1]交換//然后進行調堆voidde_SiftHeap<intr[],intk,intn>{inti,j,temp,temp1;i=k;j=2*i+1;if<i<0||i>n-1>returnerror;elseif<i==n-1>free<a[i]>;else//置i為要篩的結點,j為i的左孩子while<j<n>//篩選還沒有進行到葉子{temp1=a[i];//將a[n-1]與a[k]交換；a[i]=a[n-1];a[n-1]=temp1;if<j<n-1&&r[j]<r[j+1]>j++;//比較i的左右孩子,j為較大者 if<r[i]>r[j]>//根結點已經(jīng)大于左右孩子中的較大者break; else{ temp=r[i];r[i]=r[j];r[j]=temp;//將被篩結點與結點j交換 i=j;j=2*i+1;//被篩結點位于原來結點j的位置 }}}nm5065251301301226065203104010401208020803250圖5.15俄式乘法+7.計算兩個正整數(shù)n和m的乘積有一個很有名的算法稱為俄式乘法,其思想是利用了一個規(guī)模是n的解和一個規(guī)模是n/2的解之間的關系：n×m＝n/2×2m〔當n是偶數(shù)或：n×m＝<n-1>/2×2m＋nm5065251301301226065203104010401208020803250圖5.15俄式乘法+//俄式乘法#include<iostream>usingnamespacestd;intfun<intm,intn>{intsum=0;inttemp=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的值}returnsum+n;}intmain<>{inta,b;while<cin>>a>>b>{cout<<fun<a,b><<endl;}}8.拿子游戲?？紤]下面這個游戲：桌子上有一堆火柴,游戲開始時共有n根火柴,兩個玩家輪流拿走1,2,3或4根火柴,拿走最后一根火柴的玩家為獲勝方。請為先走的玩家設計一個制勝的策略〔如果該策略存在。如果桌上有小于4根的火柴,先手必勝,如果是5根,先手必輸；依次類推,同理15、20、25…….都是必輸狀態(tài)；所有每次把對手逼到15、20、25…….等必輸狀態(tài),就可以獲勝。9.競賽樹是一棵完全二叉樹,它反映了一系列"淘汰賽"的結果：葉子代表參加比賽的n個選手,每個內部結點代表由該結點的孩子結點所代表的選手中的勝者,顯然,樹的根結點就代表了淘汰賽的冠軍。請回答下列問題：〔1這一系列的淘汰賽中比賽的總場數(shù)是多少？〔2設計一個高效的算法,它能夠利用比賽中產(chǎn)生的信息確定亞軍?！?因為n人進行淘汰賽,要淘汰n-1人,所有要進行n-1場比賽。〔210.在120枚外觀相同的硬幣中,有一枚是假幣,并且已知假幣與真幣的重量不同,但不知道假幣與真幣相比較輕還是較重?？梢酝ㄟ^一架天平來任意比較兩組硬幣,最壞情況下,能不能只比較5次就檢測出這枚假幣？將120枚平均分為三組,記為：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有假幣；習題6動態(tài)規(guī)劃法為什么都需要填表？如何設計表格的結構？在填寫表格過程中,不僅可以使問題更加清晰,更重要的是可以確定問題的存儲結構；設計表格,以自底向上的方式計算各個子問題的解并填表。2.對于圖6.26所示多段圖,用動態(tài)規(guī)劃法求從頂點0到頂點12的最短路徑,寫出求解過程。8883510234101112圖6.26第2題圖567891367683533463552643將該多段圖分為四段；首先求解初始子問題,可直接獲得：d<0,1>=c01＝5<0→1>d<0,2>=c02＝3<0→1>再求解下一個階段的子問題,有：d<0,3>=d<0,1>+c13=6<1→3>d<0,4>=min{d<0,1>+c14,d<0,2>+c24}=8<1→4>。。。。。。。。〔以此類推最短路徑為：0→1→3→8→11→123．用動態(tài)規(guī)劃法求如下0/1背包問題的最優(yōu)解：有5個物品,其重量分別為<3,2,1,4,5>,價值分別為<25,20,15,40,50>,背包容量為6。寫出求解過程。<x1,x2,x3,x4,x5>→<1,1,1,0,0><過程略>4.用動態(tài)規(guī)劃法求兩個字符串A="xzyzzyx"和B="zxyyzxz"的最長公共子序列。寫出求解過程。略5.給定模式"grammer"和