JAVA基础(九)

一、目录

• 斐波那契数列
• 猴子吃桃
• 老鼠出迷宫
• 汉诺塔

二、斐波那契数列

问题：请使用递归的方式求出斐波那契数1,1,2,3,5,8,13…给你一个整数n，求出它的值是多少？

public class fibonacci {
    public static void main(String args[]){
        T t1 = new T();
        System.out.println("fibo(n)= " + t1.fibo(7));
    }
}

class T{
    public int fibo(int n){
        if(n >= 1){
            if (n == 1 || n == 2){
                return 1;
            }else {
                return fibo(n - 1) + fibo(n - 2);
            }
        }else{
            System.out.println("n must >= 1");
            return -1;
        }
    }
}

fibo(n)= 13

三、猴子吃桃

问题：有一堆桃子，猴子第一天吃了其中的一半，并再多吃了一个！以后每天猴子都吃其中的一半，然后再多吃一个。当到第10天时，想再吃时(即还没吃)，发现只有1个桃子了。问，最初共多少个桃子？

public class moneyeatpeach {
    public static void main(String[] args){
        M m = new M();
        System.out.println(m.money(1));
    }
}

class M{
    public int money(int day){
        if (day >= 1 && day 左
                if(findway(map, i +1, j)){ //先向下探测
                    return true;
                }else if (findway(map, i, j + 1)){//向右探测
                    return true;
                }else if(findway(map, i - 1, j)){//向上探测
                    return true;
                }else if(findway(map, i, j - 1)){//向左探测
                    return true;
                }else {
                    map[i][j] = 3;
                    return false;
                }

            }else { //map[i][j] = 1, 2, 3
                return false;
            }
        }
    }
}

The Current Map
1111111
1000001
1000001
1110001
1000001
1000001
1000001
1111111

The Current Map
1111111
1200001
1222001
1112001
1002001
1002001
1002221
1111111

五、汉诺塔

public class HanoiTower {
    public static void main(String[] args){
        H h = new H();
        h.move(2, 'A', 'B', 'C');
    }
}

class H{

    //num表示要移动的个数， a， b， c分别表示A塔，B塔，C塔
    public void move(int num, char a, char b, char c){
        //如果只有一个盘，也就是num = 1
        if (num == 1){
            System.out.println(a + "->" + c);
        }else {
            //如果有多个盘，可以看成两个，(最下面的一个盘)和(上面的所有盘)
            //1. 先移动上面所有的盘到b，借助c
            move(num - 1, a, c, b);
            //2. 把最下面的这个盘，移动到c
            System.out.println(a + "->" + c);
            //3. 最后把b塔的所有盘，移动到c，借助a
            move(num - 1, b, a, c);
        }
    }
}

A->B
A->C
B->C