day07--二维数组 & 递归

今天我们主要学习以下内容
1. 二维数组的概念，内存映象，二维数组中数据元素的访问
2. 二维数组的3中初始化方式
3. 方法的参数传递问题（基本数据类型和引用数据类型）
4 递归方法的定义，递归的算法核心思想

二维数组

引例：　　

　　我们已经学习了基本的一维数组，可以持有大量数据。

　　 思考如下场景： 假设我现在要统计，学校中某个年级中，各班的数学成绩的平均分。 思考一下，用一维数组可以吗？会遇到什么问题？ 分析一下出现问题的原因是什么呢？ 不同的维度

 

 图：二维数组的引例

　　二维数组初始化三种格式

 

 图：二维数组的初始化格式1

图：二维数组的初始化格式2 

package com.cskaoyan.two;

/**
 * @author zhangshuai@Cskaoyan.onaliyun.com on 2020/4/13.
 * @version 1.0
 * 二维数组的实质：一维 （数组的） 数组

     二维数组的初始化格式1：
      数据类型[][] 变量名 = new 数据类型[m][n];
      m代表二维数组中一维数组的个数
      n代表二维数组中包含的每个一维数组，所能包含的元素个数
      特征：二维数组中每一个一维数组包含的元素个数相同

    二维数组定义的格式2
    数据类型[][] 变量名 = new 数据类型[m][];
    m表示这个二维数组有多少个一维数组
    这一次没有直接给出一维数组的元素个数，可以动态的给出。

    int[][] arr2 = new int[2][];
    arr[0] = new int[1];
    arr[1] = new int[2];
    特征： 初始化二维数组比较麻烦，二维数组中的一维数组，都需要我们自己初始化，
          但可以让二维数组的每个一维数组包含不同的元素个数


    二维数组定义的格式3
    数据类型[][] 变量名 = new 数据类型[][]{{元素…},{元素…},{元素…}};

    简化版格式：
    数据类型[][] 变量名 = {{元素…},{元素…},{元素…}};

    注意：
    简化版只能在定义数组的引用变量时使用！



 *
 *
 *
 */
public class Demo1 {

  public static void main(String[] args) {

    // 二维数组的初始化格式1：
    // 数据类型[][] 变量名 = new 数据类型[m][n];
    firstInitialization();

    // 二维数组的初始化格式2：
    // 数据类型[][] 变量名 = new 数据类型[m][];
    secondInitialiization();

    //二维数组定义的格式3
    //数据类型[][] 变量名 = new 数据类型[][]{{元素…},{元素…},{元素…}};
    // 3个一维数组，每个一维数组的初值分别通过{}来指定
    int[][] arr3 = new int[][] {{1}, {2, 3}, {4, 5, 6}};

    traverseTwoDimensionArray(arr3);

  }


  public static void traverseTwoDimensionArray(int[][] arr) {
    //遍历二维数组，输出二维数组中的每一个值
    // arr 指向的是代表二维数组的那个一维数组  arr.length 表示二维数组中的一维数组个数
    // arr[i] 代表二维数组中的第i个一维数组  arr[i].length 表示的就是二维数组中第i个一维数组的元素个数

    for (int i = 0; i < arr.length; i++) {

      //完成，对二维数组中的一个一维数组的遍历
      for (int j = 0; j < arr[i].length; j++) {
        System.out.print(arr[i][j] + " ");
      }
      System.out.println();
    }


  }

  private static void secondInitialiization() {
    // 数据类型[][] 变量名 = new 数据类型[m][];
    int[][] arr2 = new int[2][];
    //初始化二维数组中的第一个一维数组
    arr2[0] = new int[1];
    //初始化二维数组中的第二个一维数组
    arr2[1] = new int[2];
  }

