算法设计与分析

1、算法分析与设计20132014年度 第1学期课程学习报告院系：学号： 姓名： 任课老师： 成果评定： 完成日期：2013年 12月 30 日第1章 递归与分治在任何可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，解题所需要的计算时间也就越少从而比较简洁处理。要想直接解决一个较大的问题，有时是相当困难的。分治法的设计思想是，讲一个难以解决的大问题，分割成规模较小的相同问题，以便各个击破，分而治之。假如原问题可分割成k个子问题，1kn，且这些子问题都可解，并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技

2、术供应了便利。在这种状况下，反复应用分之手段，可以使子问题与原问题的类型全都而其规模却不断缩小，最终使子问题缩小到很简洁求出其解。由此自然导出递归算法。并以其为基础，可以产生了很多高效算法。1.1递归的概念直接或间接的调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。在计算机算法设计与分析中，递归技术是格外有用的。使用递归技术往往使函数的定义和算法的描述简洁且易于理解。1.1.1整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1n2nk1，k1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。 例如正整数6有如下11种不同的划分： 6；

3、 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

4、-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

5、 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个子问题的处理方法是行之有效的。这种使子问题

6、规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。1.2.1分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到肯定的程度就可以简洁地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 这条特征涉及到分治法的效率，假如各子问题是不独立的，则分治法要做很多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。分治法的基本步骤divide-and-c

7、onquer(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)

8、子问题的思想，它几乎总是比子问题规模不等的做法要好。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个子棋盘中无特殊方格。为了

9、将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌掩盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘掩盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。 用递归与分治求解下面算法中，用整数型数组board表示棋盘。board00是棋盘的左上角方格。tile是算法中的一个全局整形变量，用来表示L型骨牌的编号，其初始值为0.算法的输入参数如下：tr：棋盘左上角方格的行号；tc：棋盘左上角方格的列号；dr：特殊方格所在的行号；size：，棋盘规格为2k×2k。设T(k)是算法chessBoard掩盖一个2k×2k棋盘所需要的时

10、间。从算法的分割策略可知，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) / 特殊方格在此棋盘中

11、 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

12、+ 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 && d

13、c >= 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个选手的竞赛日程表可

14、以通过n/2个竞赛日程表来打算。递归地用这种一分为二的策略对选手进行划分，直选手的到只剩下两个选手时，竞赛日程表的制定就变得很简洁。这时只要让这两个选手进行竞赛就可以了。按分治策略，我们可以将全部的选手分为两半，则n个选手的竞赛日程表可以通过n/2个选手的竞赛日程表来打算。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，竞赛日程表的制定就变得很简洁。这时只要让这两个选手进行竞赛就可以了。代码部分#include<stdlib.h>#include<stdio.h>int *A; /int *指针数组，int *schedule; /int数组，一维数组保

15、存二维数组的数据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&qu

