贪心法解活动安排问题(计算机算法设计与分析).doc

实 验 报 告 课程名称： 算法设计与分析 实验名称： 贪心法解活动安排问题 任课教师： 张锦雄 专 业： 计算机科学与技术 班 级: 2007 级 1班 学 号： 姓 名： 蓝冠恒 完成日期： 2011年1月12日 一、实验目的：掌握贪心法解活动安排问题的原理，并能够按其原理编程实现对输入的活动时间段进行合理安排，加深对贪心法解活动安排问题的理解。 二、主要实验内容及要求：1 要求按贪心法求解问题；2 要求读文本文件输入活动安排时间区间数据；3 要求显示结果。 三、实验环境和工具：操作系统:win7操作系统开发工具：eclipse3.4、jdk1.6开发语言：java四、实验结果与结论：（经调试正确的源程序和程序的运行结果）1、源代码：package cn.lgh;import java.io.BufferedReader;import java.io.FileReader;import java.io.IOException;import java.io.InputStreamReader;/* * 贪心法解活动安排问题。 * author 蓝冠恒 */public class GreedySelector public int startTimes;/活动起始时间点数组public int endTimes;/活动结束时间点数组public boolean resultFlags;/被选活动标识数组public String activRegions = ;/活动时间区间字符串public String result = ;/结果字符串/* * 构造方法 */public GreedySelector() /* * 构造方法 * param startTimes * 活动起始时间数组 * param endTimes * 活动结束时间数组 */public GreedySelector(int startTimes, int endTimes) this.startTimes = startTimes;this.endTimes = endTimes;/贪心算法具体实现过程private int greedySelector() int n = startTimes.length;resultFlags0 = true;int j = 0;int count = 1;for (int i = 1; i = endTimesj) resultFlagsi = true;j = i;count+; else resultFlagsi = false;return count;/按活动结束时间非递减排序private void sort()int tmp;int n=startTimes.length;for(int i=0;in;i+)for(int j=0;jn;j+)if(jendTimesj+1)tmp=endTimesj;endTimesj=endTimesj+1;endTimesj+1=tmp;tmp=startTimesj;startTimesj=startTimesj+1;startTimesj+1=tmp;/* * 从文件中获取被安排活动的时间段，并用贪心算法对其选择。 * param filePath * 文件路径 * throws IOException */public void greedyFromFile(String filePath) throws IOException String line;BufferedReader in = new BufferedReader(new FileReader(filePath);line = in.readLine().replaceAll( , );while (line != null) activRegions += line;line = in.readLine();doGreedyAction();/* * 从控制台中读取被安排活动的时间段，并用贪心算法对其选择。 * throws Exception */public void greedyFromConsole() throws Exception String input;final String form = 5，6、3，2、10，23;BufferedReader in = new BufferedReader(new InputStreamReader(System.in);do System.out.println(请输入活动时间区间(退出请按数字键1)，格式如： + form);input = in.readLine().trim(); while(input.equals();if (input.equals(1) return;activRegions = input;doGreedyAction();return;/* * 执行贪心法解活动安排具体动作。 */private void doGreedyAction() if (activRegions = ) return;String activities = activRegions.split(、);int num = activities.length;startTimes = new intnum;endTimes = new intnum;resultFlags = new booleannum;String strTmp;String region;for (int i = 0; i num; i+) strTmp = activitiesi;region = strTmp.split(，);startTimesi = Integer.parseInt(region0.replace(, );endTimesi = Integer.parseInt(region1.replace(, );sort();/排序greedySelector();result=;for (int i = 0; i resultFlags.length; i+) if (resultFlagsi) result += + startTimesi + ， + endTimesi + 、 ;int index = result.lastIndexOf(、);result = result.substring(0, index);public static void main(String args) String input;GreedySelector greedySelector = new GreedySelector();BufferedReader in = new BufferedReader(new InputStreamReader(System.in);do try do System.out.println(n按数字键1-从指定文件中的获取数据内容);System.out.println(按数字键2-从控制台输入数据内容);System.out.println(按数字键3-退出系统);input = in.readLine().trim(); while (!(input.equals(1) | input.equals(2) | input.equals(3);if (input.equals(3) break;if (input.equals(1) System.out.println(请输入数据文件路径：);input = in.readLine().trim();try greedySelector.greedyFromFile(input); catch (IOException e) e.printStackTrace();continue; else try greedySelector.greedyFromConsole(); catch (Exception e) e.printStackTrace();continue;System.out.println(活动安排区间：n + greedySelector.activRegions);System.out.println(n贪心法解活动安排结果：n + greedySelector.result); catch (IOException e) e.printStackTrace(); while (true); 2、运行结果：五、实验总结 在