  private static void firstInitialization() {


    // 一个包含2个一维数组，且每个一维数组中包含2个元素的 一个二维数组
    int[][] arr = new int[2][2];

    // 访问一下二维数组

    //1. 输出二维数组的引用变量的值
    System.out.println(arr); //[[(表示一个二维数组) I@ 4554617c
    // 2. 输出执行二维数组中，第一个一维数组的，引用的值
    System.out.println(arr[0]); // [I@74a14482

    //3. 访问二维数组中，一维数组的元素值
    System.out.println(arr[0][0]);

    arr[1][1] = 100;
    System.out.println(arr[1][1]);
  }

}

　　练习：

• 二维数组遍历
• 打印杨辉三角形(行数可以键盘录入)

package com.cskaoyan.two;

import java.util.Scanner;

/**
 * @author zhangshuai@Cskaoyan.onaliyun.com on 2020/4/13.
 * @version 1.0
 *
 * 1.二维数组遍历
    公司年销售额求和
    某公司按照季度和月份统计的数据如下：单位(万元)
    第一季度：22,66,44
    第二季度：77,33,88
    第三季度：25,45,65
    第四季度：11,66,99

   2. 打印杨辉三角形(行数可以键盘录入)
 1    1
 2    1 1
 3    1 2 1
 4    1 3 3 1
 5    1 4 6 4 1

   1. 对于杨辉三角而言，第一行和第二行数据是固定的
   2. 每一行的元素个数和行数相同(从第1行开始)
   3. 从第3行开始：
      a. 每一行的第一个和最后一个元素值固定，都是1
      b. 每一行出首尾位置之外，其他位置的元素值都有规律：
         第i行第j列 = 第i - 1行第j列的值 + 第i-1行j - 1列


 */
public class Exercise {

  public static void main(String[] args) {

    // 第三种初始化二维数组格式的简化
    int[][] sales = {{22,66,44}, {77,33,88}, {25,45,65}, {11,66,99}};
    //简化版只能在定义数组的引用变量时使用！
    //sales = {{22,66,44}, {77,33,88}, {25,45,65}, {11,66,99}};
    //sales = new int[][]{{22,66,44}, {77,33,88}, {25,45,65}, {11,66,99}};

    //System.out.println(exercise01(sales));



    //练习2
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int[][] arr = exercise02(n);
    traverseTwoDimensionArray(arr);

  }


  public static int exercise01(int[][] salse) {
    int sum = 0;

    for (int i = 0; i < salse.length; i++) {

      for (int j = 0; j < salse[i].length; j++) {
         sum += salse[i][j];
      }
    }

    return sum;
  }


  /**
   *
   * @param n  表示杨辉三角的行数
   * @return 表示n行杨辉三角数据的二维数组
   */
  public static int[][] exercise02 (int n) {

    //针对第n值为1和n值为2，做特殊处理
    if (n == 1) {
      return new int[][]{{1}};
    }

    if (n == 2) {
      return new int[][]{{1}, {1, 1}};
    }


    // 表示，最终返回的二维数组的结果
    int[][] result;
    // 用格式2初始化，结果二维数组
    result = new int[n][];
    // 初始化杨辉三角的第一行和第二行数据
    result[0] = new int[] {1};
    result[1] = new int[] {1, 1};

    // 从第3行开始，计算并初始化，每一行杨辉三角数据
    for (int i = 2; i < n; i++) {
      // 初始化杨辉三角第i + 1行 对应的第i个一维数组
      result[i] = new int[i + 1];
      //对于杨辉三角的第i行数据， 初始化首尾元素的值
      result[i][0] = 1;
      result[i][i] = 1;


      for (int j = 1; j < i; j++) {
        //第i行第j列 = 第i - 1行第j列的值 + 第i-1行j - 1列
        result[i][j] = result[i - 1][j] + result[i - 1][j - 1];
      }
    }
    return result;
  }

