{
// 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
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说医药卫生算法设计与分析 期末试卷 A卷(完整含答案)(3)在线全文阅读。
相关推荐: