如果盤數(shù)超過2個，將第三個以下的盤子遮起來，就很簡單了，每次處理兩個盤子，也就是：A->B、A ->C、B->C這三個步驟，而被遮住的部份，其實(shí)就是進(jìn)入程式的遞回處理。
事實(shí)上，若有n個盤子，則移動完畢所需之次數(shù)為2^n - 1，所以當(dāng)盤數(shù)為64時，則所需次數(shù)為：
264- 1 = 18446744073709551615
為5.05390248594782e+16年，也就是約5000世紀(jì)，如果對這數(shù)字沒什么概念，就假設(shè)每秒鐘搬一個盤子好了，也要約5850億年左右。
演算法
Procedure HANOI(n, A, B, C) [
IF(n == 1) [
PRINT("Move sheet " n " from " A " to " C);
]
ELSE [
HANOI(n-1, A, C, B);
PRINT("Move sheet " n " from " A " to " C);
HANOI(n-1, B, A, C);
]
]
實(shí)作
#include <stdio.h>
void hanoi(int n, char A, char B, char C) {
if(n == 1) {
printf("Move sheet %d from %c to %c\n", n, A, C);
}
else {
hanoi(n-1, A, C, B);
printf("Move sheet %d from %c to %c\n", n, A, C);
hanoi(n-1, B, A, C);
}
}
int main() {
int n;
printf("請輸入盤數(shù)：");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}
import java.io.*;
public class Hanoi {
public static void main(String args[]) throws IOException {
int n;
BufferedReader buf;
buf = new BufferedReader(new InputStreamReader(System.in));
System.out.print("請輸入盤數(shù)：");
n = Integer.parseInt(buf.readLine());
Hanoi hanoi = new Hanoi();
hanoi.move(n, 'A', 'B', 'C');
}
public void move(int n, char a, char b, char c) {
if(n == 1)
System.out.println("盤 " + n + " 由 " + a + " 移至 " + c);
else {
move(n - 1, a, c, b);
System.out.println("盤 " + n + " 由 " + a + " 移至 " + c);
move(n - 1, b, a, c);
}
}
}
