青蛙跳台问题

现在一共有n个台阶，一只青蛙每次只能跳一阶或是两阶，那么一共有多少种跳到顶端的方案？

例如n=2，那么一共有两种方案，一次性跳两阶或是每次跳一阶。

现在请你设计一个Java程序，计算当台阶数为n的情况下，能够有多少种方案到达顶端。

解决方法

假设青蛙已经站在了顶端（n），那么它的前一个台阶是那个呢？要么是第n-1阶台阶，要么是第n-2阶台阶。

那么到达第n阶台阶所需的方案是不是就等于到达第n-1阶台阶的方案数加上到达第n-2阶台阶的方案数。

即f(n) = f(n-1) + f(n-2)

Java实现代码

public static int steps(int n) {
    //判断0台阶的情况
    if (n == 0) {
        return 0;
    }
    //判断1阶台阶的情况
    if (n == 1) {
        return 1;
    }
    //判断2阶台阶的情况
    if (n == 2) {
        return 2;
    }
    //递归调用
    return steps(n-1) + steps(n-2);
}

汉诺塔问题

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始

按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

问题：这三根柱子我们就依次命名为A、B、C，现在请你设计一个Java程序，计算N阶（n片圆盘）汉诺塔移动操作的每一步。

解决方案

• 只有一个圆盘的时候，可以直接把圆盘从A移到C（记作A--->C）

• 当有两个圆盘时，必须要把第一个移到B（A--->B），再把第二个移到C(A--->C)，最后再把第一个圆盘从B移到C（B--->C）

• 当有三个圆盘时...

  一个圆盘一个圆盘的考虑太复杂，那么能不能只考虑只有两部分的情况（最后一个圆盘（记作@）和除它之外的所有圆盘（记作#）），也就是相当于第二种情况。先把#移动到B柱（中间过程先不考虑），再把@移动到C柱。

  把@移动到C柱之后，以后所有的操作都在与它无关（暂时认为没有它了），这时把B柱和A柱交换位置，那么情况是不是又回到了（最后一个圆盘（记作@）和除它之外的所有圆盘（记作#））这种情况，我们重复上面的步骤。没重复一次，就相当于从剩余需要移动的圆盘中挑出最大的扔掉，那么最后又回到了只有一个圆盘的情况，那这不就好办了吗，直接把最后一个扔过去

  Java实现代码

  //把n个圆盘从A移到C
  public static void tower(int n, String a, String b, String c) {
      //只有一个圆盘的情况
      if (n == 1) {
          System.out.println(a + "--->" + c);
      } else {
          //把n-1个圆盘丢到B柱上
          tower(n-1, a, c, b);
          //把剩下的移到C柱上
          System.out.println(a + "--->" + c);
          //对于现在B柱上的圆盘，先把A柱和B柱交换位置，
          //问题就变成了把n-1个圆盘从A移动到C
          tower(n-1, b, a, c);
      }
  
  }