计算机算法设计与分析第四版课后答案

计算机算法设计与分析第四版课后答案【篇一：计算机算法分析与设计(第四版)习题算法分析

部分详解(实验六)】

//6-1、6-6项目vc++6.0测试通过

//6-15项目vc2005测试通过

//6-1 最小长度电路板排列问题

//头文件stdafx.h

// stdafx.h : include file for standard system include files,

// or project specific include files that are used frequently, but // are changed infrequently

//

#pragma once

#define win32_lean_and_mean // exclude rarely-used stuff from windows headers #include stdio.h

#include tchar.h

// todo: reference additional headers your program requires here

// sy61.cpp : defines the entry point for the console application.

//

//description:

//分支限界法 6_1 最小长度电路板排列问题

//#include my.h

#include stdafx.h

#include iostream

#include queue

using namespace std;

int n,m;

//#include outofbounds.h

//定义节点类

class boardnode{

friend int fifoboards(int **,int ,int,int *);//非类成员，可以访问私有成员的函数，最优序列查找

public:

operator int() const{return cd;}//返回常数 cd

int len();

public:

int *x,s,cd,*low,*high;//x表示当前节点的电路板排列，s表示当前节点排列好的电路板的数

//表示当前节点的最大长度，low，high分别表当前节点表示每一个连接块的第一个，和最后一个电路板

//的位置

};

//编写类的len()函数,求出当前节点的连接块长度的最大值

int boardnode::len()

{

int tmp=0;

for(int k=1;k=m;k++)

if(low[k]=n high[k]0 tmphigh[k]-low[k])

tmp=high[k]-low[k];

return tmp;

}

int fifioboards(int **b,int n,int m,int *bestx)//n为电路板的数量，m为连接块的数量 {

// int bestd;

queueboardnode q;//声明boardnode类的节点队列q

boardnode e;

e.x=new int[n+1];//为数组指针x分配n+1个动态空间，存储当前的排列

e.s=0;//最初时，排列好的电路板的数目为0

e.cd=0;

e.low=new int[m+1];//存储每个连接块的第一个电路板的位置

e.high=new int[m+1];//存储每个连接块的最后一个电路板的位置 for(int i=1;i=m;i++)

{

e.high[i]=0;//初始化开始时的每个连接块的最后一个电路板的位置为0，表示连接块i还没有电路板放入e.x的排列中

e.low[i]=n+1;//初始化开始时的每个连接块的第一个电路板的位置为n+1，表示连接块i还没有电路板放入e.x的排列中

}

for(i=1;i=n;i++)

e.x[i]=i;//初始化e.x的排列为1，2,3.....n

int bestd=n+1;//最优距离

bestx=0;//记录当前最优排列

do{

if(e.s==n-1)//当已排列了n-1个时

{

//判断是否改变每个连接块的最后一个电路板的位置

for(int j=1;j=m;j++)

if(b[e.x[n]][j] ne.high[j])

e.high[j]=n;

int ld=e.len();//存储当前节点的各连接块长度中的最大长度

//如果当前的最大长度小于了n+1

if(ldbestd)

{

delete[] bestx;

bestx=e.x;

bestd=ld;//最优距离

}

else delete[] e.x;//删除分配给e.x的数组空间

delete[] e.low;//删除分配给e.low的数组空间

delete[] e.high;//删除分配给e.high的数组空间

}

else

{

int curr=e.s+1;//rr记录现在应该排列第几个电路板

for(int i=e.s+1;i=n;i++)//处理扩展节点下一层所有子节点

{

boardnode n;

n.low=new int[m+1];//与if中的意思相同

n.high=new int[m+1];

for(int j=1;j=m;j++)

{

n.low[j]=e.low[j];//将e.low[]中的值赋给n.low[]

n.high[j]=e.high[j];

if(b[e.x[i]][j])

{

if(currn.low[j])

n.low[j]=curr;//若当前节点连接块j的第一个电路板的位置比现在正在排列的电路板的位置还小

if(currn.high[j])

n.high[j]=curr;

}

}

n.cd=n.len();

//如果，当前节点的最大长度小于了最优长度则：

if(n.cdbestd)

{

n.x=new int[n+1];

n.s=e.s+1;

for(int j=1;j=n;j++)

n.x[j]=e.x[j];

n.x[n.s]=e.x[i];//交换位置

n.x[i]=e.x[n.s];//交换位置

q.push(n);//将节点n加入队列中

}

else

{

delete[] n.low;

delete[] n.high;

}

//printf(%d,bestd);

}

delete[] e.x;//当前扩展节点所有子节点均考虑，变成死结点} //try{

if(!q.empty()){

e=q.front(); //取队列首节点作为扩展节点

q.pop();

}else return bestd;

//}

//catch(outofbounds)

//{

//return bestd;

//}

//printf(finish);

}while(!q.empty());

return bestd;

return 1;

}

