算法设计及分析习题答案解析1-6章

..习题1图1.7七桥问题北区东区岛区南区图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉〔LeonhardEuler,1707—1783提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越图1.7七桥问题北区东区岛区南区七桥问题属于一笔画问题。输入：一个起点输出：相同的点一次步行经过七座桥,且每次只经历过一次回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。2．在欧几里德提出的欧几里德算法中〔即最初的欧几里德算法用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法1.r=m-n2.循环直到r=0

2.1

m=n

2.2

n=r

2.3

r=m-n

3

输出m3．设计算法求数组中相差最小的两个元素〔称为最接近数的差。要求分别给出伪代码和C++描述。//采用分治法//对数组先进行快速排序//在依次比较相邻的差#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．设数组a[n]中的元素均不相等,设计算法找出a[n]中一个既不是最大也不是最小的元素,并说明最坏情况下的比较次数。要求分别给出伪代码和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"组成的整数能被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.圣经上说：神6天创造天地万有,第7日安歇。为什么是6天呢？任何一个自然数的因数中都有1和它本身,所有小于它本身的因数称为这个数的真因数,如果一个自然数的真因数之和等于它本身,这个自然数称为完美数。例如,6=1+2+3,因此6是完美数。神6天创造世界,暗示着该创造是完美的。设计算法,判断给定的自然数是否是完美数#include<iostream>usingnamespacestd;intmain<>{intvalue,k=1;cin>>value;for<inti=2;i!=value;++i>{while<value%i==0>{k+=i;//k为该自然数所有因子之和value=value/i; }}//forif<k==value>cout<<"该自然数是完美数"<<endl; elsecout<<"该自然数不是完美数"<<endl; return0;}8.有4个人打算过桥,这个桥每次最多只能有两个人同时通过。他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟,乙过桥要用2分钟,丙过桥要用5分钟,丁过桥要用10分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥最少要用多长时间？由于甲过桥时间最短,那么每次传递手电的工作应有甲完成甲每次分别带着乙丙丁过桥例如：第一趟：甲,乙过桥且甲回来第二趟：甲,丙过桥且甲回来第一趟：甲,丁过桥一共用时19小时9．欧几里德游戏：开始的时候,白板上有两个不相等的正整数,两个玩家交替行动,每次行动时,当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差,而且这个数字必须是新的,也就是说,和白板上的任何一个已有的数字都不相同,当一方再也写不出新数字时,他就输了。请问,你是选择先行动还是后行动？为什么？设最初两个数较大的为a,较小的为b,两个数的最大公约数为factor。

