如何利用Java递归解决“九连环”公式

来自:互联网
时间:2021-02-21
阅读:

在之前有写到过一点点有关递归的东西点击打开链接,然后想到小时候自己玩的一个玩具——九连环。小时候自己曾经一边玩一边用笔记下来解开这个东西的公式,那是十几年前的事情了。前两天突然想起来,九连环的基本操作就是一个递归,一个感觉起来非常标准的递归过程。

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

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

如何利用Java递归解决“九连环”公式

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

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

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

如何利用Java递归解决“九连环”公式

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

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函数)

运行结果如下:(四个环)

如何利用Java递归解决“九连环”公式

具体实现,直接贴代码:

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;
	}
}
返回顶部
顶部