這篇文章主要介紹利用Java遞歸解決“九連環(huán)”公式的方法，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

鼓樓網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)建站！從網(wǎng)頁設計、網(wǎng)站建設、微信開發(fā)、APP開發(fā)、響應式網(wǎng)站開發(fā)等網(wǎng)站項目制作，到程序開發(fā)，運營維護。創(chuàng)新互聯(lián)建站于2013年成立到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進行。專注于網(wǎng)站建設就選創(chuàng)新互聯(lián)建站。

九連環(huán)的玩法規(guī)則用一句話來概括就是：如果你想要卸掉某一環(huán)或者裝上某一環(huán)，只需要保留這一環(huán)前面一環(huán)，再之前所有的環(huán)都卸掉。（例如你想要卸掉或者裝上第9環(huán)，那么保留第8環(huán)，第8環(huán)之前的所有的環(huán)都卸掉）其中第一環(huán)可以直接卸掉。（其實第一第二這兩環(huán)可以一起裝上一起卸掉，我們在邏輯上只是規(guī)定第一環(huán)可以自由移動）

那么按照遞歸的思想來實現(xiàn)這個問題，還是比較簡單的。與之前提到的不同的是：這次對于某一環(huán)的操作不是一種，牽扯到裝上和卸掉兩種基本操作，所以針對九連環(huán)要設置一個標記狀態(tài)——state：九連環(huán)在上，state=1；九連環(huán)在下，state=0 。這個在Node類中實現(xiàn)。（如同c++中的struct）

其中num屬性表示環(huán)號，state表示環(huán)的狀態(tài)。

第二個需要準備的就是利用ArrayList實現(xiàn)的一個棧，來將所有state=1的環(huán)壓入棧中。九連環(huán)規(guī)則中要求：要想對某一環(huán)進行操作，要保證這一環(huán)的前一環(huán)state=1 且在棧頂。

第三個就是操作過程move，根據(jù)state的不同，設置move操作不同。

準備條件做好了，就是要設計遞歸實現(xiàn)了。首先寫一下設計的思想（偽代碼）

play(n){
	n=1://基礎情形
		move(n);
	n>1:
		while(!deal)//沒有完成對這一環(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)從棧中移走（并不是僅能夠在棧頂進行操作的完全意義上的棧）
				stack.pop!=n-1://前一環(huán)不是棧頂
					for(i=n-2 to 1)
						find index where index.state!=0;//從大到小找到第一個在上的環(huán)（棧中在第n-1環(huán)之前的環(huán)）
					play(index);//將這個發(fā)現(xiàn)的在上的環(huán)移走
			
			(n-1).state=0://前一環(huán)不在上
				play(n-1);//執(zhí)行對前一環(huán)的操作（即如果前一環(huán)在上就移走，如果不在上就裝上）	
		}
}

這個只是將某一環(huán)移走或者裝上的操作，如果將整個游戲都結束，在執(zhí)行函數(shù)的時候需要從高到低依次移走這些環(huán)。（見main函數(shù)）。main函數(shù)中還需對九連環(huán)的初始狀態(tài)以及棧的初始狀態(tài)進行初始化。（見main函數(shù)）

運行結果如下：（四個環(huán)）

具體實現(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)中較大的一個。
						{
							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)”公式的方法”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

分享標題：利用Java遞歸解決“九連環(huán)”公式的方法-創(chuàng)新互聯(lián)
網(wǎng)站URL：http://chinadenli.net/article34/desgpe.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設計、品牌網(wǎng)站制作、網(wǎng)站建設、網(wǎng)站導航、手機網(wǎng)站建設、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)