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

习题1

1.

图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler，1707—1783）提出并解决了该问题。七桥问题是这样描述的：北区 一个人是否能在一次步行中穿越哥尼斯堡（现

东区 在叫加里宁格勒，在波罗的海南岸）城中全部岛区 的七座桥后回到起点，且每座桥只经过一次，

南区 图1.7是这条河以及河上的两个岛和七座桥的

图1.7 七桥问题

草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。

七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行

2， 经过七座桥，且每次只经历过一次 3， 回到起点

该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。

2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n

2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m

3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。

//采用分治法

//对数组先进行快速排序 //在依次比较相邻的差 #include using namespace std;

int partions(int b[],int low,int high) {

int prvotkey=b[low]; b[0]=b[low]; while (low

while (low=prvotkey) --high;

b[low]=b[high];

while (low

b[high]=b[low]; }

b[low]=b[0]; return low; }

void qsort(int l[],int low,int high) {

int prvotloc; if(low

prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); //递归调用排序 由low 到prvotloc-1 qsort(l,prvotloc+1,high); //递归调用排序 由 prvotloc+1到 high } }

void quicksort(int l[],int n) {

qsort(l,1,n); //第一个作为枢轴 ，从第一个排到第n个 }

int main() {

int a[11]={0,2,32,43,23,45,36,57,14,27,39}; int value=0;//将最小差的值赋值给value for (int b=1;b<11;b++) cout<

quicksort(a,11);

for(int i=0;i!=9;++i)

{

if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) ) value=a[i+1]-a[i]; else

value=a[i+2]-a[i+1]; }

cout<

return 0; }

4． 设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述。

#include using namespace std;

int main() { int a[]={1,2,3,6,4,9,0};

int mid_value=0;//将“既不是最大也不是最小的元素”的值赋值给它 for(int i=0;i!=4;++i) { if(a[i+1]>a[i]&&a[i+1]a[i+2]) { mid_value=a[i+1]; cout<

5. 编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。

#include using namespace std;

int main() {

double value=0;

for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value 13==0) { cout<<\至少为:\ break; } }//for

return 0; }

6. 计算π值的问题能精确求解吗？编写程序，求解满足给定精度要求的π值

#include using namespace std;

int main () {

double a,b;

double arctan(double x);//声明 a = 16.0*arctan(1/5.0); b = 4.0*arctan(1/239);

cout << \

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需要叠加的方程

r = (i%4==1)?r+f:r-f;

e = e*sqr;//e每次乘于x的平方 i+=2;//i每次加2 }//while return r; }

7. 圣经上说：神6天创造天地万有，第7日安歇。为什么是6天呢？任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此6是完美数。神6天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数

#include using namespace std;

int main() {

int value, k=1; cin>>value;

for (int i = 2;i!=value;++i) {

while (value % i == 0 ) {

k+=i;//k为该自然数所有因子之和 value = value/ i; }

}//for

if(k==value)

cout<<\该自然数是完美数\ else

cout<<\该自然数不是完美数\ return 0; }

8. 有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间？

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的位置 }

} }

7. 计算两个正整数n和m的乘积有一个很有名的算法称为俄式乘法，其思想是利用了一个规模是n的解和一个规模是n/2的解之间的关系：n×m＝n/2×2m（当n是偶数）或：n×m＝(n-1)/2×2m＋m（当n是奇数），并以1×m＝m作为算法结束的条件。例如，图5.15给出了利用俄式乘法计算50×65的例子。据说十九世纪的俄国农夫使用该算法并因此得名，这个算法也使得乘法的硬件实现速度非常快，因为只使用移位就可以完成二进制数的折半和加倍。请设计算法实现俄式乘法。

//俄式乘法

#include using namespace std;

int fun(int m,int n) {

int sum=0; int temp=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;

n m 50 65 25 130 130 12 260 6 520 3 1040 1040 1 2080 + 2080 3250 图5.15 俄式乘法

}

temp=n;//记录倒数第二个n的值 }

return sum+n; }

