Hanoi 塔问题(Java实现)

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);
		}
	}
}

正文完