算法部分作业答案.docx
《算法部分作业答案.docx》由会员分享，可在线阅读，更多相关《算法部分作业答案.docx（24页珍藏版）》请在冰点文库上搜索。
算法部分作业答案
算法部分作业答案（总18页）
算法：
是对特定问题求解步骤的一种描述，是指令的有限序列。
程序：
当一个算法用某种程序设计语言来描述时，得到的就是程序，也就是说,程序是用某种程序设计语言对算法的具体实现.
算法有输入、输出、确定性、能行性和有限性等特征，当不具备有穷性时，只能叫做计算过程，而不能称之为算法，算法可以终止，而程序没有此限制。
程序证明和程序测试的目的各是什么？
程序证明是确认一个算法能正确无误的工作.
程序测试的目的是发现错误
1-9解:
n!
的递归定义：
求解n!
的递归函数
longFactorial（longn）
{
if（n<0）
{
cout<<”error!
”;
exit（0）;
}
if（n==0）
return1;
elsereturnn*Factorial（n-1）;
}
1-10使用归纳法，证明上题所设计的计算n！
的递归函数的正确性
证明（归纳法证明）：
（1）首先，如果n=0，那么程序执行
if（n==0）
return1;
返回1,算法显然正确;
（2）假定函数Factorial对n1）能正确运行，那么，当n=k时，算法必定执行:
elsereturnk*Factorial（k-1）;
因为Factorial（k-1）正确，所以，当n=k时，程序运行正确
综合以上两点，可得程序正确.
证毕.
2-1,简述衡量一个算法的主要性能标准,说明算法的正确性与健壮性的关系
答:
衡量一个算法的主要性能指标有:
正确性，简单性，高效低存储，最优性
算法的正确性与健壮性的关系:
所谓算法的正确性:
是指在合法的输入下，算法应实现预先规定的功能和计算精度要求;所谓算法的健壮性，是指当输入不合法时，算法应该能按某种预定的方式做出适当的处理;
正确的算法不一定的是健壮的，健壮的算法也不一定是完全正确的.正确性和健壮性是相互补充的.一个可靠的算法，要求能在正常情况下正确的工作，而在异常情况下，亦能做出适当处理.
2-9
（1）设计一个C/C++程序，实现一个n*m的矩阵转置，原矩阵与其转置矩阵保存在二维数组中.
Voidreverse（int**a,int**b,intn,intm）
{
For（inti=0;iFor（intj=0;jb[j][i]=a[i][j];
}
（2）使用全局变量count,改写矩阵转置程序，并运行修改后的程序以确定此程序所需的程序步
Voidreverse（int**a,int**b,intn,intm,int&count）
{
inti=0;
count++;
intj=0;
count++;
For（;iFor（;j{
count++;
b[j][i]=a[i][j];
count++;
}
}
2-10试用定义证明下列等式的正确性
（1）5n2-8n+2=O（n2）
证明:
因为当n0=1,C=6时,当n>n0时，有5n2-8n+2<=6n2
2-16使用递推关系式计算求n!
的递归函数的时间（即分析1-9题中的函数的时间复杂度）,要求使用替换和迭代两种方法分别计算之.
解:
分析1-9题中的函数的时间复杂度:
用基本运算乘法的运算次数作为衡量时间复杂度的量
当n=0时，程序执行if（n==0）return1;,并没有做乘法，故T（0）=0;当n>=1时程序执行n*Factorial（n-1）;此时T（n）=T（n-1）+1故:
替换法:
T（0）=0,T
（1）=1,T
（2）=2-----
总结得到:
T（n）=n;
归纳法证明:
（1）,当n=0时,T（0）=0,结论成立;
（2）假设当k所以，对所有n>=0有T（n）=n;成立.
迭代法:
T（n）=T（n-1）+1
=（T（n-2）+1）+1=（（T（n-3）+1）+1）+1=....=T（0）+1+1......+1（n个1）=n
2-19利用递归树计算递推方程
假设n=2k,那么,总共有logn+1（即k+1）层,非递归部分之和为
n2+n2/21+n2/22+…+n2/2k=（1+1/2+1/22+1/23+…+1/2logn）n2
=2n2+2n=O（n2）
5-8三分搜索算法的做法是:
它先将待查元素X与n/3处的元素比较，然后将X与2n/3处的元素比较,比较的结果或者找到X,或者将范围缩小到原来的n/3
intSearch3（inta[],intleft,intright,intx）/*递归算法*/
{
intl,u;
if（left<=right）
{
l=left+（right-left）/3;
u=left+（right-left）*2/3;
if（x==a[u]）
returnu;
elseif（x==a[l]）
returnl;
elseif（x>a[u]）
returnSearch3（a,u+1,right,x）;
elseif（x>a[l]）
returnSearch3（a,l+1,u-1,x）;
else
returnSearch3（a,left,l-1,x）;
}
return-1;
}
voidmain（）
{
intn,*a;
intx,i;
cout<<"Pleaseinputn:
";
cin>>n;
（1）a=newint[n];假设当n=2）时，算法正确，即对于所有元素个数小于n的元素集,算法能正确排序.
那么,当n=right-left+1时，算法执行程序段:
intk=（right-left+1）/3;
stoogesort（a,left,right-k）;
stoogesort（a,left+k,right）;
stoogesort（a,left,right-k）;
由假设可知:
以上三条语句都能正确运行，所以，当n=right-left+1时,算法正确.
由以上两点可知，算法正确.
分析算法的时间复杂度:
排序算法，基本运算仍然是元素之间的比较,所以，算法时间复杂度为:
（用替换或迭代法计算之即可）
6-1设有背包问题实例，n=7，（w0,w1,w2,w3,w4,w5,w6）=（2,3,5,7,1,4,1），（p0,p1,p2,p3,p4,p5,p6）=（10,5,15,7,6,18,3），M=15。
求这一实例的最优解及最大收益.
解:
首先，选择最优量度标准为收益重量比;
其次,依据收益重量比的非增次序对输入（物品）进行排序
（p0/w0,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6）=（5,5/3,3,1,6,,3）
对物品排序结果为:
4,0,5,2,6,1,3
最后，进行贪心选择:
X=（4）X=（4,0）X=（4,0,5）
（剩余载重）U=14U=12U=8
（收益）P=6P=6+10=16P=16+18=34
X=（4,0,5,2）X=（4,0,5,2,6）X=（4,0,5,2,6,1（2/3））
（剩余载重）U=3U=2U=0
（收益）P=34+15=49P=49+3=52P=52+2/3*5=
所以,最优解为x=（1,2/3,1,0,1,1,1）;即装入第0,2,4,5,6物品和第1个物品的2/3
最大收益:
P=
6-2,0/1背包问题是一种特殊的背包问题，装入背包的物品不能分割,只允许或者整个物品装入背包，或者不装入，即xi=0,或1,（0<=i解:
首先，选择最优量度标准为收益重量比;
其次,依据收益重量比的非增次序对输入（物品）进行排序
（p0/w0,p1/w1,p2/w2,p3/w3,p4/w4,p5/w5,p6/w6）=（5,5/3,3,1,6,,3）
对物品排序结果为:
4,0,5,2,6,1,3
最后，进行贪心选择:
X=（4）X=（4,0）X=（4,0,5）
（剩余载重）U=14U=12U=8
（收益）P=6P=6+10=16P=16+18=34
X=（4,0,5,2）X=（4,0,5,2,6）X=（4,0,5,2,6）
（剩余载重）U=3U=2继续考察第1和第3个
（收益）P=34+15=49P=49+3=52物品,都不能装入.
所以,贪心法求得的0/1背包问题的最优解为x=（1,0,1,0,1,1,1）;即装入第0,2,4,5,6物品
最大收益:
P=52
但实际上，当y=（1,1,1,0,1,1,0）即装入第0,1,2,4,5物品,可获收益为P=54,所以，贪心法求得的0/1背包问题的解x一定不是最优解.
原因是:
对于0/1背包问题，贪心法并不能保证使其单位载重下的收益最大，因为通常在背包没还装满时，却再也装不下任何物品，这样，就使得单位载重下的物品收益减少,所以，0/1背包问题通常不能用贪心法求解.
6-3设有带时限的作业排序实例n=7，收益（p0,p1,p2,p3,p4,p5,p6）=（3,5,20,18,1,6,30），作业的时限（d0,d1,d2,d3,d4,d5,d6）=（1,3,4,3,2,1,2）,给出以此实例为输入，执行函数JS得到的用最优解和最大收益。
解:
X={5,6,3,2}最大收益为74
函数JS如下:
intJS（int*d,int*x,intn）
{
X:
6
X:
0123456
首先,考虑作业6,假设将其加入集合X,即x[0]=6;
考虑X中的作业能否均如期完成,因为此时X中只有作业6,其截止时限为2,故,能如期完成,此时,将作业6加入作业子集X中,此时，子集X中的最大可用下标k=0;
X:
6
接着，考虑作业2.
首先搜索作业2在X集合中的插入位置，使得X集合中的元素按作业的截止时限的非减次序排序,因为d6=2,而d2=4,所以，可将作业2插在作业6的后面，即x[1]=2,得到X=（6,2）,
X:
6
2
考虑X中的作业能否均如期完成?
因为d6=2>=1,d2=4>=2,所以，X中作业均能如期完成，将作业2加入子集X中.子集X中的最大可用下标k=k+1=1
X:
6
2
考虑作业3.
首先搜索作业3在X集合中的插入位置，使得X集合中的元素按作业的截止时限的非减次序排序,因为d6=2,d2=4,而d3=3所以，可将作业3插在作业6的后面,作业2的前面，得到X=（6,3,2）,
X:
6
3
2
0123456
k
考虑X中的作业能否均如期完成?
因为d6=2>=1,d3=3>=2,d2=4>=3所以，X中作业均能如期完成，将作业2加入子集X中.子集X中的最大可用下标k=k+1=2
X:
6
3
2
考虑作业5.
首先搜索作业5在X集合中的插入位置，使得X集合中的元素按作业的截止时限的非减次序排序,因为d6=2,d2=4,d3=3而d5=1所以，可将作业5插在作业6的前面,得到X=（5,6,3,2）,
X:
5
6
3
2
考虑X中的作业能否均如期完成?
因为d5=1>=1,d6=2>=2,d3=3>=3,d2=4>=4所以，X中作业均能如期完成，将作业5加入子集X中.子集X中的最大可用下标k=k+1=3
X:
5
6
3
2
考虑作业1.
首先搜索作业1在X集合中的插入位置，使得X集合中的元素按作业的截止时限的非减次序排序,因为d5=1,d6=2,d3=3,d2=4,而d1=3所以，可将作业1插在作业2的前面,作业3的后面,得到X=（5,6,3,1,2）,
X:
5
6
3
1
2
考虑X中的作业能否均如期完成?
因为d5=1>=1,d6=2>=2,d3=3>=3,d1=3<4所以，X中1作业不能如期完成，所以，不能将作业1加入子集X.
X:
5
6
3
2
接着考虑作业0,4均不能加入子集X,
故，执行JS得到的最优解为X=（5,6,3,2）,最大收益为P=p5+p6+p3+p2=30+20+18+6=74
6-17,最佳装载问题是将一批集装箱装上一艘载重为C的轮船，其中集装箱i的重量为wi（0<=i<=n-1）,最优装载问题是指在装载体积不受限制的情况下,求使得装箱数目最多的装载方案.
（1）按贪心策略的要求,给出关于上述最优化问题的形式化描述.
（2）给出贪心法求解这一问题的最优量度标准;
（3）讨论其最优解的最优子结构.
（4）编写装箱问题的贪心算法;
（5）设有重量为（4,6,3,5,7,2,9）的7个集装箱，轮船载重为26,求最优解.
解;
（1）,形式化描述如下：
给定C>0,wi>0
求X=（
）使得
并且使
最大
（2）以重量作为最优量度标准，以重量最轻者先装来选择集装箱装上船
（3）设（x0,x1,----xn-1）是最优装载问题的最优解，则易知（x1,x2,----xn-1）是轮船载重为C-x0w0且待装船的集装箱为{1，3----n-1}时相应最优装载问题的一个最优解，即最优装载问题具有最优子结构特性。
否则，假设（x1,x2,----xn-1）不是子问题的最优解，假设有另一个解Z=（z1,z2,----zn-1）是子问题的最优解，则有：
则：
且
，即（x0，z1,z2,--zn-1）是最优装载问题的最优解,与（x0,x1,----xn-1）是最优装载问题的最优解矛盾，所以,（x1,x2,----xn-1）是子问题的最优解,故最优装载问题具有最优子结构特性。
（4）参考程序1
/*箱子信息结构体*/
structgoodinfo
{
floatw;/*箱子重量*/
intX;/*箱子存放的状态*/
intflag;/*箱子编号*/
};
/*按物品重量做升序排列*/
voidsort（goodinfogoods[],intn）
{
intj,i;
for（j=2;j<=n;j++）
{
goods[0]=goods[j];
i=j-1;
while（goods[0].w{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
}
/*用贪心法对物品进行选择装入*/
voidloading（goodinfogoods[],floatM,intn）
{
floatcu;
inti,j;
intA=0;/*对装入箱子进行计数*/
for（i=1;i<=n;i++）/*赋初值*/
goods[i].X=0;
cu=M;/*船的剩余载重*/
for（i=1;i{
if（goods[i].w>cu）/*当该箱重量大于剩余载重跳出*/
break;
goods[i].X=1;
A++;
cu=cu-goods[i].w;/*确定船的剩余载重*/
}
for（j=2;j<=n;j++）/*对箱子按序号大小作升序排列*/
{
goods[0]=goods[j];
i=j-1;
while（goods[0].flag{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
cout<<"①最优解为:
"<for（i=1;i<=n;i++）
{
cout<<"第"<";
cout<}
cout<<"<0：
未装入；1：
装入>"<cout<cout<<"②最多能装入的箱子数为:
";
cout<}
（5）
首先，选择最优量度标准为重量;
其次,依据集装箱重量的非减次序对输入（物品）进行排序
对集装箱的排序结果为:
5,2,0,3,1,4,6
最后，进行贪心选择:
X=（5）X=（5,2）X=（5,2,0）
（剩余载重）U=24U=21U=17
X=（5,2,0,3）X=（5,2,0,3,1）X=（5,2,0,3,1）
（剩余载重）U=12U=6
所以，最优解为X=（0,1,2,3,5）,最优解值为5
参考程序2
•publicstaticfloatloading（floatc,float[]w,int[]x）
•{
•intn=;
•Element[]d=newElement[n];
•for（inti=0;i•d[i]=newElement（w[i],i）;
•（d）;
•floatopt=0;
•for（inti=0;i•for（inti=0;i•x[d[i].i]=1;
•opt+=d[i].w;
•c-=d[i].w;
•}
•returnopt;
}
7-5设有4个矩阵连乘积ABCD：
A:
45*8,B:
8*40,C:
40*25,D:
25*10,,请求出它们的最优计算次序和计算量。
解：
p0=45，p1=8，p2=40，p3=25，p4=10
可只给出矩阵形式
计算m矩阵为：
m[0][1]=p0*p1*p2=45*8*40=14400;
m[1][2]=p1*p2*p3=8*40*25=8000;
m[2][3]=p2*p3*p4=40*25*10=11250;
m[0][2]=m[0][0]+m[1][2]+p0*p1*p3=8000+45*8*25=8000+9000=17000
=m[0][1]+m[2][2]+p0*p2*p3=14400+45*40*25=14400+45000
m[1][3]=m[1][1]+m[2][3]+p1*p2*p4=11250+8*40*10=11250+3200
=m[1][2]+m[3][3]+p1*p3*p4=8000+8*25*10=10000
m[0][3]=m[0][0]+m[1][3]+p0*p1*p4=10000+45*8*10=10000+3600=13600
=m[0][1]+m[2][3]+p0*p2*p4=14400+11250+45*40*10=
=m[0][2]+m[3][3]+p0*p3*p4=17000+45*25*10=17000+11250=28250
这4个矩阵相乘需要的最小数量乘法的次数=13600
最优计算次序A（（BC）D）
7-9给定字符串A=“xzyzzyx”和B=“zxyyzxz”，使用LCS算法求最长公共子串，并给出一个最长公共子串。
提示：
从上到下，从左往右计算C矩阵，依据C矩阵，求得最长公共子序列
解：
计算求得C矩阵如下，
依矩阵C可求得两个最长公共子序列分别为xyzz和zyyx（求一个即可）
7-17设流水作业调度的实例为n=7，（a0,a1,a2,a3,a4,a5,a6）=（6,2,4,1,7,4,7）,（b0,b1,b2,b3,b4,b5,b6）=（3,9,3,8,1,5,6）.请使用流水作业调度的Johnson算法求使完成时间最小的最优调度,并求该最小完成时间。
提示：
依据调度规则，求得最优调度次序
解:
；令mi=min{ai，bi}0<=i<7
即得:
m0=b0=3,m1=a1=2,m2=b2=3,m3=a3=1,
m4=b4=1,m5=a5=4m6=b6=6
考虑mi,对其从小到大排序得（m3,m4,m1,m0,m2,m5,m6）
考虑mi序列（如果序列中下一个数mi是ai,则作业i放在最左的空位，否则，作业i放在最右的空位）得:
最优调度顺序（3,1,5,6,2,0,4）
依据最优调度在两台处理机上处理作业，最小完成时间:
36（画出如教材P170的图7-17的形式即可求得最小完成时间36）
8-2#include<>
#include<>
intcount=0;//记录可行解的个数
//先将书中的递归变为如下非递归函数，再在输出一个可行解之后，加上break;
intplace（intk,intxk,int*x）
{
for（intj=0;jif（x[j]==xk||abs（x[j]-xk）==abs（j-k））//相互冲突,return0;
return0;
return1;//互不冲突,return1
}
voidNQueens（intn,int*x）
{
intk=0;
x[k]=-1;
while（k>=0）
{
x[k]=x[k]+1;
while（x[k]place（k,x[k],x））//找安置第K个皇后的合法位置
x[k]=x[k]+1;
if（x[k]if（k==n-1）//找到一个可行解，输出
{
cout<<"Thesolutionis:
";
for（intj=0;jcout<cout<//break;//删除，则可输出所有可行解。
count++;
}
else//找到安
升级会员 