汉诺塔(Java代码)

解题思路:    使用分治算法把一个大问题分解为多个小问题

参考代码:

import java.util.Scanner;

public class 汉诺塔 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		hanNouTa(n, '1', '2', '3');
	}

	public static void hanNouTa(int n,char a,char b,char c) {
		// a代表1 b代表2 c代表3
		if(n == 1) { // 如果只有一个盘子那么就直接从a移动到c
			System.out.println("Move 1 " + "from " + a + " to " + c);
		}else { // 如果有n个盘子就可以把这n个盘子看作两个部分 最下面的一个盘子和上面的所有盘子
			
			// n-1代表的是除了最下面一个的上面的所有盘子
			
			hanNouTa(n - 1, a, c, b); // 把上面的所有盘子从a移到b 中间借助了c
			
			System.out.println("Move " + n + " from " + a + " to " + c); // 此时a就只有一个盘子直接移动到c
			
			hanNouTa(n - 1, b, a, c); // 再把b上面的所有盘子移动到c 中间借助了a
		}
		
	}
	
}