博客

问题描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

解决问题思路：

台阶为0跳法为0，台阶为1的时候跳法为1，台阶为2跳法为2。当我们输入n个台阶时，可以想到它可以是在第n-1个台阶上跳上来，也可以是从第n-2个台阶上跳上来，第n-1个台阶可以是在第n-2个台阶跳上来，也可以是在第n-3个台阶上跳上来，由此我们可以得到一个公式：Kn=Kn-1 + Kn-2; Kn-1=Kn-2 + Kn-3；依次类推当可以推到K1=1;K2=2;K0=0时便可以得到结果。

import java.util.Scanner;
public class Tses {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int input = scan.nextInt();
        System.out.println("有" + jumpNum2(input) + "种跳法");
    }
    //递归
    public static int jumpNum(int num) {
        if(num == 0) {
            return 0;
        }else if(num == 1) {
            return 1;
        }else if(num == 2) {
            return 2;
        } else {
            return jumpNum(num-1) + jumpNum(num-2);
        }
    }
    //迭代
    public static int jumpNum2(int num) {
        int k0 = 0;
        int k1 = 1;
        int k2 = 2;
        int result = 0;
        if(num == 0) {
            return k0;
        }else if(num == 1) {
            return k1;
        }else if(num == 2) {
            return k2;
        }else {
            for(int k = 3; k <= num; k ++) {
                result = k2 + k1;
                k1 = k2;
                k2 = result;
            }
            return result;
        }
    }
}

问题描述：

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。

问应该如何操作？

解决思路：

我们设三根杆为A B C ,也就是说，我们要将盘子从A，借助B移动到C杆，所以当盘子为1时就直接从A移动到C，盘子数为2的时候，我们先将第一个移动到B 再将第2个移动到C杆，最后再将第一个盘子移动到C杆。

输入n个盘子的时候，将第n-1个盘子移动到B杆，将第n个盘子移动到C杆，再将第n-2个移动到C杆。依次类推。

import java.util.Scanner;
public class Tses {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("输入盘子数目:>");
        int input = scan.nextInt();
        char A = 'A';
        char B = 'B';
        char C = 'C';
        hanio(input, A, B, C);
    }

    public static void hanio(int input, char A, char B, char C) {
        if(input == 1) {
            System.out.println("from " + A +" to " + C);
        }else {
            hanio(input-1, A, C, B);
            System.out.println ("from " + A +" to " + C);
            hanio(input-1, B, A, C);
        }
    }
}