《算法設計與分析》實驗一

《算法設計與分析》

實驗報告一學生姓名張曾然專業(yè)、班級16軟件二班指導教師唐國峰成績計算機與信息工程學院軟件工程系2018年9月19日實驗一：遞歸策略運用練習一、 實驗目的本次實驗是針對遞歸算法的算法設計及應用練習，旨在加深學生對該算法原理的理解，提高學生運用該算法解決問題的能力。二、 實驗步驟與要求實驗前復習課程所學知識以及閱讀和理解指定的課外閱讀材料；學生獨自完成實驗指定內容；實驗結束后，用統(tǒng)一的實驗報告模板編寫實驗報告。提交說明：（1） 電子版提交說明：a需要提交Winrar壓縮包，文件名為“《算法設計與分析》實驗一_學號_姓名”，如“《算法設計與分析》實驗一_09290101_張三”。b壓縮包內為一個“《算法設計與分析》實驗一_學號_姓名”命名的頂層文件夾，其下為兩個文件夾，一個文件夾命名為“源程序”另一個文件夾命名為“實驗報告電子版”。其下分別放置對應實驗成果物。（2） 打印版提交說明：a不可隨意更改模板樣式。b字體：中文為宋體，大小為10號字，英文為TimeNewRoman，大小為10號字。c行間距：單倍行距。（3） 提交截止時間：2018年10月10日16:00。三、 實驗項目1.運用遞歸策略設計算法實現(xiàn)下述題目的求解過程。題目列表如下：【必做題】（1） 運動會開了N天，一共發(fā)出金牌M枚。第一天發(fā)金牌1枚加剩下的七分之一枚，第二天發(fā)金牌2枚加剩下的七分之一枚，第3天發(fā)金牌3枚加剩下的七分之一枚，以后每天都照此辦理。到了第N天剛好還有金牌N枚，到此金牌全部發(fā)完。編程求N和M。（2） 國王分財產。某國王臨終前給兒子們分財產。他把財產分為若干份，然后給第一個兒子一份，再加上剩余財產的1/10;給第二個兒子兩份，再加上剩余財產的1/10;;給第i個兒子i份，再加上剩余財產的1/10。每個兒子都竊竊自喜。以為得到了父王的偏愛，孰不知國王是“一碗水端平”的。請用程序回答，老國王共有幾個兒子？財產共分成了多少份？（3）出售金魚問題：第一次賣出全部金魚的一半加二分之一條金魚；第二次賣出乘余金魚的三分之一加三分之一條金魚；第三次賣出剩余金魚的四分之一加四分之一條金魚；第四次賣出剩余金魚的五分之一加五分之一條金魚；現(xiàn)在還剩下11條金魚，在出售金魚時不能把金魚切開或者有任何破損的。問這魚缸里原有多少條金魚？（4）某路公共汽車，總共有八站，從一號站發(fā)軒時車上已有n位乘客，到了第二站先下一半乘客，再上來了六位乘客；到了第三站也先下一半乘客，再上來了五位乘客，以后每到一站都先下車上已有的一半乘客，再上來了乘客比前一站少一個……，到了終點站車上還有乘客六人，問發(fā)車時車上的乘客有多少？（5） 猴子吃桃。有一群猴子摘來了一批桃子，猴王規(guī)定每天只準吃一半加一只（即第二天吃剩下的一半加一只，以此類推），第九天正好吃完，問猴子們摘來了多少桃子？（6） 小華讀書。第一天讀了全書的一半加二頁，第二天讀了剩下的一半加二頁，以后天天如此……，第六天讀完了最后的三頁，問全書有多少錢頁？（7） 日本著名數(shù)學游戲專家中村義作教授提出這樣一個問題：父親將2520個桔子分給六個兒子。分完后父親說：“老大將分給你的桔子的1/8給老二；老二拿到后連同原先的桔子分1/7給老三；老三拿到后連同原先的桔子分1/6給老四；老四拿到后連同原先的桔子分1/5給老五；老五拿到后連同原先的桔子分1/4給老六；老六拿到后連同原先的桔子分1/3給老大”。結果大家手中的桔子正好一樣多。問六兄弟原來手中各有多少桔子？（8） 某種傳染病第一天只有一個患者，前5天為潛伏期，不發(fā)作也不會傳染人，第6天開始發(fā)作，從發(fā)作到治愈需要5天時間，期間每天傳染3個人，求第N天共有多少患者。【選做題】（5選3）（1） 為了保障社會秩序，保護人民群眾生命財產安全，警察叔叔需要與罪犯斗智斗勇，因而需要經(jīng)常性地進行體力訓練和智力訓練！某批警察叔叔正在進行智力訓練：123456789=110;請看上邊的算式，為了使等式成立，需要在數(shù)字間填入加號或者減號（可以不填，但不能填入其它符號）。之間沒有填入符號的數(shù)字組合成一個數(shù)，例如：12+34+56+7-8+9就是一種合格的填法；123+4+5+67-89是另一個可能的答案。請你利用計算機的優(yōu)勢，幫助警察叔叔快速找到所有答案。每個答案占一行。形如：12+34+56+7-8+9123+4+5+67-89（2） 遞歸將一個整數(shù)輸出。形如654321，輸出1,2,3,4,5,6（3） 用遞歸實現(xiàn)分解質因數(shù)。形如：12=2*2*3（4） 50個階梯，你一次可以上一階或兩階，走上去，共有多少種走法？（5） 電話號碼對應的字符組合。題目：在電話或者手機上，一個數(shù)字如2對應著字母ABC，7對應著PQRS。那么數(shù)字串27所對應的字符的可能組合就有3*4=12種（如AP，BR等）。現(xiàn)在輸入一個3到11位長的電話號碼，請打印出這個電話號碼所對應的字符的所有可能組合和組合數(shù)。四、實驗過程題目一：運動會開了N天，一共發(fā)出金牌M枚。第一天發(fā)金牌1枚加剩下的七分之一枚，第二天發(fā)金牌2枚加剩下的七分之一枚，第3天發(fā)金牌3枚加剩下的七分之一枚，以后每天都照此辦理。到了第N天剛好還有金牌N枚，到此金牌全部發(fā)完。編程求N和M。1.題目分析由題意得，本題存在兩個未知數(shù)，分別是金牌的總數(shù)m和運動會進行的天數(shù)n，所以很難從第一天開始進行正向推倒從而算出本題的答案，經(jīng)過思考我發(fā)現(xiàn)本題的突破口是在“到了第N天剛好還有金牌N枚”這句話上，所以可以從最后一天發(fā)的金牌數(shù)中開始切入。天數(shù)(D)NN-1發(fā)之前有多少枚(B)NX發(fā)之后剩多少枚{A)0 N由題意得，當天發(fā)的金牌數(shù)是當天的天數(shù)D加上發(fā)之前的數(shù)量發(fā)之后的數(shù)量0*1/7,同時也等于&A。從而可以根據(jù)N-1天的數(shù)據(jù)建立方程：X-N=(N-1)+X*1/7-(N-1)*1/7X*6/7=N+(N-ir6/7X=7/6*N+(N-1)推倒出了表達式就可以采用遞歸的思想來進行問題的解答了遞歸有兩個重要組成部分：遞歸方程：前一天所剩金牌=當天所剩金牌*7/6+當天天數(shù)。邊界條件：當天的前一天所剩金牌數(shù)和當天的天數(shù)相等。算法構造在此論證算法設計中的一些必要的設計依據(jù)。已經(jīng)完成了題目分析下面就要將遞歸方程：(前一天所剩金牌-當天天數(shù))*6/7=當天所剩金牌用代碼表示出來，可以通過一個二元數(shù)組或者鏈表結構將當前天數(shù)和剩余的金牌數(shù)存放起來，設置一個哨兵用來判斷(前一天剩余的金牌數(shù)-當天天數(shù))能否被7整除,若果不能被7整除則證明所設置的初值不正確，算法實現(xiàn)程序源代碼(請寫入必要的注釋)。First類：;publicclassFirst{publicstaticintbroken(intnum,inttoday){//num為前一天所剩的金牌數(shù)，today為當天天數(shù)if((num-today)%7!=0) 〃判斷前一天所剩金牌數(shù)-當天天數(shù)能否被7整除，不可以返回0return0;else 〃如果可以返回當天剩余金牌的數(shù)量return(num-today)*6/7;}}測試類：;importjava.util.LinkedList;publicclassTest{staticFirstone=newFirst();publicstaticvoidmain(String[]args){LinkedList<Integer>lt=newLinkedList<Integer>();for(intn=3;n<10;n++){//根據(jù)題干可知，n>=3，將n的初值設為3可以降低遞歸算法的重復率for(intm=1;m<100;m++){//利用窮舉法計算m的值lt.add(0,m);//第一天沒發(fā)之前一共有m枚金牌for(inti=1;i<=n;i++){//調用第一題中的判斷算法，依次計算每天發(fā)了多少枚lt.add(i,one.broken(lt.get(i-1),i));//到達第n天依舊沒有符合終止條件的情況跳出循環(huán)}if(lt.get(n-1)-n==0){//第n天發(fā)了門枚金牌循環(huán)終止條件System.out.println("金牌總數(shù)為："+lt.get(0)+”，運動會進行天數(shù)為：”+n);}}}}}4.運行結果Problems 3-<te-rmnaied>Te-it*4'|[PawApplcatian]C:\PragramFilesVava''^dklJS.D72\bm\jaMJW.exe1250擊牌邑踮汨運法蘭蟲行尹村由滴經(jīng)驗歸納算法的設計遠比想象中的要困難，不緊要熟練掌握高級語言的使用方法，還要透徹的理解題意，僅僅知道遞歸方程和終結條件是遠遠不夠的，還要在恰當?shù)奈恢眉由蠝蚀_的判定條件，否則程序將無法達到目標結果。題目二：國王分財產。某國王臨終前給兒子們分財產。他把財產分為若干份，然后給第一個兒子一份，再加上剩余財產的1/10；給第二個兒子兩份，再加上剩余財產的1/10； ；給第i個兒子i份，再加上剩余財產的1/10。每個兒子都竊竊自喜。以為得到了父王的偏愛，孰不知國王是“一碗水端平”的。請用程序回答，老國王共有幾個兒子？財產共分成了多少份？。1.題目分析本題也存在兩個未知數(shù)，國王兒子的數(shù)量n，以及財產的總數(shù)m，由題意得，國王分財產是“一碗水端平的”所以有多少個兒子財產就被分成了多少份，所以可以從最后一個兒子也就是第i個兒子入手，如下圖所示：第幾個兒子(N)1i-1發(fā)之前有多少財廣(B)m/iX發(fā)之后剩多少財產(A)□m/i由題意得，第j個兒工得到了功份總財產，所以可得出方程組:X-l/i=(i-l)+X*1/104-(1-1)*1/10X=(1-1)4-10/9+m/i遞歸方程為：前一位王子所剩財產=后一位王子所剩財產數(shù)*10/9+前一位王子數(shù)。邊界條件：當?shù)趇個兒子分到m/i財產，每個王子都能被9整除時循環(huán)終止。算法構造在此論證算法設計中的一些必要的設計依據(jù)。本算法我運用了兩個循環(huán)，外循環(huán)是判斷循環(huán)終止條件(結合實際當份數(shù)第一次滿足條件時，即跳出循環(huán)不然國王的孩子會越來越多)，內循環(huán)判斷是否每個王子得到的財產都能被9整除。算法實現(xiàn)程序源代碼(請寫入必要的注釋)。;publicclassTreasure{publicstaticvoidmain(String[]args){inti=0;intn=0;intprince[]=newint[100]; 〃規(guī)定一個邊界值，以免數(shù)值過大影響計

算速度(算速度(本題已經(jīng)確定份數(shù)在100份以內)while(true)(n=n+9;prince[n]=n;for(i=n-1;i>=1;i--)所擁有的財產能否被9整除{斷前一位if(prince[i+1]%9!=0)〃如果沒有break則繼續(xù)循環(huán)〃因為財產數(shù)必為9的倍數(shù)〃第n個王子得到n份〃從最后一個王子開始往前算每一位王子〃不能則跳出循環(huán)，n再加9,可以的話再判(break;}elseprince[i]=prince[i+1]*10/9+i;}if(i==0)break; 〃當所有王子所擁有的財產都能被9整除，及經(jīng)過若干次i--之后i變成了零} 〃跳出外循環(huán)，完成循環(huán)終止條件，得出結果System.out.println("國王一共有"+n+"個兒子");System.out.println("一共有資產"+n*prince[1]+"，總共分了"+prince[1]+"份");4.運行結果J^.-'adociDeclaration@Console<terminated^Trea&une[JarjaApplication]C:\PragramFile&\Java\jdk1,8.D_73-\fcin\javaw.exe（2018年9月26」I-—11:41:36）HZ-一箕iWl丑％■:箕町l.r5.經(jīng)驗歸納本題與第一題相似只是細微的部分發(fā)生了改變，設計的難點還是很難找到循環(huán)終止條件題目三出售金魚問題：第一次賣出全部金魚的一半加二分之一條金魚；第二次賣出乘余金魚的三分之一加三分之一條金魚；第三次賣出剩余金魚的四分之一加四分之一條金魚；第四次賣出剩余金魚的五分之一加五分之一條金魚；現(xiàn)在還剩下11條金魚，在出售金魚時不能把金魚切開或者有任何破損的。問這魚缸里原有多少條金魚？1.題目分析由題意得，本題中僅存在一個未知數(shù)，一開始有多少條金魚，由于已經(jīng)給出了最后一天賣出了11條金魚這個信息所以，從后往前便能推出每一天賣之前有多少條金魚：第幾次賣魚間 LJLJLJ2n賣之前有多少(B)11X■I4■1?■賣之后有多少(A)011X■1ll=X-(X/5+l/5)X=1414=X-(X/4+l/4)X=29如上圖所示第三天賣之前還有29條金魚，經(jīng)過歸納可得遞推公式：f(n)=f(n-1)-[f(n-1)/n+1/n]f(n-1)=[n/(1-n)]*[f(n)+1/n]f(n)=[(n+1/n]*[f(n+1)+1/(n+1)]f(n)表示前一次有多少條魚f(n+1)表示后一次有多少條魚；邊界條件：當函數(shù)中初值取值為5的時候，將11往前傳遞算法構造在此論證算法設計中的一些必要的設計依據(jù)。本題是最顯而易見的循環(huán)算法，將第幾次賣魚看做一個函數(shù)給定一個初值，沒有返回值的時候就根據(jù)遞推方程繼續(xù)調用自身，直至初值為5將數(shù)據(jù)傳遞歸還算法實現(xiàn)程序源代碼(請寫入必要的注釋)。;publicclassFish{publicstaticfloatfish(floatn){ 〃第幾次賣魚時共有多少條魚if(n==5)return(11); 〃如果是第五次賣魚，則有11條魚elsereturn((n+1)/n)*(fish(n+1)+1/(n+1));〃前一次賣的魚等于((n+1)/n)乘以后一次賣的魚加上后一次分之一}publicstaticvoidmain(String[]args){floatn;n=fish(1); 〃第1次賣魚時共有多少條魚System.out.println("第一次共有"+n+"條魚");}運行結果

JavadocDeclarationSConsole'i'：<termin3ted>Fish[JavaApplication]C;\ProgramI-il^^\Java\jclk1.8.0_73\bin\javaw,exe（201S年9月版日T—/iOTHO）第二禎井有5赤條魚5.經(jīng)驗歸納本題運用了最基本的遞歸算法思路，自身調用自身，達成條件后將數(shù)據(jù)傳遞歸還，加深了我對遞歸含義的運用，以及對該類算法的理解。題目四：某路公共汽車，總共有八站，從一號站發(fā)軒時車上已有n位乘客，到了第二站先下一半乘客，再上來了六位乘客；到了第三站也先下一半乘客，再上來了五位乘客，以后每到一站都先下車上已有的一半乘客，再上來了乘客比前一站少一個……，到了終點站車上還有乘客六人，問發(fā)車時車上的乘客有多少？O1.題目分析本題與第三題類似，由題意得：1站號：76到站時:6X■■■4下車后：0 6己知到達八號站臺時還剩六人，根據(jù)題意可列出方程:X*l/2+(8-7)=6X二10,■.從后往前即可依次推出歸納得到了遞歸方程:5(N)*l/2+(8-N)=S(N+l)邊界條件：到達八號站臺，并將6作為返還值2.算法構造2.在此論證算法設計中的一些必要的設計依據(jù)。本題是最顯而易見的循環(huán)算法，將第幾站上車看做一個函數(shù)并給定傳入的參數(shù)，沒有返回值的時候就根據(jù)遞推方程繼續(xù)調用自身，直至傳入?yún)?shù)為6時將數(shù)據(jù)傳遞歸還n+1）+n3.n+1）+n3.算法實現(xiàn)程序源代碼(請寫入必要的注釋)。;;publicclassBus{publicstaticfloatstation(floatn){ 〃第幾站上車時車上有多少人〃第一站上車時人員不發(fā)生變動，所以將第二站作為始發(fā)點if(n<7)return(2*(station(n+1)+n-7)); 〃如果傳入值不是最后一站則向后遞歸尋找邊界值elsereturn(6); }publicstaticvoidmain(String[]args){floatn;n=station(1); 〃第1站公交車上有多少人System.out.println("第一站公交車上有"+n+"人")；}}運行結果_Prablani-. r-De<aratiomSConsole工^tenminated>Bus[JavaApplication!C^Programriles\Javd\jdk1.8.0_73\|jin'\javaw.exe〔2。18年9月西日下斗8:49:54)至一Fl冬土，上fl1心.時經(jīng)驗歸納本題運用了最基本的遞歸算法思路，自身調用自身，達成條件后將數(shù)據(jù)傳遞歸還，加深了我對遞歸含義的運用，以及對該類算法的理解。（五）題目五：猴子吃桃。有一群猴子摘來了一批桃子，猴王規(guī)定每天只準吃一半加一只（即第二天吃剩下的一半加一只，以此類推），第九天正好吃完，問猴子們摘來了多少桃子？。1.題目分析：由題意得，本題只存在一個未知數(shù)摘來桃子的數(shù)量（與有多少只猴子是無關的），分析后得出第九天剛好吃完，而第九天也吃了剩下的二分之一加1，所以第九天吃之前剩了2個桃子，第八天吃完剩了兩個，如下表可得遞歸方程：1天數(shù)：LJUU吃之前:26XBh**吃之后:026■?■?X-2=X*1/2+1X=6X-6=X*1/2+1X=14E[N)=[E(N+1)+1)*2■遞歸方程：E(N)=(E(N+1)+1)*2邊界條件：N等于9時，返還值為2算法構造在此論證算法設計中的一些必要的設計依據(jù)。本題是最顯而易見的循環(huán)算法，將第幾天吃之前還剩多少看做一個函數(shù)并給定傳入的參數(shù)，沒有返回值的時候就根據(jù)遞推方程繼續(xù)調用自身，直至傳入?yún)?shù)為9時將數(shù)據(jù)傳遞歸還算法實現(xiàn)程序源代碼(請寫入必要的注釋)。;publicclassMonkey{publicstaticfloateatPeach(floatn){if(n==9)return(2); 〃循環(huán)終止條件，第九天吃之前剩了兩個桃子elsereturn(2*(eatPeach(n+1)+1));//如果不滿足條件，當天吃之前剩的=((后一天的)+1)*2}publicstaticvoidmain(String[]args){floatn;n=eatPeach(1); 〃算第幾天猴子吃之前有多少個桃子eatPeach方法體中寫天數(shù)System.out.println("猴子們摘來了"+n+"個桃子”);}}運行結果■■Javadoc『；Declaration□ConsoleK<terminatedl>Monkey[JavaApplication]C:\PragramFilesVava\jdk1,8,D_7vaw.exe(2018^9026日下午7誨5:01)稚子們摘^71022-0個桃亍經(jīng)驗歸納本題運用了最基本的遞歸算法思路，自身調用自身，達成條件后將數(shù)據(jù)傳遞歸還，加深了我對遞歸含義的運用，以及對該類算法的理解。題目六：小華讀書。第一天讀了全書的一半加二頁，第二天讀了剩下的一半加二頁，以后天天如此……，第六天讀完了最后的三頁，問全書有多少錢頁？。題目分析由題意得，第六天剛好讀完最后三頁，所以如下表可得遞歸方程：1天數(shù)：654?■■1>-4—、 、皿L美乙刖：310--■--■讀之后：0 3X-3=X*1/2+2X=10R(N)二(R(N+1)+2)*2邊界條件：N等于6時，返還值是3算法構造在此論證算法設計中的一些必要的設計依據(jù)。在此論證算法設計中的一些必要的設計依據(jù)。本題是最顯而易見的循環(huán)算法，將第幾天讀之前還剩多少頁沒讀看做一個函數(shù)并給定傳入的參數(shù)，沒有返回值的時候就根據(jù)遞推方程繼續(xù)調用自身，直至傳入?yún)?shù)為6時將數(shù)據(jù)傳遞歸還算法實現(xiàn)程序源代碼(請寫入必要的注釋)。;publicclassReading{publicstaticfloatRead(floatn){if(n==6)return(3); 〃循環(huán)終止條件，第六天讀之前有3頁沒讀elsereturn(2*(Read(n+1)+2));//如果不滿足條件，當天讀之前剩的頁數(shù)=((后一天的)+2)*2}publicstaticvoidmain(String[]args){floatn;n=Read(1); 〃算第1天讀之前有多少頁沒讀等價于求全書有多少頁System.out.println("整本書有"+n+"頁")；運行結果u,_Problpims。hiuadot：■；C^cla-：ationSConsoleS3<terminated>Reading[JavaApplication]C:\ProgramFilesVJava^jdk1.6.073\bin\javaw.exe[2D1B年9月業(yè)日下牛了:58:4切芒!■-7T?20,a?經(jīng)驗歸納本題基于最基本的遞歸算法思路，自身調用自身，達成條件后將數(shù)據(jù)傳遞歸還，加深了我對遞歸含義的運用，以及對該類算法的理解。題目七：日本著名數(shù)學游戲專家中村義作教授提出這樣一個問題：父親將2520個桔子分給六個兒子。分完后父親說：“老大將分給你的桔子的1/8給老二；老二拿到后連同原先的桔子分1/7給老三；老三拿到后連同原先的桔子分1/6給老四；老四拿到后連同原先的桔子分1/5給老五；老五拿到后連同原先的桔子分1/4給老六；老六拿到后連同原先的桔子分1/3給老大”。結果大家手中的桔子正好一樣多。問六兄弟原來手中各有多少桔子？題目分析：由題意得，最后大家手中的桔子都一樣多，每個人最后都有2520/6=420個桔子，本題與之前的題目不太一樣差異在于遞歸終點與遞歸起點之間存在聯(lián)系，可以推出邊界條件：第一個孩子得到的桔子總數(shù)等于平均數(shù)-最后一個孩子分給老大的差乘以8/7.算法構造為了完成這道題目，我構建了一個二維數(shù)組a[i][0]表示第i個孩子分出的桔子，a[i][1]表示第i個孩子分到的桔子，定義了兩個靜態(tài)值：分母的最大值8,和分母的最小值3,算法實現(xiàn)如下：算法實現(xiàn)程序源代碼(請寫入必要的注釋)。;publicclassOrange{staticintMAX=8;//分母最大值staticintMIN=3;//分母最小值//a[i][0]表示第i個孩子分出的桔子//a[i][1]表示第i個孩子分到的桔子publicstaticintorange(inta[][],inti){intave=2520/6;intp;if(i==0){//邊界條件〃第一個孩子得到的桔子總數(shù)等于平均數(shù)-最后一個孩子分給老大的差乘以8/7.a[i][1]=(ave-ave/(MIN-1))*(MAX-i)/(MAX-1-i);〃第一個孩子分給第二個孩子的橘子數(shù)量a[i][0]=a[i][1]-(ave-ave/(MIN-1));}else{a[i][1]=ave*(MAX-i)/(MAX-i-1)-orange(a,i-1);//第i個孩子分到的〃第i個孩子分出的a[i][0]=a[i][1]+orange(a,i-1)-ave;〃第i個孩子分出的}P=a[i][0]；returnp;}publicstaticvoidmain(String[]args){into[][]={{0,0},{0,0},{0,0},{0,0},{0,0},{0,0}};orange(o,5);//給數(shù)組里的六個元素賦值for(inti=0;i<=5;i++){System.out.println("第"+(i+1)+"個兒子最初有"+o[i][1]+"個桔子”);}}}運行結果ProblemsJavadoc1DeclaidtionSConsole<'terminated>Orange[JavaApplication]C:\ProgramFik策[八.兒子最初虧2如個桔子策2八兒子最和百彌0個桔子新個兒子最初有個桔子策4個兒子最初有441個桔子第5八兒子最初有A55個桔子新個兒子最初有49。個桔子經(jīng)驗歸納本題與之前的題目不太一樣差異在于遞歸終點與遞歸起點之間存在聯(lián)系，所以在分析初期一直找不到入手點，因為之前的題目都存在著明確的循環(huán)終點，本題就像一條銜尾蛇一樣首尾相連，經(jīng)過了一段時間的分析才推出了關系，明白了這種類型的題目，其入手點在于最后一個單位和第一個單位之間的聯(lián)系，將其作為邊界條件即可推出結果。（八）題目八：一種傳染病第一天只有一個患者，前5天為潛伏期，不發(fā)作也不會傳染人，第6天開始發(fā)作，從發(fā)作到治愈需要5天時間，期間每天傳染3個人，求第N天共有多少患者。題目分析由題意得，前五天不會發(fā)作也不會傳染給別人，所以可以得出邊界條件：當天數(shù)小于等于五時，只有一個患者。遞歸方程為：第N天患病人數(shù)等于前一天被傳染和發(fā)作的加上當天又傳染的的減去當天被治愈好的。算法構造我先定義了一個函數(shù)diseaseDay，傳入一個int值i；傳出的結果就是第i天有多少患者，構造如下：publicstaticintdisedseDay(intn){int5um=9;return1"}sum=tfi5e￡75eDt7/(n-5)*34-c/t5ec7seOf7y(n-'l);}returnsum；}邊界條件：當天數(shù)小于等于五時，只有一個患者。遞歸方程為：第N天患病人數(shù)等于前一天被傳染和發(fā)作的加上當天又傳染的的減去當天被治愈好的。算法實現(xiàn)程序源代碼(請寫入必要的注釋)。;importjava.util.Scanner;publicclassDisease{publicstaticintdiseaseDay(intn){intsum=0;if(n<=5){return1; 〃五天之內既不發(fā)作也不會傳染，所以患病人數(shù)就是1}else{sum=diseaseDay(n-5)*3+diseaseDay(n-1)-diseaseDay(n-5);//五天之后患病人數(shù)等于前一天被傳染和發(fā)作的加上當天又傳染的的減去當天被治愈好的。}returnsum;}publicstaticvoidmain(String[]args){intn;System.out.println("請輸入傳染病發(fā)生后的天數(shù)(疾病五天之后才開始傳染)");Scannerscanner=newScanner(System.in);//控制臺輸入Stringday=scanner.nextLine();n=Integer.parseInt(day);for(inti=1;i<=n;i++){System.out.println("第"+i+"天"+"得病人數(shù)為："+diseaseDay(i)+"人");}}運行結果<terminated>Di^ea^e[JavaApplication]C:\Programrile5Vava\jdk1.8L0_73\bin\javaw.exe（2018^10M5LF午我44:1B1清怖舌:，.;二舌丁=浣，玲亓.布，，什罕哈二，' '20第1天得病人敕加1%1/第玩得病人數(shù)為:1第4天得病人數(shù)為:1第5天得病人數(shù)為:1A新天得病人數(shù)為：3\第了夭得病人教為,5A踮』習.".甘第9,得病人數(shù)丸9/第16天得病人救為,11■'.第11天得病人數(shù)為:口人第U天-病人數(shù)為27,',第12天得病A數(shù)為：41人天得病人戴為,湖第15天得病人數(shù)為,81A第15天得癮人教如115-1.第17天得病人數(shù)為,169/'第天得病人數(shù)為:251第13天得病人數(shù)為:36S/第粉天髀病人戮為；W1A經(jīng)驗歸納本題所需要考慮的元素比較多，跟之前的題目比起來所需要考慮的范圍也要更全面一點，通過完成本道題目，我的思維縝密性得到了加強，邏輯嚴謹性也得到了很大的提高。選做題：（一）題目一：遞歸將一個整數(shù)輸出。形如654321，輸出1,2,3,4,5,6。題目分析本題是想要實現(xiàn)將輸入進來的字符串進行逆序操作，可以先得到字符串的長度，從長度-1的位置開始輸出，直到輸出完畢。算法構造：定義一個數(shù)組，將字符串分割之后存入數(shù)組中，定義一個遞歸函數(shù)，將數(shù)組逆序遞歸遍歷出來。算法實現(xiàn)程序源代碼（請寫入必要的注釋）。;importjava.util.Scanner;publicclassX1{staticinti=0; 〃定義一個計數(shù)器staticcharinput[]=newchar[10]; 〃定義一個數(shù)組，將輸入的字符串存儲起來publicstaticvoidniXv(Stringmes){if(i<0)return;else{System.out.print(input[i]+"_");i--;niXv(mes);}}publicstaticvoidmain(String[]args){System.out.println(-請輸入請輸入字符串，算法將對輸入的字符串進行逆序操作Scannerscan=newScanner(System.in);Stringcharacter=scan.nextLine(); //控制臺輸入character.getChars(0,character.length(),input,0);〃將輸入的字符串分割之后存入數(shù)組i=character.length()-1; //因為i記錄的是位置，數(shù)組是從0號位置開始存儲元素的niXv(character); //調用逆序算法}}運行結果ProblemsJavadoci■,DeclarationElConsole砧<termiinatedl>X1[JavaApplication)C:\ProgramFiIe5\Java\jdkl,8?073\bin\javaw.exe(20118年1曰月7日1^^6:23:02)請輸入請輸入字符串,算法將對輸入的字符串進行謹序操件654321123456經(jīng)驗歸納：本題相對來說比較簡單，僅僅是利用數(shù)組的性質構建的遞歸算法。(二)題目二：用遞歸實現(xiàn)分解質因數(shù)。形如：12=2*2*3。題目分析本題的的目的是：輸入一個合數(shù)，通過算法對其進行質因數(shù)分解，質數(shù)是只能被1和自身整除的數(shù)，所以先定義一個判斷是否為質數(shù)的算法，在定義一個分解算法，分解算法先判斷出在從2到n-1遍歷的過程中找到能被目標整數(shù)整除還是質數(shù)的數(shù)，將這個數(shù)輸出出來之后，用目標數(shù)整除它，整除得到的值再放入分解算法之中。算法構造定義一個boolean型的判斷算法isZhishu，在定義一個遞歸算法resolveZhishu，在resolveZhishu之中用到了isZhishu的功能，最后在主函數(shù)之中調用了resolveZhishu算法。算法實現(xiàn);importjava.util.Scanner;publicclassX2{publicstaticbooleanisZhishu(intn){//判斷一個數(shù)是否是質因數(shù)for(inti=2;i<n;i++) 〃從2開始遍歷到n-1{if(n%i==0)returnfalse; 〃如果可以被其中一個數(shù)整除，則不是質數(shù)}returntrue;publicstaticvoidresolveZhishu(intn)(//質因數(shù)分解for(inti=2;i<n;i++){if((isZhishu(i))&&(n%i==0)){//判斷質因數(shù)System.out.println(i);//如果是質因數(shù)則將其輸出打印出來n=n/i; 〃除以被判斷出來的質數(shù)resoLveZhishu(n); 〃遞歸調用除出來的數(shù)再繼續(xù)判斷break;}}}publicstaticvoidmain(String[]args){intnum;System.out.println("請輸入一個整型數(shù)字：");Scannerscan=newScanner(System.in);Stringcharacter=scan.nextLine(); //控制臺輸入num=Integer.parseInt(character);Systemout.println("整數(shù)"+num+"分解質因數(shù)結果如下：”)；resoLveZhishu(num); //調用分解算法}}運行結果■1-■IVLFFFl-JJJUTTUTMWLL*1VIUI I UhZU—u|^terminated>X2[JavaApplication]CAProqramFilesXJ對前dkL&Q73\bin\javaw.exe〔2。18年1。月7日下午7;14;""一?WM戒r： ' '12憨數(shù)12分解質困數(shù)結果如E經(jīng)驗歸納：本題我為了讓整個算法顯得精煉，定義了兩個函數(shù)，一個判斷函數(shù)一個分解函數(shù)，分解函數(shù)調用了判斷函數(shù)，分解函數(shù)在進行遞歸。(三)題目三：50個階梯，你一次可以上一階或