本篇博客將詳細講解如何解決漢諾塔問題
文章目錄
- 什么是漢諾塔
- 問題剖析
- n=1
- n=2
- n=3
- 總結
- Java代碼實作
- 代碼講解
- move函式
- hanoiTower函式
- 附：C語言實作漢諾塔
什么是漢諾塔
漢諾塔問題是一個經典的問題，漢諾塔（Hanoi Tower），又稱河內塔，源于印度一個古老傳說，
大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，
大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，任何時候，在小圓盤上都不能放大圓盤，且在三根柱子之間一次只能移動一個圓盤，問應該如何操作？
問題剖析
我們假設圓盤數量為n，圓盤初始放在A柱上，最后移到C柱，
n=1
移動方法：A -> C
n=2
移動方法：A -> B A -> C B -> C
n=3
移動方法：A -> C A -> B C -> B A -> C B -> A B -> C A -> C
總結
通過這上面三個情況，我們可以知道：
- 當紅色圓盤上面沒有其他圓盤的時候，就直接把紅色圓盤移到C柱上，
- 當紅色圓盤上面有其他圓盤的時候，先把其他圓盤移到B柱上，然后再將紅色圓盤移到C柱上，在把B柱上紫色圓盤上面的其他圓盤移到A柱，接著再將紫色圓盤移到C柱上，然后再次回圈，
例如當n=4時，
Java代碼實作
public class TestDemo {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
hanoiTower(n,'A','B','C');
}
public static void hanoiTower(int n,char A,char B,char C) {
if(n < 2) {
move(A,C);
} else {
hanoiTower(n - 1,A,C,B);
move(A,C);
hanoiTower(n - 1,B,A,C);
}
}
public static void move(char src,char des) {
System.out.println(src + " -> " + des);
}
}
例如輸入3，結果為：
代碼講解
move函式
public static void move(char src,char des) {
System.out.println(src + " -> " + des);
}
src表示起始圓盤所在的柱子，des表示該圓盤需要移動到的柱子，
hanoiTower函式
public static void hanoiTower(int n,char A,char B,char C) {
if(n < 2) {
move(A,C);
} else {
hanoiTower(n - 1,A,C,B);
move(A,C);
hanoiTower(n - 1,B,A,C);
}
}
hanoiTower的第一個引數，代表還有n個圓盤需要移動，A代表起始圓盤所在的柱子，C代表該圓盤所要移動到的柱子，B代表圓盤移動時所經歷的中間柱子，
例如n=3時，先需要把上面兩個圓盤經過一系列的移動，全部移動到B柱上，所以就得呼叫hanoiTower(2,A,C,B);然后再將A柱上唯一的一個圓盤移動到C柱上，所以呼叫move(A,C);然后再將B柱上除最下面的圓盤以外的圓盤移動到A柱上，然后再重復這個步驟，直到所有的圓盤都移動到C柱為止，
所以呼叫hanoiTower(2,B,A,C);
附：C語言實作漢諾塔
#include<stdio.h>
void Move(char src, char des)
{
printf("%c -> %c", src, des);
printf("\n");
}
void HanoiTower(int n, char A, char B, char C)
{
if (n == 1)
{
Move(A, C);
}
else
{
HanoiTower(n - 1, A, C, B);
Move(A, C);
HanoiTower(n - 1, B, A, C);
}
}
int main()
{
int n = 0;
scanf("%d", &n);
HanoiTower(n, 'A', 'B', 'C');
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/292224.html
標籤：其他