  public static void traverseTwoDimensionArray(int[][] arr) {
    //遍历二维数组，输出二维数组中的每一个值
    // arr 指向的是代表二维数组的那个一维数组  arr.length 表示二维数组中的一维数组个数
    // arr[i] 代表二维数组中的第i个一维数组  arr[i].length 表示的就是二维数组中第i个一维数组的元素个数

    for (int i = 0; i < arr.length; i++) {

      //完成，对二维数组中的一个一维数组的遍历
      for (int j = 0; j < arr[i].length; j++) {
        System.out.print(arr[i][j] + " ");
      }
      System.out.println();
    }


  }

}

　　看程序写结果，并总结基本类型和引用类型参数的传递问题(题目在备注部分)

package com.cskaoyan.method;

/**
 * @author zhangshuai@Cskaoyan.onaliyun.com on 2020/4/13.
 * @version 1.0
 *
 * 总结一下：
 *
 *   在java语言中，不管参数的类型，是引用类型还是，基本数据类型，在实际参数和形式参数进行值传递的方式只有一种：
 *   实际参数的值   复制一份 赋值给形式参数
 *
 *   所以，实参的值，其实就有两份，调用方法中一份，被调用方法中一份
 *
 * 1. 当方法的参数是基本数据类型的参数的时候，
 *     参数有两份，同时参数对应的数据的值，也有两份
 *
 * 2. 当方法的参数是引用数据类型的时候
 *     参数值有两份，但是两个数组类型引用变量，对应的值(数组)，只有一个
 *
 *
 */
public class Demo1 {

  public static void main(String[] args) {

    //int a = 10;
    //int b = 20;
    //System.out.println("main a:" + a + ",b:" + b);
    //change(a, b);
    //System.out.println("main a:" + a + ",b:" + b);



    int[] arr = {1, 2, 3, 4, 5};
    change(arr);
    System.out.println(arr[1]);
  }

  public static void change(int a, int b) {
    System.out.println("change a:" + a + ",b:" + b);
    a = b;
    b = a + b; // 2 * b
    System.out.println("change a:" + a + ",b:" + b);
  }


  public static void change(int[] arr) {
    for (int x = 0; x < arr.length; x++) {
      if (arr[x] % 2 == 0) {
        arr[x] *= 2;
      }
    }
  }
}

 图：方法的参数传递

递归

递归定义：方法定义中调用方法本身的现象

实现递归需要注意的问题：

• 递归一定要有出口！！
• 次数不能太多，否则就出现 stack overflow

 图：递归方法错误 & 栈内存管理

package com.cskaoyan.recursion;

/**
 * @author zhangshuai@Cskaoyan.onaliyun.com on 2020/4/13.
 * @version 1.0
 *
 * 仅仅从语法角度：
 * 递归方法定义：方法 定义中 调用 方法本身的方法
 *
 * 实现递归需要注意的问题：
      1. 递归一定要有出口！！(递归一定要有终止条件，在一定条件下，终止自己调用自己)
      2. 次数不能太多，否则就出现 stack overflow
 *
 */
public class Demo1 {

  public static void main(String[] args) {

    //调用递归方法
    //recursion1();

    //调用带递归出口的递归方法
    recursion2(4);

    //次数不能太多，否则就出现 stack overflow
    recursion2(Integer.MAX_VALUE);

  }


  // 按照递归方法的定义来书写  java.lang.StackOverflowError 栈溢出错误
  public static void recursion1() {
    // 方法体中，自己调用自己
    recursion1();
  }


  /*
      带递归出口的递归方法
   */
  public static void recursion2(int n) {

    //每一次调用自己之前，判断一下 n>0才自己调用自己，否则(n <= 0)，终止自己调用自己
    if (n <= 0) {
      System.out.println("达到出口条件，不在自己调用自己 " + n);
      return;
    }

    n--;
    //否则，如果还没有达到递归的出口条件，继续自己调用自己
    recursion2(n);

  }
}

 图：带出口条件的递归方法

例子：

1.汉诺塔问题：

　　有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。

