Java使用遞歸法解決漢諾塔問題的代碼示例

更新時(shí)間：2016年04月19日 08:42:58 投稿：goldensun

這篇文章主要介紹了Java使用遞歸法解決漢諾塔問題的代碼示例,漢諾塔問題是使用遞歸解決問題的經(jīng)典范例,用到的算法非常簡(jiǎn)單,需要的朋友可以參考下

漢諾（Hanoi）塔問題：古代有一個(gè)梵塔，塔內(nèi)有三個(gè)座A、B、C，A座上有n個(gè)盤子，盤子大小不等，大的在下，小的在上（如圖）。

201641984628317.jpg (586×209)

有一個(gè)和尚想把這n個(gè)盤子從A座移到B座，但每次只能允許移動(dòng)一個(gè)盤子，并且在移動(dòng)過程中，3個(gè)座上的盤子始終保持大盤在下，小盤在上。在移動(dòng)過程中可以利用B座，要求打印移動(dòng)的步驟。如果只有一個(gè)盤子，則不需要利用B座，直接將盤子從A移動(dòng)到C。

如果有2個(gè)盤子，可以先將盤子1上的盤子2移動(dòng)到B；將盤子1移動(dòng)到c；將盤子2移動(dòng)到c。這說明了：可以借助B將2個(gè)盤子從A移動(dòng)到C，當(dāng)然，也可以借助C將2個(gè)盤子從A移動(dòng)到B。
如果有3個(gè)盤子，那么根據(jù)2個(gè)盤子的結(jié)論，可以借助c將盤子1上的兩個(gè)盤子從A移動(dòng)到B；將盤子1從A移動(dòng)到C，A變成空座；借助A座，將B上的兩個(gè)盤子移動(dòng)到C。這說明：可以借助一個(gè)空座，將3個(gè)盤子從一個(gè)座移動(dòng)到另一個(gè)。
如果有4個(gè)盤子，那么首先借助空座C，將盤子1上的三個(gè)盤子從A移動(dòng)到B；將盤子1移動(dòng)到C，A變成空座；借助空座A，將B座上的三個(gè)盤子移動(dòng)到C。

Java代碼如下：

public class Hanoi { 
  
 public static void main(String[] args) { 
  int disk = 3; //盤子 
  move(disk, 'A', 'B', 'C'); 
 } 
  
 /* 
  * 根據(jù)題意，從上向下編號(hào) => 1 ~ n 
  */ 
 /** 
  * 
  * @param topN 源塔頂?shù)谋P子編號(hào) 
  * @param from 從哪個(gè)塔移動(dòng) 
  * @param inter 中介，過渡的塔 
  * @param to 目的塔 
  */ 
 private static void move(int topN, char from, char inter, char to) { 
  if (topN == 1) { 
   System.out.println("Disk 1 from " + from + " to " + to); 
  } else { 
   move(topN - 1, from, to, inter); 
   System.out.println("Disk " + topN + " from " + from + " to " + to); 
   move(topN - 1, inter, from, to); 
  } 
 } 
   
}

out

Disk 1 from A to C 
Disk 2 from A to B 
Disk 1 from C to B 
Disk 3 from A to C 
Disk 1 from B to A 
Disk 2 from B to C 
Disk 1 from A to C

您可能感興趣的文章:

Java
遞歸

相關(guān)文章

淺談SpringBoot處理url中的參數(shù)的注解
下面小編就為大家分享一篇淺談SpringBoot處理url中的參數(shù)的注解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2018-01-01
IDEA 自動(dòng)跳出括號(hào)的快捷鍵分享
這篇文章主要介紹了IDEA 自動(dòng)跳出括號(hào)的快捷鍵分享，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2021-02-02
HashMap線程不安全問題解析
這篇文章主要介紹了HashMap線程不安全問題解析,HashMap的線程不安全體現(xiàn)在會(huì)造成死循環(huán)、數(shù)據(jù)丟失、數(shù)據(jù)覆蓋等問題,其中死循環(huán)和數(shù)據(jù)丟失是在JDK1.7中出現(xiàn)的問題,在JDK1.8中已經(jīng)得到解決,但是1.8中仍會(huì)有數(shù)據(jù)覆蓋這樣的問題,需要的朋友可以參考下
2023-11-11
Spring Gateway自定義請(qǐng)求參數(shù)封裝的實(shí)現(xiàn)示例
這篇文章主要介紹了Spring Gateway自定義請(qǐng)求參數(shù)封裝的實(shí)現(xiàn)示例，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2020-09-09
java并發(fā)學(xué)習(xí)之Executor源碼解析
這篇文章主要為大家介紹了java并發(fā)學(xué)習(xí)之Executor源碼示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
2023-07-07
springboot中使用mybatisplus自帶插件實(shí)現(xiàn)分頁的示例代碼
這篇文章主要介紹了springboot中使用mybatisplus自帶插件實(shí)現(xiàn)分頁,本文通過示例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2022-09-09
springboot項(xiàng)目事務(wù)標(biāo)簽驗(yàn)證
本文主要介紹了springboot項(xiàng)目事務(wù)標(biāo)簽驗(yàn)證，文中通過示例代碼介紹的非常詳細(xì)，詳細(xì)的介紹了不加事務(wù)標(biāo)簽和加事物標(biāo)簽的使用，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
2021-07-07
淺談JDK9的特性之JVM的xlog
在java程序中，我們通過日志來定位和發(fā)現(xiàn)項(xiàng)目中可能出現(xiàn)的問題。在現(xiàn)代java項(xiàng)目中，我們使用log4j或者slf4j，Logback等日志記錄框架來處理日志問題。本文將介紹JDK9的特性之JVM的xlog。
2021-06-06
SpringBoot JSON全局日期格式轉(zhuǎn)換器實(shí)現(xiàn)方式
這篇文章主要介紹了SpringBoot JSON全局日期格式轉(zhuǎn)換器,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2023-04-04
Java基礎(chǔ)之初識(shí)Maven
這篇文章主要介紹了Java基礎(chǔ)之初識(shí)Maven,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)java基礎(chǔ)的小伙伴們有非常好的幫助,需要的朋友可以參考下
2021-05-05