算法设计与分析习题答案6章.docx
《算法设计与分析习题答案6章.docx》由会员分享,可在线阅读,更多相关《算法设计与分析习题答案6章.docx(19页珍藏版)》请在冰点文库上搜索。
![算法设计与分析习题答案6章.docx](https://file1.bingdoc.com/fileroot1/2023-5/20/c90fd2a6-afbc-454b-b7ab-9d645e468a68/c90fd2a6-afbc-454b-b7ab-9d645e468a681.gif)
算法设计与分析习题答案6章
习题1
(LeonhardEuler,1707—1783)
1.图论诞生于七桥问题。
出生于瑞士的伟大数学家欧拉
提出并解决了该问题。
七桥问题是这样描述的:
一个人是否能在一次步行中穿越哥尼斯堡(现在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经过一次,图是这条河以及河上的两个岛和七座桥的草图。
请将该问题的数据模型抽象出来,并判断此问题是否有解。
七桥问题属于一笔画问题。
输入:
一个起点
输出:
相同的点
1,一次步行
2,经过七座桥,且每次只经历过一次
3,回到起点
该问题无解:
能一笔画的图形只有两类:
一类是所有的点都是偶点。
另一类是只有二个奇点的图形。
2•在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减
法。
请用伪代码描述这个版本的欧几里德算法
=m-n
2.循环直到r=0
m=n
n=r
r=m-n
3输出m
3•设计算法求数组中相差最小的两个元素(称为最接近数)的差。
要求分别给出伪代码和C++描述。
编写程序,求n至少为多大时,n个"1”组成的整数能被2013整除。
#includeusingnamespacestd;
intmain()
{
doublevalue=0;
for(intn=1;n<=10000;++n)
{value=value*10+1;
if(value%2013==0)
{
cout<<"n至少为:
"<}
}计算n值的问题能精确求解吗编写程序,求解满足给定精度要求的n值
#includeusingnamespacestd;
intmain()
{
doublea,b;
doublearctan(doublex);圣经上说:
神6天创造天地万有,第7日安歇。
为什么是6天呢任何一个自然数的因数中都有1和它本身,所有小于它本身的因数称为这个数的真因数,如果一个自然数的真因数之和等于它本身,这个自然数称为完美数。
例如,6=1+2+3,
因此6是完美数。
神6天创造世界,暗示着该创造是完美的。
设计算法,判断给定的自然数是否是完美数
#includeusingnamespacestd;
intmain()
{
intvalue,k=1;
cin>>value;
for(inti=2;i!
=value;++i)
{
while(value%i==0)
{
k+=i;有4个人打算过桥,这个桥每次最多只能有两个人同时通过。
他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们只有一只手电筒。
这就意味着两个人过桥后必须有一个人将手电筒带回来。
每个人走路的速度是不同的:
甲过桥要用1分钟,乙过桥要用2分钟,丙过桥要用5分钟,丁过桥要用10分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥最少要用多长时间由于甲过桥时间最短,那么每次传递手电的工作应有甲完成
甲每次分别带着乙丙丁过桥
例如:
第一趟:
甲,乙过桥且甲回来
第二趟:
甲,丙过桥且甲回来
第一趟:
甲,丁过桥一共用时19小时
9•欧几里德游戏:
开始的时候,白板上有两个不相等的正整数,两个玩家交替行动,每次行动时,当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差,而且这个数字必须是新的,也就是说,和白板上的任何一个已有的数字都不相同,当一方再也写不出新数字时,他就输了。
请问,你是选择先行动还是后行动为什么
设最初两个数较大的为a,较小的为b,两个数的最大公约数为factor。
则最终能出现的数包括:
factor,factor*2,factor*3,…,factor*(a/factor)=a.—共
a/factor个。
如果a/factor是奇数,就选择先行动;否则就后行动。
习题2
1.如果Ti(n)=Qf(n)),T2(n)=Qg(n)),解答下列问题:
(1)证明加法定理:
「(n)+T2(n)=max{Qf(n)),Qg(n))};
(2)证明乘法定理:
T1(n)xT2(n)=Qf(n))xQg(n));
(3)举例说明在什么情况下应用加法定理和乘法定理
|
(1)
(2)
(3)比如在
for(f(n))
{
for(g(n))
}
中应该用乘法定理
如果在“讲两个数组合并成一个数组时”,应当用加法定理
2•考虑下面的算法,回答下列问题:
算法完成什么功能算法的基本语句是什么基本语句
(1)
for(i=1;i
<=n;i++)
(2)
m=0;
if(2*i<=n)
for(i=
1;i<=n;i++)
for(j:
=2*i;j<=n;
for(j=
=1;j<=2*i;
j++)
j++)
3.分析以下程序段中基本语句的执行次数是多少,要求列出计算公式。
(1)基本语句2*i基本语句y=y+i*j执行了2/n次一共执行次数=n/2+n/2=O(n)
(2)基本语句m+=1执行了(n/2)*n=0(n*n)
4.使用扩展递归技术求解下列递推关系式:
(1)intT(intn)
{
if(n==1)
return4;
elseif(n>1)return3*T(n-1);}
⑵
intT(intn)
{
if(n==1)
return1;
elseif(n>1)return2*T(n/3)+n;}
5.求下列问题的平凡下界,并指出其下界是否紧密。
(1)求数组中的最大元素;
(2)判断邻接矩阵表示的无向图是不是完全图;
(3)确定数组中的元素是否都是惟一的;
(4)生成一个具有n个元素集合的所有子集
⑶Q(logn+n)(先进行快排,然后进行比较查找)
⑷Q(2An)
&国际象棋是很久以前由一个印度人Shashi发明的,当他把该发明献给国王时,国
王很高兴,就许诺可以给这个发明人任何他想要的奖赏。
Shashi要求以这种方式给他一些
粮食:
棋盘的第1个方格内只放1粒麦粒,第2格2粒,第3格4粒,第4格8粒,••…以此类推,直到64个方格全部放满。
这个奖赏的最终结果会是什么样呢
#includeusingnamespacestd;
intmain()
{
longdoubleresult=1;doublej=1;
for(inti=1;i<=64;++i){j=j*2;result+=j;
j++;
}cout<return0;
习题3
1.假设在文本"ababcabccabccacbab"中查找模式"abccac",写出分别采用BF算法和KMP
算法的串匹配过
式化简。
设计算法,将一个给定的真分数化简为最简分数形式。
例如,将6/8化简为3/4。
#include
usingnamespacestd;
intmain()
{
intn;数字游戏。
把数字1,2,…,9这9个数字填入以下含有加、减、乘、除的四则运算式中,使得该等式成立。
要求9个数字均出现一次且仅出现一次,且数字1不能出现
在乘和除的一位数中(即排除运算式中一位数为1的平凡情形)。
x+--=0
5.设计算法求解anmodm其中a、n和m均为大于1的整数。
(提示:
为了避免an超出int型的表示范围,应该每做一次乘法之后对n取模)
#includeusingnamespacestd;
intsquare(intx)
{
returnx*x;
设计算法,在数组r[n]中删除所有元素值为x的元素,要求时间复杂性为O(n),空间复杂性为O
(1)。
7.设计算法,在数组r[n]中删除重复的元素,要求移动元素的次数较少并使剩余元素间的相对次序保持不变。
#includeusingnamespacestd;
voiddeletere(inta[],intN)
{
intb[100]={0};
inti,k;
k=0;
staticintj=0;
for(i=0;ib[a[i]]++;
for(i=0;i<100;i++)
{
if(b[i]!
=0)
{
if(b[i]==2)
{k++;
}
a[j]=i;j++;
}
}
for(i=0;i}intmain()
{
inta[]={1,2,1,3,2,4};deletere(a,6);
return0;
}
设表A={ai,a2,…,an},将A拆成B和C两个表,使A中值大于等于0的元素存入表
B,值小于0的元素存入表C要求表B和C不另外设置存储空间而利用表A的空间。
荷兰国旗问题。
要求重新排列一个由字符R,VVB(R代表红色,W代表白色,B代表兰色,这都是荷兰国旗的颜色)构成的数组,使得所有的R都排在最前面,W排在其次,B
排在最后。
为荷兰国旗问题设计一个算法,其时间性能是O(n)。
设最近对问题以k维空间的形式出现,k维空间的两个点pi=(xi,X2,…,Xk)和p2=(yi,
y2,…,yk)的欧几里德距离定义为:
k
d(Pi,P2)(yi-xj2。
对k维空间的最近对问题设
'Vi111
计蛮力算法,并分析其时间性能。
(1)x+yw4;
(2)
11•设计蛮力算法求解小规模的线性规划问题。
假设约束条件为:
x+3y<6;(3)x>0且y》0;使目标函数3x+5y取得极大值。
#include
usingnamespacestd;
intmain()
{
intx,y,x0,y0;
intsummax=0,temp=0;
for(x0=0;x0<=4;++x0)
{
for(y0=0;(x0+y0<=4)&&(x0+3*y0<=6);++y0)
temp=3*x0+5*y0;
if(temp>=summax)
{summax=temp;
x=x0;变位词。
给定两个单词,判断这两个单词是否是变位词。
如果两个单
词的字母完全相同,只是位置有所不同,则这两个单词称为变位词。
例如,eat和tea是变
位词。
分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关,试说明这几个参数与分治法时间复杂性之间的关系。
2.证明:
如果分治法的合并可以在线性时间内完成,则当子问题的规模之和小于原问题的规模时,算法的时间复杂性可达到C(n)。
O(N)=2*O(N/2)+x
O(N)+x=2*O(N/2)+2*x
a*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);设计分治算法求一个数组中的最大元素,并分析时间性能。
设计分治算法,实现将数组A[n]中所有元素循环左移k个位置,要求时间复杂性为
O(n),空间复杂性为O
(1)。
例如,对abcdefgh循环左移3位得到defghabc。
设计递归算法生成n个元素的所有排列对象。
#include
usingnamespacestd;
intdata[100];
设计分治算法求解一维空间上n个点的最近对问题。
参见最近对问题的算法分析及算法实现
9.在有序序列(ri,「2,…,rn)中,存在序号i(1
请设计一个分治算法找到这个元素,要求算法在最坏情况下的时间性能为O(log2n)。
在一个序列中出现次数最多的元素称为众数。
请设计算法寻找众数并分析算法的时间复杂性。
设M是一个nxn的整数矩阵,其中每一行(从左到右)和每一列(从上到下)的元素都按升序排列。
设计分治算法确定一个给定的整数x是否在M中,并分析算法的时间复
杂性。
12.设S是n(n为偶数)个不等的正整数的集合,要求将集合S划分为子集Si和虫
使得ISi|=|S2|=n/2,且两个子集元素之和的差达到最大。
设ai,比,…,an是集合{1,2,…,n}的一个排列,如果iaj,则序偶(ai,aQ
称为该排列的一个逆序。
例如,2,3,1有两个逆序:
(3,1)和(2,1)。
设计算法统计给定排列中含有逆序的个数。
循环赛日程安排问题。
设有n=2k个选手要进行网球循环赛,要求设计一个满足以下要求
的比赛日程表:
(1)每个选手必须与其他n-1个选手各赛一次;
(2)每个选手一天只能赛一次。
采用分治方法。
将2Ak选手分为2Ak-1两组,采用递归方法,继续进行分组,直到只剩下2个选手时,然
后进行比赛,回溯就可以指定比赛日程表了
15.格雷码是一个长度为2n的序列,序列中无相同元素,且每个元素都是长度为n的
二进制位串,相邻元素恰好只有1位不同。
例如长度为23的格雷码为(000,001,011,010,110,111,101,100)。
设计分治算法对任意的n值构造相应的格雷码。
矩阵乘法。
两个nxn的矩阵X和Y的乘积得到另外一个nxn的矩阵Z,且Zj
3
满足(1
可以用分
治法解决矩阵乘法问题,将矩阵X和Y都划分成四个n/2xn/2的子块,从而X和Y的乘积
可以用这些子块进行表达,即
从而得到分治算法:
先递归地计算8个规模为n/2的矩阵乘积AE、BG、AF、BH、CE、DG、
CFDH然后再花费Qn2)的时间完成加法运算即可。
请设计分治算法实现矩阵乘法,并分析时间性能。
能否再改进这个分治算法
习题5
1.下面这个折半查找算法正确吗如果正确,请给出算法的正确性证明,如果不正确,请说明产生错误的原因。
intBinSearch(intr[],intn,intk)
{
intlow=0,high=n-1;
intmid;
while(low<=high)
{
mid=(low+high)/2;
if(kelseif(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(kelseif(k>r[mid])low=mid+1;
elsereturnmid;
}
return0;
}
2.请写出折半查找的递归算法,并分析时间性能。
求两个正整数m和n的最小公倍数。
(提示:
m和n的最小公倍数lcm(mn)与m和n的最大公约数gcd(mn)之间有如下关系:
lcm(mn)=mxn/gcd(mn))
插入法调整堆。
已知(ki,k2,…,kn)是堆,设计算法将(ki,k2,…,kn,kn+1)调
整为堆(假设调整为大根堆)。
参照:
voidSiftHeap(intr[],intk,intn)
{
设计算法实现在大根堆中删除一个元
inti,j,temp;
i=k;j=2*i+1;
素,要求算法的时间复杂性为Olog2n)。
50
65
25
130
130
12
260
6
520
3
1040
1040
1
2080
2080
nm
3250
图俄式乘法
计算两个正整数n和m的乘积有一个很有名的算法称
为俄式乘法,其思想是利用了一个规模是n的解和一个规
模是n/2的解之间的关系:
nxm=n/2x2m(当n是偶数)或:
nxm=(n-1)/2x2m^m(当n是奇数),并以1xm=m作为算法结束的条件。
例如,图给出了利用俄式乘法计算50x65的例子。
据说十九世纪的俄国农夫使用该算法并因此得名,这个算法也使得乘法的硬件实现速度非常快,因为只使用移位就可以完成二进制数的折半和加倍。
请设计算法实现俄式乘法。
拿子游戏。
考虑下面这个游戏:
桌子上有一堆火柴,游戏开始时共有n根火柴,两个
玩家轮流拿走1,2,3或4根火柴,拿走最后一根火柴的玩家为获胜方。
请为先走的玩家设计一个制胜的策略(如果该策略存在)。
如果桌上有小于4根的火柴,先手必胜,如果是5根,先手必输;依次类推,同理15、
20、25…….都是必输状态;所有每次把对手逼到15、20、25…….等必输状态,就可以获
胜。
9.竞赛树是一棵完全二叉树,它反映了一系列“淘汰赛”的结果:
叶子代表参加比赛的n个选手,每个内部结点代表由该结点的孩子结点所代表的选手中的胜者,显然,树的根结点就代表了淘汰赛的冠军。
请回答下列问题:
(1)这一系列的淘汰赛中比赛的总场数是多少
(2)设计一个高效的算法,它能够利用比赛中产生的信息确定亚军。
(1)因为n人进行淘汰赛,要淘汰n-1人,所有要进行n-1场比赛。
(2)
10.在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不同,贝UB有假币;如果A,B相同,则C有假币;
习题6
1.动态规划法为什么都需要填表如何设计表格的结构
在填写表格过程中,不仅可以使问题更加清晰,更重要的是可以确定问题的存储结构;设计表格,以自底向上的方式计算各个子问题的解并填表。
将该多段图分为四段;
首先求解初始子问题,可直接获得:
d(0,1)=coi=5(0t1)
d(0,2)=5=3(0t1)
再求解下一个阶段的子问题,有:
d(0,3)=d(0,1)+C13=6(1t3)
最短路径为:
0t1t3t8t11T12
d(0,4)=min{d(0,1)+c14,d(0,2)+c24}=8(1t4)
0000000
。
(以此类推)
3•用动态规划法求如下0/1背包问题的最优解:
有5个物品,其重量分别为(3,2,1,
4,5),价值分别为(25,20,15,40,50),背包容量为6。
写出求解过程。
(x1,x2,x3,x4,x5)t(1,1,1,0,0)(过程略)
4.用动态规划法求两个字符串A="xzyzzyx"和B="zxyyzxz"的最长公共子序列。
写出
求解过程。
略
5.给定模式"grammer"和文本"grameer",写出动态规划法求解K-近似匹配的过程。
略
6.对于最优二叉查找树的动态规划算法,设计一个线性时间算法,从二维表R中生成
最优二叉查找树。
7.Ackermann函数A(m,n)的递归定义如下:
n1m0
A(m,n)A(m1,1)m0,n0
A(m1,A(m,n1))m0,n0
设计动态规划算法计算A(m,n),要求算法的空间复杂性为O(m)。
考虑下面的货币兑付问题:
在面值为(Vi,V2,…,Vn)的n种货币中,需要支付y值的
nn货币,应如何支付才能使货币支付的张数最少,即满足xiViy,且使xi最小(xi是
i1i1
非负整数)。
设计动态规划算法求解货币兑付问题,并分析时间性能和空间性能。
#include
#defineN100000
#defineM20
inta[N][M];
intValue[M];
usingnamespacestd;
intmain()
{
while(true)
{
inti,j,k;
intx,y,z;
cout<<"输入货币种类的个数:
"<cin>>x;
cout<<"从小到大输入货币的价值,其中第一个必须为一:
"<for(i=1;i<=x;i++)多边形游戏。
多边形游戏是一个单人玩的游戏,开始时有一
个由n个顶点构成的多边形,每个顶点具有一个整数值,每条边具有一个运算符“+”或“X”。
游戏规则是每次选择一条边e以及和e相关联的两个顶点i和j,用一个新的顶点k取代边
e、顶点i和j,顶点k的整数值是顶点i和j的整数值通过边e上的运算符计算得到的结果。
当所有边都删除时,游戏结束,游戏的得分就是所剩顶点的整数值。
设计动态规划算法,对于给定的多边形计算最高得分。
(1)Q(n)紧密
(2)Q(n*n)