2014理工復試機試點蠟燭問題（Java實現(xiàn)）140+胡奧勇一、說明機試點蠟燭的問題，題目具體描述見主程序中類注釋“描述”部分，主要用遞歸算法實現(xiàn)，另需要對蠟燭長度數(shù)組排序；代碼即文檔，講究代碼規(guī)，關鍵邏輯處，注釋寫清楚，只考慮完成功能的話（現(xiàn)實文件讀寫）java實現(xiàn)大約200行代碼；主程序TestCase.java讀輸入文件input.txt,計算每組蠟燭可燃燒最人天數(shù)，并輸出到結果文件output.txt：CandleADT為自定義抽象數(shù)據(jù)結構（復試看數(shù)據(jù)結構時候感觸頗深，順便用一卞）,主要解決蠟燭燃燒這一類的問題，定義了一些擴展接II,主要考慮是解決不限于題目所描述燃燒規(guī)則中求解最人燃燒天數(shù)這一類問題。利用定義的擴展接II可適應解決其他燃燒規(guī)則中蠟燭最大天數(shù)的求解，此處留給有興趣的讀者驗證；（提示，可采用設計模式中的策略模式，在CandleADT中只定義接「I,具體實現(xiàn)交給不同的燃燒規(guī)則類去實現(xiàn)）關鍵的幾個函數(shù)為：sortListO；H升序排序以便后續(xù)按照最優(yōu)策略燃燒lightmg（days）;//第i天的蠟燭燃燒，消耗掉pnntQy/顯示燃燒后結果couiitDays（）;//遞歸向下進行Candle實體，含蠟燭標示，（機試的題目再出難一點，要求跟蹤顯示燃燒過程中具體每根蠟燭的燃燒情況）是為進一步的優(yōu)化，可跟蹤顯示燃燒過程中每根蠟燭燃燒過程中變化情況。顯示即（A4E2C2D2TA3E2C2D2等）相應的CandleADT中l(wèi)ist<Intergea換成list<Candle>相關接II略微更改即可，排序的接II需要自定義比較類。此處筆者不去具體實現(xiàn)，留與感興趣的讀者實現(xiàn)。機試如果要求顯示燃燒過程中每根蠟燭的燃燒情況，估計在2h考試場景，以java程序猿從來不浪費記憶力在記API上（都是即需即查）的性格，沒有網(wǎng)絡條件下，基本上沒人能做出來了，包扌舌筆者在。筆者在調試其他擴展接II過程中就花了不少時間。。。以上所述，包括以下代碼，為機試交卷完成后憑記憶回憶重新輸出的，僅供部交流討論，請注明出處。（歡迎針對代碼設計和實現(xiàn)的討論，聯(lián)系QQ:252302770。）二、主程序package?whut.huay;miportjava.io.BuffeiedReadef；miportjava.10.BuffeiedWriter;miportjava.io.File;miportjava.io.FileNotFoundException;miportjava.io.FileReader;miportjava.io.FileWriter;miportjava.io.IOException;miportjava.util.AnayList;miportjava.util.List;/**<p>*點蠟燭問題主程序*描述：1.一根蠟燭燃燒一天消耗一個單位；*2.第1天要燃燒1根蠟燭；*3.給定一個數(shù)量不定，每根蠟燭長度不定的蠟燭組，求這組蠟燭在滿足條件1,2前提下的最大燃燒天數(shù)4.數(shù)據(jù)來源為mput.txt文件，結果寫入到output.txt**分析：1?仔細分析，對于蠟燭組，最多可燃燒天數(shù)最佳策略為，每次從長度最長的蠟燭開始燃燒;2.第1天若存在1根長度不為0的蠟燭，說明可燃燒至第i天；3.遞歸向下計算第i+1天是否有i+1根長度不為0的蠟燭*4.直到某個第n天時，可供燃燒蠟燭數(shù)量少于11,此時，最人可燃燒天數(shù)為(ml)；</p>author:huavsmce:2014年4月6日下午8:40:52history:************************************************file:TestCase.javaCopyright:XX電子股份.Allrightreseived.************************************************/publicclassTestCase{privatestaticStringsourceFile=nD:/input.txtM;〃輸入文件路徑privatestaticStringdestFile=MD:/output.txtn;//輸出文件路徑*paramargscreate2014年4月7日上午12:36:51huavhistory*/publicstaticvoidniain(Striiig[]aigs){〃讀inpuuxt文件作為題目條件，此處沒有作文件的存在性校驗SuppressW7anungs(nresouiceH)BufferedReaderreader=newBufferedReader(newFileReader(souiceFile));Fileoutputfile=newFile(destFile);if(!outputfile.existsQ){//如果不存在在該路徑下創(chuàng)建文件outputfile.createNewFile();}BufferedWiiterwriter=newBufferedWnter(newFileWnter(outputfile));List<CandleADT>dataList=newAiiavList<CandleADT>Q;Suingtemp=null;//讀文件指針temp=reader.readLine();//逐行讀取wliile(temp!=null){CandleADTcandleADT=newCandleADTQ;caiidleADT.setCount(IiitegeEvalueOf(temp));//奇數(shù)行為蠟燭根數(shù)如：4temp=ieader.readLme();//偶數(shù)行為每根蠟燭可燃燒值如：4222Strmg[]kiddleDetail=temp.split(Hn);caiidleADT.mitList(kiddleDetail)^/初始化數(shù)組temp=reader.readLme();//讀卜一奇數(shù)行dataList.add(candleADT);//添加到list統(tǒng)一處理}//計算文件中每組數(shù)據(jù)的最大可燃燒天數(shù)并另存到文件output.txtfor(CandleADTCandleADT:dataList){CandleADT.countDaysQ;writer.wnte(CandleADT.getDavsQ+}writer.closeO；//關閉}catch(FileNotFoundExceptione){e.piiiitStackTiace();}catch(IOExceptione){e.piiiitStackTiace();}三、每組蠟燭的抽象數(shù)據(jù)結構package?whut.huay;unportjava.util.AnayList;unportjava.util.Collections;unportjava.util.List;/***<p>whut復試點蠟燭問題CandleADT蠟燭組抽象數(shù)據(jù)結構</p>*author:huavsmce:2014年4月6日下午8:40:52liistorv:************************************************file:CaiidleADT.javaCopyright:XX電子股份.Allrightreseived.************************************************/publicclassCandleADT{privateList<Iiitegei>candles=newAixayList<Integer>0^/蠟燭數(shù)組每根長短不一privatemtcount;//蠟燭總根數(shù)實際上跟candles.size()X小一樣也可以放在初始化函數(shù)中privateintdays=1;//該組蠟燭可供燃燒的最人的天數(shù)初始化為1/***從文件中讀入的蠟燭數(shù)組*paramkiddleDetailAiTaycreate2014年4月6日下午8:43:52huayhistory*/tpublicvoidHiitList(Strmg[]kiddleDetailAiray){for(Stimgstring:kiddleDetailAiTay){candles.add(Iiiteger.valueOf(stimg));}System.out.pun?文件中初始讀入:n)；pnnt0;sortList();//升序排序SystenLout.priiit(M排序后輸出:”);pnntO；}}}}*按照題意的燃燒規(guī)則遞歸計算最多能燃燒天數(shù)*CoreMetliod核心方法retmnmt最多可燃燒天數(shù)create2014年4月6日下午8:40:52huayhistory*/publiciiitcountDavsQ{if(isCandleEnough(days)){//if(isTotalEnough(days)&&isCandleEnougli(days)){//滿足isCandleEnough(days)Pl'J必然滿足isTotalEnough(davs)soilListO；//升序排序以便后續(xù)按照最優(yōu)策略燃燒lightiiig(days);//第i天的蠟燭燃燒，消耗掉System.out.prmt(”燃燒”+days+”天后：”)；prmtQ;//顯示燃燒后結果days++；//指示器countDavs();//遞歸向下進行}else{//直到第n天沒有n根可供燃燒的蠟燭days-；〃可供燃燒的最多天數(shù)為(ii-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的蠟燭的根數(shù)*returncreate2014年4月6日下午8:40:52huayhistoiy*/publicmtcountCandle(){mtcount=0;for(Integerelement:candles){if(element>0){count++;}}returncount;}嚴按照每根蠟燭的燃燒單位升序排序按照每根蠟燭的燃燒單位升序排序*create2014年4月6日下午8:40:52huayhistoiy*/publicvoidsoitListQ{*第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根}}}}}}Collections.soil(candles);//調用javaAPI函數(shù)默認按照升序排序*打印輸出*create2014年4月6口卜?午8:40:52huayhistory*/tpublicvoidpiiiitQ{for(Integerelement:candles){System.out.prmt(element+"}System.out.prmthiQ;}*所有蠟燭燃燒單位的總數(shù)是否充足換用其他燃燒規(guī)則后可能用擴展方法*parami第1天returncreate2014年4月6口下午8:40:52huayhistory*/publicBooleanisTotalEnough(iiiti){Booleanresult=false;mtsum=(1+i)計算蠟燭總的燃燒單位擴展方法*returncreate2014年計算蠟燭總的燃燒單位擴展方法*returncreate2014年4月6口卜?午8:40:52huayhistory*/tpubliciiitcountTotalQ{mtcount=0;for(Integerelement:candles){result=tme;}returnresult;}count+=element;retunicount;}/***清空數(shù)組作為擴展接11*create2014年4月7口上午12:30:59huavhistory*/publicvoidclearListQ{candles.removeAll(candles);}/***返回蠟燭總個數(shù)擴展接11*retuni蠟燭總個數(shù)create2014年4月6口下午8:40:52huayhistory*/tpublicmtgetSizeQ{if(candles!=null){returncandles.sizeQ;}else{return0;}}嚴*returnthecandles*/publicList<Integei>getCaiidles(){retunicandles;}/**paramcandlesthecandlestoset*/publicvoidsetCaiidles(List<Integer>candles){tins.candles=candles;/**returnthecount*/publiciiitgetCouiitQ{retunicount;}/**paramcountthecounttoset*/JpublicvoidsetCount(mtcount){tliis.count=count;}/**returnthedays*/publiciiitgetDays(){returndays;}/**paramdaysthedaystosetJ*/publicvoidsetDays(iiitdays){tliis.days=days;}publicstaticvoidinain(Striiig[]aigs){CandleADTtest=newCandleADTQ;test.initList(newStrmg[]{?”5”「2”,T,W,”3”});//測試用例test.countDavsQ;package?whut.model;<p>*蠟燭實體類帶標示符顯示跟蹤每根蠟燭在燃燒過程中長度變化</p>*author:huavsmce:2014年4月7日下午10:26:10liistorv:************************************************file:Caiidle.javaCopyright:XX電子股份.Allrightreseived.************************************************/publicclassCandle{privateStringcaiidleNaine;//蠟燭標示蠟燭ABCDE等privateintlength;//長度*默認構造*/JpublicCaiidleQ{superQ;}/retuinthecandleName*/retuinthecandleName*/publicSuinggetCaiidleNameQ{returncaiidleName;paramcaiidleNameparamlength*/tpublicCaiidle(StrmgcaiidleName,intlength){superQ;tins.caiidleName=candleNaine;tliis.length=length;}/**?paramcaiidleNamethecandleNametoset*/publicvoidsetCaiidleName(StimgcandleName){tliis.caiidleName=candleName;}*retuinthelengtli*/tpublicmtgetLengtli(){returnlength;}/**paramlengththelengtlitoset*/publicvoids