2011_09信科——算法设计与分析样题(1).doc

一、设n为正整数，利用大“O()”记号，将下列程序段的执行时间表示为n的函数，分析下列程序段的时间复杂度1程序段1i=1; k=0;while(in) k=k+0.1*i;i+; 类似的问题还有一道二、简答题关于算法的定义、性质等两道题目答：算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。一个算法应该具有以下七个重要的特征：算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。1、有穷性:算法的有穷性是指算法必须能在执行有限个步骤之后终止2、确切性:算法的每一步骤必须有确切的定义；3、输入项:一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；4、输出项:一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；5、可行性:算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成；（也称之为有效性）6、 高效性:执行速度快，占用资源少；7、 健壮性对数据响应正确。书上答案：算法是指解决问题的一种方法或过程，更严谨的讲，是由若干条指令组成的有穷序列，满足以下4个性质：输入，输出，确定性，有限性。如，制定一个算法一般要经历哪几个阶段？三、请你阐述kruscal算法和prim算法的不同点和特色，并给出某图的最小生成树（要求画出相应生成树，分析过程可以省略）。四、有n种不同的货物，规定每种最多只能拿一件，车容量为c，第i件货物占空间为wi(0=i=n)，价值为pi(0=i=n)，目标为装载的物品价值最大。请用下述不同的贪婪策略装载求解。1） 贪婪策略1：从剩余的物品中选择价值最大的物品。2） 贪婪策略2：从剩余的物品中选择占空间最小的物品。3） 贪婪策略3：从剩余的物品中选择价值密度最大（ pi /wi ）的物品。4） 分析不同策略的解，它们是最优解吗？如果不是，请直接写出最优解。贪婪算法本身只能求出近似最优解，贪婪策略3 解决了前两种的一些不足，但是货物本身却是不可分割的，即0-1性，只能是在或不在两种情况，不可能是只有一部分在，所有先选密度最大的货物的策略也可能不是最优的。最优策略可以用动态规划+贪婪策略3，即局部贪婪后，当发现更好的解可以及时替换相似例题：在杂货店比赛中你获得了第一名，奖品是一车免费杂货。店中有n种不同的货物。规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i需占用wi的空间，价值为pi。你的目标是使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。这个问题可仿照0/1背包问题进行建模，其中车对应于背包，货物对应于物品。0/1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。在每一步过程中利用贪婪准则选择一个物品装入背包。一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2,w=100,10,10,p=20,15,15,c=105。当利用价值贪婪准则时，获得的解为x=1,0,0，这种方案的总价值为20。而最优解为0,1,1，其总价值为30。另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n=2,w=10,20,p=5,100,c=25。当利用重量贪婪策略时，获得的解为x=1,0,比最优解0,1要差。还可以利用另一方案，价值密度pi/wi贪婪算法，这种选择准则为：从剩余物品中选择可装入包的pi/wi值最大的物品，这种策略也不能保证得到最优解。利用此策略试解n=3,w=20,15,15,p=40,25,25,c=30时的最优解。我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧，0/1背包问题是一个NP-复杂问题。对于这类问题，也许根本就不可能找到具有多项式时间的算法。虽然按pi/wi非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。我们希望它是一个好的启发式算法，且大多数时候能很好地接近最后算法。在600个随机产生的背包问题中，用这种启发式贪婪算法来解有239题为最优解。有583个例子与最优解相差10%，所有600个答案与最优解之差全在25%以内。该算法能在O(nlogn)时间内获得如此好的性能。我们也许会问，是否存在一个x(x100)，使得贪婪启发法的结果与最优值相差在x%以内。答案是否定的。为说明这一点，考虑例子n=2,w=1,y,p=10,9y,和c=y。贪婪算法结果为x=1,0,这种方案的值为10。对于y10/9，最优解的值为9y。因此，贪婪算法的值与最优解的差对最优解的比例为(9y-10)/9y*100)%，对于大的y，这个值趋近于100%。但是可以建立贪婪启发式方法来提供解，使解的结果与最优解的值之差在最优值的x%(x100)之内。首先将