天津商业大学信息工程学院算法分析与设计实验指导书杨亮2011/3/1目录实验1：大整数运算（分治策略） (1)程序1-1. 未使用分治策略 (2)程序1-2. 使用分治策略 (3)实验2：最长公共子序列（动态规划） (5)程序2-1 自底向上方法 (6)实验3：图的最小生成树（贪心策略） (9)程序3-1 Kruskal算法 (13)程序3-2 Prim算法 (16)实验4：八皇后问题（解空间搜索方法） (19)程序4-1 回溯法与剪枝 (20)实验1：大整数运算（分治策略）实验目的：通过大整数相乘的算法实现来加深对分治策略的了解。
技术描述：在大整数相乘的算法中，如果不使用分之策略所需的时间复杂度为O(n2)，而使用了动态规划思想进行重新设计后时间复杂度可以降低到O(n1.59)。
时间：100分钟实验内容：编程完成相应的大整数加法，普通乘法和使用分治策略设计的大整数乘法，比较其相应的性能差别，并完成实验报告。
算法描述：设X和Y都是n位的二进制整数，现在要计算它们的乘积XY。
我们可以用小学所学的方法来设计一个计算乘积XY的算法，但是这样做计算步骤太多，显得效率较低。
如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要作O(n2)步运算才能求出乘积XY。
下面我们用分治法来设计一个更有效的大整数乘积算法。
图1-1 大整数X和Y的分段我们将n位的二进制整数X和Y各分为2段，每段的长为n/2位(为简单起见，假设n是2的幂)，如图6-3所示。
由此，X=A2n/2+B ，Y=C2n/2+D。
这样，X和Y的乘积为：XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD (1)如果按式(1)计算XY，则我们必须进行4次n/2位整数的乘法(AC，AD，BC和BD)，以及3次不超过n位的整数加法(分别对应于式(1)中的加号)，此外还要做2次移位(分别对应于式(1)中乘2n和乘2n/2)。
所有这些加法和移位共用O(n)步运算。
设T(n)是2个n位整数相乘所需的运算总数，则由式(1)，我们有:(2)由此可得T(n)=O(n2)。
因此，用(1)式来计算X和Y的乘积并不比小学生的方法更有效。
要想改进算法的计算复杂性，必须减少乘法次数。
为此我们把XY写成另一种形式:XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD (3)虽然，式(3)看起来比式(1)复杂些，但它仅需做3次n/2位整数的乘法(AC，BD和(A-B)(D-C))，6次加、减法和2次移位。
由此可得:(4)用解递归方程的套用公式法马上可得其解为T(n)=O(n log3)=O(n1.59) 程序1-1. 未使用分治策略#include <stdio.h>#include <string.h>#define MAX_LEN 200unsigned an1[MAX_LEN+10];unsigned an2[MAX_LEN+10];unsigned aResult[MAX_LEN* 2 + 10];char szLine1[MAX_LEN+10];char szLine2[MAX_LEN+10];int main(){gets( szLine1); //gets函数读取一行gets( szLine2);int i, j;int nLen1 = strlen( szLine1);memset( an1, 0, sizeof(an1));memset( an2, 0, sizeof(an2));memset( aResult, 0, sizeof(aResult));j = 0;for( i = nLen1 - 1;i >= 0 ; i --)an1[j++] = szLine1[i] - '0';int nLen2 = strlen(szLine2);j = 0;for( i = nLen2 - 1;i >= 0 ; i --)an2[j++] = szLine2[i] - '0';//每一轮都用an1的一位，去和an2各位相乘，从an1的个位开始for( i = 0;i < nLen2; i ++ ) {//用选定的an1的那一位，去乘an2的各位for( j = 0; j < nLen1; j ++ )//两数第i, j位相乘，累加到结果的第i+j位aResult[i+j] += an2[i]*an1[j];}//下面的循环统一处理进位问题int nHighestPos = 0;for( i = 0; i < MAX_LEN * 2; i ++ ){if( aResult[i] >= 10 ) {aResult[i+1] += aResult[i] / 10;aResult[i] %= 10;}if( aResult[i] ) n HighestPos = i;}for( i = nHighestPos; i >= 0; i --)printf("%d", aResult[i]);return 0;}程序1-2. 使用分治策略#include <iostream.h>#include <math.h>long mult(long x,long y,int n);int num(long x);void main() //主函数{long x,y;cout<<"input x and y:"<<endl;cin>>x>>y;cout<<mult(x,y,num(x))<<endl;}long mult(long x,long y,int n){long a,b,c,d,s;if (n==1) //起初这里落了个＝号return x*y;else{a=long(x/pow(10,(n/2))); //取x的左半部分b=long(x%long(pow(10,(n/2)))); //取x的右半部分c=long(y/pow(10,(n/2))); //取y的左半部分d=long(y%long(pow(10,(n/2)))); //取y的右半部分s=mult(a,c,n)*pow(2,n)+(mult((a-b),(d-c),n)+mult(a,c,n)+mult(b,d,n))*pow(2,n/2)+mult(b,d,n); //书上的公式return (s);}}int num(long x) //判断输入的数字的位数{int i=0;if(x-9<=0)return 1;else{while (x!=0){i++;x=x/10;}return i;}}实验2：最长公共子序列（动态规划）实验目的：通过对最长公共子序列的编程实现，增强对动态规划方法的了解。
技术描述：在最优化问题的求解过程中，通常会出现大量重复计算问题，当遇到此类问题的时候，如果我们又可以容易的找到它的最优子结构，那么就可以尝试使用动态规划方法求解，动态规划方法中可以使用自底向上法和自顶向下记录法两种方法来减少重复的运算量，从而达到提高运算效率的目的。
时间：100分钟实验内容：编程用动态规划的自底向上的方法求解两个序列的最长公共子序列问题。
算法描述：求两字符序列的最长公共字符子序列，并完成实验报告。
问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。
令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。
例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。
不难证明有以下性质：（1）如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列；（2）如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列；（3）如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。
这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。
求解：引进一个二维数组c[][]，用c[i][j]记录X[i]与Y[j] 的LCS 的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。
我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[i][j-1]均已计算出来。
此时我们根据X[i] = Y[j]还是X[i] != Y[j]，就可以计算出c[i][j]。
问题的递归式写成：回溯输出最长公共子序列过程：算法分析：由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。
返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m + n)。
程序2-1 自底向上方法#include <stdio.h>#include <string.h>#define MAXLEN 100void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])...{int i, j;for(i = 0; i <= m; i++)c[i][0] = 0;for(j = 1; j <= n; j++)c[0][j] = 0;for(i = 1; i<= m; i++)...{for(j = 1; j <= n; j++)...{if(x[i-1] == y[j-1])...{c[i][j] = c[i-1][j-1] + 1;b[i][j] = 0;}else if(c[i-1][j] >= c[i][j-1])...{c[i][j] = c[i-1][j];b[i][j] = 1;}else...{c[i][j] = c[i][j-1];b[i][j] = -1;}}}}void PrintLCS(int b[][MAXLEN], char *x, int i, int j) ...{if(i == 0 || j == 0)return;if(b[i][j] == 0)...{PrintLCS(b, x, i-1, j-1);printf("%c ", x[i-1]);}else if(b[i][j] == 1)PrintLCS(b, x, i-1, j);elsePrintLCS(b, x, i, j-1);}int main(int argc, char **argv)...{char x[MAXLEN] = ...{"ABCBDAB"};char y[MAXLEN] = ...{"BDCABA"};int b[MAXLEN][MAXLEN];int c[MAXLEN][MAXLEN];int m, n;m = strlen(x);n = strlen(y);LCSLength(x, y, m, n, c, b);PrintLCS(b, x, m, n);return 0;}实验3：图的最小生成树（贪心策略）实验目的：通过编程实现最小生成树，增强对贪心策略的理解 。
