《算法设计与分析》历年期末试题整理(含答案)

1《算法设计与分析》历年期末试题整理(含答案)（1）用计算机求解问题的步骤：1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程（3）算法的三要素1、操作2、控制结构3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。斐波那契数列为：0、1、1、2、3、……，即：2fib(0)=0;fib(1)=1;fib(n)=fib(n-1)+fib(n-2)（当n1时）。写成递归函数有：intfib(intn){if(n==0)return0;if(n==1)return1;if(n1)returnfib(n-1)+fib(n-2);}一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第12个月时，该饲养场共有兔子多少只？分析：这是一个典型的递推问题。我们不妨假设第1个月时兔子的只数为u1，第2个月时兔子的只数为u2，第3个月时兔子的只数为u3，……根据题意，“这种兔子从出生的下一个月开始，每月新生一只兔子”，则有u1＝1，u2＝u1＋u1×1＝2，u3＝u2＋u2×1＝4，……根据这个规律，可以归纳出下面的递推公式：un＝un－1×2(n≥2)对应un和un－1，定义两个迭代变量y和x，可将上面的递推公式转换成如下迭代关系：y=x*2x=y让计算机对这个迭代关系重复执行11次，就可以算出第12个月时的兔子数。参考程序如下：clsx=1fori=2to12y=x*2x=ynextiprintyend分而治之法1、分治法的基本思想任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；3（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。3、分治法的基本步骤分治法在每一层递归上都有三个步骤：（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；（3）合并：将各个子问题的解合并为原问题的解。快速排序在这种方法中，n个元素被分成三段（组）：左段left，右段right和中段middle。中段仅包含一个元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此left和right中的元素可以独立排序，并且不必对left和right的排序结果进行合并。middle中的元素被称为支点(pivot)。图14-9中给出了快速排序的伪代码。//使用快速排序方法对a[0:n-1]排序从a[0:n-1]中选择一个元素作为middle，该元素为支点把余下的元素分割为两段left和right，使得left中的元素都小于等于支点，而right中的元素都大于等于支点递归地使用快速排序方法对left进行排序递归地使用快速排序方法对right进行排序所得结果为left+middle+right考察元素序列[4,8,3,7,1,5,6,2]。假设选择元素6作为支点，则6位于middle；4，3，1，5，2位于left；8，7位于right。当left排好序后，所得结果为1，2，3，4，5；当right排好序后，所得结果为7，8。把right中的元素放在支点元素之后，left中的元素放在支点元素之前，即可得到最终的结果[1,2,3,4,5,6,7,8]。把元素序列划分为left、middle和right可以就地进行（见程序14-6）。在程序14-6中，支点总是取位置1中的元素。也可以采用其他选择方式来提高排序性能，本章稍后部分将给出这样一种选择。程序14-6快速排序templateclassTvoidQuickSort(T*a,intn){//对a[0:n-1]进行快速排序{//要求a[n]必需有最大关键值quickSort(a,0,n-1);templateclassTvoidquickSort(Ta[],intl,intr){//排序a[l:r]，a[r+1]有大值if(l=r)return;inti=l,//从左至右的游标j=r+1;//从右到左的游标Tpivot=a[l];//把左侧=pivot的元素与右侧=pivot的元素进行交换while(true){do{//在左侧寻找=pivot的元素i=i+1;}while(apivot);do{//在右侧寻找=pivot的元素j=j-1;}while(a[j]pivot);if(i=j)break;//未发现交换对象4Swap(a,a[j]);}//设置pivota[l]=a[j];a[j]=pivot;quickSort(a,l,j-1);//对左段排序quickSort(a,j+1,r);//对右段排序}贪婪法它采用逐步构造最优解的思想，在问题求解的每一个阶段，都作出一个在一定标准下看上去最优的决策；决策一旦作出，就不可再更改。制定决策的依据称为贪婪准则。贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。【问题】背包问题问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。#includestdio.hvoidmain(){intm,n,i,j,w[50],p[50],pl[50],b[50],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,&w[i],&p[i]);pl[i]=p[i];s=s+w[i];}if(s=m){printf(wholechoose\n);//return;}for(i=1;i=n;i=i+1){max=1;for(j=2;j=n;j=j+1)if(pl[j]/w[j]pl[max]/w[max])max=j;pl[max]=0;b[i]=max;}for(i=1,s=0;sm&&i=n;i=i+1)s=s+w[b[i]];if(s!=m)w[b[i-1]]=m-w[b[i-1]];for(j=1;j=i-1;j=j+1)printf(chooseweight%d\n,w[b[j]]);}动态规划的基本思想前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。5动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。不足之处：如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。3、动态规划算法的基本步骤设计一个标准的动态规划算法，通常可按以下几个步骤进行：（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和