算法题计算机算法设计与分析期末试题套含答案Word文件下载.docx
《算法题计算机算法设计与分析期末试题套含答案Word文件下载.docx》由会员分享，可在线阅读，更多相关《算法题计算机算法设计与分析期末试题套含答案Word文件下载.docx（20页珍藏版）》请在冰点文库上搜索。
二、建立迭代关系式。
所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。
迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
三、对迭代过程进行控制。
在什么时候结束迭代过程？
这是编写迭代程序必须考虑的问题。
不能让迭代过程无休止地重复执行下去。
迭代过程的控制通常可分为两种情况：
一种是所需的迭代次数是个确定的值，可以计算出来；
另一种是所需的迭代次数无法确定。
对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；
对于后一种情况，需要进一步分析出用来结束迭代过程的条件。
编写计算斐波那契（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
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<
classT>
voidQuickSort（T*a,intn）
{对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）式}
ift比fk（xk）更优thenfk（xk）:
=t;
{计算fk（xk）的最优值}
end;
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<
i）元组（x1，x2，…，xj）一定也满足D中仅涉及到x1，x2，…，xj的所有约束，i=1，2，…，n。
换句话说，只要存在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行配置第一个皇后开始，在第m列col[m]行放置了一个合理的皇后后，准备考察第m+1列时，在数组a[
]、b[]和c[]中为第m列，col[m]行的位置设定有皇后标志；
当从第m列回溯到第m-1列，并准备调整第m-1列的皇后配置时，清除在数组a[
]、b[]和c[]中设置的关于第m-1列，col[m-1]行有皇后的标志。
一个皇后在m列，col[m]行方格内配置是合理的，由数组a[]、b[]和c[]对应位置的值都为1来确定。
细节见以下程序：
【程序】
#include
#defineMAXN20
intn,m,good;
intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];
voidmain（）
{intj;
charawn;
printf（“Entern:
“）;
scanf（“%d”,&
n）;
for（j=0;
j<
=n;
j++）a[j]=1;
=2*n;
j++）cb[j]=c[j]=1;
m=1;
col[1]=1;
col[0]=0;
{printf（“列\t行”）;
for（j=1;
j++）
printf（“%3d\t%d\n”,j,col[j]）;
printf（“Enteracharacter（Q/qforexit）!
\n”）;
scanf（“%c”,&
awn）;
if（awn==’Q’||awn==’q’）exit（0）;
while（col[m]==n）
{m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
col[m]++;
else
{a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
col[++m]=1;
{while（col[m]==n）
good=a[col[m]]&
&
b[m+col[m]]&
c[n+m-col[m]];
试探法找解算法也常常被编写成递归函数，下面两程序中的函数queen_all（）和函数queen_one（）能分别用来解皇后问题的全部解和一个解。
intn;
queen_all（1,n）;
}
voidqueen_all（intk,intn）
{inti,j;
for（i=1;
i<
i++）
if（a[i]&
b[k+i]&
c[n+k-i]）
{col[k]=i;
a[i]=b[k+i]=c[n+k-i]=0;
if（k==n）
queen_all（k+1,n）;
a[i]=b[k+i]=c[n+k-i];
采用递归方法找一个解与找全部解稍有不同，在找一个解的算法中，递归算法要对当前候选解最终是否能成为解要有回答。
当它成为最终解时，递归函数就不再递归试探，立即返回；
若不能成为解，就得继续试探。
设函数queen_one（）返回1表示找到解，返回0表示当前候选解不能成为解。
细节见以下函数。
intqueen_one（intk,intn）
{inti,found;
i=found=0;
While（!
found&
i{i++;
if（k==n）return1;
found=queen_one（k+1,n）;
a[i]=b[k+i]=c[n+k-i]=1;
returnfound;
分支定界法：
分支限界法：
这是一种用于求解组合优化问题的排除非解的搜索算法。
类似于回溯法，分枝定界法在搜索解空间时，也经常使用树形结构来组织解空间。
然而与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。
因此，可以很容易比较回溯法与分枝定界法的异同。
相对而言，分枝定界算法的解空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。
算法思想：
分枝定界（branchandbound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。
每个活节点有且仅有一次机会变成E-节点。
当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。
在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。
从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。
有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）：
1）先进先出（FIFO）即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活
节点表的性质与队列相同。
2）最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。
如果查找
一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费
的活节点；
如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个
E-节点是具有最大收益的活节点
装载问题
用一个队列Q来存放活结点表，Q中weight表示每个活结点所相应的当前载重量。
当weight＝－1时，表示队列已达到解
升级会员 