如何利用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递归解决“九连环”公式的文章就介绍到这了,更多相关Java递归“九连环”公式内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19