算法分析与设计重点课后习题答案

习题1

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

++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<

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]

{

mid_value=a[i+1];

cout<

break;

}

else if(a[i+1]a[i+2])

{

mid_value=a[i+1];

cout<

break;

}

}//for

return 0;

}

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%2013==0)

{

cout<<"n至少为:"<

break;

}

}//for

return 0;

}

习题2

2．考虑下面的算法，回答下列问题：算法完成什么功能？算法的基本语句是什么？基本

语句执行了多少次？算法的时间复杂性是多少？

（2）int Q(int n)

（1）int Stery(int n)

{ {

if (n == 1)

int S = 0;

for (int i = 1; i <= n; i++) return 1;

S = S + i * i; else

return S; return Q(n-1) + 2 * n - 1;

} }

（1） 完成的是1-n的平方和

基本语句：s+=i*i，执行了n次

时间复杂度O（n）

（2） （2）完成的是n的平方

基本语句：return Q(n-1) + 2 * n – 1，执行了n次

时间复杂度O（n）

3. 分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。

（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; j++) for (j = 1; j <= 2*i; j++)

y = y + i * j； m=m+1;

（1） 基本语句2*i

基本语句y = y + i * j执行了2/n次

一共执行次数=n/2+n/2=O（n）

（2） 基本语句m+=1执行了(n/2)*n=O(n*n)

4. 使用扩展递归技术求解下列递推关系式：

（1）

T(n)





4n1

（2）



3T(n1)n1

1n1



T(n)





2T(n3)nn1

(1) int T(int n)

{

if(n==1)

return 4;

else if(n>1)

return 3*T(n-1);

}

(2)

int T(int n)

{

if(n==1)

return 1;

else if(n>1)

return 2*T(n/3)+n;

}

习题3

6. 设计算法，在数组r[n]中删除所有元素值为x的元素，要求时间复杂性为O(n)，空间

复杂性为O(1)。

#include

using namespace std;

void deletere(int a[],int N)

{

int b[100]={0};

int i,k;

k=0;

static int j=0;

for(i=0;i

b[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

cout<

}

int main()

{

int a[]={1,2,1,3,2,4};

deletere(a,6);

return 0;

}

8. 设表A={a

1

, a

2

, …, a

n

}，将A拆成B和C两个表，使A中值大于等于0的元素存入

表B，值小于0的元素存入表C，要求表B和C不另外设置存储空间而利用表A的空间。

//先对A进行快排

//将大于0的元素给B，小于0的元素给C

#include

using namespace std;

int partions(int l[],int low,int high)

{

int prvotkey=l[low];

l[0]=l[low];

while (low

{

while (low=prvotkey)

--high;

l[low]=l[high];

while (low

++low;

l[high]=l[low];

}

l[low]=l[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]={-2,2,32,43,-23,45,36,-57,14,27,-39};

quicksort(a,11);

for(int i=1;i<11;i++)

{

if(a[i]<0)

cout<<"C: "<

else

cout<<"B: "<

}

cout<

return 0;

}

习题4

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

using namespace std;

extern const int n=6;//声明

int main()

{

int a[n]={0,6,1,2,3,5};//初始化

int mid=n;

int num_max1=0,num_max2=0;

for(int i=0;i<=n;++i)//前半部分

{

if(a[i]>num_max1)

num_max1=a[i];

}

for(int j=n+1;j

{

if(a[j]>num_max2)

num_max2=a[j];

}

if(num_max1>=num_max2)

cout<<"数组中的最大元素： "<

else

cout<<"数组中的最大元素： "<

return 0;

}

时间复杂度：O（n）

9. 在有序序列(r

1

, r

2

, …, r

n

)中，存在序号i（1≤i≤n），使得r

i

=i。请设计一个分治算法

找到这个元素，要求算法在最坏情况下的时间性能为O(log

2

n)。

//在有序数组中

//采用二分法查找符合条件的元素

#include

using namespace std;

void Findnum(int *a,int n)

{

int low=0;

int high=n-1;

while(low<=high)

{

int mid=(low+high)/2;

if(a[mid]==mid)

{

cout<<"这个数是： "<

break;

}

else if(a[mid]>mid)

high=mid-1;

else

low=mid+1;

}

}

int main()

{

int a[7]={1,0,2,5,6,7,9};

Findnum(a,7);

return 0;

}

时间复杂度为O(log

2

n)。

10. 在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时

间复杂性。

//先对序列进行快速排序

//再进行一次遍历

//输出众数的重复次数

#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

++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[10]={1,2,3,5,3,3,3,2,5,1};

int i=0;

int count=0;

int max=0;//max表示出现的次数

qsort(a,0,10);

while(i<10)

{

int j;

j=i+1;

if(a[i]=a[j]&&i<10)

{

count++;

i++;

}

if(count>max)

{

max=count;

count=0;

}

}//while

cout<<"重复次数："<

return 0;

}

时间复杂度nlog(n)

习题5

2.请写出折半查找的递归算法，并分析时间性能。

//折半查找的递归实现

#include

using namespace std;

int digui_search(int a[],int low,int high,int x)

{

if (low > high)

return 0;

int mid = (low+high)/2;

if (a[mid] == x)

return mid;

else if (a[mid] < x)

digui_search(a,low,mid-1,x);

else

digui_search(a,mid+1,high,x);

}

int main()

{

int a[6]={0,1,2,9,5,3};

int result=digui_search(a,0,5,5);

cout<

return 0;

}

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)=c

01

＝5(0→1)

d(0, 2)=c

02

＝3(0→1)

再求解下一个阶段的子问题，有：

d(0,3)= d(0, 1)+ c

13

=6(1→3)

d(0,4)=min{d(0,1)+ c

14

,d(0,2)+ c

24

}=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"的最长公共子序列。写出求

解过程。

略