算法设计与分析 期末试卷 A卷(完整含答案)(3)

2021-09-24 18:05

{

// x[i] = 1; 无条件左子树 cw += a[i];

Backtrack(i+1);

(6) ; // x[i] = 0;

搜索完左子树,无条件右子树 } (7) ;

}

(6) (7) 参考解答:

(6) cw -= a[i]; (7) Backtrack(i+1);

4、“n皇后问题”是求解:n×n的棋盘上放置n个不同行不同列不同斜线的皇后,是否有放置方案,有请输出可行的放置方案数。其算法框架nQueen( )如下,请补充完整。

{

……

//假定n,sum,x[]数组等都为全局变量,并在nQueen中初始化;

7

}

void Backtrack(int t) //完全n叉树的搜索算法,根节点t=1 {

if(t>n) //搜索到n叉树的叶子 {

sum++; //sum为可行放置方案个数的统计变量

…… //并输出x[]解向量,此处略

} else {

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

x[t] = i;

if( Place(t) )

Backtrack(t+1); } } }

int Place(int k) {

for(int j=1;j<k;j++)

if( (8) || (9) ) return 0; //可使用abs()库函数求绝对值 }

for(int i=1; i<=n; i++) x[i]=0; Backtrack(1); return sum;

(8) (9)

参考解答:

(8) abs(k-j)==abs(x[k]-x[j]) (9) x[j]==x[k]

5、大于1的正整数 n 都可以分解为 n = x1×x2×...×xm,对于给定正整数n,计算n共有多少种不同的分解式的solve( )过程如下。例如:当n=12时,共有8种不同的分解式: 12 = 12; 12 = 6*2; 12 = 4*3; 12 = 3*4;12 = 3*2*2;12 = 2*6; 12 = 2*3*2; 12 = 2*2*3

void solve(int n) //递归实现对n的不同分解式的个数统计 {

if (n==1) total++;

else for (int i=2; i<=n; i++)

if (n%i == 0) (10) ; }

(10)

参考解答:

(10) solve(n/i); 或if (n==1) total=1; else … total=solve(i)*solve(n/i);

6、二维0-1背包问题:n种物品,每种物品仅1件,物品i的重量wi,体积bi,价值vi,背包容量为c,容积为d。所有参数均为正整数,如何选择装入背包的物品子集,使得装入背包物品的总价值最大?其动态规划算法Knapsack2( )算法如下,其中m[i][x][y]含义:每种物品仅1件,但可选物品1…i,背包容量为x容积为y(1≤i≤n,0≤x≤c,0≤y≤d),可获得装入物品的最大价值和存于m[i][x][y]中。

//全局变量有n, w[], b[], v[];含义如题说明。 //全局变量有m[][][]数组;含义如题说明。 ……

8

int Knapsack2() //动态规划法计算二维背包问题,填充m数组 {

int i,x,y;

for(x=0;x<=c;x++) //初始化m[1][x][y] { for(y=0;y<=d;y++) {

if(x>=w[1] && y>=b[1]) m[1][x][y]=v[1]; else m[1][x][y]=0; }

}

for(i=2;i<=n;i++) //递推填充m[i][x][y],2<=i<=n { for(x=0;x<=c;x++) { for(y=0;y<=d;y++) { if(x>=w[i] && y>=b[i] && m[i-1][x][y]<m[i-1][x-w[i]][y-b[i]]+v[i]) m[i][x][y] = (11) ; else

m[i][x][y] = (12) ; } } }

return m[n][c][d]; }

装

订

线

(11) (12) 参考解答:

(11) m[i][x][y] = m[i-1][ x-w[i] ][ y-b[i] ] + v[i]; (12) m[i][x][y] = m[i-1][x][y];

得分

五、算法设计题(共2小题,共15分)

此大题请写出算法设计的详细步骤,可用伪代码、文字、图表来描述。 1、【区间相交问题】(7分)

给定数轴上n个区间。去掉尽可能少的区间,使剩下的区间都不相交。请给出删除区间的方案。(这里:两区间仅边界有交点不算相交)

参考解答:区间相交问题基本等同于活动安排问题。 1)、将区间按照区间后端点排序(从小到大)。 2)、选择第一个区间

3)、依次扫描后续区间,和第一个不相交的,拉入相容区间集合 4)、总区间数减去相容区间集合得到的就是最少的需要去掉的区间数

评分准则: 1) 2) 3)

答到贪心算法,且贪心算法表述正确,本题即可得满分; 说明用到贪心算法,但表述不正确或含糊,扣2分以上;

未提及贪心算法,但有解题思路,若错误,扣一大半分数,若正确,扣一半,因为贪心算法在这个问题中求解的效率最高;

9

其它情况酌情考虑。

2、【最长上升子序列问题】(8分)

对于给定的一个序列(a1,a2,...,aN),1 N 10000。我们可以得到一些递增上升的子序列。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8)。你的任务:对于给定的序列,求出最长上升子序列的长度。要求写出算法思想和递推公式,并分析算法时间复杂度。

参考解答:设f(i)表示:从左向右扫描过来直到以a[i]元素结尾的序列,获得的最长上升子序列的长度,且子序列包含a[i]元素(1≤i≤n)。

1i 1

f(i) max{f(j) 1:当a[i] a[j];1 j i}i 1

1i 1; j(1 j i),都有a[i] a[j]

即,f(i)是从f(1), f(2),…f(i-1)中找最大的一个值,再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列,如果能加入,是之前已获得的最长上升子序列长度加一;如果不能加入,就取这最后一个元素作为一个单独子序列,长度为1。

最后,所要求的整个序列的最长公共子序列长度为max{f(i): 1<=i<=n} 例如,对于序列:4 2 6 3 1 5 2

i array f(i)

评分准则: 1) 2)

答到使用动态规划算法,并且推导出动态规划算法的递推函数公式表达,边界设定清晰,本题即可得满分;(阅卷时仔细看递推公式表达,公式表达含义正确即可,因其表达形式可能不唯一) 说明使用动态规划算法,但对递推函数表达错误或含糊,扣2分以上; 其它情况酌情考虑。

1 4 1

2 2 1

3 6 2

4 3 2

5 1 1

6 5 3

7 2 2

10


算法设计与分析 期末试卷 A卷(完整含答案)(3).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:新苏教版小学六年级 比例的基本性质下册数学教案

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: