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 个圆盘，a --> c

如果圆盘数大于1

将 n - 1 个圆盘，从 a 借助 c 移动到 b

将剩下 1 个圆盘从 a 移动到 c

将 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

Java

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。