常用算法设计方法+搜集.doc

1、1 常用算法设计方法 要使计算机能完成人们预定的工作，首先必须为如何完成预定的工作设计一个算法， 然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描 述，其中程序的数据结构和变量用来描述问题的对象，程序结构、函数和语句用来描述问 题的算法。算法数据结构是程序的两个重要方面。 算法是问题求解过程的精确描述，一个算法由有限条可完全机械地执行的、有确定结 果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令 所描述的顺序执行算法的指令能在有限的步骤内终止，或终止于给出问题的解，或终止于 指出问题对此输入数据无解。 通常求解一个问题可能会有多种算法

2、可供选择，选择的主要标准是算法的正确性和可 靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 算法设计是一件非常困难的工作，经常采用的算法设计技术主要有迭代法、穷举搜索 法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计 和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。 (下载源码就到源码网: ） 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为 f(x)=0， 用某种数学方法导出等价的形式 x=g(x)，然后按以下步骤执行： （1） 选一个方程的近似根，赋给变量 x0； （2） 将 x0 的值保存于变量

3、x1，然后计算 g(x1)，并将结果存于变量 x0； （3） 当 x0 与 x1 的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的 x0 就 认为是方程的根。上述算法用 C 程序的形式表示为： 【算法】迭代法求方程的根 x0=初始近似根； do x1=x0； x0=g(x1)； /*按特定的方程计算新的近似根 */ while ( fabs(x0-x1)Epsilon)； printf(“方程的近似根是%fn”，x0)； 迭代算法也常用于求方程组的根，令 X=（x 0，x 1，x n-1） 设方程组为： xi=g

4、i(X) (I=0， 1，n-1) 则求方程组根的迭代算法可描述如下： 2 【算法】迭代法求方程组的根 for (i=0;iEpsilon)； for (i=0;i*ptj-1) break; if (j=0) break; for (i=VARIABLES-1;i=j;i-) if (*pti*pti-1) break; t=*ptj-1;* ptj-1 =* pti; *pti=t; for (i=VARIABLES-1;ij;i-,j+) t=*ptj; *ptj =* pti; *pti=t; 从上述问题解决的方法中，最重要的因素就是确定某种方法来确定所有的候选解。下 面再用一个示例来

5、加以说明。( 下载源码就到源码网: ） 【问题】 背包问题 问题描述：有不同价值、不同重量的物品 n 件，求从这 n 件物品中选取一部分物品的 选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。 设 n 个物品的重量和价值分别存储于数组 w 和 v 中，限制重量为 tw。考虑一个 n 元组（x 0，x 1，x n-1） ，其中 xi=0 表示第 i 个物品没有选取，而 xi=1 则表示第 i 个物品 被选取。显然这个 n 元组等价于一个选择方案。用枚举法解决背包问题，需要枚举所有的 5 选取方案，而根据上述方法，我们只要枚举所有的 n 元组，就可以得到问题的解。 显然

6、，每个分量取值为 0 或 1 的 n 元组的个数共为 2n 个。而每个 n 元组其实对应了一 个长度为 n 的二进制数，且这些二进制数的取值范围为 02 n-1。因此，如果把 02 n-1 分 别转化为相应的二进制数，则可以得到我们所需要的 2n 个 n 元组。 【算法】 maxv=0; for (i=0;i1) return fib(n-1)+fib(n-2); 递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为 n）的求解推到比原问题简单一些的问题（规模小于 n）的求解。例如上例中，求解 fib(n)， 把它推到求解 fib(n-1)和 fib(n-2)。也就是说，

7、为计算 fib(n)，必须先计算 fib(n-1)和 fib(n-2)， 而计算 fib(n-1)和 fib(n-2)，又必须先计算 fib(n-3)和 fib(n-4)。依次类推，直至计算 fib(1)和 fib(0)，分别能立即得到结果 1 和 0。在递推阶段，必须要有终止递归的情况。例如在函数 fib 中，当 n 为 1 和 0 的情况。 在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如 得到 fib(1)和 fib(0)后，返回得到 fib(2)的结果，在得到了 fib(n-1)和 fib(n-2)的结果后， 返回得到 fib(n)的结果。 在编写递归函数时要

8、注意，函数中的局部变量和参数知识局限于当前调用层，当递推 进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问 题”层，它们各有自己的参数和局部变量。 由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行 效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。 例如上例计算斐波那契数列的第 n 项的函数 fib(n)应采用递推算法，即从斐波那契数列的前 两项出发，逐次由前两项计算出下一项，直至计算出要求的第 n 项。 8 【问题】 组合问题 问题描述：找出从自然数 1、2、n 中任取 r 个数的所有组合。例如 n=5，r

9、=3 的 所有组合为： （1）5、4、3 （2）5、4、2 （3）5、4、1 （4）5、3、2 （5）5、3、1 （6）5、2、1 （7）4、3、2 （8）4、3、1 （9）4、2、1 （10）3、2、1 分析所列的 10 个组合，可以采用这样的递归思想来考虑求组合函数的算法。设函数为 void comb(int m,int k)为找出从自然数 1、2、m 中任取 k 个数的所有组合。当组合 的第一个数字选定时，其后的数字是从余下的 m-1 个数中取 k-1 数的组合。这就将求 m 个 数中取 k 个数的组合问题转化成求 m-1 个数中取 k-1 个数的组合问题。设函数引入工作数 组 a 存放

10、求出的组合的数字，约定函数将确定的 k 个数字组合的第一个数字放在 ak中， 当一个组合求出后，才将 a 中的一个组合输出。第一个数可以是 m、m-1、k，函 数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元素， 继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见以下程序中的函 数 comb。 【程序】 # include # define MAXN 100 int aMAXN; void comb(int m,int k) int i,j; for (i=m;i=k;i-) ak=i; if (k1) comb(i-1,k-1); else for

11、(j=a0;j0;j-) printf(“%4d”,aj); printf(“n”); void main() a0=3; comb(5,3); 【问题】 背包问题 问题描述：有不同价值、不同重量的物品 n 件，求从这 n 件物品中选取一部分物品的 选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。 9 设 n 件物品的重量分别为 w0、w 1、w n-1，物品的价值分别为 v0、v 1、v n-1。采 用递归寻找物品的选择方案。设前面已有了多种选择的方案，并保留了其中总价值最大的 方案于数组 option ，该方案的总价值存于变量 maxv。当前正在考察新方案，其物

12、品选择 情况保存于数组 cop 。假定当前方案已考虑了前 i-1 件物品，现在要考虑第 i 件物品；当 前方案已包含的物品的重量之和为 tw；至此，若其余物品都选择是可能的话，本方案能达 到的总价值的期望值为 tv。算法引入 tv 是当一旦当前方案的总价值的期望值也小于前面方 案的总价值 maxv 时，继续考察当前方案变成无意义的工作，应终止当前方案，立即去考 察下一个方案。因为当方案的总价值不比 maxv 大时，该方案不会被再考察，这同时保证 函数后找到的方案一定会比前面的方案更好。 对于第 i 件物品的选择考虑有两种可能： （1） 考虑物品 i 被选择，这种可能性仅当包含它不会超过方案总重

13、量限制时才是 可行的。选中后，继续递归去考虑其余物品的选择。 （2） 考虑物品 i 不被选择，这种可能性仅当不包含物品 i 也有可能会找到价值更 大的方案的情况。 按以上思想写出递归算法如下： try(物品 i，当前选择已达到的重量和，本方案可能达到的总价值 tv) /*考虑物品 i 包含在当前方案中的可能性*/ if(包含物品 i 是可以接受的) 将物品 i 包含在当前方案中； if (i=0 if (pos=0) void main() int i; for (i=1;inext) if (j-remainder=ai) break; if (j=NULL) j=(HNODE *)mall

14、oc(sizeof(HNODE); j-remainder=box_volume-ai; j-head=NULL; if (box_h=NULL) box_h=box_t=j; else box_t=boix_t-next=j; j-next=NULL; box_count+; else j-remainder-=ai; for (q=j-next;q!=NULLq=q-link); if (q=NULL) p-link=j-head; j-head=p; else p-link=NULL; q-link=p; printf(“共使用了%d 只箱子”，box_count); printf(“各

15、箱子装物品情况如下：”); for (j=box_h,i=1;j!=NULL;j=j-next,i+) printf(“第%2d 只箱子，还剩余容积%4d ，所装物品有；n”,I,j-remainder); for (p=j-head;p!=NULL;p=p-link) printf(“%4d”,p-vno+1); printf(“n”); 【问题】 马的遍历 30 问题描述：在 88 方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每 一格并且只经过一次的一条路径。 马在某个方格，可以在一步内到达的不同位置最多有 8 个，如图所示。如用二维数组 board 表示棋盘，其元素记录马经过

16、该位置时的步骤号。另对马的 8 种可能走法（称为 着法）设定一个顺序，如当前位置在棋盘的（i，j ）方格，下一个可能的位置依次为 （i+2，j+1） 、 （i+1，j+2 ） 、 （i-1，j+2 ） 、 （i-2，j+1） 、 （i-2，j-1） 、 （i-1，j-2） 、 （i+1，j-2） 、 （i+2，j-1） ，实际可以走的位置尽限于还未走过的和不越出边界的那些位置。为便于程序 的同意处理，可以引入两个数组，分别存储各种可能走法对当前位置的纵横增量。 4 3 5 2 马 6 1 7 0 对于本题，一般可以采用回溯法，这里采用 Warnsdoff 策略求解，这也是一种贪婪法， 其选择下

17、一出口的贪婪标准是在那些允许走的位置中，选择出口最少的那个位置。如马的 当前位置（i，j）只有三个出口，他们是位置（i+2，j+1 ） 、 （i-2，j+1 ）和（i-1 ，j-2） ，如分 别走到这些位置，这三个位置又分别会有不同的出口，假定这三个位置的出口个数分别为 4、2、3，则程序就选择让马走向（i-2，j+1）位置。 由于程序采用的是一种贪婪法，整个找解过程是一直向前，没有回溯，所以能非常快 地找到解。但是，对于某些开始位置，实际上有解，而该算法不能找到解。对于找不到解 的情况，程序只要改变 8 种可能出口的选择顺序，就能找到解。改变出口选择顺序，就是 改变有相同出口时的选择标准。以

18、下程序考虑到这种情况，引入变量 start，用于控制 8 种 可能着法的选择顺序。开始时为 0，当不能找到解时，就让 start 增 1，重新找解。细节以 下程序。 【程序】 # include int delta_i =2,1,-1,-2,-2,-1,1,2; int delta_j =1,2,2,1,-1,-2,-2,-1; int board88; int exitn(int i,int j,int s,int a ) int i1,j1,k,count; for (count=k=0;k=0 return count; 31 int next(int i,int j,int s) in

19、t m,k,mm,min,a8,b8,temp; m=exitn(i,j,s,a); if (m=0) return 1; for (min=9,k=0;km。然而，这样选取分割点 m，有可能造成划分出的子集 S1 和 S2 的不平衡。例如在最 坏情况下，|S 1|=1，|S 2|=n-1，由此产生的分治法在最坏情况下所需的计算时间 T（ n） 应满 足递归方程： T（ n） =T（ n-1） +O（ n） 它的解是 T（ n） =O（ n2） 。这种效率降低的现象可以通过分治法中“平衡子问题”的 方法加以解决。也就是说，我们可以通过适当选择分割点 m，使 S1 和 S2 中有大致相等个 数的

20、点。自然地，我们会想到用 S 的 n 个点的坐标的中位数来作分割点。在选择算法中介 绍的选取中位数的线性时间算法使我们可以在 O（ n） 时间内确定一个平衡的分割点 m。 至此，我们可以设计出一个求一维点集 S 中最接近点对的距离的算法 pair 如下。 Float pair（S）; if | S | =2 = | x2x1 | /*x1n存放的是 S 中 n 个点的坐标*/ else if ( | S | =1) = 37 else m=S 中各点的坐标值的中位数 ; 构造 S1 和 S2，使 S1=xS | xm，S2=xS | xm; 1=pair(S1); 2=pair(S2); p=

21、max(S1); q=min(S2); =min(1，2， q-p); return(); 由以上的分析可知，该算法的分割步骤和合并步骤总共耗时 O(n)。因此，算法耗费的 计算时间 T(n)满足递归方程： 解此递归方程可得 T(n)=O(nlogn)。 【问题】循环赛日程表 问题描述：设有 n=2k 个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛 日程表： （1）每个选手必须与其他 n-1 个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在 n-1 天内结束。 请按此要求将比赛日程表设计成有 n 行和 n-1 列的一个表。在表中的第 i 行，第 j 列处 填入第 i

22、 个选手在第 j 天所遇到的选手。其中 1in，1j n-1。 按分治策略，我们可以将所有的选手分为两半，则 n 个选手的比赛日程表可以通过 n/2 个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下 两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 2 1 4 3 6 7 8 5 3 4 1 2 7 8 5 6 1 2 3 4 3 2 1 8 5 6 7 1 2 3 4 5 6 7 8 1 4 3 2 1 2 1 4 3 6 5 8 7 2 1 4 3 1 2 3 4 1

23、2 7 8 5 6 3 2 1 4 38 2 1 4 3 2 1 8 7 6 5 4 3 2 1 （1） （2） （3） 图 1 2 个、4 个和 8 个选手的比赛日程表 图 1 所列出的正方形表（3）是 8 个选手的比赛日程表。其中左上角与左下角的两小块 分别为选手 1 至选手 4 和选手 5 至选手 8 前 3 天的比赛日程。据此，将左上角小块中的所 有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角， 这样我们就分别安排好了选手 1 至选手 4 和选手 5 至选手 8 在后 4 天的比赛日程。依此思 想容易将这个比赛日程表推广到具有任意多个选手的情形。 八、动

24、态规划法 经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简 单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗 时会按问题规模呈幂级数增加。 为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把 所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。以下先用实例说明 动态规划方法的使用。 【问题】 求两字符序列的最长公共字符子序列 问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干 个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列 X=“x0，x 1， ，x m-1”，序列

25、 Y=“y0，y 1，y k-1”是 X 的子序列，存在 X 的一个严格 递增下标序列，使得对所有的 j=0，1， ，k-1 ，有 xij=yj。例如， X=“ABCBDAB”，Y=“BCDB ”是 X 的一个子序列。 给定两个序列 A 和 B，称序列 Z 是 A 和 B 的公共子序列，是指 Z 同是 A 和 B 的子序 列。问题要求已知两序列 A 和 B 的最长公共子序列。 如采用列举 A 的所有子序列，并一一检查其是否又是 B 的子序列，并随时记录所发现 的子序列，最终求出最长公共子序列。这种方法因耗时太多而不可取。 考虑最长公共子序列问题如何分解成子问题，设 A=“a0，a 1，a m-

26、1”， B=“b0，b 1， ，b m-1”，并 Z=“z0，z 1，z k-1”为它们的最长公共子序列。不难证明有 以下性质： （1） 如果 am-1=bn-1，则 zk-1=am-1=bn-1，且“z 0，z 1，z k-2”是“a 0，a 1，a m-2”和 “b0，b 1，b n-2”的一个最长公共子序列； （2） 如果 am-1!=bn-1，则若 zk-1!=am-1，蕴涵“z 0，z 1，z k-1”是“a 0，a 1，a m-2”和 “b0，b 1，b n-1”的一个最长公共子序列； （3） 如果 am-1!=bn-1，则若 zk-1!=bn-1，蕴涵“z 0，z 1，z k-1

27、”是“a 0，a 1，a m-1”和 “b0，b 1，b n-2”的一个最长公共子序列。 这样，在找 A 和 B 的公共子序列时，如有 am-1=bn-1，则进一步解决一个子问题，找 “a0，a 1，a m-2”和“b 0，b 1，b m-2”的一个最长公共子序列；如果 am-1!=bn-1，则要 解决两个子问题，找出“a 0，a 1，a m-2”和“b 0，b 1， ，b n-1”的一个最长公共子序列 39 和找出“a 0，a 1，a m-1”和“b 0，b 1，b n-2”的一个最长公共子序列，再取两者中较 长者作为 A 和 B 的最长公共子序列。 定义 cij为序列“a 0，a 1，a

28、i-2”和“b 0，b 1，b j-1”的最长公共子序列的长度， 计算 cij可递归地表述如下： （1）cij=0 如果 i=0 或 j=0； （2）cij= ci-1j-1+1 如果 I，j0，且 ai-1=bj-1； （3）cij=max （cij-1 ， ci-1j） 如果 I，j0，且 ai-1!=bj-1。 按此算式可写出计算两个序列的最长公共子序列的长度函数。由于 cij的产生仅依 赖于 ci-1j-1、ci-1j 和 cij-1，故可以从 cmn开始，跟踪 cij的产生过程，逆向 构造出最长公共子序列。细节见程序。 # include # include # define N 1

29、00 char aN,bN,strN; int lcs_len(char *a, char *b, int c N) int m=strlen(a), n=strlen(b), i,j; for (i=0;i0) if (cij=ci-1j) i-; else if (cij=cij-1) j-; else s-k=ai-1; i-; j-; return s; 40 void main() printf (“Enter two string（=2ai。 （2）因在 ai0 的所有堆中，薄片数最多的堆 在平分过程中被它的相邻堆取走的薄片数也 最多。在用策略（1）搜索移动时，当发生没有满足条件（1）的可移走薄片的堆时，采用 本策略，让在 ai0 的所有堆中，薄片数最多的堆被它的相邻堆取走它的全部薄片。