中南大学算法实验报告.doc

中 南 大 学算法分析与设计实验报告姓 名：专 业 班 级：软件工程1005学 号： 指导教师：完成日期：2011.12实验1 分治算法实验1、实验目的(1) 了解分治策略算法思想(2) 掌握快速排序、归并排序算法(3) 了解其他分治问题典型算法2、实验内容(1) 编写一个简单的程序，实现归并排序。(2) 编写一段程序，实现快速排序。该实验我采用了java语言，在实验过程中，我发现java不能像c+一样传递参数的引用，因而只能采用数组。采用归并排序：采用快速排序：代码：package Sorts;import java.awt.*;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.awt.event.WindowAdapter;import java.awt.event.WindowEvent;import java.util.Random;public class Sort extends Frameprivate int Num=new int10;private Panel Readylist;private Panel Function;private Panel Result;private Panel Pnum;private Panel Renum;private Button num1;private Button num2;private Button num3;private Button num4;private Button num5;private Button num6;private Button num7;private Button num8;private Button num9;private Button num10;private Button randomdata;private Button readylist;private Button mergesort;private Button quicksort;private Button resetdata;private Button exit;private Button sortresult;private TextField pnum1;private TextField pnum2;private TextField pnum3;private TextField pnum4;private TextField pnum5;private TextField pnum6;private TextField pnum7;private TextField pnum8;private TextField pnum9;private TextField pnum10;private TextField renum1;private TextField renum2;private TextField renum3;private TextField renum4;private TextField renum5;private TextField renum6;private TextField renum7;private TextField renum8;private TextField renum9;private TextField renum10;public Sort(String title)super(title);setSize(400,600);setLocation(100,100);setReadylist();setFunction();setResult();setLayout(new GridLayout(1,3);add(Readylist);add(Function);add(Result);addWindowListener(new WindowAdapter() public void windowClosing(WindowEvent e) System.exit(0); );public void setReadylist() Readylist=new Panel();readylist=new Button(待排序数组);num1=new Button(NUM1);num2=new Button(NUM2);num3=new Button(NUM3);num4=new Button(NUM4);num5=new Button(NUM5);num6=new Button(NUM6);num7=new Button(NUM7);num8=new Button(NUM8);num9=new Button(NUM9);num10=new Button(NUM10);pnum1=new TextField();pnum2=new TextField();pnum3=new TextField();pnum4=new TextField();pnum5=new TextField();pnum6=new TextField();pnum7=new TextField();pnum8=new TextField();pnum9=new TextField();pnum10=new TextField();Readylist.add(readylist);Readylist.add(num1);Readylist.add(pnum1);Readylist.add(num2);Readylist.add(pnum2);Readylist.add(num3);Readylist.add(pnum3);Readylist.add(num4);Readylist.add(pnum4);Readylist.add(num5);Readylist.add(pnum5);Readylist.add(num6);Readylist.add(pnum6);Readylist.add(num7);Readylist.add(pnum7);Readylist.add(num8);Readylist.add(pnum8);Readylist.add(num9);Readylist.add(pnum9);Readylist.add(num10);Readylist.add(pnum10);Readylist.setLayout(new GridLayout(21,1);public void setFunction() Function=new Panel();randomdata=new Button(产生随机数组);mergesort=new Button(归并排序);quicksort=new Button(快速排序);resetdata=new Button(清空数据);exit=new Button(退出);Function.setLayout(new GridLayout(5,1);Function.add(randomdata);Function.add(mergesort);Function.add(quicksort);Function.add(resetdata);Function.add(exit);ActionListener exit1 = new ActionListener()public void actionPerformed(ActionEvent e) System.exit(0); ; exit.addActionListener(exit1);ActionListener randomdata1 = new ActionListener()public void actionPerformed(ActionEvent e) for (int i = 0; i = 9; i+) Numi = (int)(Math.random() * 1000); pnum1.setText( +Num0);pnum2.setText( +Num1);pnum3.setText( +Num2);pnum4.setText( +Num3);pnum5.setText( +Num4);pnum6.setText( +Num5);pnum7.setText( +Num6);pnum8.setText( +Num7);pnum9.setText( +Num8);pnum10.setText( +Num9);renum1.setText( );renum2.setText( );renum3.setText( );renum4.setText( );renum5.setText( );renum6.setText( );renum7.setText( );renum8.setText( );renum9.setText( );renum10.setText( ); ; randomdata.addActionListener(randomdata1); ActionListener resetdata1 = new ActionListener()public void actionPerformed(ActionEvent e) pnum1.setText( );pnum2.setText( );pnum3.setText( );pnum4.setText( );pnum5.setText( );pnum6.setText( );pnum7.setText( );pnum8.setText( );pnum9.setText( );pnum10.setText( );renum1.setText( );renum2.setText( );renum3.setText( );renum4.setText( );renum5.setText( );renum6.setText( );renum7.setText( );renum8.setText( );renum9.setText( );renum10.setText( ); ; resetdata.addActionListener(resetdata1); ActionListener mergesort1 = new ActionListener()public void actionPerformed(ActionEvent e) merge_sort(Num,0,9);renum1.setText( +Num0);renum2.setText( +Num1);renum3.setText( +Num2);renum4.setText( +Num3);renum5.setText( +Num4);renum6.setText( +Num5);renum7.setText( +Num6);renum8.setText( +Num7);renum9.setText( +Num8);renum10.setText( +Num9); ; mergesort.addActionListener(mergesort1); ActionListener quicksort1 = new ActionListener()public void actionPerformed(ActionEvent e) quicksort(Num,0,9);renum1.setText( +Num0);renum2.setText( +Num1);renum3.setText( +Num2);renum4.setText( +Num3);renum5.setText( +Num4);renum6.setText( +Num5);renum7.setText( +Num6);renum8.setText( +Num7);renum9.setText( +Num8);renum10.setText( +Num9); ; quicksort.addActionListener(quicksort1); public void setResult() Result=new Panel();sortresult=new Button(排序结果);renum1=new TextField();renum2=new TextField();renum3=new TextField();renum4=new TextField();renum5=new TextField();renum6=new TextField();renum7=new TextField();renum8=new TextField();renum9=new TextField();renum10=new TextField();Result.setLayout(new GridLayout(11,1);Result.add(sortresult);Result.add(renum1);Result.add(renum2);Result.add(renum3);Result.add(renum4);Result.add(renum5);Result.add(renum6);Result.add(renum7);Result.add(renum8);Result.add(renum9);Result.add(renum10);public void merge_sort(int data,int left,int right)if(leftright)int mid=(right+left)/2;merge_sort(data,left,mid);merge_sort(data,mid+1,right);merge(data,left,mid,right); public void merge(int array,int p,int q,int r)int i,k;int begin1,end1,begin2,end2;inttemp=new intr-p+1;begin1=p;end1=q;begin2=q+1;end2=r;k=0;while(begin1=end1)&(begin2=end2)if(arraybegin1arraybegin2)tempk=arraybegin1;begin1+;elsetempk=arraybegin2;begin2+;k+;while(begin1=end1)tempk+=arraybegin1+;while(begin2=end2)tempk+=arraybegin2+;for(i=0;i(r-p+1);i+)arrayp+i=tempi; public void quicksort(int Num,int left2,int right2) int p; if(left2right2) p=partition(Num,left2,right2); quicksort(Num,left2,p-1); quicksort(Num,p+1,right2); public int partition(int Num,int left1,int right1) int s,temp; s=Numleft1; while(left1s) right1-; while(Numleft1s) left1+; temp=Numleft1; Numleft1=Numright1; Numright1=temp; /swich(Numleft1,Numright1); Numleft1=s; return left1; /* public void swich(int x,int y) int temp=x; x=y; y=temp; */public static void main(String args)throws HeadlessException Sort pr=new Sort(排序);pr.show();(3) 编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天package yy_1110_table;public class RaceTable static int MAX = 32; /日程表边长static int a = new int MAXMAX; /日程表数组void Copy(int tox, int toy, int fromx, int fromy, int n) int i, j; for (i=0; in; i+)for (j=0; jn; j+)atox + itoy + j = afromx + ifromy + j; void Table(int k, int a) int i, n = 1 k; int r; for (i=0; in; i+)a0i = i + 1; for (r=1; rn; r=1) for (i=0; in; i+=2*r) Copy(r, i + r, 0, i, r);Copy(r, i, 0, i + r, r); void Out(int a, int n) int i, j; for (i=0; in; i+) for (j=0; jn; j+) System.out.print(aij+t);System.out.println(); System.out.println(); public static void main(String args) RaceTable b= new RaceTable(); for (int i=0; i5; i+) int len=1 i; /len比赛队伍数,左移一位扩大2倍 b.Table(i, a); b.Out(a, len); 实验2 贪心算法实验1、实验目的(1) 了解贪心算法思想(2) 掌握贪心法典型问题，如背包问题、作业调度问题等。2、实验内容(1) 编写一个简单的程序，实现单源最短路径问题。 package yy_suanfa_test2;import java.util.Scanner;/* * 单源最短路径问题 * author yyang * */public class ShortestPath /定义D数组存储特殊点得距离private int D;/定义P数组存储父节点private int P;/节点个数属性private int v;/用二维数组描述有向图private int graph;/用R数组存储红点集private int R;/用B数组存储蓝点集private int B;/创建一个数组，用来存储进入红点集点得个数private int C;Scanner sc =new Scanner(System.in);private int n = 1;public ShortestPath() /请输入节点的个数System.out.print(请输入节点的个数：);v = sc.nextInt();/输入代表有向图的数组graph = new int vv;/初始化各数组R = new intv;B = new intv;D = new intv;P = new intv;C = new intv;C0 = 0;System.out.println(请输入代表有向图的数组：);for(int i = 0;iv;i+)for(int j =0;jv;j+)graphij = sc.nextInt();/显示代表有向图的数组for(int i = 0;iv;i+)for(int j =0;jv;j+)System.out.print(graphij+t);System.out.println(); public void dijkstra() /对红点集合蓝点集进行初始化操作，值为1则在集合中，值为0则不再集合中 /初始时，红点集中仅有源结点0 R0=1;B0=0; for(int i =1;iv;i+) Bi = 1; /对D数组和P数组进行初始化 for(int i = 0;iv;i+) Di = graph0i; if(Di!=-1) Pi=0; else Pi=-1; /输出D、P表头 System.out.print( ); for(int i=0;iv;i+) System.out.print(D+i+ ); System.out.print( ); for(int i=0;iv;i+) System.out.print(P+i+ ); System.out.println(); for(int k=1;kv;k+) /每次从蓝点集中取出具有最短特殊路长度的结点min for(int min=0;minv;min+) if(Bmin = 1) for(int j=min;jv;j+) if(Dj!=-1&DjDmin&Bj=1) min=j; /将具有最短特殊路长度的结点min添加到红点集中 Rmin=1; Bmin=0; /对数组D作必要的修改 for(int j=1;jDmin+graphminj|Dj=-1) Dj=Dmin+graphminj; /每次迭代求最小值，最后一次即为到源点的最短路径 Pj=min; System.out.print( ); for(int i=0;iv;i+) System.out.print(Di+ ); System.out.print( ); for(int i=0;iv;i+) System.out.print(Pi+ ); System.out.println(); public static void main(String args) ShortestPath sp = new ShortestPath(); sp.dijkstra(); (2) 编写一段程序，实现找零。【问题描述】当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案（要求找出的硬币数目最少）。我使用了java语言编写这个程序，制作内容一个简单的界面输入需要找的零钱数目单位为分：开始找零：代码：package src;import java.awt.*;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.awt.event.WindowAdapter;import java.awt.event.WindowEvent;public class Changes extends Frameprivate Panel Panel1;private Button num1;private Button num2;private Button num3;private Button num4;private Button num5;private Button num6;private TextField pnum1;private TextField pnum2;private TextField pnum3;private TextField pnum4;private TextField pnum5;public Changes(String title)super(title);setSize(300,500);setLocation(100,100);setChanges();setLayout(new GridLayout(1,1);add(Panel1);addWindowListener(new WindowAdapter() public void windowClosing(WindowEvent e) System.exit(0); );public void setChanges() Panel1=new Panel();num1=new Button(需找的钱数(单位：分）);num2=new Button(25分硬币个数);num3=new Button(10分硬币个数);num4=new Button(5分硬币个数);num5=new Button(1分硬币个数);num6=new Button(开始找零);pnum1=new TextField();pnum2=new TextField();pnum3=new TextField();pnum4=new TextField();pnum5=new TextField();Panel1.add(num1);Panel1.add(pnum1);Panel1.add(num2);Panel1.add(pnum2);Panel1.add(num3);Panel1.add(pnum3);Panel1.add(num4);Panel1.add(pnum4);Panel1.add(num5);Panel1.add(pnum5);Panel1.add(num6);Panel1.setLayout(new GridLayout(11,1);ActionListener change = new ActionListener()public void actionPerformed(ActionEvent e) int oprt1 = Integer.parseInt(pnum1.getText();int a = (int)oprt1/25;oprt1=oprt1%25;pnum2.setText( +a);int b=(int)oprt1/10;pnum3.setText( +b);oprt1=oprt1%10;int c = (int)oprt1/5;oprt1=oprt1%5;pnum4.setText( +c);pnum5.setText( +oprt1); ; num6.addActionListener(change); public static void main(String args)throws HeadlessException Changes pr=new Changes(找零); pr.show();(3) 编写程序实现多机调度问题【问题描述】要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。#include using namespace std;#define N 10#define M 3void sort(int t,int n);int set_work1(int t,int n);int max(int t,int num);int min(int t,int m);int set_work2(int t,int n);int timeN;int sM=0,0,0;void main()cout请输入每个进程的运行时间(共10个):;for(int k=0;ktimek;sort(time,N);if(M=N) /作业数小于机器数 coutset_work1(time,N)endl;else coutset_work2(time,N)endl; void sort(int t,int n)for(int k=0;kn-1;k+) /用选择法将处理时间从大到小排序 int j=k; for (int i=k; itj) j=i; int temp=tj;tj=tk;tk=temp; int max(int t,int num) /max函数求解处理时间总和最长 int max=t0; for(int i=1;inum;i+) if(maxti) max=ti; return max;int min(int t,int m) int min=0; /min记录目前处理作业时间和最小的机器号 for(int i=1;isi) min=i; return min;int set_work1(int t,int n) int m=0; for(int i=0;in;i+) /分派作业 sm+=ti; return max(s,N);int set_work2(int t,int n) for(int i=0;in;i+) smin(s,M)+=ti; return max(s,M); 实验三、动态规划算法实验1、 实验目的(1) 掌握动态规划方法贪心算法思想(2) 掌握最优子结构原理(3) 了解动态规划一般问题2、 实验内容(1) 编写一个简单的程序，解决0-1背包问题。设N=5，C=10，w=2，2，6，5，4,v=6,3,5,4,6(2) 合唱队形安排。【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2，K，他们的身高分别为T1，T2，TK， 则他们的身高满足T1.Ti+1TK(1=i=K)。已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。3、 算法思想分析 在求解问题中，对于每一步的决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。4、 实验过程分析（1）0-1背包过程分析：0-1背包问题的最优子结构，设(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背包问题的最优值。（2）合唱队形安排过程分析：分别从左到右求最大上升子序列，从右到左求最大下降子序列。 5、 算法源代码及用户屏幕 （1）0-1背包#define N 5#define C 10#include stdlib.h#includeint i