算法题计算机算法设计及分析期末试题卷4套含答案解析.docx

算法题计算机算法设计及分析期末试题卷4套含答案解析.docx

《算法题计算机算法设计及分析期末试题卷4套含答案解析.docx》由会员分享，可在线阅读，更多相关《算法题计算机算法设计及分析期末试题卷4套含答案解析.docx（24页珍藏版）》请在冰点文库上搜索。

算法题计算机算法设计及分析期末试题卷4套含答案解析

（1）用计算机求解问题的步骤：

1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制

（2）算法定义：

算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程

（3）算法的三要素

1、操作2、控制结构3、数据结构

算法具有以下5个属性：

　　有穷性：

一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。

　　确定性：

算法中每一条指令必须有确切的含义。

不存在二义性。

只有一个入口和一个出口

　　可行性：

一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。

　　输入：

一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。

　　输出：

一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

算法设计的质量指标：

　　正确性：

算法应满足具体问题的需求；

　　可读性：

算法应该好读，以有利于读者对程序的理解；

　　健壮性：

算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

　　效率与存储量需求：

效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。

一般这两者与问题的规模有关。

经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法

迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。

利用迭代算法解决问题，需要做好以下三个方面的工作：

　　一、确定迭代模型。

在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

　　二、建立迭代关系式。

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。

在什么时候结束迭代过程？

这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地重复执行下去。

迭代过程的控制通常可分为两种情况：

一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。

编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。

　　斐波那契数列为：

0、1、1、2、3、……，即：

　　fib（0）=0;

　　fib

（1）=1;

　　fib（n）=fib（n-1）+fib（n-2）（当n>1时）。

　　写成递归函数有：

　　intfib（intn）

　　{if（n==0）return0;

　　if（n==1）return1;

　　if（n>1）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*2

　　x=y

　　让计算机对这个迭代关系重复执行11次，就可以算出第12个月时的兔子数。

参考程序如下：

　　cls

　　x=1

　　fori=2to12

　　y=x*2

　　x=y

　　nexti

　　printy

　　end

分而治之法

1、分治法的基本思想

任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。

问题的规模越小，越容易直接求解，解题所需的计算时间也越少。

例如，对于n个元素的排序问题，当n=1时，不需任何计算；n=2时，只要作一次比较即可排好序；n=3时只要作3次比较即可，…。

而当n较大时，问题就不那么容易处理了。

要想直接解决一个规模较大的问题，有时是相当困难的。

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治法所能解决的问题一般具有以下几个特征：

（1）该问题的规模缩小到一定的程度就可以容易地解决；

（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快速排序

template

　　voidQuickSort（T*a,intn）

　　{//对a[0:

n-1]进行快速排序

　　{//要求a[n]必需有最大关键值

　　quickSort（a,0,n-1）;

　　template

　　voidquickSort（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（a

　　do{//在右侧寻找<=pivot的元素

　　j=j-1;

　　}while（a[j]>pivot）;

　　if（i>=j）break;//未发现交换对象

　　Swap（a,a[j]）;

　　}

　　//设置pivot

　　a[l]=a[j];

　　a[j]=pivot;

　　quickSort（a,l,j-1）;//对左段排序

　　quickSort（a,j+1,r）;//对右段排序

　　}

贪婪法

它采用逐步构造最优解的思想，在问题求解的每一个阶段，都作出一个在一定标准下看上去最优的决策；决策一旦作出，就不可再更改。

制定决策的依据称为贪婪准则。

贪婪法是一种不追求最优解，只希望得到较为满意解的方法。

贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。

贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。

【问题】背包问题

问题描述：

有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。

#include

voidmain（）

{

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;s

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]]）;

}动态规划的基本思想

前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。

在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。

一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。

动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。

由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。

贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。

因此贪心法自顶向下，一步一步地作出贪心选择；

而分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。

不足之处：

如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。

解决上述问题的办法是利用动态规划。

该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优（最大或最小）值的解。

若存在若干个取最优值的解的话，它只取其中的一个。

在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，（亦即各子问题可包含公共的子问题）也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。

因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。

动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。

3、动态规划算法的基本步骤

设计一个标准的动态规划算法，通常可按以下几个步骤进行：

（1）划分阶段：

按照问题的时间或空间特征，把问题分为若干个阶段。

注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。

（2）选择状态：

将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。

当然，状态的选择要满足无后效性。

（3）确定决策并写出状态转移方程：

之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。

所以，如果我们确定了决策，状态转移方程也就写出来了。

但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。

（4）写出规划方程（包括边界条件）：

动态规划的基本方程是规划方程的通用形式化表达式。

一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。

动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。

根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：

标准动态规划的基本框架

1. 对fn+1（xn+1）初始化;   {边界条件}

fork:

=ndownto1do

for每一个xk∈Xkdo

for每一个uk∈Uk（xk）do

begin

fk（xk）:

=一个极值;                {∞或－∞}

xk+1:

=Tk（xk,uk）;                 {状态转移方程}

t:

=φ（fk+1（xk+1）,vk（xk,uk））;      {基本方程（9）式}

if t比fk（xk）更优thenfk（xk）:

=t;{计算fk（xk）的最优值}

end;

t:

=一个极值;                              {∞或－∞}

for每一个x1∈X1do

iff1（x1）比t更优thent:

=f1（x1）;      {按照10式求出最优指标}

输出t;

但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：

