《算法设计与分析期末试题_考试版》由会员分享，可在线阅读，更多相关《算法设计与分析期末试题_考试版（3页珍藏版）》请在装配图网上搜索。
1、1、用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程3、算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合
2、。输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法Main()intI,a=1,b=1;Print(a,b);For(i=1;i1)returnfib(n-1)+fib(n-2);一
3、个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第12个月时，该饲养场共有兔子多少只？Print(c);A=b;B=c;决；(2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；(3) 利用该问题分解出的子问题的解可以合并为该问题的解；(4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。3、分治法的基本步骤(1) 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；贪婪法基本思想：以逐步的局部最优，达到最终的全局最优。无后【问题】背包问
4、题问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总#includevoidmain()intm,n,i,j,w50,p50,pl50,b50,s=0,max;printf(输入背包容量m,物品种类n:);scanf(%d%d,&m,&n);for(i=1;i=n;i=i+1)printf(输入物品的重量W和价值P:);scanf(%d%d,&wi,&pi);pli=pi;s=s+wi;if(s=m)printf(wholechoosen);/return;动态规划基本思想：把求解的问题分成许多阶段或多个子问题，然后按顺序求解各个子问题。前一个子
5、问题的解为后一个子问题的求解提供了有用的信息。在求解任何一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解，依次解决各子问题，最后一个子问题就是问题的解。基本步骤(1) 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的(即无后向性)，否则问题就无法用动态规划求解。(2) 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。(3) 确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决
6、策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，(2) 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；(3) 合并：将各个子问题的解合并为原问题的解。效性重量不超过指定的限制重量，但选中物品的价值之和最大。for(i=1;i=n;i=i+1)max=1;for(j=2;jplmax/wmax)max=j;plmax=0;bi=max;for(i=1,s=0;sm&i=n;i=i+1)s=s+wbi;if(s!=m)wbi-1=m-wbi-1;for(j=1;j=i-1;j=j+1)printf(chooseweight%dn,wbj);
7、我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。回溯法基本思想：按照深度优先策略，从根结点出发搜索解空间。算法搜索至解空间的任一结点时总是先判断该结点是否问题的约束条件。如果满足进入该子树，继续按深度优先的策略搜索。否则，不去搜索以该结点为根的子树，而是逐层向其祖先结点回溯。其实回溯法就是对隐式图的深度优先搜索算法基本步骤：1、确定问题的解空间：应用回溯法时，首先应明确定义问题的解的空间。问题的解空间应至少包含问题的一个解。2、确定结点的扩展规则3、搜索解空间：从开始结点出发，以深度优先的方式搜索整个解空间。【问题】n皇后问题分支限界法基本思想：分支限界法是由“分支”和“限界”两部分组成。2“分支”策略体现在对问题空间是按广度优先的策略进行搜索“限界”策略是为了加速搜索速度面采用启发信息剪枝策略。可能会让画出“子集树斩图”235页例题及图好好看一下。3
算法设计与分析期末试题_考试版
