【Java笔记】10 递归

猴子吃桃

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

  1. public calss Recursion{
  2.     public static void main(String[] args){
  3.         T t1 = new T();
  4.         int day = 0;
  5.         int peachNum = t1.peach(day);
  6.         if(peachNum != -1){
  7.             System.out.println("第"+day+"天有"+peachNum+"个桃子");
  8.         }
  9.     }
  10. }
  12. class T{
  13.     /*
  14.     1.day=10时 有1个桃子
  15.     2.day=9时 有(day10+1)*2=4
  16.     3.day=8时 有(day9+1)*2=10
  17.     前一天的桃子=(后一天的桃子+1)*2
  18.     */
  19.     public int peach(int day){
  20.         if(day == 10){//第10天，只有1个桃
  21.             return 1;
  22.         }else if(day >= 1&&day <= 9){
  23.             return (peach(day+1)+1)*2;
  24.         }else{
  25.             System.out.println("day在1-10");
  26.             return -1;
  27.         }
  28.     }
  29. }

迷宫问题

  1. public class MiGong{
  2.     public static void main(String[] args){
  3.         //先创建迷宫，用二维数组表示 int[][] map=new int[8][7];
  4.         //先规定map数组的元素值：0表示可以走 1表示障碍物
  5.         int[][] map = new int[8][7];
  6.         //设置障碍物
  7.         for(int i = 0;i < 7;i++){
  8.             map[0][i] = 1;
  9.             map[7][i] = 1;
  10.         }
  11.         for(int i = 0;i < 8;i++){
  12.             map[i][0] = 1;
  13.             map[i][6] = 1;
  14.         }
  15.         //输出当前的地图
  16.         System.out.println("===当前地图情况===");
  17.         for(int i = 0;i < map.length;i++){
  18.             for(int j = 0;j < map[i].length;j++){
  19.                 System.out.println(map[i][j]+" ");
  20.             }
  21.             System.out.println();
  22.         }
  23.         //使用findWay找路
  24.         T t1 = new T();
  25.         //下右上左
  26.         t1.findWay(map,1,1);
  27.         System.out.println("\n===找路的情况如下===");
  28.         for(int i = 0;i < map.length;i++){
  29.             for(int j = 0;j < map[i].length;j++){
  30.                 System.out.println(map[i][j]+" ");
  31.             }
  32.             System.out.println();
  33.         }
  34.     }
  35. }
  37. class T{
  38.     /*
  39.     findWay用来找出迷宫的路径
  40.     如果找到，就返回true，否则返回false
  41.     map就是二维数组，即表示迷宫
  42.     i,j就是老鼠的位置，初始化的位置为(1,1)
  43.     map数组的各个值的含义 0表示可以走 1表示障碍物 2表示可以走 3表示走过，但走不通是死路
  44.     当map[6][5]=2就说明找到通路，就可以结束，否则就继续找
  45.     找路策略 下->右->上->左
  46.     */
  47.     public boolean  findWay(int[][] map,int i,int j){
  48.         if(map[6][5] == 2){//说明已经找到
  49.             return true;
  50.         }else{
  51.             if(map[i][j] == 0){//当前这个位置0，说明表示可以走
  52.                 map[i][j] = 2;
  53.                 //使用找路策略，来确定该位置是否真的可以走通
  54.                 if(findWay(map,i+1,j)){
  55.                     return true;
  56.                 }else if(findWay(map,i,j+1)){
  57.                     return true;
  58.                 }else if(findWay(map,i-1,j)){
  59.                     return true;
  60.                 }else if(findWay(map,i,j-1)){
  61.                     return true;
  62.                 }else{
  63.                     map[i][j] = 3;
  64.                     return false;
  65.                 }
  67.             }else{
  68.                 return false;
  69.             }
  70.         }
  71.     }
  72. }

汉诺塔

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

  1. public class HanoiTower{
  2.     public static void main(String[] args){
  3.         Tower tower = new Tower();
  4.         tower.move(64,'A','B','C');
  5.     }
  6. }
  8. class Tower{
  9.     //num表示要移动的个数，a,b,c分别表示A塔，B塔，C塔
  10.     public void move(int num,char a,char b,char c){
  11.         //如果只有一个盘 num=1
  12.         if(num == 1){
  13.             System.out.println(a+"->"+c);
  14.         }else{
  15.             //如果有多个盘，可以看成两个，最下面的和上面的所有盘
  16.             //先移动上面所有的盘到b，借助c 
  17.             move(num-1,a,c,b);
  18.             //把最下面的这个盘，移动到c
  19.             System.out.println(a+"->"+c);
  20.             //再把b塔的所有盘，移动到c，借助a 
  21.             move(num-1,b,a,c);
  22.         }
  23.     }
  24. }