要求按下列规则将所有圆盘移至 C 杆：

• 每次只能移动一个圆盘；
• 大盘不能叠在小盘上面。

提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

问：最少要移动多少次？如何移？

/**
 * @author zhangshuai@Cskaoyan.onaliyun.com on 2020/4/13.
 * @version 1.0
 *
 * 1.有三根杆子A，B，C。A杆上有 N(64) 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
    a. 每次只能移动一个圆盘；
    b. 大盘不能叠在小盘上面。
    提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。
    问：最少要移动多少次？如何移？


    解决思路以N个圆盘为例：

         1. 当我们要解决N个圆盘的搬运问题，对于N个圆盘，我们可能无法一次性得到结果，
            于是，我们把N个圆盘的搬运问题， -》 最大的云盘的搬运 & 最大圆盘上面的 n - 1

         2. 对于规模为1那个待搬运的最大的圆盘，直接就知道如何搬运（一步搞定）

         3. 在2的基础上，只要，解决 N - 1个圆盘搬运的问题

         总结一下，汉诺塔问题，解决思路(递归算法的核心思想)： 分而治之
                                     把一个复杂的大规模的问题，分解成若干相似的小规模的子问题，
                                    当问题规模，足够小的是时候，我们就可以直接得到小规模问题的解，
                                    再把小规模问题的解，组合起来，——> 大规模问题提的解


    1.用递归方法 -> 实现按照递归的方式，解决汉诺塔问题的代码

    n 为3时的输出序列：
      A——>C
      A——>B
      C——>B
      A——>C
      B——>A
      B——>C
      A——>C

    2. n个圆盘，总共要搬运多少次，才能完成n个圆盘的搬运？
       f(n) 表示n个圆盘搬运的次数

       f(n) = f(n - 1) +  1 +  f(n - 1) = 2 * f(n - 1) + 1
       f(n) + 1 = 2(f(n - 1) + 1)
       ...
       f(1) + 1 = 2

      {f(n) + 1} = 2^n
       f(n) = 2^n - 1


 */
public class Demo2 {

  public static void main(String[] args) {

    //hanoi(3, 'A', 'C', 'B');

    System.out.println(count(3));

  }

  //  f(n) = f(n - 1) +  1 +  f(n - 1)
  public static int count(int n) {

    // 出口条件
    if (n == 1) {
      return 1;
    }

    // 递归计算，n个圆盘搬运的的次数

    return count(n - 1) + 1 + count(n - 1);
  }


  /**
   *
   * @param n      表示当前待搬运的圆盘的数量(代表当前问题的规模)
   * @param start  当前待搬运的圆盘所在的杆的名字
   * @param end    待搬运的n个盘盘，搬运到的目标杆的名字
   * @param middle  此次把n个圆盘从start杆 -》 end杆时，所使用的辅助杆的名字
   */
  public static void hanoi(int n, char start, char end, char middle) {

    //递归方法的出口条件
    if (n == 1) {
      System.out.println(start + "——>" + end);
      return;
    }

    //分解规模为n汉汉塔问题

    // 将待搬运那上面的n-1个圆盘，搬运到辅助杆上
    hanoi(n - 1, start, middle, end);

    // 将起始杆上剩下的那个，待搬运的最大的圆盘，一次搬运到目标杆，它的最终位置
    System.out.println(start + "——>" + end);

    //接下来，对于剩余的在middle上的那n-1个圆盘，从middle杆开始，以start为辅助，移动到end杆上
    hanoi(n - 1, middle, end, start);
  }

}

 2. 周末晚上你和女朋友去看电影，月黑风高，女朋友悄悄地问你：我们在第几排？电影院太黑，没办法数？怎么办？

package com.cskaoyan.recursion;

/**
 * @author zhangshuai@Cskaoyan.onaliyun.com on 2020/4/13.
 * @version 1.0
 *
 * 2. 周末晚上你和女朋友去看电影，月黑风高，女朋友悄悄地问你：我们在第几排？电影院太黑，没办法数？怎么办？
 *    a. 无法直接看到，自己在第几排，但是我可以，问前排的同学，他在第几排
 *    b. 当依次向前询问，当问到第一排同学的时候，他可以用触觉来判断，比如，摸了一下发现前面没有椅子
 *
 *    f(n) = f(n - 1) + 1

 */
public class Demo3 {


  public static void main(String[] args) {

    int row = f(10);
    System.out.println(row);
  }


  /*
       模拟，依次向前询问，自己在第几排，最终得到自己所在的排数
       f(n) = f(n - 1) + 1
   */
  public static int f(int n) {

    if(n == 1) {
      return 1;
    }

    //如果当前不是第一排的同学，就继续问他前排的同学
    return f(n - 1) + 1;
  }

}

3. 求n的阶乘

package com.cskaoyan.recursion;

/**
 * @author zhangshuai@Cskaoyan.onaliyun.com on 2020/4/13.
 * @version 1.0
 * 3. 求n的阶乘
     f(n) = n * ((n - 1) * (n - 2) ... * 2 * 1)
     f(n) = n * f(n - 1)
 */
public class Demo4 {


  public static void main(String[] args) {
    System.out.println(multiple(5));
  }

  /**
   *
   * @param n  所求的问题规模 n的阶乘
   * @return
   *
   *  f(n) = n * f(n - 1)
   *  f(1) = 1
   */
  public static int multiple(int n) {

    if(n == 1) {
      return 1;
    }

    return n * multiple(n - 1);

  }

}

4. 求n的阶乘 4.有一对兔子，从出生后第三个月开始每月生一对兔子，小兔子从第三个月开始每月也生一对兔子，假如是不死神兔，那么第20个月一共生多少对兔子？

package com.cskaoyan.recursion;

/**
 * @author zhangshuai@Cskaoyan.onaliyun.com on 2020/4/13.
 * @version 1.0
 *
 * 4.有一对兔子，从出生后第三个月开始每月生一对兔子，小兔子从第三个月开始每月也生一对兔子，
 *   假如是不死神兔，那么第20个月一共生多少对兔子？
 *
 *  月份         1   2   3   4  ...
    兔子的数量    1   1   2   3  ...


    i                      i + 1                   i + 2
    N(i)     +              N(i)              =     N(i) * 2
    N(i - 1) +              N(i - 1) * 2      =     N(i - 1) * 2 + N(i - 1)
    N(i - 2) +              N(i - 2) * 2      =     N(i - 2) * 2 + N(i - 2)

      N(i) + N(i + 1) = N(i + 2)

     count(n) = count(n - 1) + count(n - 2)

     count(1) = 1
     count(2) = 1
 */
public class Demo5 {

  public static void main(String[] args) {
    System.out.println(count(20));
  }

  /*
      计算不死神兔的数量
       count(n) = count(n - 1) + count(n - 2)
   */
  public static int count(int n) {

    if(n == 1) {
      return 1;
    }

    if (n == 2) {
      return 1;
    }

    return count(n - 1) + count(n - 2);

  }





  /*
     分析：

   首先，我们设有n条直线时的答案为f(n)
   1.那么当有n - 1条直线时，平面最多被分成了f（n - 1）个区域。
   2.则第n条直线，如果要切成的区域数最多，那么第n条直线就必须与每条直线相交，且不能有同一交点。这样就会得到n - 1个交点。
   3.而这些交点将这条直线(第n条直线)分为2条射线和n - 2条线段。而每条射线和线断将以有的区域一分为二。
     这样就多出了2 + (n - 2)，也就是n个区域。

    f(1) = 2;  一条直线将一个平面分成2份
    f(n) = f(n-1) + n;

   */
  public static int f(int n) {
    if (n == 1) {
      return 2;
    }
    return f(n - 1) + n;
  }

}