武汉理工复试机试 点蜡烛问题java胡奥勇.docx
- 文档编号:10114722
- 上传时间:2023-05-23
- 格式:DOCX
- 页数:18
- 大小:51.38KB
武汉理工复试机试 点蜡烛问题java胡奥勇.docx
《武汉理工复试机试 点蜡烛问题java胡奥勇.docx》由会员分享,可在线阅读,更多相关《武汉理工复试机试 点蜡烛问题java胡奥勇.docx(18页珍藏版)》请在冰点文库上搜索。
武汉理工复试机试点蜡烛问题java胡奥勇
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实体,含蜡烛标示,(机试的题目再出难一点,要求跟踪显示燃烧过程中具体每根蜡烛的燃烧情况)是为进一步的优化,可跟踪显示燃烧过程中每根蜡烛燃烧过程中变化情况。
显示即(A4B2C2D2A3B2C2D2等)相应的CandleADT中list
此处笔者不去具体实现,留与感兴趣的读者实现。
6.机试如果要求显示燃烧过程中每根蜡烛的燃烧情况,估计在2h考试场景,以java程序猿从来不浪费记忆力在记API上(都是即需即查)的性格,没有网络条件下,基本上没人能做出来了,包括笔者在内。
笔者在调试其他扩展接口过程中就花了不少时间。
。
。
以上所述,包括以下代码,为机试交卷完成后凭记忆回忆重新输出的,仅供内部交流讨论,转载请注明出处。
(欢迎针对代码设计和实现的讨论,联系QQ:
252302770。
)
二、主程序
packagecom.whut.huay;
importjava.io.BufferedReader;
importjava.io.BufferedWriter;
importjava.io.File;
importjava.io.FileNotFoundException;
importjava.io.FileReader;
importjava.io.FileWriter;
importjava.io.IOException;
importjava.util.ArrayList;
importjava.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电子股份有限公司.Allrightreserved.
************************************************/
publicclassTestCase{
privatestaticStringsourceFile="D:
/input.txt";//输入文件路径
privatestaticStringdestFile="D:
/output.txt";//输出文件路径
/**
*
*@paramargs
*@create2014年4月7日上午12:
36:
51huay
*@history
*/
publicstaticvoidmain(String[]args){
try{
//读input.txt文件作为题目条件,此处没有作文件的存在性校验
@SuppressWarnings("resource")
BufferedReaderreader=newBufferedReader(newFileReader(sourceFile));
Fileoutputfile=newFile(destFile);
if(!
outputfile.exists()){
//如果不存在在该路径下创建文件
outputfile.createNewFile();
}
BufferedWriterwriter=newBufferedWriter(newFileWriter(outputfile));
List
Stringtemp=null;//读文件指针
temp=reader.readLine();//逐行读取
while(temp!
=null){
CandleADTcandleADT=newCandleADT();
candleADT.setCount(Integer.valueOf(temp));//奇数行为蜡烛根数如:
4
temp=reader.readLine();//偶数行为每根蜡烛可燃烧值如:
4222
String[]kiddleDetail=temp.split("");
candleADT.initList(kiddleDetail);//初始化数组
temp=reader.readLine();//读下一奇数行
dataList.add(candleADT);//添加到list统一处理
}
//计算文件中每组数据的最大可燃烧天数并另存到文件output.txt
for(CandleADTCandleADT:
dataList){
CandleADT.countDays();
writer.write(CandleADT.getDays()+"\r\n");
}
writer.close();//关闭
}catch(FileNotFoundExceptione){
e.printStackTrace();
}catch(IOExceptione){
e.printStackTrace();
}
}
}
三、每组蜡烛的抽象数据结构
packagecom.whut.huay;
importjava.util.ArrayList;
importjava.util.Collections;
importjava.util.List;
/**
*
*
*whut复试点蜡烛问题CandleADT蜡烛组抽象数据结构
*
*
*@author:
huay
*@since:
2014年4月6日下午8:
40:
52
*@history:
************************************************
*@file:
CandleADT.java
*@Copyright:
XX电子股份有限公司.Allrightreserved.
***********************************************
*/
publicclassCandleADT{
privateList
privateintcount;//蜡烛总根数实际上跟candles.size()大小一样也可以放在初始化函数中
privateintdays=1;//该组蜡烛可供燃烧的最大的天数初始化为1
/**
*从文件中读入的蜡烛数组
*
*@paramkiddleDetailArray
*@create2014年4月6日下午8:
43:
52huay
*@history
*/
publicvoidinitList(String[]kiddleDetailArray){
for(Stringstring:
kiddleDetailArray){
candles.add(Integer.valueOf(string));
}
System.out.print("文件中初始读入:
");
print();
sortList();//升序排序
System.out.print("排序后输出:
");
print();
}
/**
*按照题意的燃烧规则递归计算最多能燃烧天数
*
*@CoreMethod核心方法
*@returnint最多可燃烧天数
*@create2014年4月6日下午8:
40:
52huay
*@history
*/
publicintcountDays(){
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+"天");
}
returndays;
}
/**
*是否满足第i天的燃烧
*
*@parami
*第i天
*@return
*@create2014年4月6日下午8:
40:
52huay
*@history
*/
publicBooleanisCandleEnough(inti){
Booleanresult=false;
if(countCandle()>=i){
result=true;
}
returnresult;
}
/**
*计算长度单位不为0的蜡烛的根数
*
*@return
*@create2014年4月6日下午8:
40:
52huay
*@history
*/
publicintcountCandle(){
intcount=0;
for(Integerelement:
candles){
if(element>0){
count++;
}
}
returncount;
}
/**
*第i天的蜡烛燃烧
*
*@parami
*第i天
*@create2014年4月6日下午8:
40:
52huay
*@history
*/
publicvoidlighting(inti){
for(intj=candles.size()-1;j>candles.size()-1-i;j--){
//从燃烧单位最多的蜡烛开始烧起,第i天烧i根
//kiddles.size()-1-(kiddles.size()-1-i)=i个
candles.set(j,candles.get(j)-1);//从长度最长的蜡烛开始,每根消耗一个单位总共i根
}
}
/**
*按照每根蜡烛的燃烧单位升序排序
*
*@create2014年4月6日下午8:
40:
52huay
*@history
*/
publicvoidsortList(){
Collections.sort(candles);//调用javaAPI函数默认按照升序排序
}
/**
*打印输出
*
*@create2014年4月6日下午8:
40:
52huay
*@history
*/
publicvoidprint(){
for(Integerelement:
candles){
System.out.print(element+"");
}
System.out.println();
}
/**
*所有蜡烛燃烧单位的总数是否充足换用其他燃烧规则后可能用扩展方法
*
*@parami
*第i天
*@return
*@create2014年4月6日下午8:
40:
52huay
*@history
*/
publicBooleanisTotalEnough(inti){
Booleanresult=false;
intsum=(1+i)*i/2;//到第i天消耗蜡烛单位总量
if(countTotal()>=sum){
result=true;
}
returnresult;
}
/**
*计算蜡烛总的燃烧单位扩展方法
*
*@return
*@create2014年4月6日下午8:
40:
52huay
*@history
*/
publicintcountTotal(){
intcount=0;
for(Integerelement:
candles){
count+=element;
}
returncount;
}
/**
*清空数组作为扩展接口
*
*@create2014年4月7日上午12:
30:
59huay
*@history
*/
publicvoidclearList(){
candles.removeAll(candles);
}
/**
*返回蜡烛总个数扩展接口
*
*@return蜡烛总个数
*@create2014年4月6日下午8:
40:
52huay
*@history
*/
publicintgetSize(){
if(candles!
=null){
returncandles.size();
}
else{
return0;
}
}
/**
*@returnthecandles
*/
publicList
returncandles;
}
/**
*@paramcandles
*thecandlestoset
*/
publicvoidsetCandles(List
this.candles=candles;
}
/**
*@returnthecount
*/
publicintgetCount(){
returncount;
}
/**
*@paramcount
*thecounttoset
*/
publicvoidsetCount(intcount){
this.count=count;
}
/**
*@returnthedays
*/
publicintgetDays(){
returndays;
}
/**
*@paramdays
*thedaystoset
*/
publicvoidsetDays(intdays){
this.days=days;
}
publicstaticvoidmain(String[]args){
CandleADTtest=newCandleADT();
test.initList(newString[]{"6","5","2","1","4","3"});//测试用例
test.countDays();
}
}
四、蜡烛实体
packagecom.whut.model;
/**
*
*蜡烛实体类带标示符显示跟踪每根蜡烛在燃烧过程中长度变化
*
*
*@author:
huay
*@since:
2014年4月7日下午10:
26:
10
*@history:
************************************************
*@file:
Candle.java
*@Copyright:
XX电子股份有限公司.Allrightreserved.
************************************************/
publicclassCandle{
privateStringcandleName;//蜡烛标示蜡烛ABCDE等
privateintlength;//长度
/**
*默认构造
*/
publicCandle(){
super();
}
/**
*@paramcandleName
*@paramlength
*/
publicCandle(StringcandleName,intlength){
super();
this.candleName=candleName;
this.length=length;
}
/**
*@returnthecandleName
*/
publicStringgetCandleName(){
returncandleName;
}
/**
*@paramcandleName
*thecandleNametoset
*/
publicvoidsetCandleName(StringcandleName){
this.candleName=candleName;
}
/**
*@returnthelength
*/
publicintgetLength(){
returnlength;
}
/**
*@paramlength
*thelengthtoset
*/
publicvoidsetLength(intlength){
this.length=length;
}
}
五、程序运行结果截图
Input.txt文件
Output.txt文件
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 武汉理工复试机试 点蜡烛问题java 胡奥勇 武汉理工 复试 蜡烛 问题 java