m[1][4] min m[1][2] m[3][4] p0p2p4 5000 2500 500 8000
m[1][3] m[4][4] ppp 7500 0 5000 12500
034
因此:m[1][4] 8000
4、操场上摆放一行共n堆石头,呈直线排列。n堆石子从左到右方向编号为1~n,每堆石子个数分别为a[1],…,a[n],现在要将石子有次序的合并为一堆,规定每次只能选相邻的2堆合并为新的一堆,并将新的一堆的石子数记为该次合并的得分,经过n-1次合并,最终合并为一堆,总得分为n-1次合并得分之和。现要设计一个算法,计算出将一行的n堆石子合并为一堆的最小得分。这里假设m[i,j]为合并石子Ai…Aj, 1≤i≤j≤n,所得到的最小得分。请写出m[i,j]的递推公式。(5分)
参考解答:设n堆石子从左到右方向编号为1,2,…,n,每堆石子个数分别为a[1],…,a[n]。n堆石子的合并有许多不同的方式,每种合并方式对应于n个矩阵连乘的一种完全加括弧方式。显然,这里合并是满足最优子结构性质的,用A1…An来代表每堆的石子,则最后一次合并在Ak和Ak+1之间,则A1…An的最优合并为((A1…Ak)(Ak+1…An)),可以看出最优解左边部分(A1…Ak)和右边部分(Ak+1…An)的合并也分别是最优的。
假设m[i,j]为合并石子Ai…Aj, 1≤i≤j≤n,所得到的最小得分,若没有“合并”这个动作,则为0。原问题所求的最优值即为m[1,n]。
i j 0 j
m[i,j]
min{m[i,k] m[k 1,j]} a[t]i j t i i k j
填充m[i,j]即可得到任意行状摆放的石子合并的最小得分。
5、有这样一类特殊0-1背包问题:可选物品重量越轻的物品价值越高。n=6,c=20,P=(4,8,15,1,6,3),W=(5,3,2,10,4,8)。其中n为物品个数,c为背包载重量,P表示物品的价值,W表示物品的重量。请问对于此特殊的0-1背包问题,为使放进背包的物品总价值最大,应如何选择放进去的物品?此例能获得的最大总价值多少?(5分)
参考解答:因为该0-1背包问题比较特殊,恰好重量越轻的物品价值越高,所以优先取重量轻的物品放进背包。最终可以把重量分别为2,3,4,5的三个物品放进背包,得到的价值和为15 + 8 + 6 + 4 = 33,为最大值。
得分
三、画图题(共16分,每图4分)
1、字符a~h出现的频率恰好是前八个Fibonacci数(数列最开始两个元素都为1,之后每个元素都等于前两个元素之和),请画出a~h这八个字符的Huffman编码树。(4分)
参考解答:若字符a~h出现的频率恰好是前8个Fibonacci数,它们的Haffman编码树如下图所示。
4
装
订
线
2、对如下问题采用回溯的搜索算法,请画出搜索状态的解空间树。注意这题无需说明算法或搜索过程,只画解空间树即可。(8分:4分+4分)
(1)作业分配问题:n个作业分配给n个人,将第i个作业分给第j个人所需费用代价为c[i][j],
为每个作业分配给不同的人来完成,并使得所有工作的总费用和最小。以n=3为例,请画出搜索的解空间树。
(2)图的m着色问题:给定n个顶点的无向连通图G和m种不同的颜色,用这m种颜色为图G的各顶点着色,且G中邻接顶点(指有边相连的顶点)不能着同色,求所有不同的着色方法
数。以n=3,m=3为例,请画出搜索的解空间树。
参考解答:
(1)
(2)
(1)n=3的排列树
(2)n=3,m=3的n层完全m叉树)
3、折纸留痕:你喜欢折纸吗?给你一张很大的纸,对折以后再对折,再对折……,每次对折都是从右往左折(沿逆时针),因此折了很多次以后,原来的大纸就会变成窄窄的纸条。现在把这个纸条沿着折纸的痕迹打开,把每个痕迹视为一个“直角”,那么从纸的一端沿着与纸面平行的方向看过去(即截面图),会看到一个曲线。例如,对折2次和3次,看到如下曲线。请你画出对折4次的截面曲线。(4分)
对折两次后形成的曲线
对折三次后形成的曲线
参考解答:
5
对折四次后形成的曲线
得分
四、程序填空题(共12个空格,每空2分,共24分, 结果集中的填于程序下方划线处) 1、有重复元素的全排列:对n个元素集 R = {r1, r2, …, rn}进行全排列,其中r1,r2,…,rn可能相同,下面算法框架Permpp( )可以输出R的所有不同的排列,请补充完整。
{
if(k==m) {
输出list内的所有元素; return; }
for(int i=k; i<=m; i++) {
if ( Findsame(list,k,i) )//判断第i个元素是否在list[k,i-1]中出现过
continue; Swap(list[k], list[i]); (1) ; }
}
int Findsame (int a[], int k, int m)//判断第m个元素是否在a[k,m-1]中出现过 {
for (int j=k; j<m; j++) if ( (3) ) return 1; }
(1) (2) (3)
参考解答:
(1) Permpp(list, k+1, m); (2) Swap(list[k], list[i]); (3) a[m]==a[j]
2、求二维数组的“最大子矩阵和”算法框架MaxSum2( )如下,请补充完整。
{
int sum=0,b=0;
for (int i=0;i<n;i++) {
if(b>0) b+=a[i]; else b=a[i];
if(b>sum) sum=b; }
return sum;
6
装
订
线
int MaxSum2(int m, int n, int **a) //{
求解二维整数数组的最大子矩阵和 int sum=0;
int *b=new int[n]; for(int i=0;i<m;i++) {
for(int k=0;k<n;k++) //b b[k]=0;
数组初始化 for(int j=i;j<m;j++) {
for(int k=0;k<n;k++) (4) ;
//先纵向相加到b数组中
//调用一维最大子段和
} sum = max;
}
return sum; }
(4) (5) 参考解答:
(4) b[k]+=a[j][k]; (5) MaxSum(n,b);
3、“子集和问题”是求解:n个元素的整数集合,是否能找到一个子集,使得子集元素之和为c。其回溯搜索算法框架Backtrack( )如下,请补充完整。
{
if(i>n) // {
搜索到子集树的叶子 if (cw == c) found=1; //cw else found=0; //found return;
是一个寻找标志,找到则为为当前的子集之和,foundtrue,否则为已被初始化为false false } if(found==0)
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读,免费范文网,提供经典小说医药卫生算法设计与分析 期末试卷 A卷(完整含答案)(2)在线全文阅读。
相关推荐: