算法设计与分析习题.doc

《算法设计与分析》习题
第一章算法引论
1、 算法的定义？
答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。
通俗讲，算法：就是解决问题的方法或过程。

2、 算法的特征？
答：1)算法有零个或多个输入； ２)算法有一个或多个输出； 3)确定性 ； ４)有穷性

3、 算法的描述方法有几种？
答：自然语言、图形、伪代码、计算机程序设计语言

4、 衡量算法的优劣从哪几个方面？
答：(1) 算法实现所耗费的时间（时间复杂度）；
(2) 算法实现所所耗费的存储空间（空间复杂度）；
(3) 算法应易于理解，易于编码，易于调试等等。

5、 时间复杂度、空间复杂度定义？
答：指的是算法在运行过程中所需要的资源（时间、空间）多少。

6、时间复杂度计算：
{i=1；
while（i<=n）
i=i*2； }
答：语句①执行次数1次，
语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n;
算法执行时间： T(n)= 2log2n +1
时间复杂度：记为O(log2n) ；

7.递归算法的特点？
答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件）
②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式）

8、算法设计中常用的算法设计策略？
答：①蛮力法； ②倒推法； ③循环与递归； ④分治法；
⑤动态规划法； ⑥贪心法； ⑦回溯法； ⑧分治限界法

9、设计算法：
　　递归法：汉诺塔问题？兔子序列（上楼梯问题）？
　　整数划分问题？
　　蛮力法：百鸡百钱问题？
倒推法：穿越沙漠问题？
答：算法如下：
（1） 递归法
l 汉诺塔问题
void hanoi(int n, int a, int b, int c)
{if (n > 0)
{
hanoi(n-1, a, c, b);
move(a,b);
hanoi(n-1, c, b, a);
} }
l 兔子序列（fibonaci数列 ）
递归实现：
Int F(int n)
{
if(n<=2) return 1;
else
return F(n-1)+ F(n-2);
}
l 上楼梯问题
Int F(int n)
{
if(n=1) return 1
if(n=2) return 2;
else
return F(n-1)+ F(n-2);
}
l 整数划分问题
问题描述：将正整数n表示成一系列正整数之和，n=n1+n1+n3+…
将最大加数不大于m的划分个数，记作q(n,m)。正整数n的划分数p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系：

递归算法：
Int q( int n, int m){
if(n<1||m<1) return 0;
If((n=1)||(m=1)) return 1;
If (n<m) return q(n,n);
If(n=m) return q(n,m-1)+1;
else
return q(n,m-1)+q(n-m,m);
}
（2） 蛮力法：百鸡百钱问题
算法设计1：
设x，y，z分别为公鸡、母鸡、小鸡的数量。 约束条件： x+y+z=100 且 5*x+3*y+z/3=100
main( )
{ int x,y,z;
 for(x=1;x<=20;x=x+1)
    for(y=1;y<=34;y=y+1)
      for(z=1;z<=100;z=z+1)
          if(100=x+y+z and 100=5*x+3*y+z/3)
     {　print(the cock number is",x)；
print(the hen number is", y)；
　　　　print(the chick number is "z);}
}
算法分析：以上算法需要枚举尝试20*34*100=68000次。算法的效率显然太低
算法设计2：
在公鸡（x）、母鸡（y）的数量确定后，小鸡 的数量  z就固定为100-x-y，无需再进行枚举了 。  此时约束条件只有一个： 5*x+3*y+z/3=100
main( )
{  int x,y,z;
    for(x=1;x<=20;x=x+1)              
        for(y=1;y<=33;y=y+1)          
        { z=100-x-y;            
         if(z mod 3=0 and
5*x+3*y+z/3=100)                                  
             {print(the cock number is",x)；
print(the hen number is", y)；
　　　　print(the chick number is "z);}
        }
}
算法分析：以上算法只需要枚举尝试20*33=660次。实现时约束条件又限定Z能被3整除时，才会判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的算术计算和条件判断，进一步提高了算法的效率。
(3) 倒推法：穿越沙漠问题
desert（ ）
{ int dis，k，oil,k; // dis表示距终点的距离，k表示贮油点从后到前的序号
dis=500;k=1;oil=500; 　　　 //初始化
while ( dis<1000)
{
print(“storepoint”,k,”distance”, 1000-dis,”oilquantity”,oil) //1000- dis则表示距起点的距离，
k=k+1; //k表示储油点从后到前的序号
dis=dis+500/(2*k-1);
oil= 500*k;
}
print(“storepoint”,k,”distance”,dis,”oilquantity”,oil)；
}

第二章 分治算法
1、分治算法基本思想是什么？ 适合用分治算法解决的问题，一般具有几个特征？ 分治算法基本步骤是什么？
答：1) 基本思想: 将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
2) 特征：
Ø 该问题的规模缩小到一定的程度就可以容易解决;
Ø 该问题可以分解为若干个规模较小的相同子问题，即该问题具有最优子结构性质；
Ø 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
Ø 4)利用该问题分解出子问题解可以合并为该问题解;
3）基本步骤： 分解、求小问题解、合并

2、改写二分查找算法：设a[1…n]是一个已经排好序的数组，改写二分查找算法:
ü 当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j； (即返回x的左、右2个元素)
ü 当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。
并计算其时间复杂度？
答：

３、设计一个合并排序的算法？（分治法解） 　　并计算其时间复杂度？(要求写出递推公式，及其求解过程)
答：
void MergeSort (int A[]，int low，int high)
{ int middle;
if (low<high)
{
middle=(low+high)/2; //取中点
MergeSort(A,low,middle);
MergeSort(A,middle+1,high);
　Merge(A,low,middle,high);　　 //合并算法
}
}
void Merge(int A[]，int low，int middle，int high) //合并过程描述：
{
int i,j,k; int *B=new int[high-low+1];
i=low; j=middle+1; k=low;
while(i<=middle&&j<=high) {　 //两个子序列非空
　　 if(A[i]<=A[j]) 　　 B[k++]=A[i++];
　else 　　　　　　 B[k++]=A[j++];
}
while (i<=middle) 　　B[k++]=A[i++];　//子序列A[low，middle]非空，将A复制到B
while (j<=high) 　B[k++]=A[j++]; /子序列A[middle+1， high]非空，将A复制到B
for(i=low;i<=high;i++) 　A[i++]=B[i++];　　　//将合并后的序列复制回A
}
• 合并排序算法运行时间T(n)的递归形式为：

u 分析该算法时间复杂度：
令T(n)为元素个数为n时所需比较次数（时间）：
当n=１时，　　　时间复杂度记为O(1)。
当n>１时，T(n)=2 T(n/2) + O(n)
=2 (2T(n/22)+O(n/2) ) + O(n)
=22T(n/22) + 2 O(n)
=23T(n/23) + 3O(n)
=……
=2x T(n/2x) + x*O(n)
分解到最后只有2个元素可以求解，n/2x＝1， x=logn;
故 T(n)=n*T(1)+n*logn ，故时间复杂度记为：O（n * logn）

４、金块问题（求最大最小元问题）
老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。
要求：１）设计一算法求解该问题？ （分治法解）
２）计算其时间复杂度？(要求写出递推公式，及其求解过程)
答：递归求取最大和最小元素
maxmin （int i, int j ,float &fmax, float &fmin）
{ int mid; float lmax, lmin, rmax, rmin;
if (i=j) {fmax= a[i]; fmin=a[i];} //只有1个元素
else if (i=j-1) //只有2个元素
if(a[i]<a[j]) { fmax=a[j]；fmin=a[i];}
else {fmax=a[i]; fmin=a[j];}
else //多于2个元素
{mid=(i+j)/2;
maxmin （i，mid，lmax，lmin）;//递归调用算法求最大最小
 maxmin （mid+1，j，rmax，rmin）;//递归调用算法求最大最小
if(lmax>rmax) fmax=lmax; //合并取大
else fmax=rmax;
if(lmin>rmin) fmin=rmin; //合并取小
else fmin=lmin;
}
u 分析该算法时间复杂度：
令T(n)为元素个数为n时所需比较次数（时间）：
当n=2时，查找查找最大最小元只需要1次比较，T(2)=1； 时间复杂度记为O(1)。
当n>2时， T(n)=2T(n/2) + 2 T(2)
=4T(n/4) + 4 T(2) + 2 T(2)
=8T(n/8) + 8 ＋ 4 ＋ 2
=……
=2x T(n/2x) + 2x +2x-1+…+8+4+2
分解到最后只有2个元素可以求解，n/2x＝2，
T(n)= 2x *1 + 2x +2x-1… + 22 + 21
= 2x *1 +(2- 2x*2 )/(1-2）
= 2x + 2x+1 - 2
=3n/2 - 2
故时间复杂度记为：O（n）

５、用分治思想设计一个有效的算法，可以进行两个n位大整数的乘法运算？ 并计算其时间复杂度？（要求写出递推公式，及其求解过程）
答：
int mult( int x, int y, int n) //x, y为两个n位整数
{ s=sign(x)*sign(y); //s为x* y的符号
x=abs(x); y=abs(y); int mul;
if( n=1) { mul=s*x*y; return mul; }
else // 计算XY = ac 2n + ((a-b)(d-c)+ac+bd) 2n/2 + bd
{ int a=x左边n/2位； // 移位操作，把X分为2块
int b=x右边n/2位；
int c=y左边n/2位； //移位操作，把Y分为2块
int d=y右边n/2位；
int m1= mult( a, c, n/2); // a, c还不够小继续分为2块,直到最后1×1位
int m2= mult( a-b, d-c, n/2);
int m3= mult( b, d, n/2);
mul=s*( m1*2n+(m1+m2+m3)*2n/2+m3 );
return mul;
} }

６、设计一棋盘覆盖问题算法（分治法）？ 并计算其时间复杂度？（要求写出递推公式，及其求解过程）
在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
（该算法中可能用到的变量：
　　tr ：棋盘中左上角方格所在行；　tc ：棋盘中左上角方格所在列。
　　dr： 残缺方块所在行；　　　　dl ：残缺方块所在列。
　　size:棋盘的行数或列数；　用二维数组board[ ][ ]，模拟棋盘。）
答：void chessBoard(int tr, int tc, int dr, int dc, int size)
{
if (size == 1) return; //size:棋盘行数
int t = tile++, // L型骨牌号
s = size/2; // 分割棋盘
// 覆盖左上角子棋盘
if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中
chessBoard(tr, tc, dr, dc, s);
else {// 此棋盘中无特殊方格
board[tr + s - 1][tc + s - 1] = t; // 用 t 号L型骨牌覆盖右下角
chessBoard(tr, tc, tr+s-1, tc+s-1, s);} // 覆盖其余方格
// 覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中
chessBoard(tr, tc+s, dr, dc, s);
else {// 此棋盘中无特殊方格
board[tr + s - 1][tc + s] = t; // 用 t 号L型骨牌覆盖左下角
chessBoard(tr, tc+s, tr+s-1, tc+s, s);} // 覆盖其余方格
// 覆盖左下角子棋盘
if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中
chessBoard(tr+s, tc, dr, dc, s);
else {
board[tr + s][tc + s - 1] = t; // 用 t 号L型骨牌覆盖右上角
chessBoard(tr+s, tc, tr+s, tc+s-1, s);} // 覆盖其余方格
// 覆盖右下角子棋盘
if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中
chessBoard(tr+s, tc+s, dr, dc, s);
else {
board[tr + s][tc + s] = t; // 用 t 号L型骨牌覆盖左上角
chessBoard(tr+s, tc+s, tr+s, tc+s, s);} // 覆盖其余方格
}

第三章动态规划算法
１、动态规划算法基本思想？ 动态规划算法与分治算法异同点？　　适合用动态规划算法求解问题的基本要素？　　动态规划算法的基本步骤？
答：1）基本思想：将待求解问题分解成若干个子问题；由于子问题有重叠，动态规划算法能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算.
2）相同：都是将原问题分解成小问题，通过小问题求解得到原问题解。
不同：
ü 用分治法求解时,分解的子问题是互相独立的,且与原问题类型一致。分治算法实现一般用递归；
ü 动态规划方法经分解得到的子问题往往不是互相独立的；动态规划算法实现一般用循环;
3）基本要素：具有最优子结构；子问题具有重叠性
4）步骤：1)分析最优解的性质，并刻划其结构特征。
2)递推地定义最优值。
3)以自底向上的方式计算出最优值.
4)根据计算最优值时得到的信息，构造问题的最优解.

２、序列X={X1，X2,…Xm }和 Y={Y1,Y2…Yn}的最长公共子序列为Z={Z1,Z2,…Zk}
用动态规划的方法求序列 X 和Y的最长公共子序列长度？
（要求按照动态规划写出动态规划求解问题的步骤分析①最优子结构②写出递归方程③算法描述）
注：C[ ｍ][ ｎ]记录序列X与Y的最长公共子序列的长度
答：①最优子结构
设序列X={ x1，x2，…xm } 与
序列Y={ y1，y2，…yn }的一个
最长公共子序列Z={ z1，z2，…zk }
Ⅰ、若xm= yn, 则zk=xm= yn, 且{ z1，z2，…zk-1 }是序列Xm-1与
序列Yn-1 的最长公共自序列；
Ⅱ、若xm≠yn, 且xm≠ zk, 则Z是Xm-1与Y的最长公共子序列；
Ⅲ、若xm≠yn, 且yn≠ zk, 则Z是X与Yn-1的最长公共子序列;

由此可见，2个序列的最长公共子序列包含了这2个序列的前缀（去掉一个元素）的最长公共子序列。 即，原问题最优解，包含子问题最优解；
因此，最长公共子序列问题具有最优子结构性质。
②写出递归方程

③循环实现，计算最优值C[ i][ j]，算法描述
Int lcsLength( x[ ], y[ ], b[ ][ ])
{ int m=x.length-1;
n=y.length-1;
for(int i=1; i<m;i++) C[i][0]=0; //y序列空
for(int i=1; i<n;i++) C[0][i]=0; //x序列空
for (int i = 1; i <= m; i++) //x序列长为ｍ
for (int j = 1; j <= n; j++)　　 //ｙ序列长为n
if (x[i]==y[j])
{ C[i][j]=C[i-1][j-1]+1; b[i][j]=1;}
else if (c[i-1][j]>=c[i][j-1])
{ C[i][j]=C[i-1][j]; b[i][j]=2;}
else
{ C[i][j]=C[i][j-1]; b[i][j]=3;}
return C[m][n];
}
u 时间复杂度分析：该算法时间复杂度：O(m*n)
④构造最长公共子序列，算法描述：
void LCS (char X[ i], Y[ j], int b[ ][ ])
{
if (i ==0 || j==0) return;
if (b[ i][ j]== 1)
{ LCS( X[ i-1], Y[ j-1], b);
system.out.print( x[ i] ); }

else if (b[ i][ j]== 2)
LCS(X[i-1]，Y[ j]，b);
else if (b[ i][ j]== 3)
LCS(X[ i] ，Y[j-1], b);
}
u 时间复杂度分析：
　此算法每一次递归调用使得i或j减１，因此该算法时间复杂度为O(m+n)

３、长江游艇俱乐部在长江上设置了n个游艇出租站1,2…n.
游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。
游艇出租站i到游艇出租站j之间的租金为r(i，j)，其中1<=i<j<=n；
试设计一个算法，计算出游艇从出租站1到出租站n所需最少租金？
（见习题集第三章算法设计与计算题T2）

4、掌握动态规划方法求解０－１背包问题？
答：①分析问题的最优解结构
设（y1,y2,…yn）所给0－1背包容量为M的解；
则，（y2,…yn）相应子问题背包容量为M－w1的解；
（即原问题最优解，包含了子问题最优解）
②递归定义最优值

③计算最优值m(i，j)
void knapsack( int v[ ], int w[ ], int M, int m[ ] [ ] )
{int n=v.length;
if ( M<w[ n] )　　　 // i=n时，只有１个物品　
m[ n][ M]=0;
else if (M>=w[ n])
{ m[ n][ M]=v[ n]; M=M-w[ n]; }
for( int i=n-1; i>=1; i--) // i<n时，xi…xn多个物品
{ if (M<w[ i])
m[ i] [M]=m[ i+1][ M];
else if (M>=w[ n])
{ m[ i][ M]=math.max( m[ i+1][ M], m[ i+1][M-w[ i]+v[i]);
M=M-w[ i]; }
}
}
u 该算法时间复杂度：O(c*n) 　　 c常数
④构造最优解
void trackack( int m[ ] [ ], int w[ ], int M, int x[ ] )
{//x[ i]标记i是否放入背包
int n=w.length;
for( int i=1; i<n; i++ ) //判断前n-1个物体是否放入背包
{ if (m[ i][ M]=m[ i+1][ M] ) x[ i]=0;
else
{ x[ i]=1; M=M-w[ i]; }
}
x[ n]=(m[ n][ M]>0)? 1:0 ; //判断第n个物体是否放入背包
}
u 该算法时间复杂度：O(n) 　　

第 4 章 贪心算法
1、 贪心算法基本思想？
答：从问题的初始解出发逐步逼近给定的目标，每一步都做出当前看来是最优的选择（贪心选择），最终得到整个问题的最优解

2、 贪心算法的基本要素？
答：贪心选择性； 最优子结构

3、 贪心算法与动态规划算法的异同?
答：1 ） 相同点：　对于要求解的问题都具有最优子结构；
2 ）不同点： 算法的基本思想不同；
　　 求解问题的类型不同；
　　　　例：普通背包问题　　贪心算法求解
　　　　　　0-1背包问题　　动态规划算法求解

4、设计普通背包装载问题的贪心算法? 并分析其时间复杂度？
答：
float greedy_knapsack ( float M, float w[ ], float p[ ], float x[ ] )
// M 背包载重 x[ ]背包问题最优解, w[ ]物品重量， P[ ]物品价值
{ int n=w.length; //n物品的个数
float pp=0; //pp计算当前背包总价值
float mm＝M; //mm背包剩余载重
for( int i=1;i<=n; i++ )
{ float ww[ i]= p[ i] / w[ i]； //计算物品单位价值ww[ ]
x[ i]=0; } //初始化，所有物品没有放入背包
Mergesort (w[ i ], ww[ i]，n ); //按单位价值将物品排序，便于贪心选择
for( int i=1; i<=n; i++ ) //贪心选择，总是选择价值最大放入背包
{ if ( w[ i]<=mm ) //当前物品小于背包剩余载重
{ x[ i]=1; mm=mm - w[ i]; pp=pp + p[ i]; } //整个放入背包
else { x[ i]=mm/w[ i]; pp=pp + x[ i]*p[ i]; break; } //i部分放入背包
}
return pp;
}
该算法主要包括以下几部分：
Ø 计算物品单位价值时间，其时间复杂度O(n)；
Ø 按照物品单位价值排序时间，其时间复杂度为O(n*logn);　　　(合并排序时间)
Ø 贪心选择时间，其时间复杂度为O(n)；
故该算法的时间复杂度为：O(n*logn+2n)； 记为： O(n*logn)

5、设计找零问题的贪心算法? 并分析其时间复杂度？
答：void greedy_zhaoling ( float GZ, int B[ ], int S[ ] )　 //GZ应发工资
{ B[ j]初始化排序；　　//为了贪心选择，依次选最大币种
for( j=1, j<=6;j++)
{ S[ j]=0； //初始化S[ j]
　　 A=GZ/B[ j]; //A表示对应j币种张数
S[ j]=A; //S[ j]存放对应j币种总张数
GZ=GZ-A*B[ j]; }
//每求出一种面额所需的张数后， 一定要把这部分金额减去：
for(i=1;i<=6;i++)
print( B[ i], “----”, S[ i]); //输出币种和对应张数
}

6、设计活动安排问题的贪心算法? 并分析其时间复杂度？
答：伪代码：
Int greedyselector(int s[ ], int f[ ], boolean a[ ])
{int n=s.length; //n活动的个数 ；a[ ]按活动结束时间递增排序；//便于贪心选择
a[1]=true; //活动１被选中
int j=1; //j记录最近加入活动集合A的活动j
int count=1; //count存储相容活动个数
for(int i=2; i<=n; i++)//贪心选择从活动j=2…n判是否可加入A
{ if( 活动i的开始时间，大于　最近活动j的结束时间 )
{将活动i加入活动集合A；
　 j=i; 　　//活动i作为最近加入活动集合A的最近活动
count++; }
else
活动i不加入活动集合A；}
return count;
}
程序设计语言：
Int greedyselector(int s[ ], int f[ ], boolean a[ ])
{ int n=s.length; //n活动的个数
Mergesort (a[ ],f[ ], n ); //按活动结束时间排序，便于贪心选择
a[1]=true; //活动１被选中
int j=1; //j记录最近依次加入活动集合A的活动j
int count=1; //count存储相容活动个数
for(int i=2; i<=n; i++) //贪心选择从活动i=2…n判是否可加入A
{ if( s[ i]>=f[ j] )
{ a[ i]=true; //将活动i加入活动集合A
j=i; //活动i作为最近加入活动集合A的最近活动
count++; }
else a[ i]=false; // s[ i]<f[ j], 活动i不加入活动集合A
}
return count;
}
该算法主要包括２部分：
Ø 按照按活动结束时间对活动排序时间，其时间复杂度为：O(n*logn)；
Ø 贪心选择时间，其需要经过n-1次的比较（s[ i]>=f[ j]）
时间复杂度为：O(n-1);
故本算法的时间复杂度： O(n*logn＋n-1)；
记为： O(n*logn)。

7、掌握例dijkstra算法的求单源最短路径问题。　　　　　算法设计？求解过程？
答:
void dijkstra (int v, float a[][], float dist[])
{ //v表示源,a[i][j]表示边i到j的权值
//dist[i]记录源到顶点i的最短路径长度
　//prev[i]记录顶点i的前一个点,可以找出最短路径
int n=dist.length;
boolean s[ ]; //s[i]标记顶点i是否加入顶点集合s
if( v<1 || v>n) return; //源点v不存在
for(int i=1;i<=n;i++)
{ dist[i]=a[v][i]; //初始化数组dist[i]、s[i]
s[i]=false;
　　if(dist[i]=max-value) //源到顶点i没有边
prev[i]=0;
else prev[i]=v; }
dist[v]=0; s[v]=true; //把源v加入到集合s中
for(int i=1; i<n; i++)　//剩下n-1个顶点，每次选择一个加入s中
{float temp＝max-value;
int u=v;
for(int j=1;j<=n;j++)
　　　　//贪心选择，计算V-S中顶点的dist[ ]值，选择最小的那个顶点j
if( (!s[j]) &&(dist[j]<temp) )
{ u=j; temp=dist[j]; }
s[u]=true; /