则最终能出现的数包括:factor,factor*2,factor*3,...,factor*<a/factor>=a.一共a/factor个。如果a/factor是奇数,就选择先行动；否则就后行动。习题41.分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关,试说明这几个参数与分治法时间复杂性之间的关系。2.证明：如果分治法的合并可以在线性时间内完成,则当子问题的规模之和小于原问题的规模时,算法的时间复杂性可达到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.分治策略一定导致递归吗？如果是,请解释原因。如果不是,给出一个不包含递归的分治例子,并阐述这种分治和包含递归的分治的主要不同。不一定导致递归。如非递归的二叉树中序遍历。这种分治方法与递归的二叉树中序遍历主要区别是：应用了栈这个数据结构。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.设计分治算法求一个数组中的最大元素,并分析时间性能。//简单的分治问题//将数组均衡的分为"前","后"两部分//分别求出这两部分最大值,然后再比较这两个最大值#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<<"数组中的最大元素："<<num_max1<<endl; elsecout<<"数组中的最大元素："<<num_max2<<endl; return0;}时间复杂度：O〔n6.设计分治算法,实现将数组A[n]中所有元素循环左移k个位置,要求时间复杂性为O<n>,空间复杂性为O<1>。例如,对abcdefgh循环左移3位得到defghabc。//采用分治法//将数组分为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个数中输出n个排列数〔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个点的最近对问题。参见最近对问题的算法分析及算法实现9.在有序序列<r1,r2,…,rn>中,存在序号i〔1≤i≤n,使得ri=i。请设计一个分治算法找到这个元素,要求算法在最坏情况下的时间性能为O<log2n>。//在有序数组中//采用二分法查找符合条件的元素#include<iostream>usingnamespacestd;voidFindnum<int*a,intn>{intlow=0;inthigh=n-1;while<low<=high>{intmid=<low+high>/2; if<a[mid]==mid> { cout<<"这个数是："<<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.在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间复杂性。//先对序列进行快速排序//再进行一次遍历//输出众数的重复次数#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表示出现的次数 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<<"重复次数："<<max<<endl;return0;}时间复杂度nlog<n>11.设M是一个n×n的整数矩阵,其中每一行〔从左到右和每一列〔从上到下的元素都按升序排列。设计分治算法确定一个给定的整数x是否在M中,并分析算法的时间复杂性。12.设S是n〔n为偶数个不等的正整数的集合,要求将集合S划分为子集S1和S2,使得|S1|=|S2|=n/2,且两个子集元素之和的差达到最大。//先用快速排序进行一趟排序//如果s1〔大的数集的的个数大于n/2//将〔i<=n/2-low-1个最小的数排到后面//如果s1〔大的数集的的个数小于n/2//将s2〔小的数集n/2-low-1排到前面//将排好的数组的前n/2个数赋值给s1//将排好的数组的后n/2个数赋值给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〔大的数集的的个数大于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〔大的数集的的个数小于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>。设计算法统计给定排列中含有逆序的个数。//用归并进行排序//当一个子集的一个数大于第二个子集的一个数,为逆序,即a[i]>a[j]//则逆序数为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.循环赛日程安排问题。设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求的比赛日程表：〔1每个选手必须与其他n-1个选手各赛一次；〔2每个选手一天只能赛一次。采用分治方法。将2^k选手分为2^k-1两组,采用递归方法,继续进行分组,直到只剩下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>的算法。可以用分治法解决矩阵乘法问题,将矩阵X和Y都划分成四个n/2×n/2的子块,从而X和Y的乘积可以用这些子块进行表达,即从而得到分治算法：先递归地计算8个规模为n/2的矩阵乘积AE、BG、AF、BH、CE、DG、CF、DH,然后再花费O<n2>的时间完成加法运算即可。请设计分治算法实现矩阵乘法,并分析时间性能。能否再改进这个分治算法？习题5下面这个折半查找算法正确吗？如果正确,请给出算法的正确性证明,如果不正确,请说明产生错误的原因。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;}请写出折半查找的递归算法,并分析时间性能。//折半查找的递归实现#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修改第二题算法并实现：//折半查找算法使之能够进行范围查找#include<iostream>usingnamespacestd;//折半进行范围查找函数：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<<"请输入数组元素："<<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.求两个正整数m和n的最小公倍数。〔提示：m和n的最小公倍数lcm<m,n>与m和n的最大公约数gcd<m,n>之间有如下关系：lcm<m,n>=m×n/gcd<m,n>//求两个数的最小公倍数#include<iostream>usingnamespacestd;intmain<void>{inta,b;inti=1;cin>>a>>b;while<<i%a!=0>||<i%b!=0>> ++i;cout<<"a,b最小公倍数为："<<i<<endl;return0;}<该算法比较直接,要使其改进,可用欧几里得算法求得两个数的最大公约数,然后套用上面的公式再求最小公倍数>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]>//根结点已经大于左右孩子中的较大者break; else{ temp=r[i];r[i]=r[j];r[j]=temp;//将被筛结点与结点j交换 i=j;j=2*i+1;//被筛结点位于原来结点j的位置 }}}进行调堆！6.设计算法实现在大根堆中删除一个元素,要求算法的时间复杂性为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]>//根结点已经大于左右孩子中的较大者break; else{ temp=r[i];r[i]=r[j];r[j]=temp;//将被筛结点与结点j交换 i=j;j=2*i+1;//被筛结点位于原来结点j的位置 }}}nm5065251301301226065203104010401208020803250图5.15俄式乘法+7.计算两个正整数n和m的乘积有一个很有名的算法称为俄式乘法,其思想是利用了一个规模是n的解和一个规模是n/2的解之间的关系：n×m＝n/2×2m〔当n是偶数或：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是偶数{n=n*2;m=m/2;}else//如果n是奇数{n=n*2;sum+=temp;m=<m-1>/2;}temp=n;//记录倒数第二个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…….都是必输状态；所有每次把对手逼到15、20、25…….等必输状态,就可以获胜。9.竞赛树是一棵完全二叉树,它反映了一系列"淘汰赛"的结果：叶子代表参加比赛的n个选手,每个内部结点代表由该结点的孩子结点所代表的选手中的胜者,显然,树的根结点就代表了淘汰赛的冠军。请回答下列问题：〔1这一系列的淘汰赛中比赛的总场数是多少？〔2设计一个高效的算法,它能够利用比赛中产生的信息确定亚军。〔1因为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动态规划法为什么都需要填表？如何设计表格的结构？在填写表格过程中,不仅可以使问题更加清晰,更重要的是可以确定问题的存储结构；设计表格,以自底向上的方式计算各个子问题的解并填表。2.对于图6.26所示多段图,用动态规划法求从顶点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．用动态规划法求如下0/1背包问题的最优解：有5个物品,其重量分别为<3,2,1,4,5>,价值分别为<25,20,15,40,50>,背包容量为6。写出求解过程。<x1,x2,x3,x4,x5>→<1,1,1,0,0><过程略>4.用动态规划法求两个字符串A="xzyzzyx"和B="zxyyzxz"的最长公共子序列。写出求解过程。略5.给定模式"grammer"和