第一篇：2014武汉理工复试机试 点蜡烛问题(java) - 胡奥勇
2014武汉理工复试机试
——点蜡烛问题(Java 实现)
+ 胡奥勇
一、说明
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
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);*
** @author: huay * @since: 2014年4月6日 下午8:40:52 * @history: ************************************************
* @file: TestCase.java * @Copyright: XX电子股份有限公司.All right reserved.************************************************/ public class TestCase { private static String sourceFile = “D:/input.txt”;//输入文件路径
private static String destFile = “D:/output.txt”;//输出文件路径
/**
*
} * @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
temp = reader.readLine();// 读下一奇数行
dataList.add(candleADT);// 添加到list 统一处理 } // 计算文件中每组数据的最大可燃烧天数并另存到文件output.txt for(CandleADT CandleADT : dataList){
CandleADT.countDays();
writer.write(CandleADT.getDays()+ “rn”);} 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蜡烛组抽象数据结构
*
** @author: huay * @since: 2014年4月6日 下午8:40:52 * @history: ************************************************
* @file: CandleADT.java * @Copyright: XX电子股份有限公司.All right reserved.***********************************************
*/ public class CandleADT { private List
private int count;// 蜡烛总根数 实际上跟candles.size()大小一样 也可以放在初始化函数中
private int days = 1;// 该组蜡烛可供燃烧的最大的天数 初始化为1
/**
* 从文件中读入的蜡烛数组
*
* @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();
} /** * 按照题意的燃烧规则 递归计算最多能燃烧天数
*
* @Core Method 核心方法
* @return int 最多可燃烧天数
* @create 2014年4月6日 下午8:40:52 huay * @history */ public int countDays(){ if(isCandleEnough(days)){
// if(isTotalEnough(days)&& isCandleEnough(days)){
// 满足isCandleEnough(days)则必然满足isTotalEnough(days)
sortList();// 升序排序 以便后续按照最优策略燃烧
lighting(days);// 第i天的蜡烛燃烧，消耗掉
System.out.print(“燃烧” + days + “天后：”);
print();// 显示燃烧后结果
days++;// 指示器
countDays();// 递归向下进行
} else {
// 直到第n天没有n根可供燃烧的蜡烛
days--;// 可供燃烧的最多天数为(n-1)
System.out.println(“该组蜡烛最多燃烧：” + days + “天”);} return days;} /** * 是否满足第i天的燃烧
*
* @param i *
第i天
* @return * @create 2014年4月6日 下午8:40:52 huay * @history */ public Boolean isCandleEnough(int i){ Boolean result = false;if(countCandle()>= i){
result = true;}
return result;}
/**
* 计算长度单位不为0的蜡烛的根数
*
* @return
* @create 2014年4月6日 下午8:40:52 huay
* @history
*/ public int countCandle(){
int count = 0;
for(Integer element : candles){
if(element > 0){
count++;
}
}
return count;}
/**
* 第i天的蜡烛燃烧
*
* @param i
*
第i天
* @create 2014年4月6日 下午8:40:52 huay
* @history
*/ public void lighting(int i){
for(int j = candles.size()1111);// 从长度最长的蜡烛开始，每根消耗一个单位 总共i根
} }
/**
* 按照每根蜡烛的燃烧单位升序排序
*
* @create 2014年4月6日 下午8:40:52 huay
* @history
*/ public void sortList(){
} Collections.sort(candles);// 调用javaAPI函数 默认按照升序排序
/** * 打印输出
*
* @create 2014年4月6日 下午8:40:52 huay * @history */ public void print(){ for(Integer element : candles){
System.out.print(element + “ ”);} System.out.println();} /** * 所有蜡烛燃烧单位的总数是否充足 换用其他燃烧规则后可能用 扩展方法
*
* @param i *
第i天
* @return * @create 2014年4月6日 下午8:40:52 huay * @history */ public Boolean isTotalEnough(int i){ Boolean result = false;int sum =(1 + i)* i / 2;// 到第i天消耗蜡烛单位总量
if(countTotal()>= sum){
result = true;} return result;} /** * 计算蜡烛总的燃烧单位 扩展方法
*
* @return * @create 2014年4月6日 下午8:40:52 huay * @history */ public int countTotal(){ int count = 0;for(Integer element : candles){
} count += element;} return count;/** * 清空数组 作为扩展接口
*
* @create 2014年4月7日 上午12:30:59 huay * @history */ public void clearList(){ candles.removeAll(candles);} /** * 返回蜡烛总个数 扩展接口
*
* @return 蜡烛总个数
* @create 2014年4月6日 下午8:40:52 huay * @history */ public int getSize(){ if(candles!= null){
return candles.size();} else {
return 0;} } /** * @return the candles */ public List
the candles to set */ public void setCandles(List
}
} /** * @return the count */ public int getCount(){ return count;} /** * @param count *
the count to set */ public void setCount(int count){ this.count = count;} /** * @return the days */ public int getDays(){ return days;} /** * @param days *
the days to set */ public void setDays(int days){ this.days = days;} public static void main(String[] args){ CandleADT test = new CandleADT();test.initList(new String[] { “6”, “5”, “2”, “1”, “4”, “3” });// 测试用例
test.countDays();}
四、蜡烛实体
package com.whut.model;/** *
* 蜡烛实体类 带标示符 显示跟踪每根蜡烛在燃烧过程中长度变化
*
** @author: huay * @since: 2014年4月7日 下午10:26:10 * @history: ************************************************
* @file: Candle.java * @Copyright: XX电子股份有限公司.All right reserved.************************************************/
public class Candle { private String candleName;// 蜡烛标示 蜡烛A B C D E等
private int length;// 长度
/**
* 默认构造
*/ public Candle(){
super();}
/**
* @param candleName
* @param length
*/ public Candle(String candleName, int length){
super();
this.candleName = candleName;
this.length = length;}
/**
* @return the candleName
*/ public String getCandleName(){
return candleName;}
}
/** * @param candleName *
the candleName to set */ public void setCandleName(String candleName){ this.candleName = candleName;} /** * @return the length */ public int getLength(){ return length;} /** * @param length *
the length to set */ public void setLength(int length){ this.length = length;}
五、程序运行结果截图
Input.txt文件
Output.txt文件
点击咨询 