算法设计与分析

一、单项选择题1．阶乘函数用递归定义Public static int factorial(int n){if(n = = 0) return 1;return ___B__ ;}A. n*factorial(n)B. n*factorial(n-1)C. n*factorial(n-2)D. n*factorial(n+1)2．上界函数bound计算结点所相应价值的上界。

private static double bound (int i){ //计算结点所相应价值的上界double cleft = c-cw;//剩余容量double b = cp;//价值上界// 以物品单位重量价值递减序装填剩余容量while (i<=n && w[i]<=cleft){cleft -= w[i];b += p[i];i++;}//装填剩余容量装满背包if (i<=n)__A__;return b;}A. b += p[i]/w[i]*cleftB. b = p[i]/w[i]*cleftC. b += p[i]D. b = p[i]3．二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取a[n/2]与x进行比较：如果___D__，则只要在数组a的左半部继续搜索x。

有疑议:N个元素从小到大排(D),还是从大到小排(B).A. x=a[n/2]B. x>a[n/2]C. x>=a[n/2]D. x＜a[n/2]4．实现快速排序算法如下：private static void quickSort(int p ,int r){if(p<r){int q=partition(p,r); //以确定的基准元素a[p]对子数组a[p;r]进行划分___C__ //对左半段排序quickSort(q+1,r); //对右半段排序}}A. quickSort(p,q-1)B. quickSort(p+1,q-1)C. quickSort(p,q+1)D. quickSort(p,q-2)5．回溯法对解空间进行深度优先搜索，一般使用递归方法实现回溯法：void backtrack (int t){if (t＞n) output(x);elsefor (int i=f(n, t); i<=g(n,t); i++) {x[t]=h(i);if (constraint(t)&&bound(t)) _C___ ;}}A. backtrack(t-1)B. backtrack(t)C. backtrack(t+1)D. backtrack(t+2)二、填空题1、Hanoi塔问题设a,b,c是3个塔座。

开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。

各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b 上，并仍按同样顺序叠置。

在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。

请用递归思想解决解决如下Hanoi塔算法。

void hanoi(int n, int a, int b, int c){if (n > 0){Hanoi(n-1,a,b,c);（1）;move (a,b);Hanoi(n-1,c,a,b); （2） ;} }2、用随机投点法计算π值设有一半径为r 的圆及其外切四边形。

向该正方形随机地投掷n 个点。

设落入圆内的点数为k 。

由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为 。

所以当n 足够大时，k 与n 之比就逼近这一概率，从而 。

double Darts (int n){static RandomNumber dart; int k=0;for (int i=1;i <=n;i++) { double x=dart.fRandom(); double y=dart.fRandom();if ((x*x+y*y )<=1) k++;}return 4*k/double(n);（4） ; }3、N 皇后问题在n ×n 格的棋盘上放置彼此不受攻击的n 个皇后。

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 后问题等价于在n ×n 格的棋盘上放置n 个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

4422ππ=r r nk 4≈πbool Queen::Place(int k){// 解向量：(x1, x2, …, xn)// 显约束：xi=1,2, …,n// 隐约束：// 1)不同列// 2)不处于同一正、反对角线for (int j=1;j<k;j++)if (( abs(k-j)==abs(x[j]-x[k])（5）))||( x[j]==x[k]（6）)) return false; return true;}void Queen::Backtrack(int t){if (t>n) sum++;elsefor (int i=1;i<=n;i++) {x[t]=i;if (Place(t)) Backtrack(t+1);}}三、简答题1、分治法的基本思想是什么？答:任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。

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

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

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

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

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

如果原问题可分割成k个子问题（1<k≤n），且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。

在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。

这自然导致递归过程的产生。

分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

2、动态规划算法的基本思想是什么？动态规划算法通常用于求解具有某种最优性质的问题。

在这类问题中，可能会有许多可行解。

每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。

若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

我们可以用一个表来记录所有已解的子问题的答案。

不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

这就是动态规划法的基本思路。

具体的动态规划算法多种多样，但它们具有相同的填表格式。

3、贪心算法的基本思想是什么？顾名思义，贪心算法总是作出在当前看来最好的选择。

也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

当然，希望贪心算法得到的最终结果也是整体最优的。

虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。

如单源最短路经问题，最小生成树问题等。

在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。

贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。

因此能够使用贪心算法的问题必须满足下面的两个性质：1.整体的最优解可以通过局部的最优解来求出；2.一个整体能够被分为多个局部，并且这些局部都能够求出最优解。

使用贪心算法当中的两个典型问题是活动安排问题和背包问题。

4、回溯法的基本思想是什么？回溯法又称试探法。

回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

当我们遇到某一类问题时，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。

回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。

但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。

5、分支限界法的基本思想是什么？分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。

活结点一旦成为扩展结点，就一次性产生其所有儿子结点。

在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。

这个过程一直持续到找到所需的解或活结点表为空时为止。

四、棋盘覆盖问题假设对4×4的棋盘进行L型分割示意图如下：L型分割:#include <stdio.h>#define BOARD_SIZE 8int board[BOARD_SIZE][BOARD_SIZE];/*c1, r1: 棋盘左上角的行号和列号*//*c2, r2: 特殊方格的行号和列号*//*size = 2 ^ k*/void chessboard(int r1, int c1, int r2, int c2, int size){int half_size;static int domino_num = 1;int d = domino_num++;if(size==1) return;half_size = size / 2;if(r2 < r1 + half_size && c2 < c1 + half_size) /*特殊方格在左上角子棋盘*/{chessboard(r1, c1, r2, c2, half_size);}else/* 不在此棋盘，将此棋盘右下角设为相应的骨牌号*/board[r1 + half_size - 1][c1 + half_size - 1] = d;chessboard(r1, c1, r1 + half_size - 1, c1 + half_size - 1, half_size);}if(r2 < r1 + half_size && c2 >= c1 + half_size) /*特殊方格在右上角子棋盘*/{chessboard(r1, c1 + half_size, r2, c2, half_size);}else/*不在此棋盘，将此棋盘左下角设为相应的骨牌号*/{board[r1 + half_size - 1][c1 + half_size] = d;chessboard(r1, c1 + half_size, r1 + half_size - 1, c1 + half_size, half_size);}if(r2 >= r1 + half_size && c2 < c1 + half_size) /*特殊方格在左下角子棋盘*/{chessboard(r1 + half_size, c1, r2, c2, half_size);}else /* 不在此棋盘，将此棋盘右上角设为相应的骨牌号*/{board[r1 + half_size][c1 + half_size - 1] = d;chessboard(r1 + half_size, c1, r1 + half_size, c1 + half_size - 1, half_size);}if(r2 >= r1 + half_size && c2 >= c1 + half_size)/*特殊方格在左上角子棋盘*/{chessboard(r1 + half_size, c1 + half_size, r2, c2, half_size);}else/*不在此棋盘，将此棋盘左上角设为相应的骨牌号*/{board[r1 + half_size][c1 + half_size] = d;chessboard(r1 + half_size, c1 + half_size, r1 + half_size, c1 + half_size, half_size); }}int main(){int i, j;board[2][5] = 0;chessboard(0, 0, 2, 5, BOARD_SIZE);for(i = 0; i < BOARD_SIZE; i++){for(j = 0; j < BOARD_SIZE; j++){printf("%-4d", board[i][j]);}printf("\n");get();}五、算法分析题给出如下顺序搜索算法，请分别分析该算法最好情况下、最坏情况下、及平均情况下的算法搜索次数。