数据结构与算法之汉诺塔问题（Java递归）

汉诺塔问题：

有三根柱子，源杆A，暂存杆temp，目的杆C A上有n层盘子，由小到大向下排列，现需要将A杆的盘子移到C杆中

要求：1）大的盘在下面，小的盘在上面
             2）一次只能移动一个盘子
             
         个人思路：先分析问题，用数学的归纳法
                 当只有一个盘时，直接移动；
                 当有两个盘时，先将小的移到暂存杆，再将大的移到目的杆C，最后将暂存杆temp的小盘移到目的杆C中；
                 当有三个盘时，在下面的代码中的注释中写有详细步骤
                 ......
                 n个盘时，把它看做两部分一是上面的（n-1）盘，二是第n个盘，先将（n-1）首先将上面的（n-1）个盘子从A杆借助C杆移至temp杆，其次剩下第n个盘，直接放至C杆，最后一次递归调用解决即可。
                 
                 其中汉诺塔层数可以由程序内存储读取或者键盘输入，c为程序计数器，计算移动盘的次数

import java.util.Scanner;

public class Hanoi {
    int c=0;//计数器，计算移动的次数
    public void moveone(int n, String A, String C) {
        System.out.println("move  " + n + "  from  " + A + "     to  " + C);
    }

    public void movesome(int n, String A, String temp, String C) {

        c++;
    
        if (n <= 0) {
            System.out.println("number error");
            return;
        } else if (n == 1) {
            moveone(n, A, C);
        } else {
            movesome(n - 1, A, C, temp);
            // 首先将上面的（n-1）个盘子从A杆借助C杆移至temp杆
            moveone(n, A, C);
            // 然后将编号为n的盘子从A杆移至C杆
            movesome(n - 1, temp, A, C);
//            将剩下的（n-1）个盘子从temp杆借助A杆移至C杆
        }
        //草稿纸上手写汉诺塔三层的实现
//        moveone(1,A,C);
//        moveone(2,A,temp);
//        moveone(1,C,temp);
//        moveone(3, A, C);
//        moveone(1, temp, A);
//        moveone(2, temp, C);
//        moveone(1, A, C);

    }

    public static void main(String[] args) {
       //层数
        System.out.println("请输入汉诺塔层数:");
        Scanner input =new Scanner(System.in);
                int  in=input.nextInt();
                int l = 3;

        Hanoi h = new Hanoi();
        //    h.moveone(l,A,C);//程序内存储读取
        h.movesome(in, "初始位置", "临时存放地", "目的地址");
        System.out.println("汉诺塔的实现需要的移动次数:"+h.c);

//        h.movesome(l, "初始位置", "临时存放地", "目的地址");

    }
}

程序运行结果：