（1）分析最优解的性质，并刻划其结构特征。

（2）递归地定义最优值。

（3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。

（4）根据计算最优值时得到的信息，构造一个最优解。

步骤

（1）～（3）是动态规划算法的基本步骤。

在只需要求出最优值的情形，步骤（4）可以省略，若需要求出问题的一个最优解，则必须执行步骤（4）。

此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速地构造出一个最优解。

总结：

动态规划实际上就是最优化的问题，是指将原问题的大实例等价于同一最优化问题的较小实例，自底向上的求解最小实例，并将所求解存放起来，存放的结果就是为了准备数据。

与递归相比，递归是不断的调用子程序求解，是自顶向下的调用和求解。

回溯法

     回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。

当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。

如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。

在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。

扩大当前候选解的规模，以继续试探的过程称为向前试探。

1、回溯法的一般描述

可用回溯法求解的问题P，通常要能表达为：

对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E={（x1，x2，…，xn）∣xi∈Si，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。

其中Si是分量xi的定义域，且|Si|有限，i=1，2，…，n。

我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。

解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。

但显然，其计算量是相当大的。

我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组（x1，x2，…，xi）满足D中仅涉及到x1，x2，…，xi的所有约束意味着j（j

换句话说，只要存在0≤j≤n-1，使得（x1，x2，…，xj）违反D中仅涉及到x1，x2，…，xj的约束之一，则以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）一定也违反D中仅涉及到x1，x2，…，xi的一个约束，n≥i>j。

因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（x1，x2，…，xj）违反D中仅涉及x1，x2，…，xj的一个约束，就可以肯定，以（x1，x2，…，xj）为前缀的任何n元组（x1，x2，…，xj，xj+1，…，xn）都不会是问题P的解，因而就不必去搜索它们、检测它们。

回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。

树T类似于检索树，它可以这样构造：

     设Si中的元素可排成xi

（1），xi

（2），…，xi（mi-1），|Si|=mi，i=1，2，…，n。

从根开始，让T的第I层的每一个结点都有mi个儿子。

这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1

（1），xi+1

（2），…，xi+1（mi），i=0，1，2，…，n-1。

照这种构造方式，E中的一个n元组（x1，x2，…，xn）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为x1，x2，…，xn，反之亦然。

另外，对于任意的0≤i≤n-1，E中n元组（x1，x2，…，xn）的一个前缀I元组（x1，x2，…，xi）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2，…，xi，反之亦然。

特别，E中的任意一个n元组的空前缀（），对应于T的根。

     因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1，x2，…，xn满足约束集D的全部约束。

在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（x1i）、前缀2元组（x1，x2）、…，前缀I元组（x1，x2，…，xi），…，直到i=n为止。

     在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。

【问题】n皇后问题

问题描述：

求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局。

这是来源于国际象棋的一个问题。

皇后可以沿着纵横和两条斜线4个方向相互捕捉。

如图所示，一个皇后放在棋盘的第4行第3列位置上，则棋盘上凡打“×”的位置上的皇后就能与这个皇后相互捕捉。

12345678

××

×××

×××

××Q×××××

×××

×××

××

××

从图中可以得到以下启示：

一个合适的解应是在每列、每行上只有一个皇后，且一条斜线上也只有一个皇后。

求解过程从空配置开始。

在第1列至第m列为合理配置的基础上，再配置第m+1列，直至第n列配置也是合理时，就找到了一个解。

接着改变第n列配置，希望获得下一个解。

另外，在任一列上，可能有n种配置。

开始时配置在第1行，以后改变时，顺次选择第2行、第3行、…、直到第n行。

当第n行配置也找不到一个合理的配置时，就要回溯，去改变前一列的配置。

得到求解皇后问题的算法如下：

{输入棋盘大小值n；

m=0;

good=1;

do{

if（good）

if（m==n）

{输出解；

改变之，形成下一个候选解;

}

else扩展当前候选接至下一列；

else改变之，形成下一个候选解；

good=检查当前候选解的合理性；

}while（m!

=0）;

}

在编写程序之前，先确定边式棋盘的数据结构。

比较直观的方法是采用一个二维数组，但仔细观察就会发现，这种表示方法给调整候选解及检查其合理性带来困难。

更好的方法乃是尽可能直接表示那些常用的信息。

对于本题来说，“常用信息”并不是皇后的具体位置，而是“一个皇后是否已经在某行和某条斜线合理地安置好了”。

因在某一列上恰好放一个皇后，引入一个一维数组（col[

]），值col[i]表示在棋盘第i列、col[i]行有一个皇后。

例如：

col[3]=4，就表示在棋盘的第3列、第4行上有一个皇后。

另外，为了使程序在找完了全部解后回溯到最初位置，设定col[0]的初值为0当回溯到第0列时，说明程序已求得全部解，结束程序运行。

为使程序在检查皇后配置的合理性方面简易方便，引入以下三个工作数组：

（1）数组a[]，a[k]表示第k行上还没有皇后；

（2）数组b[]，b[k]表示第k列右高左低斜线上没有皇后；

（3）数组c[]，c[k]表示第k列左高右低斜线上没有皇后；

棋盘中同一右高左低斜线上的方格，他们的行号与列号之和相同；同一左高右低斜线上的方格，他们的行号与列号之差均相同。

初始时，所有行和斜线上均没有皇后，从第1列的第1行配置第一个皇后开始，在第