最优合并问题.doc

课程设计说明书1 引言1.1 问题描述给定k个排好序的序列S1，S2，Sk，用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总比较次数最少。为了进行比较，还需要确定合并这个序列的最差合并顺序，使所需的总比较次数最多。1.2 问题分析两路合并算法是通过反复执行将两个有序子文件合并成一个有序文件的操作，最终将n个长度不等的有序子文件合并成一个有序文件。编写该软件是实现将给定的几个长度不等的有序子文件合并成一个有序的文件，并且求出合并过程中比较的次数。2 系统分析2.1 实现方法2.1.1 蛮力法 采用蛮力法，若有n个序列，则有n！种合并方法，实现列举出每种方法，并计算比较次数。2.1.2 贪心法本方法采用构造最大堆和最小堆来解决。思路：最差合并顺序总是最长的两个先合并；最优合并顺序总是最短的两个先合并。2.1.3 贪心法最优合并证明 最优合并顺序证明：设有n个权值W=作为外结点的权值，构造两路合并树的贪心算法将生成一棵具有最小带权路径长度的二叉树。证明：1）对于n=1，算法将返回只有一个外结点的二叉树，这棵树显然是最优的。2）假定外结点的数目为kn时，算法能够生成有k个外结点的最佳二路合并树。3）当k=n时，假定有n个权值，并设贪心算法生成的两路合并树为 ，设cost()是的带权外路径长度。如果它不是最优的，而另一棵同样以此n个权值为外结点的两路径合并树是最优的，即cost()cost()。对于，现假定结点p是该树上离根最远的内结点，它有两个孩子和。如果它们不是最小的两个权值和，可以通过交换使得p的孩子为和。于是得到另一棵有n个外结点的两路合并树，必有cost()cost()。对于，用权值为的外结点取代以p为根的子树（见图2），得到一棵有n-1个外结点的两路合并树。同样，可以对由贪心法得到的两路合并树也进行类似替代，即对由两个外结点和合并形成的子树，用一个权值为的外结点取代之，从而得到一棵n-1个外结点的两路合并树。二叉树正是对权值集执行上述贪心算法所生成的两路合并树。根据归纳法假设，cost()cost(),由于cost() = cost() +和cost()=cost()+,所以cost()cost();又因为cost()cost(),所以cost()cost()，这与假设矛盾，这就证明了贪心算法生成的两路合并树必定是具有最小带权外路径长度的二叉树，因而 root root是最佳两路合并树。. . . . . pp （b）（a）图22.2 数据结构 本方法的数据结构采用堆。堆是一种灵巧的，部分有序的数据结构。堆可以定义为一颗二叉树， 数的节点中包含键（每个节点一个键），并且满足以下两个条件： （1）树的形状要求:这棵二叉树为完全二叉树。 （2）父母优势要求：对于最大堆，每个节点的键都要大于或等于它子女的键。对于最小堆来说，每个节点都要小于或等于它子女的键。本方法中堆采用数组来实现对于堆的插入，删除，堆排序等操作。3 总体设计开 始选择蛮力、贪心合并读取蛮力法贪心法读取 文 件输入各序列的长度的值输入输入长度 各序列的长度的值最差合并最优合并文 件 用n！种方法 合并子序列选择最优、最差合并 输出合并次数存入文 件最优合并模块最差合并模块存入存入输出最差合并次数输出最优合并次数结 束 图34 模块设计及实现 4.1 主模块 本模块包括：界面设计，文件的读入、读出，选择使用蛮力法或贪心法，动态演示。4.2 蛮力法模块 本模块包括：读取指定有序子序列文件的长度存放到数组中，然后将n！种合并方式的结果存放到文件中，并且计算每种方式的比较次数也存放到文件中。4.3 贪心法模块4.3.1 最优合并模块 本模块包括：读取指定合并有序子序列文件的长度存放到数组中，建立最小堆 ，同时对最小堆进行操作，计算出最优合并所用的次数；对于任意给定一组数，该组数为各有序子序列的长度，将其存放到数组中，建立最小堆 ，同时对最小堆进行操作，计算出最优合并所用的次数。4.3.2 最差合并模块本模块包括：读取指定合并有序子序列文件的长度存放到数组中，建立最大堆 ，同时对最大堆进行操作，计算出最优合并所用的次数；对于任意给定一组数，该组数为各有序子序列的长度，将其存放到数组中，建立最大堆 ，同时对最大堆进行操作，计算出最优合并所用的次数。5 源程序代码5.1 界面设计package mywind;import java.awt.Dimension;import java.awt.GridLayout;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.File;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.FileWriter;import java.io.IOException;import javax.swing.JApplet;import javax.swing.JButton;import javax.swing.JDialog;import javax.swing.JFrame;import javax.swing.JLabel;import javax.swing.JMenu;import javax.swing.JMenuBar;import javax.swing.JMenuItem;import javax.swing.JOptionPane;import javax.swing.JPanel;import javax.swing.JScrollPane;import javax.swing.JTextArea;import javax.swing.JTextField;public class Mywindow extends JFrame implements ActionListener public String string, string1, str;JTextField jtf1, jtf2,jtf3, jtf4;JPanel jps = new JPanel();JPanel jp = new JPanel();JPanel jp1 = new JPanel();JPanel jp2 = new JPanel();JPanel jp3 = new JPanel();JScrollPane jsp;JMenuBar jmb;JMenu jmenu, jmenu1, jmenu2;JMenuItem jmi1, jmi2, jmi3, jmi4, jmi5;JTextArea jta1, jta2;JButton jbtn1, jbtn2, jbtn3;Mywindow(String s) setTitle(s);setVisible(true);setBounds(200, 200, 800, 400);setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);GridLayout grids = new GridLayout(0, 2);jps.setLayout(grids);GridLayout grid = new GridLayout(2, 0);jp.setLayout(grid);add(jps);jp.add(jp1);jp.add(jp2);jps.add(jp);jps.add(jp3);jmi1 = new JMenuItem(打开);jmi2 = new JMenuItem(保存);jmi3 = new JMenuItem(退出);jmenu = new JMenu(文件);jmenu1 = new JMenu(帮助);jmenu2 = new JMenu(关于本程序);jmi4 = new JMenuItem(帮助);jmi5 = new JMenuItem(关于本程序);jmb = new JMenuBar();jmenu1.add(jmi4);jmenu2.add(jmi5);jmenu.add(jmi1);jmenu.add(jmi2);jmenu.add(jmi3);jmi1.addActionListener(this);jmi2.addActionListener(this);jmi3.addActionListener(this);jmi4.addActionListener(this);jmi5.addActionListener(this);jmb.add(jmenu);jmb.add(jmenu1);jmb.add(jmenu2);setJMenuBar(jmb);/ *jp1jp1.setLayout(null);JLabel jlabel1 = new JLabel(目标序列:);jp1.add(jlabel1);jlabel1.setBounds(0, 0, 80, 20);jta1 = new JTextArea();jsp = new JScrollPane(jta1);jp1.add(jsp);jsp.setBounds(60, 20, 300, 140);/ *jp2jp2.setLayout(null);JLabel jlabel2 = new JLabel(最优比较次数:);JLabel jlabel3 = new JLabel(最差比较次数:);jtf1 = new JTextField();jtf2 = new JTextField();jp2.add(jlabel2);jlabel2.setBounds(100, 0, 100, 20);jp2.add(jtf1);jtf1.setBounds(200, 0, 100, 20);jp2.add(jlabel3);jlabel3.setBounds(100, 40, 100, 20);jp2.add(jtf2);jtf2.setBounds(200, 40, 100, 20);jbtn1 = new JButton(蛮力法);jp2.add(jbtn1);jbtn1.setBounds(90, 100, 100, 20);jbtn2 = new JButton(贪心算法);jp2.add(jbtn2);jbtn2.setBounds(210, 100, 100, 20);jbtn3 = new JButton(贪心法范例演示);jp2.add(jbtn3);jbtn3.setBounds(125, 70, 140, 20);jbtn3.addActionListener(new ActionListener() public void actionPerformed(final ActionEvent arg0) try Runtime.getRuntime().exec(cmd /c start file:/F:/11/11.html); catch (Exception ex) System.out.println(error);ex.printStackTrace(););JLabel jlabel5 = new JLabel(时间复杂度:);jp2.add(jlabel5);jlabel5.setBounds(0, 140, 80, 20);jtf3 = new JTextField();jtf4 = new JTextField();jp2.add(jtf3);jtf3.setBounds(90, 140, 100, 20);jp2.add(jtf4);jtf4.setBounds(210, 140, 100, 20);/*jp3jp3.setLayout(null);JLabel jlabel4 = new JLabel(动态演示过程:);jp3.add(jlabel4);jlabel4.setBounds(0, 0, 90, 20);jta2 = new JTextArea();jta2.setWrapStyleWord(true);jsp = new JScrollPane(jta2);jp3.add(jsp);jsp.setBounds(40, 20, 320, 260);jbtn1.addActionListener(this);jbtn2.addActionListener(this);validate();/ *mouseOverridepublic void actionPerformed(ActionEvent e) / TODO Auto-generated method stubif (e.getSource() = jmi1) / 打开string = JOptionPane.showInputDialog(null, 请输入文件名字：, 文件操作,JOptionPane.INFORMATION_MESSAGE);File rdFile = new File(d:zyhb, string);try FileReader readfile = new FileReader(rdFile);BufferedReader rd = new BufferedReader(readfile);String str = null;while (str = rd.readLine() != null) jta1.setText(str);readfile.close();rd.close(); catch (FileNotFoundException e1) / TODO Auto-generated catch blocke1.printStackTrace(); catch (IOException e1) / TODO Auto-generated catch blocke1.printStackTrace();if (e.getSource() = jmi2) / 保存string1 = JOptionPane.showInputDialog(null, 请输入文件名字：, 文件操作,JOptionPane.INFORMATION_MESSAGE);File wFile = new File(d:zyhb, string1);try FileWriter writfile = new FileWriter(wFile);BufferedWriter wt = new BufferedWriter(writfile);String strg = null;strg = jta1.getText();wt.write(strg);wt.flush();writfile.close();wt.close(); catch (FileNotFoundException e1) / TODO Auto-generated catch blocke1.printStackTrace(); catch (IOException e1) / TODO Auto-generated catch blocke1.printStackTrace();if (e.getSource() = jmi4) / 帮助zmywin zwad = new zmywin(这是一个帮助程序);if (e.getSource() = jmi5) / 关于JOptionPane.showMessageDialog(null, 本程序, 关于本程序,JOptionPane.WARNING_MESSAGE);if (e.getSource() = jmi3) / 退出/ file:/C:/Users/king/Desktop/a.htmlSystem.exit(0);if (e.getSource() = jbtn1) / 蛮力str = jta1.getText().toString();manli ml = new manli(str);String string3 = ;jtf1.setText(Integer.toString(ml.getmin();jtf2.setText(Integer.toString(ml.getmax();jtf3.setText(Integer.toString(ml.sjfz();for (int i = 0; i ml.getchucun().length(); i+) if (ml.getchucun().charAt(i) != a) string3 = string3 + ml.getchucun().substring(i, i + 1); else string3 = string3 + n;jta2.append(string3);string3 = ;if (e.getSource() = jbtn2) / 贪心str = jta1.getText().toString();String string4 = ;tanxin tx = new tanxin(str);jtf1.setText(Integer.toString(tx.getzyhbcs();jtf2.setText(Integer.toString(tx.getzchbcs();jtf4.setText(Integer.toString(tx.sjfz();for (int i = 0; i tx.getstring1().length(); i+) if (tx.getstring1().charAt(i) != !) string4 = string4 + tx.getstring1().substring(i, i + 1); else string4 = string4 + n;jta2.append(string4);string4 = ;for (int i = 0; i tx.getstring3().length(); i+) if (tx.getstring3().charAt(i) != !) string4 = string4 + tx.getstring3().substring(i, i + 1); else string4 = string4 + n;jta2.append(string4);string4 = ;string4 = tx.getstring2() + n;jta2.append(string4);5.2 蛮力法package mywind;public class manli public String s1;public String ss=;public String chucun=;public int ms=new int100;public int sum=0;public int min=10000;public int max=0;public int sjfz=0;manli(String s)s1=s; int k=0;int l=0;s1=s1+ ; for(int i=0;is1.length();i+) if(s1.charAt(k)!= ) ss=ss+s1.substring(k, k+1); else msl=Integer.parseInt(ss,10);System.out.println(msl);l+;ss=; k+; perm(ms,0,l-1);public String getchucun()return chucun;public int getmin()return min;public int sjfz()return sjfz;public int getmax()return max;public void perm(int buf,int start,int end) sjfz+; int sum=0; if(start=end)/当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可（特殊情况） for(int i=0;i=end;i+) System.out.print(bufi+ ); chucun=chucun+bufi+ ; sum=(buf0+buf1)*(end)-1;for(int i=2;imax)max=sum;if(summin)min=sum; chucun=chucun+次数:+sum+a; System.out.println(); else/多个字母全排列（普遍情况） for(int i=start;i=end;i+)/（让指针start分别指向每一个数） int temp=bufstart;/交换数组第一个元素与后续的元素 bufstart=bufi; bufi=temp; perm(buf,start+1,end);/后续元素递归全排列 temp=bufstart;/将交换后的数组还原 bufstart=bufi; bufi=temp; 5.2 贪心法package mywind;public class tanxin public String str = , str1 = ,str2 = ;public int zy = new int1000;public int zyhb = 0; /最优合并public int zyhbcs = 0; /最优合并次数public int zc = new int1000;public int zchb = 0; /最差合并public int zchbcs = 0; /最差合并次数public int flag = 0,flag2=0;public int b = 1;public int sjfzd = 0; /时间复杂度public String string1 = , string2 = ,string3 = ;tanxin(String s) str = s;begin();for (int i = 1; i = b; i+) zci = zyi;zystrheap(b);zyrtsheap(b);string1 = 当前堆内序列: ;for (int j = 1; j = b; j+) string1 = string1 + Integer.toString(zyj) + ;string1 = string1 + !;insert1(b);str=s;b=1;begin();string3 = 当前堆内序列: ;for (int j = 1; j = b; j+) string3 = string3 + Integer.toString(zcj) + ;string3 = string3 + !;zcstrheap(b);zcrtsheap(b);insert2(b);public void begin() /将字符串转换成十进制的整型数组int a = 0;str = str + ;for (int i = 0; i 0; i-) if (zy2 * i + 1 != 0) if (zy2 * i + 1 zyi) swap(zy, 2 * i + 1, i);if (zy2 * i != 0) if (zy2 * i zyi) swap(zy, 2 * i, i);public void zyrtsheap(int c) / 从上向下构造最小堆for (int k = 1; k = c / 2; k+) if (zyk * 2 + 1 != 0) if (zyk * 2 + 1 zyk) swap(zy, k * 2 + 1, k);if (zyk * 2 != 0) if (zyk * 2 zyk) swap(zy, k * 2, k);public void insert1(int p) /合并前两个sjfz+;if (b = 1 & zyhb = 0) System.out.println(zyhbcs); else if (flag 1) zyhb = zyhb + zy1;zy1 = zyb;zyb = 0;flag+;b-;zyrtsheap(b);zystrheap(b);string1 = string1 + 当前最小堆内序列: ;for (int i = 1; i = b; i+) string1 = string1 + Integer.toString(zyi) + ;string1 = string1 + !; else zyhb = zyhb + zy1;zyhbcs = zyhbcs + zyhb - 1;flag = 0;zy1 = zyhb;zyhb = 0;zyrtsheap(b);zystrheap(b);string1 = string1 + 当前最小堆内序列: ;for (int i = 1; i 0; i-) if (zc2 * i + 1 != 0) if (zc2 * i + 1 zci) swap(zc, 2 * i + 1, i);if (zc2 * i != 0) if (zc2 * i zci) swap(zc, 2 * i, i);public void zcrtsheap(int c) / 从上向下构造最大堆for (int k = 1; k zck) swap(zc, k * 2 + 1, k);if (zck * 2 != 0) if (zck * 2 zck) swap(zc, k * 2, k);public void insert2(int p) /合并前两个sjfz+;if (b = 1 & zchb = 0) System.out.println(zchbcs); else if (flag2 1) zchb = zchb + zc1;zc1 = zcb;zcb = 0;flag2+;b-;zcrtsheap(b);zcstrheap(b);string3 = string3 + 当前最大堆内序列: ;for (int i = 1; i = b; i+) string3 = string3 + Integer.toString(zci) + ;string3 = string3 + !; else zchb = zchb + zc1;zchbcs = zchbcs + zchb - 1;flag2 = 0;zc1 = zchb;zchb = 0;zcrtsheap(b);zcstrheap(b);string3 = string3 + 当前最大堆内序列: ;for (int i = 1; i = b; i+) string3 = string3 + Integer.toString(zci) + ;string3 = string3 + !;insert2(b);public static void swap(int array, int i, int j) /两数组交换int temp = 0;temp = arrayi;arrayi = arrayj;arrayj = temp;public int getzyhbcs() return zyhbcs;public int getzchbcs() return zchbcs;public String getstring1() return string1;public String getstring2() return string2;public String getstring3() return string3;public int sjfz() return sjfz;6 程序测试结果6.1 打开文件结果6.2 保存文件结果6.3 蛮力法结果6.4 贪心法结果7 课程设计体会 在这次课程设计当中，我了解到了我的不足，如算法的不完善。但是通过这次课程设计，我的缺点有所改善。我在写新的程序时，首先要考虑的深入一点、仔细一点，这样要修改程序的时间就会少很多，并且也尽量避免因为自己不细心而导致的浪费时间的情况出现。 在进行程序设计时，要注意想好思路，即要有恰当模块名、变量名、常量名、子程序名等。将每个功能的模块，即函数名要清晰的表述出来，使用户能够一目了然的知道此程序的功能。当然适当的注释，也是方便用户的理解。还有在编写程序时要注意对程序的适当分配，便于用户看懂程序，也便于自己检查。但是完成任何一个较大的程序，都需要掌握一定的编程基础，需要不断的探索和求知过程，这样对自己编程能力的提高有较大的帮助。当然，任何程序必须经过计算机的调试，看是否调试成功，发现错误，一个个，一步步去解决，这样就能从错误中进步。通过此次课程设计加强了我的动手能力，以及提升了局部和统一考虑问题的思维方式。回顾起此次课程设计，至今我仍感慨颇多，从拿到题目到完成整个编程，从理论到实践，在整整半个月的日子里，不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所