16、ot;); /*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 *)

17、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;/*co

18、pyeven: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组和第

19、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天

20、)/ 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

21、; 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); /依据偶数个选手来求解

22、 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章 动态规划动态规

23、划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最终解决原问题需要耗费过多的时间。在用分治法求解时，有些子问题被重复计算了很多次。假如我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避开大量的重复计算。为了达到此目的，可以用一个表来记录全部已解决的子问题的答案。这就是动态规划法的基本思想。2.1动态规划算法的基本要素2.1.1最优子结构矩阵连乘计算次序问题的最优解

24、包含着其子问题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致冲突。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。2.1.2 重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简洁地用常数

25、时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。2.2实例分析 2.2.1 计算最优值对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有 由此可见，在递归计算时，很多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简洁查一下，从而避开大量的重复计算，最终得到多项式时间的算法。用动态规划法求最优解public static

26、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

27、; 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<

28、;=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.*;public class Knapsack extends JFrame final JScrollPane scrollPane = new JScrollPane();public static JTextArea resulttextArea;public JLabel l1 = new JLabel("最优解

29、");public JLabel l3 = new JLabel("所用时间");public static JTextField t1 = new JTextField();public static JTextField t2 = new JTextField();final JLabel label = new JLabel();final JLabel label_1 = new JLabel();public Knapsack()this.setResizable(false);this.setTitle("动态规划计算0-1背包")

30、; 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

31、(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(Swing

32、Constants.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.setHorizon

33、talAlignment(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&g

34、t;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("

35、;-"); 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

36、=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"

37、+n+"="+xn-1+"/n");System.out.println("-"); public static void main(String args)final int c=1000;final int n=50;int v=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,1

38、5,10,8,5,3,1,1;int w=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=new intnc;int x=new intn;long start = System.currentTimeMillis();Knapsack k=new Knapsack();k.setVisible(true);k.display(v,w,c,

39、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堆石子合并成一堆的最小得分和最大得分。输入文件

40、: 包含两行，第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,

41、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+sum(6,2) 第三阶段：三三合并可以拆成两两合并，拆分方法有两种，前两个为一组或后两个为一组. s1,3=s1,2+s3,1+sum(1,3)或s1,3=s1,

42、1+s2,2+sum(1,3)，取其最优 s2,3=s2,2+s4,1+sum(2,3)或s1,3=s2,1+s3,2+sum(2,3)，取其最优 第四阶段：四四合并的拆分方法用三种，同理求出三种分法的得分，取其最优即可。以后第五阶段、第六阶段依次类推，最终在第六阶段中找出最优答案即可源程序#include "stdio.h"#include "stdlib.h"int num101;int s99100;int sum(int i,int j,int n)/求和 int result,final; result=numi;for(int p=1;p&l

43、t;=j-1;p+) if(i+p>n) final=(i+p)%n; else final=i+p; result=result+numfinal; return result; int max(int n) int k,t,w,result; for(int i=1;i<=n;i+)/初始阶段就是s1,1,s2,1,s3,1,s4,1,s5,1,s6,1，由于一开头还没有合并，所以这些值应当全部为0 si1=0; for(int r=2;r<=n;r+)/枚举阶段，从两两合并开头计算 for( i=1;i<=n;i+)/计算当前阶段的n种不同状态的值,从一开头的1到

44、n种不同状态，例如s1n和s2n if(i+1>n) w=(i+1)%n; else w=i+1; sir=si1+swr-1+sum(i,r,n);/s(i,r,n)表示从i开头数r个数的和 /mir=w; for( k=1;k<=r-1;k+)/枚举不同的分段方法 if(i+k>n) w=(i+k)%n; else w=i+k; t=sik+swr-k+sum(i,r,n); if(t>sir)/比较取s1.nr中的最值 sir=t; /mir=k; result=s1n; for(int u=1;u<=n;u+)/从s1n到snn中取最大值 / printf

45、("%d ",sun); if(sun>result) result=sun; return result;int min(int n)/同max()差不多 int k,t,w,result; for(int i=1;i<=n;i+) si1=0; for(int r=2;r<=n;r+) for( i=1;i<=n;i+) if(i+1>n) w=(i+1)%n; else w=i+1; sir=si1+swr-1+sum(i,r,n); mir=w; for( k=1;k<=r-1;k+) if(i+k>n) w=(i+k)%n

46、; else w=i+k; t=sik+swr-k+sum(i,r,n); if(t<sir)/比较 sir=t; mir=k; result=s1n; for(int u=1;u<=n;u+)/还是比较，与max比较不同 / printf("%d ",sun); if(sun<result) result=sun; return result;int main() int n; scanf("%d",&n); for(int i=1;i<=n;i+) scanf("%d",&numi); pr

47、intf("%dn",min(n); printf("%dn",max(n); return 1; 第三章 贪心算法贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，期望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对全部问题都得到整体最优解，但对很多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些状况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。3.1 贪心算法的特性贪欲算法可解决的问题通常大部分都有如下的特性： 有一个以最优方式来解决的问题。为了构造问题的解决方案，有一个候选的对象的集合：比如不同面值的硬币。 随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。 有一个函数来检查一个候选对象的集合是否供应了问题的解答。该函数不考虑此时的解决方法是否最优。 还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性