第一范文网 - 专业文章范例文档资料分享平台

《算法设计与分析》考试题目及答案解析

来源:用户分享 时间:2025/5/25 15:02:41 本文由沐浅 分享 下载这篇文档手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:xxxxxxx或QQ:xxxxxx 处理(尽可能给您提供完整文档),感谢您的支持与谅解。

7. 贪心选择 最优子结构

二、简答题(本题25分,每小题5分)

6、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同;对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。 7、“最优化原理”用数学化的语言来描述:假设为了解决某一优化问题,需要依次作出n个决策D1,D2,…,Dn,如若这个决策序列是最优的,对于任何一个整数k,1 < k < n,不论前面k个决策是怎样的,以后的最优决策只取决于由前面决策所确定的当前状态,即以后的决策Dk+1,Dk+2,…,Dn也是最优的。

8、某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。

9、回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索,解为叶子结点。搜索过程中,每到达一个结点时,则判断该结点为根的子树是否含有问题的解,如果可以确定该子树中不含有问题的解,则放弃对该子树的搜索,退回到上层父结点,继续下一步深度优先搜索过程。在回溯法中,并不是先构造出整棵状态空间树,再进行搜索,而是在搜索过程,逐步构造出状态空间树,即边搜索,边构造。 10、 P(Polynomial问题):也即是多项式复杂程度的问题。

NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题。

NPC(NP Complete)问题,这种问题只有把解域里面的所有可能都穷举了之后才能得出答案,这样的问题是NP里面最难的问题,这种问题就是NPC问题。

三、算法填空(本题20分,每小题5分) 1、n后问题回溯算法

(1) !M[j]&&!L[i+j]&&!R[i-j+N] (2) M[j]=L[i+j]=R[i-j+N]=1; (3) try(i+1,M,L,R,A) (4) A[i][j]=0

(5) M[j]=L[i+j]=R[i-j+N]=0 2、数塔问题。 (1)c<=r

(2)t[r][c]+=t[r+1][c] (3)t[r][c]+=t[r+1][c+1] 3、Hanoi算法 (1)move(a,c)

(2)Hanoi(n-1, a, c , b)

(3)Move(a,c) 4、(1)p[v]=NIL (2)p[v]=u (3) v∈adj[u] (4)Relax(u,v,w)

四、算法理解题(本题10分)

1 2 3 4 5 6 7 8

2 1 4 3 6 5 8 7

3 4 1 2 7 8 5 6

4 3 2 1 8 7 6 5

5 6 7 8 1 2 3 4 五、(1)8天(2分);

6 5 8 7 2 1 4 3 3

(2)当n=2=8时,循环赛日程表(3分)。

7 8 5 6 3 4 1 2 六、算法设计题(本题15分) 8 7 6 5 4 3 2 1 (1)贪心算法 O(nlog(n))

? 首先计算每种物品单位重量的价值Vi/Wi,然后,依贪心选择策略,将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后,背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。 ? 具体算法可描述如下:

void Knapsack(int n,float M,float v[],float w[],float x[]) {Sort(n,v,w); int i;

for (i=1;i<=n;i++) x[i]=0; float c=M;

for (i=1;i<=n;i++) {if (w[i]>c) break; x[i]=1; c-=w[i]; }

if (i<=n) x[i]=c/w[i]; }

(2)动态规划法 O(nc)

m(i,j)是背包容量为j,可选择物品为i,i+1,…,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质,可以建立计算m(i,j)的递归式如下。

j?wi?max{m(i?1,j),m(i?1,j?wi)?vi}m(i,j)??0?j?wim(i?1,j)?j?wn?vm(n,j)??n?00?j?wn

void KnapSack(int v[],int w[],int c,int n,int m[][11]) {int jMax=min(w[n]-1,c);

for (j=0;j<=jMax;j++) /*m(n,j)=0 0=

for (j=w[n];j<=c;j++) /*m(n,j)=v[n] j>=w[n]*/ m[n][j]=v[n];

for (i=n-1;i>1;i--)

{ int jMax=min(w[i]-1,c);

for (j=0;j<=jMax;j++) /*m(i,j)=m(i+1,j) 0=

for (j=w[i];j<=c;j++)/*m(n,j)=v[n] j>=w[n]*/ m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); }

m[1][c]=m[2][c]; if(c>=w[1])

m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); }

(3)回溯法 O(2n)

cw:当前重量 cp:当前价值 bestp:当前最优值 void backtrack(int i) //回溯法 i初值1

{ if(i > n) //到达叶结点

{ bestp = cp; return; }

if(cw + w[i] <= c) //搜索左子树 { cw += w[i];

cp += p[i]; backtrack(i+1);

cw -= w[i];

cp -= p[i]; }

if(Bound(i+1)>bestp) //搜索右子树

backtrack(i+1);

}

七、算法设计题(本题10分)

为了尽可能地逼近目标,我们选取的贪心策略为:每一步总是选择一个使剩下的数最小的数字删去,即按高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字,否则删除第一个递减区间的首字符。然后回到串首,按上述规则再删除下一个数字。重复以上过程s次,剩下的数字串便是问题的解了。

具体算法如下: 输入s, n;

while( s > 0 )

{ i=1; //从串首开始找

while (i < length(n)) && (n[i]

delete(n,i,1); //删除字符串n的第i个字符 s--; }

while (length(n)>1)&& (n[1]=‘0’)

delete(n,1,1); //删去串首可能产生的无用零 输出n;

《算法设计与分析》考试题目及答案解析.doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印
本文链接:https://www.diyifanwen.net/c4505o0wb306cyp27lz4y3h0qq02ukg01bzo_6.html(转载请注明文章来源)
热门推荐
Copyright © 2012-2023 第一范文网 版权所有 免责声明 | 联系我们
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ:xxxxxx 邮箱:xxxxxx@qq.com
渝ICP备2023013149号
Top