//测试

void main()

{

//scanf(%d%d,n,m);

cinnm;

int **b=new int*[n+1];

for (int t=0; t=n; t++)

b[t] = new int[m+1];

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

for(int j=1;j=m;j++)

cinb[i][j];

//scanf(%d,b[i][j]);

int *bestx=new int[n+1];

int bestd=0;

bestd=fifioboards(b,n,m,bestx);

printf(%d\n,bestd);

for(i=1;i=n;i++){

coutbestx[i] ;

}

coutendl;

}

//6-6 经典n皇后问题

//description:经典n皇后问题广度优先建议n=14解空间为子集树 //参考答案说排列树是不正确的，本例打印n*n棋盘的所有解，即放置方法 #include iostream

#include fstream

#include algorithm

#include functional

#include queue

using namespace std;

//本例子直接输入棋盘大小，不用文件

//ifstream in(input.txt); //请在项目文件夹下新建一个input.txt

//ofstream out(output.txt);

class node{

public:

node(int n){

t = 0;

this-n = n;

loc = new int[n + 1];

for (int i = 0; i= n; ++i)

{

loc[i] = 0;

}

}

node(const node other){

this-t = other.t;

this-n = other.n;

this-loc = new int [n + 1];

for (int i = 0; i = n; ++i){

this-loc[i] = other.loc[i];

}

}

int t;//已放置t个皇后

【篇二：计算机算法分析与设计(第四版)习题算法分析

部分详解(实验二)】

>实验内容：算法实现问题2-1、2-5、2-7

//2-1 众数问题

思路1：先排序，然后再统计，时间复杂度较高。

思路2：递归实现

–先根据某数x，将小于x的放于其左，大于x的放于其右

–统计x出现的次数t

–如果x左边数的个数t，向左递归

–如果x右边数的个数t，向右递归

#includeiostream

#includecstdlib

#includefstream

#includemap

using namespace std;

int key;

int maxcount=0;

void zs(int* a,int l,int r){

int num =a [l];

int an=0;

int *b=new int[r-l+1];

int bn=0;

int *c=new int[r-l+1];

int cn=0;

for(int i=l;i(r-l+1);i++){

if (num==a[i]) {

an++;

}else if (numa[i]) {

b[bn]=a[i];

bn++;

}else{

c[cn]=a[i];

cn++;

}

if (anmaxcount) {

key=a[i];

maxcount=an;

}

}

if (bnmaxcount) { //小于部分

zs(b,0,bn-1);

}

if (cnmaxcount) { //大于部分

zs(c,0,cn-1);

}

delete b;

delete c;

}

int main()

{

ifstream inputfile(input.txt,ios::in); //读数据文件

ofstream outputfile(output.txt,ios::out); //写数据文件 if(!inputfile)

{

cerrinputfile could not be opened.endl;

exit(1);

}

int number;

inputfilenumber;

int l=0,r=number-1;

int * a =new int[number];

int i=0;

while(inputfilenumber){ //使用c++文件输入流输入数据

a[i]=number;

i++;

}

zs(a,l,r); //众数问题递归函数

delete a;

outputfilekeyendlmaxcount; //使用c++文件输出流输出结果

return 0;

}

//将nput.txt、output.txt文件放在项目文件夹下，分别存储输入数据和结果

例如：项目名sy21

//算法实现题：2-5

思路：回溯法搜索排列树，相同元素不交换位置，修复前后紧邻相同元素问题

#include iostream.h

templateclass type

void perm(type list[],int k,int m)

{// 产生list[k:m]的所有排列

if(k == m)

{ //只剩下1个元素

for(int i=0;i=m;i++) coutlist[i];

coutendl;

}

else //还有多个元素待排列，递归产生排列

for(int i=k;i=m;i++)

{

if ((list[k]==list[i])(k!=i)|| (list[i]==list[i-1])) {

continue;

}

swap(list[k],list[i]);

perm(list,k+1,m);

swap(list[k],list[i]);

}

}

templateclass type

inline void swap(type a,type b)

{

type temp=a;a=b;b=temp;

}

void main(){

char a[4]={a,b,c,a};

perm(a,0,3);

}

//集合划分问题2-7

思路：对于n个元素的集合，可以划分成由m(1=m=n)个子集构成的子集，如 {{1}，{2}，{3}，{4}}就是由4个子集构成的非空子集。假设f(n,m)表示将n个元素的集合划分成由m个子集构成的集合的个数，那么可以这样来看：

1)若m==1，则f(n,m)=1;

2)若n==m，则f(n,m)=1;

3)若非以上两种情况，f(n,m)可以由下面两种情况构成

a.向n-1个元素划分成的m个集合里面添加一个新的元素，则有m*f(n-1,m)种方法；

b.向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合，则有f(n-1,m-1)种方法。

??m??1||n??m??1f(n,m)????f?n?1,m?1??m*f?n?1,m??m?n m!?1?

//参考代码

#includestdio.h

int f(int n,int m)

{

if(m==1||n==m)

return 1;

else

return f(n-1,m-1)+f(n-1,m)*m;

}

int main(void)

{

int n;

while(scanf(%d,n)==1n=1) //按ctrl+break退出程序

{

int i;

int sum=0;

for(i=1;i=n;i++)

{

sum+=f(n,i);

}

printf(%d\n,sum);

}

return 0;

}

【篇三：2013《计算机算法设计与分析》习题及答案】ass=txt>2013 秋

《计算机算法设计与分析》习题及答案

一．选择题

1、二分搜索算法是利用（ a ）实现的算法。

a、分治策略

b、动态规划法

c、贪心法

d、回溯法

2、下列不是动态规划算法基本步骤的是（ a ）。

a、找出最优解的性质

b、构造最优解

c、算出最优解

d、定义最优

解

3、最大效益优先是（ a ）的一搜索方式。

a、分支界限法

b、动态规划法

c、贪心法

d、回溯法

4、在下列算法中有时找不到问题解的是（ b ）。

a、蒙特卡罗算法

b、拉斯维加斯算法

c、舍伍德算法

d、数值概率

算法

5. 回溯法解旅行售货员问题时的解空间树是（ a ）。

a、子集树

b、排列树

c、深度优先生成树

d、广度优先生成树

6．下列算法中通常以自底向上的方式求解最优解的是（ b ）。

a、备忘录法

b、动态规划法

c、贪心法

d、回溯法

7、衡量一个算法好坏的标准是（ c ）。

a 运行速度快

b 占用空间少

c 时间复杂度低

d 代码短

8、以下不可以使用分治法求解的是（ d ）。

a 棋盘覆盖问题

b 选择问题

c 归并排序

d 0/1背包问题

9. 实现循环赛日程表利用的算法是（ a ）。

