2014武汉理工复试机试点蜡烛问答(java)胡奥勇
- 格式：doc
- 大小：55.35 KB
- 文档页数：23
. 2014武汉理工复试机试 ——点蜡烛问题(Java 实现) 140 + 胡奥勇
一、说明 1．机试点蜡烛的问题，题目具体描述见主程序中类注释“描述”部分，主要用递归算法实现，另需要对蜡烛长度数组排序； 2．代码即文档，讲究代码规范，关键逻辑处，注释写清楚，只考虑完成功能的话（现实文件读写）java实现大约200行代码； 3．主程序TestCase.java读输入文件input.txt，计算每组蜡烛可燃烧最大天数，并输出到结果文件output.txt； 4．CandleADT为自定义抽象数据结构（复试看数据结构时候感触颇深，顺便用一下），主要解决蜡烛燃烧这一类的问题，定义了一些扩展接口，主要考虑是解决不限于题目所描述燃烧规则中求解最大燃烧天数这一类问题。利用定义的扩展接口可适应解决其他燃烧规则中蜡烛最大天数的求解，此处留给有兴趣的读者验证； （提示，可采用设计模式中的策略模式，在CandleADT中只定义接口，具体实现交给不同的燃烧规则类去实现） 关键的几个函数为： sortList(); // 升序排序 以便后续按照最优策略燃烧 lighting(days); // 第i天的蜡烛燃烧，消耗掉 print();// 显示燃烧后结果 countDays(); // 递归向下进行 . 5．Candle实体，含蜡烛标示，（机试的题目再出难一点，要求跟踪显示燃烧过程中具体每根蜡烛的燃烧情况）是为进一步的优化，可跟踪显示燃烧过程中每根蜡烛燃烧过程中变化情况。显示即（A4 B2 C2 D2 A3 B2 C2 D2 等）相应的CandleADT中list 换成list 相关接口略微更改即可，排序的接口需要自定义比较类。此处笔者不去具体实现，留与感兴趣的读者实现。 6．机试如果要求显示燃烧过程中每根蜡烛的燃烧情况，估计在2h考试场景，以java程序猿从来不浪费记忆力在记API上（都是即需即查）的性格，没有网络条件下，基本上没人能做出来了，包括笔者在内。笔者在调试其他扩展接口过程中就花了不少时间。。。 以上所述，包括以下代码，为机试交卷完成后凭记忆回忆重新输出的，仅供内部交流讨论，转载请注明出处。（欢迎针对代码设计和实现的讨论，联系QQ：252302770。）
二、主程序 package com.whut.huay; . 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 java.util.ArrayList; import java.util.List;
/** *
* 点蜡烛问题 主程序 * 描述： * 1.一根蜡烛燃烧一天消耗一个单位； * 2.第i天要燃烧i根蜡烛； * 3.给定一个数量不定，每根蜡烛长度不定的蜡烛组，求这组蜡烛在满足条件1，2前提下的最大燃烧天数 * 4.数据来源为input.txt文件，结果写入到output.txt * * 分析： . * 1.仔细分析，对于蜡烛组，最多可燃烧天数最佳策略为，每次从长度最长的蜡烛开始燃烧； * 2.第i天若存在i根长度不为0的蜡烛，说明可燃烧至第i天； * 3.递归向下计算第i+1天是否有i+1根长度不为0的蜡烛 * 4.直到某个第n天时，可供燃烧蜡烛数量少于n ,此时，最大可燃烧天数为(n-1); *
/** * * @param args * @create 2014年4月7日 上午12:36:51 huay * @history . */
public static void main(String[] args) { try { // 读input.txt文件 作为题目条件，此处没有作文件的存在性校验 @SuppressWarnings("resource") BufferedReader reader = new BufferedReader(new FileReader(sourceFile)); File outputfile = new File(destFile); if (!outputfile.exists()) { // 如果不存在 在该路径下创建文件 outputfile.createNewFile(); } BufferedWriter writer = new BufferedWriter(new FileWriter(outputfile));
List dataList = new ArrayList(); String temp = null; // 读文件指针 temp = reader.readLine(); // 逐行读取 while (temp != null) { CandleADT candleADT = new CandleADT(); candleADT.setCount(Integer.valueOf(temp));// 奇数行为蜡烛根数 如：4 . temp = reader.readLine();// 偶数行为每根蜡烛可燃烧值 如：4 2 2 2 String[] kiddleDetail = temp.split(" "); candleADT.initList(kiddleDetail);// 初始化数组 temp = reader.readLine();// 读下一奇数行 dataList.add(candleADT);// 添加到list 统一处理 }
// 计算文件中每组数据的最大可燃烧天数并另存到文件output.txt for (CandleADT CandleADT : dataList) { CandleADT.countDays(); writer.write(CandleADT.getDays() + "\r\n"); } writer.close();//关闭 } catch (FileNotFoundException e) { e.printStackTrace(); } catch (IOException e) { e.printStackTrace(); }
} } . 三、每组蜡烛的抽象数据结构
package com.whut.huay;
import java.util.ArrayList; import java.util.Collections; import java.util.List;
/** * *
* whut复试 点蜡烛问题 CandleADT蜡烛组抽象数据结构 *
/** * 从文件中读入的蜡烛数组 * * @param kiddleDetailArray * @create 2014年4月6日 下午8:43:52 huay * @history */ public void initList(String[] kiddleDetailArray) { for (String string : kiddleDetailArray) { candles.add(Integer.valueOf(string)); } System.out.print("文件中初始读入："); print(); sortList();// 升序排序 System.out.print("排序后输出："); print();
