复杂程序Complex Programs

语句嵌套

基础规则

if, switch, for， while 可以随意嵌套

样例

1 2 3 4 5 6 7 8 9 10 11 
for (...) {    if (...) {        ...    }     while(...) {        if (...) {            ...        }    }}

留意

换行缩进

变量作用域及生命周期

循环嵌套

需求

小明每天吃3顿饭, 吃完了就睡觉

三天过去了, 小明干了什么

 < < < < < < < < < < < <
吃饭吃饭吃饭睡觉吃饭吃饭吃饭睡觉吃饭吃饭吃饭睡觉

代码

1 2 3 4 5 6 7 8 9 10 11 12 
Console.println("吃饭");Console.println("吃饭");Console.println("吃饭");Console.println("睡觉");Console.println("吃饭");Console.println("吃饭");Console.println("吃饭");Console.println("睡觉");Console.println("吃饭");Console.println("吃饭");Console.println("吃饭");Console.println("睡觉");

消除重复1

1+2 3 4 5 6+7-8-9-10-11-12-13-14-
for (int i = 0; i < 3; i++){    Console.println("吃饭");    Console.println("吃饭");    Console.println("吃饭");    Console.println("睡觉");}Console.println("吃饭");Console.println("吃饭");Console.println("吃饭");Console.println("睡觉");Console.println("吃饭");Console.println("吃饭");Console.println("吃饭");Console.println("睡觉");

消除重复2

1 2+3 4+5-6-7 8 
for (int i = 0; i < 3; j++){    for (int j = 0; j < 3; i++){        Console.println("吃饭");    }    Console.println("吃饭");    Console.println("吃饭");    Console.println("睡觉");}

内外循环

内循环

外循环

执行顺序

内循环	秒针
外循环	分针

秒针走一圈，分针走一格

11
for (12; 13; 14) {
    21
    for (22; 23; 24) {
        31
    }
    25
}
15

11
12 13
21, 22 23, 31 24 23, 31 24 23, ... 31 24 23, 25, 14 13
21, 22 23, 31 24 23, 31 24 23, ... 31 24 23, 25, 14 13
...

21, 22 23, 31 24 23, 31 24 23, ... 31 24 23, 25, 14 13
15

消代码大法

写出原始代码，逐层消除重复

案例

需求

输出

 < < <
* * * * * *

步骤

写出不循环的代码

尽量使用最小单元

1 2 3 4 5 6 7 8 9 10 11 
Console.print("* ");Console.print("* ");Console.print("* ");Console.println(); Console.print("* ");Console.print("* ");Console.println(); Console.print("* ");Console.println();

一次消除

1 2 3 4 5 6 7 8 9 10 11 12 13 14 
for (int i = 0; i < 3; i++) {    Console.print("* ");}Console.println(); for (int i = 0; i < 2; i++) {    Console.print("* ");}Console.println(); for (int i = 0; i < 1; i++) {    Console.print("* ");}Console.println();

二次消除

1 2 3 4 5 6 
for (int j = 0; j < 3; j++) {    for (int i = 0; i < 3 - j; i++) {        Console.print("* ");    }    Console.println();}

整理

1 2 3 4 5 6 7 
int size = 3;for (int i = 0; i < size; i++) {    for (int j = 0; j < 3 - i; j++) {        Console.print("* ");    }    Console.println();}

挑战

输出

 < < <
    *   * *

提示：

1 
Console.print("  ");

填模板大法

准备好双层 for 循环模板

分析最小单元代码，及其频率，

放到对应位置里去

案例

需求

输出

 < <   < <
1 x 1 = 1, 1 x 2 = 2, ... 1 x 9 = 92 x 2 = 4, 2 x 3 = 6, ... 2 x 9 = 9...8 x 8 = 64, 8 x 9 = 729 x 9 = 81

步骤

准备好双层 for 循环模板

1 2 3 4 5 6 7 
for (int i = 0; i < _A_; i++) {    _B_;    for (int j = 0; j < _C_; j++) {        _D_;    }    _E_;}

找出最小单元

1 2 3 4 5 6 7 
Console.print(left);Console.print(" x ");Console.print(right);Console.print(" = ");Console.print(result);Console.print(",");Console.println();

找出相对频率

1 2 3 4 5 6 7 
Console.print(left);        较高Console.print(" x ");       较高Console.print(right);       较高Console.print(" = ");       较高Console.print(result);      较高Console.print(",");         较高Console.println();          较低

根据相对频率，放到内外循环中

较高的放内循环，较低的放外循环

1 2 3 4 5 6 7 8 9 10 11 
for (int i = 0; i < _A_; i++) {    for (int j = 0; j < _C_; j++) {        Console.print(left);        Console.print(" x ");        Console.print(right);        Console.print(" = ");        Console.print(result);        Console.print(",");    }    Console.println();}

分析内外循环次数

外循环 9 次

内循环次数跟外循环次数有数学关系

1 2 3 4 5 6 7 8 9 10 11 
for (int i = 0; i < 9; i++) {    for (int j = 0; j < 9 - i; j++) {        Console.print(left);        Console.print(" x ");        Console.print(right);        Console.print(" = ");        Console.print(result);        Console.print(",");    }    Console.println();}

找出最小单元跟循环 i j 的数学关系