a、分治策略

b、动态规划法

c、贪心法

d、回溯法

10、下列随机算法中运行时有时候成功有时候失败的是（ c ）

a 数值概率算法

b 舍伍德算法

c 拉斯维加斯算法

d 蒙特卡罗算法

11．下面不是分支界限法搜索方式的是（ d ）。

a、广度优先

b、最小耗费优先

c、最大效益优先

d、深度优先

12．下列算法中通常以深度优先方式系统搜索问题解的是（ d ）。

a、备忘录法

b、动态规划法

c、贪心法

d、回溯法

13.备忘录方法是那种算法的变形。（ b ）

a、分治法

b、动态规划法

c、贪心法

d、回溯法

14．哈夫曼编码的贪心算法所需的计算时间为（ b ）。

a、o（n2n）

b、o（nlogn）

c、o（2n）

d、o（n）

15．分支限界法解最大团问题时，活结点表的组织形式是（ b ）。

a、最小堆

b、最大堆

c、栈

d、数组

16．最长公共子序列算法利用的算法是（ b ）。

a、分支界限法

b、动态规划法

c、贪心法

d、回溯法

17．实现棋盘覆盖算法利用的算法是（ a ）。

a、分治法

b、动态规划法

c、贪心法

d、回溯法

18.下面是贪心算法的基本要素的是（ c ）。

a、重叠子问题

b、构造最优解

c、贪心选择性质

d、定义最优解

19.回溯法的效率不依赖于下列哪些因素（ d ）

a.满足显约束的值的个数

b. 计算约束函数的时间

c.计算限界函数的时间

d. 确定解空间的时间

）

a．递归函数 b.剪枝函数 c。随机数函数 d.搜索函数

21、下面关于np问题说法正确的是（ b ）

a np问题都是不可能解决的问题

b p类问题包含在np类问题中

c np完全问题是p类问题的子集

d np类问题包含在p类问题中

22、蒙特卡罗算法是（ b ）的一种。

a、分支界限算法

b、概率算法

c、贪心算法

d、回溯算法

23.下列哪一种算法不是随机化算法（ c ）

a. 蒙特卡罗算法

b.拉斯维加斯算法

c.动态规划算法

d.舍伍德算法

24. （ d ）是贪心算法与动态规划算法的共同点。

a、重叠子问题

b、构造最优解

c、贪心选择性质

d、最优子结构性质

25. 矩阵连乘问题的算法可由（ b ）设计实现。

a、分支界限算法

b、动态规划算法

c、贪心算法

d、回溯算法

26. 分支限界法解旅行售货员问题时，活结点表的组织形式是

（ a ）。

a、最小堆

b、最大堆

c、栈

d、数组

27、strassen矩阵乘法是利用（ a ）实现的算法。

a、分治策略

b、动态规划法

c、贪心法

d、回溯法

29、使用分治法求解不需要满足的条件是（ a ）。

a 子问题必须是一样的

b 子问题不能够重复

c 子问题的解可以合并

d 原问题和子问题使用相同的方法解

30、下面问题（ b ）不能使用贪心法解决。

a 单源最短路径问题

b n皇后问题

c 最小生成树问题

d 背包问题

31、下列算法中不能解决0/1背包问题的是（ a ）

a 贪心法

b 动态规划

c 回溯法

d 分支限界法

32、回溯法搜索状态空间树是按照（ c ）的顺序。

a 中序遍历

b 广度优先遍历

c 深度优先遍历

d 层次优先遍历

33、下列随机算法中运行时有时候成功有时候失败的是（ c ）

a 数值概率算法

b 舍伍德算法

c 拉斯维加斯算法

d 蒙特卡罗算法 34．实现合并排序利用的算法是（ a ）。

a、分治策略

b、动态规划法

c、贪心法

d、回溯法

35．下列是动态规划算法基本要素的是（ d ）。

a、定义最优解

