如何利用Java遞歸解決“九連環(huán)”公式
在之前有寫到過一點(diǎn)點(diǎn)有關(guān)遞歸的東西點(diǎn)擊打開鏈接,然后想到小時(shí)候自己玩的一個(gè)玩具——九連環(huán)。小時(shí)候自己曾經(jīng)一邊玩一邊用筆記下來解開這個(gè)東西的公式,那是十幾年前的事情了。前兩天突然想起來,九連環(huán)的基本操作就是一個(gè)遞歸,一個(gè)感覺起來非常標(biāo)準(zhǔ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)可以直接卸掉。(其實(shí)第一第二這兩環(huán)可以一起裝上一起卸掉,我們?cè)谶壿嬌现皇且?guī)定第一環(huán)可以自由移動(dòng))
那么按照遞歸的思想來實(shí)現(xiàn)這個(gè)問題,還是比較簡單的。與之前提到的不同的是:這次對(duì)于某一環(huán)的操作不是一種,牽扯到裝上和卸掉兩種基本操作,所以針對(duì)九連環(huán)要設(shè)置一個(gè)標(biāo)記狀態(tài)——state:九連環(huán)在上,state=1;九連環(huán)在下,state=0 。這個(gè)在Node類中實(shí)現(xiàn)。(如同c++中的struct)

其中num屬性表示環(huán)號(hào),state表示環(huán)的狀態(tài)。
第二個(gè)需要準(zhǔn)備的就是利用ArrayList實(shí)現(xiàn)的一個(gè)棧,來將所有state=1的環(huán)壓入棧中。九連環(huán)規(guī)則中要求:要想對(duì)某一環(huán)進(jìn)行操作,要保證這一環(huán)的前一環(huán)state=1 且在棧頂。
第三個(gè)就是操作過程move,根據(jù)state的不同,設(shè)置move操作不同。

準(zhǔn)備條件做好了,就是要設(shè)計(jì)遞歸實(shí)現(xiàn)了。首先寫一下設(shè)計(jì)的思想(偽代碼)
play(n){
n=1://基礎(chǔ)情形
move(n);
n>1:
while(!deal)//沒有完成對(duì)這一環(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)從棧中移走(并不是僅能夠在棧頂進(jìn)行操作的完全意義上的棧)
stack.pop!=n-1://前一環(huán)不是棧頂
for(i=n-2 to 1)
find index where index.state!=0;//從大到小找到第一個(gè)在上的環(huán)(棧中在第n-1環(huán)之前的環(huán))
play(index);//將這個(gè)發(fā)現(xiàn)的在上的環(huán)移走
(n-1).state=0://前一環(huán)不在上
play(n-1);//執(zhí)行對(duì)前一環(huán)的操作(即如果前一環(huán)在上就移走,如果不在上就裝上)
}
}
這個(gè)只是將某一環(huán)移走或者裝上的操作,如果將整個(gè)游戲都結(jié)束,在執(zhí)行函數(shù)的時(shí)候需要從高到低依次移走這些環(huán)。(見main函數(shù))。main函數(shù)中還需對(duì)九連環(huán)的初始狀態(tài)以及棧的初始狀態(tài)進(jìn)行初始化。(見main函數(shù))
運(yùn)行結(jié)果如下:(四個(gè)環(huán))

具體實(shí)現(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)中最大的一個(gè)。
{
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;
}
}
總結(jié)
到此這篇關(guān)于如何利用Java遞歸解決“九連環(huán)”公式的文章就介紹到這了,更多相關(guān)Java遞歸“九連環(huán)”公式內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java中zip的壓縮和解壓縮的實(shí)現(xiàn)代碼
這篇文章主要介紹了Java中zip的壓縮和解壓縮的實(shí)現(xiàn)代碼,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-02-02
Java使用責(zé)任鏈模式處理學(xué)生請(qǐng)假問題詳解
這篇文章主要介紹了Java使用責(zé)任鏈模式處理學(xué)生請(qǐng)假問題,結(jié)合實(shí)例形式詳細(xì)分析了責(zé)任鏈模式的概念、原理及Java使用責(zé)任鏈模式處理學(xué)生請(qǐng)假問題的相關(guān)步驟、操作技巧與相關(guān)注意事項(xiàng),需要的朋友可以參考下2018-04-04
如何使用SpringBoot進(jìn)行優(yōu)雅的數(shù)據(jù)驗(yàn)證
這篇文章主要介紹了如何使用SpringBoot進(jìn)行優(yōu)雅的數(shù)據(jù)驗(yàn)證,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-11-11
springboot整合Nginx實(shí)現(xiàn)負(fù)載均衡反向代理的方法詳解
這篇文章主要給大家介紹了關(guān)于springboot整合Nginx實(shí)現(xiàn)負(fù)載均衡反向代理的相關(guān)資料,文中通過圖文以及實(shí)例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2022-01-01
java實(shí)現(xiàn)網(wǎng)頁爬蟲的示例講解
下面小編就為大家?guī)硪黄猨ava實(shí)現(xiàn)網(wǎng)頁爬蟲的示例講解。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-08-08
idea構(gòu)建web項(xiàng)目的超級(jí)詳細(xì)教程
好多朋友在使用IDEA創(chuàng)建項(xiàng)目時(shí),總會(huì)碰到一些小問題,下面這篇文章主要給大家介紹了關(guān)于idea構(gòu)建web項(xiàng)目的超級(jí)詳細(xì)教程,文中通過圖文介紹的非常詳細(xì),需要的朋友可以參考下2023-03-03
基于html5+java實(shí)現(xiàn)大文件上傳實(shí)例代碼
本文通過一段實(shí)例代碼給大家介紹基于html5+java實(shí)現(xiàn)大文件上傳,涉及到html5 java 文件上傳相關(guān)知識(shí),感興趣的朋友一起學(xué)習(xí)吧2016-01-01

