Hanoi 塔问题（Java实现）

Hanoi 塔问题是一个很经典的递归问题

• 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：
  • 规则1：每次只能移动1个圆盘；
  • 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
  • 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。

思路

1. 如果只有 1 个圆盘，a --> c
2. 如果圆盘数大于1
   1. 将 n - 1 个圆盘，从 a 借助 c 移动到 b
   2. 将剩下 1 个圆盘从 a 移动到 c
   3. 将 n - 1 个圆盘，从 b 借助 a 移动到 c

Java源代码

import java.util.Scanner;

/*
 * 若尘
 */

/**
 * Hanoi 塔问题 
 * @author ruochen
 * @version 1.0
 */
public class Hanoi {

	public static void main(String[] args) {
		int n;
		Scanner sc = new Scanner(System.in);
		System.out.print("Please input num: ");
		n = sc.nextInt();
		System.out.println("Process: ");
		move(n, 'A', 'B', 'C');
	} /**
	 * 圆盘移动
	 * @param n 圆盘个数
	 * @param a 需要移动的位置
	 * @param b 借助的位置
	 * @param c 移动目的地
	 */
	public static void move(int n, char a, char b, char c) {
		if (n < 0) { System.out.println("enter n > 0");
		} else if (n == 1) { System.out.println(a + "-->" + c);
		} else { move(n - 1, a, c, b); move(1, a, b, c); move(n-1, b, a, c);
		}
	}
}



  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
 

文章来源: ruochen.blog.csdn.net，作者：若尘，版权归原作者所有，如需转载，请联系作者。

原文链接：ruochen.blog.csdn.net/article/details/106253867