2014武汉理工复试机试点蜡烛问题java-胡奥勇

2014理工复试机试 点蜡烛问题（Java实现）140+胡奥勇一、说明.机试点蜡烛的问题，题目具体描述见主程序中类注释“描述”部分，主要用递归算法实现，另需要对蜡烛长度数组排序；.代码即文档，讲究代码规，关健逻辑处，注释写清楚，只考虑完成功能的话（现实文件读写）java实现大约200行代码；.主程序TestCase.java读输入文件mput.txt,计算每组蜡烛可燃烧最大天数，并输出到结果文件output.txt：.CandleADT为自定义抽象数据结构（发试看数据结构时候感触颇深，顺便用一下）,主要解决蜡烛燃烧这一类的问题，定义了一些扩展接口，主要考虑是解决不限于题目所描述燃烧规则中求解最大燃烧天数这一类问题。利用定义的扩展接II可适应解决其他燃烧规则中蜡烛最大天数的求解，此处留给有兴趣的读者验证；（提示，可采用设计模式中的策略模式，在CandleADT中只定义接口，具体实现交给不同的燃烧规则类去实现）关键的几个函数为：sortListO；H升序排序以便后续按照最优策略燃烧lightmg（days）;H第i天的蜡烛燃烧，消耗掉pnntQy/显示燃烧后结果countDays（）;//递归向下进行.Candle实体，含蜡烛标示，（机试的题目再出难一点，要求跟踪显示燃烧过程中具体每根蜡烛的燃烧情况）是为进一步的优化，可跟踪显示燃烧过程中每根蜡烛燃烧过程中变化情况。显示即（A4B2C2D2TA3B2C2D2等）相应的CandleADT中Bst〈Interger>换成Hst<Candle>相关接II略微更改即可，排序的接II需要自定义比较类。此处笔者不去具体实现，留与感兴趣的读者实现。.机试如果要求显示燃烧过程中每根蜡烛的燃烧情况，估计在2h考试场景，以java程序猿从来不浪费记忆力在记API上（都是即需即查）的性格，没有网络条件下，基本上没人能做出来了，包括笔者在。笔者在调试其他扩展接口过程中就花了不少时间。。。以上所述，包括以下代码，为机试交卷完成后凭记忆回忆重新输出的，仅供部交流讨论，请注明出处。（欢迎针对代码设计和实现的讨论，联系QQ：252302770。）二、主程序package.whut.huay;miportjava.io.BufferedReader;miportjava.io.BufferedWriter;miportjava.io.File;miportjava.io.FileNotFoundException;miportjava.io.FileReader;miportjava.io.FileWnter;miportjava.10.IOException;miportjava.util.AnayList;miportjava.util.List;/***<p>点蜡烛问题主程序描述：1.一根蜡烛燃烧一天消耗一个单位；2.第1天要燃烧1根蜡烛；3.给定一个数量不定，每根蜡烛长度不定的蜡烛组，求这组蜡烛在满足条件1,2前提下的最大燃烧天数4.数据来源为mput.txt文件，结果写入到output.txt*分析：1.仔细分析，对于蜡烛组，最多可燃烧天数最佳策略为，每次从长度最长的蜡烛开始燃烧;2.第1天若存在1根长度不为0的蜡烛，说明可燃烧至第1天；3.递归向下计算第i+1天是否有i+1根长度不为0的蜡烛4.直到某个第n天时，可供燃烧蜡烛数量少于11,此时，最大可燃烧天数为(n-1);</p>*author:huaysmce:2014年4月6口下午8:40:52history:************木**********木************************file:TestCase.javaCopyright:XX电子股份.Allrightreseived.***********木**********木******木*木***************/publicclassTestCase{privatestaticStringsourceFile=nD:/input.txtM;〃输入文件路径privatestaticStringdestFile="D:/output.txt”；〃输出文件路径/**paramargscreate2014年4月7日上午12:36:51huayhistory*/publicstaticvoidniain(Strmg[]aigs){tiy{〃读input.txt文件作为题目条件，此处没有作文件的存在性校验SuppressWaniings(nresourcen)BufferedReaderreader=newBufferedReader(newFileReader(souiceFile));Fileoutputfile=newFile(destFile);if(!outputfile.existsQ){//如果不存在在该路径下创建文件outputfile.createNe\vFile();BufferedWiiterwriter=newBufferedWnter(newFileWntei(outputfile));List<CandleADT>dataList=newAiiayList<CandleADT>Q;Suingtemp=null;//读文件指针temp=reader.readLine();//逐行读取wliile(temp!=null){CandleADTcandleADT=newCandleADT();caiidleADT.setCount(IiitegeEvalueOf(temp));//奇数行为蜡烛根数如：4temp=ieader.readLme();//偶数行为每根蜡烛可燃烧值如：4222String口kiddleDetail=temp.split(Hn);caiidleADT.mitList(kiddleDetail)^/初始化数组temp=reader.readLme();//读下一奇数行dataList.add(candleADT);//添加到list统一处理//计算文件中每组数据的最大可燃烧天数并另存到文件output.txtfbr(CandleADTCandleADT:dataList){CandleADT.countDaysQ;writer.write(CandleADT.getDaysQ+H\r\nM);)wiiter.ck)se();〃关闭}catch(FileNotFoundExceptione){e.prmtStackTiaceQ;}catch(lOExceptione){e.prmtStackTrace();三、每组蜡烛的抽象数据结构package.whut.huay;unportjava.util.AnayList;unportjava.util.Collections;unportjava.util.List;/***<p>试点蜡烛问题CandleADT蜡烛组抽象数据结构</p>*author:huaysince:2014年4月6口下午8:40:52liistory:************************************************file:CaiidleADT.javaCopyright:XX电子股份.Allrightreseived.************************************************/publicclassCandleADT{privateList<Iiitegei>candles=newAixayList<Integer>0^/蜡烛数组每根长短不一privatemtcount;//蜡烛总根数实际上跟candles.size。大小一样也可以放在初始化函数中privatenitdays=1;//该组蜡烛可供燃烧的最大的天数初始化为1/**从文件中读入的蜡烛数组*paramkiddleDetailAiTaycreate2014年4月6日下午8:43:52huayhistory/publicvoidHiitList(Strmg[]kiddleDetailAiray){for(Stimgstring:kiddleDetailAiTay){candles.add(Iiiteger.valueOf(stimg));)System.out.print("文件中初始读入：”);pnnt0;sortList();//升序排序System.out.pnnt("排序后输出：)print。；按照题意的燃烧规则递归计算最多能燃烧天数*CoreMetliod核心方法retmnmt最多可燃烧天数create2014年4月6口下午8:40:52huayhistory/publicmtcountDaysQ{if(isCandleEnough(days)){//if(isTotalEnough(days)&&isCandleEnougli(days)){//满足isCandleEnough(days)则必然满足isTotalEnough(days)soilListO；//升序排序以便后续按照最优策略燃烧lightiiig(days);//第i天的蜡烛燃烧，消耗掉System.out.print(“燃烧”+days+”天后：,f);prmtQ;//显示燃烧后结果days++;//指示器countDays();//递归向下进行)else{//直到第n天没有n根可供燃烧的蜡烛days--;〃可供燃烧的最多天数为(n-1)System.out.println("该组蜡烛最多燃烧："+days+"天))returndays;)是否满足第1天的燃烧parami第i天retuincreate2014年4月6日下午8:40:52huayhistory/publicBooleanisCaiidleEnough(iiiti){Booleanresult=false;if(countCaiidleQ>=i){result=tme;returnresult;计算长度单位不为0的蜡烛的根数*returncreate2014年4月6日下午8:40:52huayhistoiy/publicmtcountCandle(){mtcount=0;fbr(Integerelement:candles){if(element>0){count++;))returncount;}/**第1天的蜡烛燃烧*parami第i天create2014年4月6日下午8:40:52huayhistoiy/publicvoidlightmg(inti){for(intj=candles.sizeQ-1;j>candles.size()-1-i;j-){〃从燃烧单位最多的蜡烛开始烧起，第1天烧1根//kiddles.sizeQ-1-(kiddles.size()-1-i)=i彳、candles.set(j,candles.get(j)-1);//从长度最长的蜡烛开始，每根消耗一个单位总共1根)}/**按照每根蜡烛的燃烧单位升序排序*create2014年4月6日下午8:40:52huayhistoiy/publicvoidsoitListQ{Collections.soil(candles);//调用javaAPI函数默认按照升序排序打印输出*create2014年4月6日下午8:40:52huay*history*/Jpublicvoidprint。{fbr(Integerelement:candles){System.out.prmt(element+”)System.out.prmthiQ;}/**所有蜡烛燃烧单位的总数是否充足换用其他燃烧规则后可能用扩展方法*parami第i天returncreate2014年4月6日下午8:40:52huayhistory/publicBooleanisTotalEnough(iiiti){Booleanresult=false;mtsum=(1+i)*i/2;//到第i天消耗蜡烛单位总量if(countTotal()>=sum){result=tme;)returnresult;}/**计算蜡烛总的燃烧单位扩展方法*returncreate2014年4月6日下午8:40:52huay*history*/JpublicmtcountTotalQ{mtcount=0;fbr(Integerelement:candles){count+=element;)retunicount;}/**清空数组作为扩展接11*create2014年4月7口上午12:30:59huayhistory/publicvoidclearListQ{candles.removeAll(candles);}/**返回蜡烛总个数扩展接11*return蜡烛总个数create2014年4月6日下午8:40:52huayhistory*/fpublichitgetSizeQ{if(candles!=null){returncandles.sizeQ;)else{return0;)}/**returnthecandles*/publicList<Integei>getCaiidles(){retunicandles;}/**paramcandlesthecandlestoset*/publicvoidsetCaiidles(List<Integer>candles){tins.candles=candles;)/***returnthecount*/publichitgetCouiitQ{retunicount;}/**paramcountthecounttoset*/JpublicvoidsetCount(mtcount){tliis.count=count;}/**returnthedays/publichitgetDays(){returndays;}/**paramdaysthedaystosetJ/publicvoidsetDays(mtdays){tliis.days=days;}publicstaticvoidinain(Striiig[]args){CandleADTtest=newCandleADT();test.initList(newStrmg[]{26“J‘5“，“2”，})//测试用例test.countDaysQ;、蜡烛实体package.whut.model;芦*<p>*蜡烛实体类带标示符显示跟踪每根蜡烛在燃烧过程中长度变化</p>*author:huaysince:2014年4月7口下午10:26:10liistory:************************************************file:Caiidle.javaCopyright:XX电子股份.Allrightreseived.*木**********木****木*木**************木*************/publicclassCandle{privateStringcaiidleNaine;//蜡烛标示蜡烛ABCDE等privateintlength;//长度/**默认构造/fpublicCaiidleQ{superQ;}/**paramcaiidleNameparamlength*/publicCaiidle(StrmgcaiidleName,intlength){superQ;tins.caiidleName=candleNaine;tills,length=length;}/**retuinthecandleName/publicStimggetCaiidleNameQ{returncaiidleName;/**•paramcaiidleNamethecandleNametoset*/publicvoidsetCaiidleName(StimgcandleName){tliis.caiidleName=candleName;}/**retuinthelengtli*/Jpublic