int main() {

int a,b;

while(cin>>a>>b) {

cout<

8. 拿子游戏。考虑下面这个游戏：桌子上有一堆火柴，游戏开始时共有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不同，则B有假币；如果A,B相同，则C有假币；

习题6

1. 动态规划法为什么都需要填表？如何设计表格的结构？

在填写表格过程中，不仅可以使问题更加清晰，更重要的是可以确定问题的存储结构； 设计表格，以自底向上的方式计算各个子问题的解并填表。

2. 对于图6.26所示多段图，用动态规划法求从顶点0到顶点12的最短路径，写出求解过程。 1 6 3 8 1 7 3 3 3 5 6 5 10 4 4 5 5 8 2 0 12 3

5 3 8 3 11 3 7 9 8 2 6 6 6 4 图6.26 第2题图

将该多段图分为四段；

首先求解初始子问题，可直接获得： 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→12 3．用动态规划法求如下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. 给定模式\和文本\，写出动态规划法求解K-近似匹配的过程。 略

6. 对于最优二叉查找树的动态规划算法，设计一个线性时间算法，从二维表R中生成最优二叉查找树。

7. Ackermann函数A(m, n)的递归定义如下：

n?1??A(m,n)??A(m?1,1)?A(m?1,A(m,n?1))?m?0m?0,n?0 m?0,n?0设计动态规划算法计算A(m, n)，要求算法的空间复杂性为O(m)。

//求ackman函数 //使用栈

#include using namespace std;

long ackman(long m, long n) {

long stack[10000]; int pos=1;

stack[0]=m;stack[1]=n; while(pos) {

n=stack[pos--]; m=stack[pos]; if(m==0)

stack[pos]=n+1; if(m!=0&&n==0) {

stack[pos++]=m-1; stack[pos]=1; }

if(m!=0&&n!=0) {

stack[pos++]=m-1; stack[pos++]=m; stack[pos]=n-1; } }

return stack[0]; }

int main(int argc, char *argv[]) {

long m,n; cin>>m>>n;

cout<

return 0; }

8. 考虑下面的货币兑付问题：在面值为(v1, v2, ?, vn)的n种货币中，需要支付y值的货币，应如何支付才能使货币支付的张数最少，即满足

nn?xvi?1ii?y，且使?xi最小（xi是

i?1非负整数）。设计动态规划算法求解货币兑付问题，并分析时间性能和空间性能。

#include #define N 100000 #define M 20

int a[N][M]; int value[M];

using namespace std;

int main() {

while(true) {

int i,j,k; int x,y,z;

cout<<\输入货币种类的个数：\ cin>>x;

cout<<\从小到大输入货币的价值，其中第一个必须为一：\ for(i=1;i<=x;i++)//x为货币种类的个数 {

cout<<\ cin>>y; value[i]=y; }

cout<<\输入要兑换的钱的价值：\ cin>>z;//z为钱 for(j=0;j<=z;j++) a[j][0]=0;

for(k=0;k<=x;k++) a[0][k]=0; for(i=1;i<=z;i++) {

for(j=1;j<=x;j++) {

if(value[j]==i) a[i][j]=1; else if(value[j]>i) a[i][j]=a[i][j-1]; else

a[i][j]=a[i-value[j]][j]+1;//相当于把乘法换成加法，即碰到一个钱数于

兑换货币自身价值时，返回到

钱数减去该货币值的地方，其值再加1// }//for }

cout<<\兑换的最小货币个数是：\

}//while

return 0; }

for(k=0;k<=x;k++) a[0][k]=0; for(i=1;i<=z;i++) {

for(j=1;j<=x;j++) {

if(value[j]==i) a[i][j]=1; else if(value[j]>i) a[i][j]=a[i][j-1]; else

a[i][j]=a[i-value[j]][j]+1;//相当于把乘法换成加法，即碰到一个钱数于

兑换货币自身价值时，返回到

钱数减去该货币值的地方，其值再加1// }//for }

cout<<\兑换的最小货币个数是：\

}//while

return 0; }

本文来源：https://www.bwwdw.com/article/ci07.html