1 2 3 4 5 6 7 8 9 10 11 12 13 14 
for (int i = 0; i < 9; i++) {    for (int j = 0; j < 9 - i; j++) {        int left = i + 1;        int right = left + j;        int result = left * right;        Console.print(left);        Console.print(" x ");        Console.print(right);        Console.print(" = ");        Console.print(result);        Console.print(",");    }    Console.println();}

细节调整

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 
int size = 9;for (int i = 0; i < size; i++) {    for (int j = 0; j < size - i; j++) {        int left = i + 1;        int right = left + j;        int result = left * right;        Console.print(left);        Console.print(" x ");        Console.print(right);        Console.print(" = ");        Console.print(result);        if (right != size) {            Console.print(",");        }    }    Console.println();}

挑战

输出

 < < <
    *   * *

剥洋葱大法

将一整个大问题，逐层分解为小问题

大事化小、小事化了

案例

需求

输出 100 以内所有的质数

步骤

原始问题

1 
// 输出 100 以内所有的质数

使用 for 降级

1+2 3+
for (int i = 2; i <= 100; i++) {    // 给定一个数 i, 如果是质数, 就把它输出出来}

使用 if 降级

1 2+3 4 5+6+7+8 
for (int i = 2; i <= 100; i++) {    boolean test;    // 检测一个数 i, 是否是质数     if (test) {        Console.println(i);    }}

伪代码分析

质数是只能被 1 和自己整除

也就是说, 从 2 到它自己, 没有任何数能把它整除

1 2*3 4 5 6 7 8 9 10*11 12 13 
for (int i = 2; i <= 100; i++) {    boolean isPrime = true;     //  对 i 进行检查    //  (从 2 到 i, 不包含 i) {     //      应该没有任何能整除 i 的    //      一旦发现, 就不是质数了    //  }     if (isPrime) {        Console.println(i);    }}

使用 for 降级

1 2 3 4+5 6 7+8 9 10 11 12 
for (int i = 2; i <= 100; i++) {    boolean isPrime = true;     for (int factor = 2; factor < i; factor++){        //  应该没有任何能整除 i 的        //  一旦发现, 就不是质数了    }     if (isPrime) {        Console.println(i);    }}

伪代码分析

1 2 3 4 5*6*7*8 9 10 11 12 13 
for (int i = 2; i <= 100; i++) {    boolean isPrime = true;     for (int factor = 2; factor < i; factor++){        //  如果 (factor 能整除 i) {        //      i 就不是质数        //  }    }     if (isPrime) {        Console.println(i);    }}

使用 if 降级

1 2 3 4 5*6*7*8 9 10 11 12 13 
for (int i = 2; i <= 100; i++) {    boolean isPrime = true;     for (int factor = 2; factor < i; factor++){        if (i % factor == 0){            isPrime = false;        }    }     if (isPrime) {        Console.println(i);    }}

挑战

输出

 < < <
    *   * *

循环嵌套 x 循环控制

规则

break 和 continue 只对离它最近的循环语句生效，

不会影响到外层循环

for (...) {
    for (...) {
        if (...) {
            if (...) {
                break;
            }
            // 1
        }
        // 2
    }
    // 3
}
// 4

break 执行后，会跳到哪个注释区域的代码

案例

1 2 3 4 5 6 7+8 9 10 11 12 13 14 
for (int i = 2; i <= 100; i++) {    boolean isPrime = true;     for (int factor = 2; factor < i; factor++){        if (i % factor == 0){            isPrime = false;            break;        }    }     if (isPrime) {        Console.println(i);    }}

排序Sorting

什么是

入门级经典问题

给定一个数组, 里面有一堆乱序的数, 执行一段程序后, 居然就从小到大排列好了

有哪些

很多

选择排序

插入排序

冒泡排序

选择排序

插入排序

冒泡排序

二维数组

二维数组实质

一维数组的元素类型是一维数组

语法

声明

<元素类型>[][] <数组名>;

int[][] matrix;

创建

new <元素类型>[<维度1尺寸>][<维度2尺寸>];

new int[3][4];

字面量

{{2, 5, 1, 4}, {1, 3, 7, 0}, {8, 5, 2, 9}};

{{2, 5, 1, 4},
 {1, 3, 7, 0},
 {8, 5, 2, 9}};

二维数组访问

1 2 3 
int[][] matrix = new int[3][4];matrix[1][1] = 2;Console.println(matrix[1][1]);

二维数组代码样例

二维数组遍历

1 2 3 4 5 6 7 8 9 10 11 
int[][] matrix = {    {2, 5, 1, 4},    {1, 3, 7, 0},    {8, 5, 2, 9}}; for (int i = 0; i < matrix.length; i++){    for (int j = 0; j < matrix[i].length; j++){        Console.println(matrix[i][j]);    }}

制造二维数组

制造一个全是 1 的 4 x 4 的二维数组

1 2 3 4 5 6 7 
int size = 4;int[][] matrix = new int[size][size];for (int i = 0; i < size; i++){    for (int j = 0; j <size; j++){        matrix[i][j] = 1;    }}

二维数组变一维数组

1 2 3 4 5 6 7 8 9 10 11 12 
int width = 3;int height = 2;int[][] matrix = {    {6, 7, 3},    {8, 4, 1}};int[] linear = new int[width * height];for (int y = 0; y < height; y++){    for (int x = 0; x < width; x++){        linear[y * width + x] = matrix[y][x];    }}

多维数组

以此类推

比如三维数组

1 
int[][][] cube = new int[3][3][3];