算法设计与分析.doc

. .算法分析与设计20132014年度 第1学期课程学习报告院系：学号： ： 任课教师： 成绩评定： 完成日期：2013年 12月 30 日第一章 递归与分治在任何可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，解题所需要的计算时间也就越少从而比较容易处理。要想直接解决一个较大的问题，有时是相当困难的。分治法的设计思想是，讲一个难以解决的大问题，分割成规模较小的相同问题，以便各个击破，分而治之。如果原问题可分割成k个子问题，1kn，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分之手段，可以使子问题与原问题的类型一致而其规模却不断缩小，最终使子问题缩小到很容易求出其解。由此自然导出递归算法。并以其为基础，可以产生了许多高效算法。1.1递归的概念直接或间接的调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。在计算机算法设计与分析中，递归技术是十分有用的。使用递归技术往往使函数的定义和算法的描述简洁且易于理解。1.1.1整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1n2nk1，k1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。(1) q(n,1)=1,n³1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即(2) q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。(3) q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。(4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1n-1 的划分组成。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。据此，设计计算去q（n，m）的递归算法如下。public static 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;return q(n,m-1)+q(n-m,m) ;1.1.2递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。1.2分治法的基本思想分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。1.2.1分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。分治法的基本步骤divide-and-conquer(P) if ( | P | <= n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i<=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。1.3 问题描述在一个2k×2k （k0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4k种，因而有4k种不同的棋盘，所示是k=2时16种棋盘中的一个。棋盘覆盖问题（chess cover problem）要求用4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。 用递归与分治求解下面算法中，用整数型数组board表示棋盘。board00是棋盘的左上角方格。tile是算法中的一个全局整形变量，用来表示L型骨牌的编号，其初始值为0.算法的输入参数如下：tr：棋盘左上角方格的行号；tc：棋盘左上角方格的列号；dr：特殊方格所在的行号；size：，棋盘规格为2k×2k。设T(k)是算法chessBoard覆盖一个2k×2k棋盘所需要的时间。从算法的分割策略可知，T（k）满足如下递归方程解此递归方程可得T(K)=O()。由于覆盖2k×2k棋盘所需要的L型骨牌个数为（）/3，故此算法是一个在渐进意义下最优的算法。 程序代码如下所示：public void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr < tr + s && dc < tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t; / 覆盖其余方格 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 / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角 boardtr + s - 1tc + s = t; / 覆盖其余方格 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 / 用 t 号L型骨牌覆盖右上角 boardtr + stc + s - 1 = t; / 覆盖其余方格 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 / 用 t 号L型骨牌覆盖左上角 boardtr + stc + s = t; / 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 1.4课后习题设有N个运动员要进行网球循环赛，设计一个满足以下要求的比赛日程表（1） 每个选手必须与其他n-1个选手各赛一次（2） 每个选手一天只能赛一次（3） 当n 是偶数，循环赛进行n-1天，当n是奇数，循环赛进行n天分治策略：我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直选手的到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。代码部分#include<stdlib.h>#include<stdio.h>int *A; /int *指针数组，int *schedule; /int数组，一维数组保存二维数组的数据int N =1; /问题的规模。初始化时会设定/isodd:判断x是否奇数，是则返回1，否则0int isodd(int x) return x&1;/print:打印赛程void print() int i,j, row, col; if(isodd(N) row=N; col=N+1; else row=N; col=N; printf("第1列是选手编号n"); for(i=0;i<row; i+) for(j=0;j<col; j+) printf("%4d", Aij); printf("n"); /*init：初始化，设置问题规模N值，分配内存，用schedule指向； 把A构造成一个二维数组*/void init() int i, n; char line100='0' printf("请输入选手人数："); fgets(line,sizeof(line), stdin); N=atoi(line); if(N<=0) exit(-1); if(isodd(N) n=N+1; else n=N; /schedule是行化的二维数组 schedule=(int *)calloc(n*n, sizeof(int); A=(int *)calloc(n, sizeof(int *); if(!schedule | A=NULL) exit(-2); for(i=0;i<n;i+) /把A等价为二维数组 Ai=schedule+i*n; Ai0=i+1;/初始化这个数组的第一列 return;/*replaceVirtual:把第m号虚的选手去掉（换做0）*/void replaceVirtual(int m) int i,j; for(i=0;i<m-1;i+) /行：对应选手号1m-1 for (j=0;j<=m;j+) /列: 比行要多1 Aij = (Aij=m)?0:Aij; return;/*copyeven:m为偶数时用,由前1组的m位选手的安排，来构成第2组m位选手 的赛程安排，以及两组之间的比赛安排 */void copyeven(int m) if(isodd(m) return; int i,j; for (j=0;j<m;j+) /1. 求第2组的安排（+m） for (i=0;i<m;i+) Ai+mj=Aij+m; for (j=m;j<2*m;j+)/两组间比赛的安排 for (i=0;i<m;i+) /2. 第1组和第2组 Aij=Ai+mj-m; /把左下角拷贝到右上角 for (i=m;i<2*m;i+) /3. 对应的，第2组和第1组 Aij=Ai-mj-m; /把左上角拷贝到右下角 return;/*copyodd:m为奇数时用,由前1组的m位选手的安排，来构成第2组m位选手 的赛程安排，以及两组之间的比赛安排。这时和m为偶数时的 处理有区别。*/void copyodd(int m) int i,j; for (j=0;j<=m;j+) /1. 求第2组的安排(前m天) for (i=0;i<m;i+)/行 if (Aij!=0) Ai+mj=Aij+m; else /特殊处理：两个队各有一名选手有空，安排他们比赛 Ai+mj = i+1; Aij = i+m+1; /安排两组选手之间的比赛(后m-1天)/ for(i=0,j=m+1;j<2*m;j+) Aij = j+1; /2. 1号选手的后m-1天比赛 A (Aij -1) j = i+1; /3. 他的对手后m-1天的安排 /以下的取值要依赖于1号选手的安排，所以之前先安排1号的赛程 for (i=1;i<m;i+) /第1组的其他选手的后m-1天的安排 for (j=m+1;j<2*m;j+) /2. 观察得到的规则一：向下m+12*m循环递增 Aij = (Ai-1j+1)%m=0)?Ai-1j+1 :m + (Ai-1j+1)%m; /3. 对应第2组的对手也要做相应的安排 A (Aij-1) j = i+1; return;/*makecopy:当前有m位（偶数）选手，分成两组，每组由m/2位选手构成 由第一组的m/2位选手的安排来构成第二组的比赛安排，第一 组与第二组的比赛安排。要区分m/2为奇数和偶数两种情况*/void makecopy(int m) if (isodd(m/2) /m/2为奇数 copyodd(m/2); else /m/2为偶数 copyeven(m/2);void tournament(int m) if(m=1) A00=1; return ; else if(isodd(m) /如果m为奇数，则m+1是偶数 tournament(m+1); /按照偶数个选手来求解 replaceVirtual(m+1); /然后把第m+1号虚选手置成0 return ; else /m是偶数， tournament(m/2); /则先安排第1组的m/2人比赛 makecopy(m); /然后根据算法，构造左下、右下、右上、右下的矩阵 return ;/*endprogram:回收分配的内存*/void endprogram() free(schedule); free(A); int main() init(); /初始化 tournament(N);/求解 print(); /打印结果 endprogram(); /回收内存 return 0;第二章 动态规划动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费过多的时间。在用分治法求解时，有些子问题被重复计算了许多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算。为了达到此目的，可以用一个表来记录所有已解决的子问题的答案。这就是动态规划法的基本思想。2.1动态规划算法的基本要素2.1.1最优子结构矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。2.1.2 重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。2.2实例分析 2.2.1 计算最优值对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有 由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。用动态规划法求最优解public static void matrixChain(int p, int m, int s) int n=p.length-1; for (int i = 1; i <= n; i+) mii = 0; for (int r = 2; r <= n; r+) for (int i = 1; i <= n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k < j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t < mij) mij = t; sij = k; 2.2.2 0-1 背包问题 给定 n 种物品和一背包。 物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包中物品，使得装入背包中物品的总价值最大？设(y1,y2,.,yn)是所给0-1背包问题的一个最优解，则(y2,y3,.,yn)是经过一次选择后的0-1背包问题的最优解。0-1背包问题的递归关系，设当前子问题的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为i,i+1,.,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式：当i= n时，若j>=wn，则m(i,j)=vn；若0<=j<wn，则m(i,j)=0。当i<n时，若j>=wi，则m(i,j)=maxm(i+1,j),m(i+1,j-wi)+vi；若0<=j<wi，则m(i ,j)=m(i+1,j)。 程序代码如下:import javax.swing.*;publicclassKnapsackextends JFrame final JScrollPane scrollPane = new JScrollPane();publicstatic JTextArea resulttextArea;public JLabel l1 = new JLabel("最优解");public JLabel l3 = new JLabel("所用时间");publicstatic JTextField t1 = new JTextField();publicstatic JTextField t2 = new JTextField();final JLabel label = new JLabel();final JLabel label_1 = new JLabel();public Knapsack()this.setResizable(false);this.setTitle("动态规划计算0-1背包");this.getContentPane().setLayout(null);this.setBounds(100, 100, 670, 400);this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);scrollPane.setBounds(190, 25, 454, 293); getContentPane().add(scrollPane);resulttextArea = new JTextArea();resulttextArea.setEditable(false);scrollPane.setViewportView(resulttextArea);label.setHorizontalTextPosition(SwingConstants.RIGHT);label.setHorizontalAlignment(SwingConstants.RIGHT);label.setText("最优解：");label.setBounds(10, 42, 66, 18); getContentPane().add(label);t1.setHorizontalAlignment(SwingConstants.RIGHT);t1.setHorizontalAlignment(SwingConstants.RIGHT);t1.setBounds(80, 42, 66, 18); getContentPane().add(t1);label_1.setHorizontalTextPosition(SwingConstants.RIGHT);label_1.setHorizontalAlignment(SwingConstants.RIGHT);label_1.setText("所用时间：");label_1.setBounds(10, 75, 66, 18); getContentPane().add(label_1);t2.setHorizontalAlignment(SwingConstants.RIGHT);t2.setHorizontalAlignment(SwingConstants.RIGHT);t2.setBounds(80, 75, 66, 18); getContentPane().add(t2);void display(int v,int w,int c,int n,int m)int jMax = Math.min(wn-1-1,c);for(int j=0;j<=jMax;j+)mnj = 0;/初始化for(int j=wn-1;j<c;j+)mnj=vn;for(int i=n-1;i>0;i-)jMax=Math.min(wi-1,c);for(int j=0;j<=jMax;j+)mij=mi+1j;for(int j=wi;j<c;j+)mij=Math.max(mi+1j,mi+1j-wi+vi);System.out.println("出来的循环m0c-1:"+m0c-1);System.out.println("出来的循环m1c-1:"+m0c-1);m0c-1=m1c-1;if(c>=w0)m0c-1=Math.max(m0c-1,m1c-w0+v0);System.out.println("-"); System.out.println("此0-1背包问题的最优解为："+m0c-1);System.out.println("物品的选择（0代表没有选择，1代表选择）如下：");System.out.println("-"); t1.setText(""+m0c-1);void taceback(int w,int c,int n,int m,int x)resulttextArea.append("物品的选择（0代表没有选择，1代表选择）如下：/n");for(int i=0;i<n;i+)if(mic-1=mi+1c-1) xi=0;else xi=1;c-=wi; System.out.println("x"+i+"="+xi);resulttextArea.append("x"+i+"="+xi+"/n");if(mn-1c-1=1) xn-1=1;else xn-1=0;System.out.println("x"+n+"="+xn-1);resulttextArea.append("x"+n+"="+xn-1+"/n");System.out.println("-"); publicstaticvoid main(String args)finalint c=1000;finalint n=50;intv=220,208,198,192,180,180,165,162,160,158,155,130,125,122, 120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1,1;intw=80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30, 32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,1,1;int m=newintnc;int x=newintn;long start = System.currentTimeMillis();Knapsack k=new Knapsack();k.setVisible(true);k.display(v,w,c,n-1,m);k.taceback(w,c,n-1,m,x);long end = System.currentTimeMillis();t2.setText(end - start)+"ms");System.out.println("/n Time consuming: " + (end - start);2.2.3 石子合并 在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。 试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。输入文件: 包含两行，第1 行是正整数n（1<=n<=100），表示有n堆石子。 第2行有n个数，分别表示每堆石子的个数。 输出两行。 第1 行中的数是最小得分；第2 行中的数是最大得分。动态规划思路： 阶段i：石子的每一次合并过程，先两两合并，再三三合并，.最后N堆合并 状态s：每一阶段中各个不同合并方法的石子合并总得分。 决策：把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案 具体来说我们应该定义一个数组si,j用来表示合并方法，i表示从编号为i的石头开始合并，j表示从i开始数j堆进行合并，si,j为合并的最优得分。 对于上面的例子来说，初始阶段就是s1,1,s2,1,s3,1,s4,1,s5,1,s6,1，因为一开始还没有合并，所以这些值应该全部为0。 第二阶段：两两合并过程如下，其中sum(i,j)表示从i开始数j个数的和 s1,2=s1,1+s2,1+sum(1,2) s2,2=s2,1+s3,1+sum(2,2) s3,2=s3,1+s4,1+sum(3,2) s4,2=s4,1+s5,1+sum(4,2) s5,2=s5,1+s6,1+sum(5,2) s6,2=s6,1+s1,1