本文主要是介绍递归算法之九连环操作步骤,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
import java.util.ArrayList;
import java.util.Scanner;
/**
* 九连环的装卸需要遵守两个规则。
* 1、第一个(最右边)环任何时候都可以装上或卸下。
* 2、如果第k个环没有被卸下,且第k个环右边的所有环都被卸下,则第k+1个环(第k个环左边相邻的环)可以任意装上或卸下。
*/
public class NineInterlockingLinks2 {
private static int numberOfSteps = 0;
public static void main(String[] args) {
System.out.print("请输入环数,按回车键:");
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]);
NineInterlockingLinks2 nc = new NineInterlockingLinks2();
for (int t = n; t > 0; t--)
nc.play(node, list, t);
System.out.println(n + "连环总步数:" + NineInterlockingLinks2.numberOfSteps);
}
public static void move(Node node) {
NineInterlockingLinks2.numberOfSteps++;
//1 在九连环上;0 在九连环下
if (node.state == 1)
System.out.println("下 " + node.num);
else
System.out.println("上 " + 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);
}
}
}
}
}
class Node {
int num;
int state;//1 在九连环上;0 在九连环下
public Node(int num, int state) {
this.num = num;
this.state = state;
}
}
这篇关于递归算法之九连环操作步骤的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!