利用Java递归解决“九连环”公式的方法

这篇文章主要介绍利用Java递归解决“九连环”公式的方法，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

九连环的玩法规则用一句话来概括就是：如果你想要卸掉某一环或者装上某一环，只需要保留这一环前面一环，再之前所有的环都卸掉。（例如你想要卸掉或者装上第9环，那么保留第8环，第8环之前的所有的环都卸掉）其中第一环可以直接卸掉。（其实第一第二这两环可以一起装上一起卸掉，我们在逻辑上只是规定第一环可以自由移动）

那么按照递归的思想来实现这个问题，还是比较简单的。与之前提到的不同的是：这次对于某一环的操作不是一种，牵扯到装上和卸掉两种基本操作，所以针对九连环要设置一个标记状态——state：九连环在上，state=1；九连环在下，state=0 。这个在Node类中实现。（如同c++中的struct）

其中num属性表示环号，state表示环的状态。

第二个需要准备的就是利用ArrayList实现的一个栈，来将所有state=1的环压入栈中。九连环规则中要求：要想对某一环进行操作，要保证这一环的前一环state=1 且在栈顶。

第三个就是操作过程move，根据state的不同，设置move操作不同。

准备条件做好了，就是要设计递归实现了。首先写一下设计的思想（伪代码）

play(n){	n=1://基础情形	move(n);	n>1:	while(!deal)//没有完成对这一环的操作	{	(n-1).state=1://前一环在上	stack.pop=n-1://前一环为栈顶	move(n);	deal=true;	stack.remove(size-2);//将第n环从栈中移走（并不是仅能够在栈顶进行操作的完全意义上的栈）	stack.pop!=n-1://前一环不是栈顶	for(i=n-2 to 1)	find index where index.state!=0;//从大到小找到第一个在上的环（栈中在第n-1环之前的环）	play(index);//将这个发现的在上的环移走	(n-1).state=0://前一环不在上	play(n-1);//执行对前一环的操作（即如果前一环在上就移走，如果不在上就装上）	} }

这个只是将某一环移走或者装上的操作，如果将整个游戏都结束，在执行函数的时候需要从高到低依次移走这些环。（见main函数）。main函数中还需对九连环的初始状态以及栈的初始状态进行初始化。（见main函数）

运行结果如下：（四个环）

具体实现，直接贴代码：

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) {//前一环在上	if(list.get(list.size()-1).num==n-1)//前一环为栈顶	{	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//前一环在上，但是前一环不是栈顶	{	int index=1;	for(int i=n-2;i>0;i--)//找到前一环之前的所有在上的环中最大的一个。	{	if(node[i].state==1) {	index=i;	break;	}	}	play(node,list,index);//将前一环之前的在上的最大的一环移走	}	}	//-------------------------------------------------------------------------	else if(node[n-1].state==0) {//前一环不在上	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递归解决“九连环”公式的方法”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注亿速云行业资讯频道！