用栈来求解汉诺塔问题

[编程题]用栈来求解汉诺塔问题

热度指数：2314 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

汉诺塔问题比较经典，这里修改一下游戏规则：现在限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。求当塔有n层的时候，打印最优移动过程和最优移动总步数。

输入描述:

输入一个数n，表示塔层数

输出描述:

按样例格式输出最优移动过程和最优移动总步数

示例1

输入

输出

Move 1 from left to mid
Move 1 from mid to right
Move 2 from left to mid
Move 1 from right to mid
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to mid
Move 1 from mid to right
It will move 8 steps.

说明

当塔数为两层时，最上层的塔记为1，最下层的塔记为2

备注:

算法知识视频讲解

Java

小星教授

import java.util.*;

public class Main {
	static int steps = 0;
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
        HanNuo(n, "left", "mid", "right");
        System.out.println("It will move "+steps+" steps.");
	}
	
	public static void HanNuo(int n,String a,String b,String c) {
		if(n==1) {
			System.out.println("Move "+n+" from "+a+" to "+b);
			System.out.println("Move "+n+" from "+b+" to "+c);
		}else {
			HanNuo(n-1,a,b,c);
			System.out.println("Move "+n+" from "+a+" to "+b);
			HanNuo(n-1,c,b,a);
			System.out.println("Move "+n+" from "+b+" to "+c);
			HanNuo(n-1,a,b,c);
		}
		steps+=2;
	}
}

发表于 2019-10-25 16:25:50 回复(2)