您好,登錄后才能下訂單哦!
這篇文章主要介紹利用Java遞歸解決“九連環(huán)”公式的方法,文中介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們一定要看完!
九連環(huán)的玩法規(guī)則用一句話來(lái)概括就是:如果你想要卸掉某一環(huán)或者裝上某一環(huán),只需要保留這一環(huán)前面一環(huán),再之前所有的環(huán)都卸掉。(例如你想要卸掉或者裝上第9環(huán),那么保留第8環(huán),第8環(huán)之前的所有的環(huán)都卸掉)其中第一環(huán)可以直接卸掉。(其實(shí)第一第二這兩環(huán)可以一起裝上一起卸掉,我們?cè)谶壿嬌现皇且?guī)定第一環(huán)可以自由移動(dòng))
那么按照遞歸的思想來(lái)實(shí)現(xiàn)這個(gè)問(wèn)題,還是比較簡(jiǎn)單的。與之前提到的不同的是:這次對(duì)于某一環(huán)的操作不是一種,牽扯到裝上和卸掉兩種基本操作,所以針對(duì)九連環(huán)要設(shè)置一個(gè)標(biāo)記狀態(tài)——state:九連環(huán)在上,state=1;九連環(huán)在下,state=0 。這個(gè)在Node類中實(shí)現(xiàn)。(如同c++中的struct)
其中num屬性表示環(huán)號(hào),state表示環(huán)的狀態(tài)。
第二個(gè)需要準(zhǔn)備的就是利用ArrayList實(shí)現(xiàn)的一個(gè)棧,來(lái)將所有state=1的環(huán)壓入棧中。九連環(huán)規(guī)則中要求:要想對(duì)某一環(huán)進(jìn)行操作,要保證這一環(huán)的前一環(huán)state=1 且在棧頂。
第三個(gè)就是操作過(guò)程move,根據(jù)state的不同,設(shè)置move操作不同。
準(zhǔn)備條件做好了,就是要設(shè)計(jì)遞歸實(shí)現(xiàn)了。首先寫一下設(shè)計(jì)的思想(偽代碼)
play(n){ n=1://基礎(chǔ)情形 move(n); n>1: while(!deal)//沒(méi)有完成對(duì)這一環(huán)的操作 { (n-1).state=1://前一環(huán)在上 stack.pop=n-1://前一環(huán)為棧頂 move(n); deal=true; stack.remove(size-2);//將第n環(huán)從棧中移走(并不是僅能夠在棧頂進(jìn)行操作的完全意義上的棧) stack.pop!=n-1://前一環(huán)不是棧頂 for(i=n-2 to 1) find index where index.state!=0;//從大到小找到第一個(gè)在上的環(huán)(棧中在第n-1環(huán)之前的環(huán)) play(index);//將這個(gè)發(fā)現(xiàn)的在上的環(huán)移走 (n-1).state=0://前一環(huán)不在上 play(n-1);//執(zhí)行對(duì)前一環(huán)的操作(即如果前一環(huán)在上就移走,如果不在上就裝上) } }
這個(gè)只是將某一環(huán)移走或者裝上的操作,如果將整個(gè)游戲都結(jié)束,在執(zhí)行函數(shù)的時(shí)候需要從高到低依次移走這些環(huán)。(見(jiàn)main函數(shù))。main函數(shù)中還需對(duì)九連環(huán)的初始狀態(tài)以及棧的初始狀態(tài)進(jìn)行初始化。(見(jiàn)main函數(shù))
運(yùn)行結(jié)果如下:(四個(gè)環(huán))
具體實(shí)現(xiàn),直接貼代碼:
import java.util.*; public class NC { public static void move(Node node) { if(node.state==1) System.out.println("down "+node.num); else System.out.println("up "+node.num); } public void play(Node[]node,ArrayList<Node> list,int n) { boolean deal=false; if(n==1) { if(node[n].state==1) { move(node[n]);// move the 1st; node[n].state=0; list.remove(list.size()-1); } else { move(node[n]); node[n].state=1; list.add(node[n]); } } else { while(!deal) { if(node[n-1].state==1) {//前一環(huán)在上 if(list.get(list.size()-1).num==n-1)//前一環(huán)為棧頂 { if(node[n].state==1) { move(node[n]); node[n].state=0; deal=true; list.remove(list.size()-2); } else { move(node[n]); node[n].state=1; deal=true; list.add(list.size()-1,node[n]); } } else//前一環(huán)在上,但是前一環(huán)不是棧頂 { int index=1; for(int i=n-2;i>0;i--)//找到前一環(huán)之前的所有在上的環(huán)中最大的一個(gè)。 { if(node[i].state==1) { index=i; break; } } play(node,list,index);//將前一環(huán)之前的在上的最大的一環(huán)移走 } } //------------------------------------------------------------------------- else if(node[n-1].state==0) {//前一環(huán)不在上 play(node,list,n-1); } } } } public static void main (String[]args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); Node []node= new Node[n+1]; for(int i=1;i<n+1;i++) node[i]=new Node(i,1); ArrayList<Node> list= new ArrayList(); for(int j=n;j>0;j--) list.add(node[j]); NC nc= new NC(); for(int t=n;t>0;t--) nc.play(node, list,t); } } class Node{ int num; int state; public Node(int num,int state) { this.num=num; this.state=state; } }
以上是“利用Java遞歸解決“九連環(huán)”公式的方法”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對(duì)大家有幫助,更多相關(guān)知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。