b、构造最优解

c、算出最优解

d、子问题重叠性质

36．下列算法中通常以自底向下的方式求解最优解的是（ b）。

a、分治法

b、动态规划法

c、贪心法

d、回溯法

37．采用广度优先策略搜索的算法是（ a ）。

a、分支界限法

b、动态规划法

c、贪心法

d、回溯法

38、合并排序算法是利用（ a ）实现的算法。

a、分治策略

b、动态规划法

c、贪心法

d、回溯法

39、在下列算法中得到的解未必正确的是（ b ）。

a、蒙特卡罗算法

b、拉斯维加斯算法

c、舍伍德算法

d、数值概率算法

40、背包问题的贪心算法所需的计算时间为（b）

a、o（n2n）

b、o（nlogn）

c、o（2n）

d、o（n）

41．实现大整数的乘法是利用的算法（ c ）。

a、贪心法

b、动态规划法

c、分治策略

d、回溯法

42．0-1背包问题的回溯算法所需的计算时间为（ a ）

na、o（n2） b、o（nlogn） c、o（2n） d、o（n）

43．采用最大效益优先搜索方式的算法是（ a ）。

a、分支界限法

b、动态规划法

c、贪心法

d、回溯法

44．贪心算法与动态规划算法的主要区别是（ b ）。

a、最优子结构

b、贪心选择性质

c、构造最优解

d、定义最优解

45. 实现最大子段和利用的算法是（ b ）。

a、分治策略

b、动态规划法

c、贪心法

d、回溯法

46.优先队列式分支限界法选取扩展结点的原则是（ c ）。

a、先进先出

b、后进先出

c、结点的优先级

d、随机

47.背包问题的贪心算法所需的计算时间为（ b ）。

nna、o（n2）b、o（nlogn） c、o（2） d、o（n）

48、广度优先是（ a ）的一搜索方式。

a、分支界限法

b、动态规划法

c、贪心法

d、回溯法

49、舍伍德算法是（ b ）的一种。

a、分支界限算法

b、概率算法

c、贪心算法

d、回溯算法

50下列哪一种算法是随机化算法（ d ）

a. 贪心算法

b. 回溯法

c.动态规划算法

d.舍伍德算法

51. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ b ）。

a、重叠子问题

b、最优子结构性质

c、贪心选择性质

d、定义最优解

52．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为 (b ) 。

nna、o（n2）b、o（nlogn）c、o（2）d、o（n）

53. 以深度优先方式系统搜索问题解的算法称为 (d) 。

a、分支界限算法

b、概率算法

c、贪心算法

d、回溯算法

54. 实现最长公共子序列利用的算法是（ b ）。

a、分治策略

b、动态规划法

c、贪心法

d、回溯法

55. hanoi塔问题如下图所示。现要求将塔座a上的的所有圆盘移到塔座b上，并仍按同样顺序叠置。移动圆盘时遵守hanoi塔问题的移动规则。由此设计出解hanoi塔问题的递

hanoi塔

56.? 动态规划算法的基本要素为（ c ）

a. 最优子结构性质与贪心选择性质b．重叠子问题性质与贪心选择性质

c．最优子结构性质与重叠子问题性质 d. 预排序与递归调用

57. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（ a ）

a. 最优子结构性质与贪心选择性质b．重叠子问题性质与贪心选择性质

c．最优子结构性质与重叠子问题性质 d. 预排序与递归调用

58. 回溯法在问题的解空间树中，按（ d ）策略，从根结点出发搜索解空间树。

a.广度优先

b. 活结点优先

c.扩展结点优先

d. 深度优先

59. 分支限界法在问题的解空间树中，按（ a ）策略，从根结点出发搜索解空间树。

a.广度优先

b. 活结点优先

c.扩展结点优先

d. 深度优先

60. 程序块（ a ）是回溯法中遍历排列树的算法框架程序。

a.

b.