【Java笔记】10 递归

• 【Java笔记】10 递归
• 猴子吃桃
• 迷宫问题
• 汉诺塔

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

public calss Recursion{
    public static void main(String[] args){
        T t1 = new T();
        int day = 0;
        int peachNum = t1.peach(day);
        if(peachNum != -1){
            System.out.println("第"+day+"天有"+peachNum+"个桃子");
        }
    }
}

class T{
    
    public int peach(int day){
        if(day == 10){//第10天，只有1个桃
            return 1;
        }else if(day >= 1&&day <= 9){
            return (peach(day+1)+1)*2;
        }else{
            System.out.println("day在1-10");
            return -1;
        }
    }
}

public class MiGong{
	public static void main(String[] args){
		//先创建迷宫，用二维数组表示 int[][] map=new int[8][7];
		//先规定map数组的元素值：0表示可以走 1表示障碍物
		int[][] map = new int[8][7];
		//设置障碍物
		for(int i = 0;i < 7;i++){
			map[0][i] = 1;
			map[7][i] = 1;
		}
		for(int i = 0;i < 8;i++){
			map[i][0] = 1;
			map[i][6] = 1;
		}
		//输出当前的地图
		System.out.println("===当前地图情况===");
		for(int i = 0;i < map.length;i++){
			for(int j = 0;j < map[i].length;j++){
				System.out.println(map[i][j]+" ");
			}
			System.out.println();
		}
		//使用findWay找路
		T t1 = new T();
		//下右上左
		t1.findWay(map,1,1);
		System.out.println("n===找路的情况如下===");
		for(int i = 0;i < map.length;i++){
			for(int j = 0;j < map[i].length;j++){
				System.out.println(map[i][j]+" ");
			}
			System.out.println();
		}
	}
}

class T{
	
	public boolean  findWay(int[][] map,int i,int j){
		if(map[6][5] == 2){//说明已经找到
			return true;
		}else{
			if(map[i][j] == 0){//当前这个位置0，说明表示可以走
				map[i][j] = 2;
				//使用找路策略，来确定该位置是否真的可以走通
				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{
				return false;
			}
		}
	}
}

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子， 在一根柱子上从下往上按照大小顺序摞着 64 片圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一 根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

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

class Tower{
	//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{
			//如果有多个盘，可以看成两个，最下面的和上面的所有盘
			//先移动上面所有的盘到b，借助c 
			move(num-1,a,c,b);
			//把最下面的这个盘，移动到c
			System.out.println(a+"->"+c);
			//再把b塔的所有盘，移动到c，借助a 
			move(num-1,b,a,c);
		}
	}
}