C-Week4

Lesson16 习题课 4—— 综合专题

16.1 输出给定条件的整数集

• 问题描述：给定不超过 6 的正整数 A，考虑从 A 开始的的连续 4 个数字。请输出所有由这四个数字组成的无重复数字的三位数。
• 输出要求：每行 6 个输出结果，一行内的输出结果之间用空格隔开，行末无空格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int A, cnt = 0;
scanf("%d", &A);
for (int a = A; a < A + 4; a++){
    for (int b = A; b <  A + 4; b++){
        for (int c = A; c < A + 4; c++){
            if (a == b || b == c){
                continue;
            }
            cnt++;
            printf("%d%d%d", a, b, c);
            //接下来解决输出格式要求
            if (cnt % 6 == 0){
                printf("\n");
            }
            else{
                printf(" ");
            }
        }
    }
}

16.2 水仙花数

• 问题描述：水仙花数（Narcissistic number）是一个 $N$ 位（$N\geqslant3$）正整数，它的每个位上数字的 $N$ 次幂之和等于它本身。最小的水仙花数是 $153=1^3+5^3+3^3$。给定位数 $N$（$3\leqslant N\leqslant7$），输出所有 $N$ 位水仙花数。
• 输出格式：按递增顺序输出所有 $N$ 位水仙花数，每个数字占一行。

计算方面：

• 先确定输入，用户输入只指定了（隐含的）范围，具体的输入由程序自己生成。我们使用 for 循环来递增生成数字

• 分离各位数字。我们采用 12.5 的方式来做

• 求幂、求和。

• 判断是否为水仙花数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <math.h>

int N;
scanf("%d", &N);
for (int i = pow(10, N - 1); i < pow(10, N); i++)//生成数字
{
    int sum = 0;
    int t = i;
    for (int q = 0; q < N; q++)//分离各位数字并求幂、求和
    {
        int n = t % 10;
        t /= 10;
        sum += pow(n, N);
    }
    if (sum == i)
    {
        printf("%d\n", i);
    }
    else
    {
        continue;
    }
}

16.3 九九乘法表

• 问题描述：给定 1 位正整数 $N(1\leqslant N\leqslant 9)$，输出从 $1×1$ 到 $N×N$ 的部分乘法口诀表。

  参考：

  

• 输出格式：要求等号右边数字占 4 位（不足的部分用空格代替），表达式左对齐。

计算方面：

• 计算方面不难，一个乘法计算器而已。难的是格式化输出。怎么写能让输出按下三角形输出？
• 我们可以按行输出。只有在一行的口诀都输出后，才进入下一行的计算。观察口诀表，我们发现，在同一行中，每个表达式的第二个算子都不变，且等于该行序号。
• 对于空格补足，由于结果只有一位或两位数，因此我们直接用判断解决。
• 该行结束时需要换行。观察发现，每行最后一个表达式的两个算子的值相同，可以作为判断依据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int N;
scanf("%d", &N);
for (int i = 1; i <= N; i++){
    for (int p = 1; p <= i; p++){
        int ret = p * i;
        printf("%d*%d=%d", p, i, ret);
        if (ret < 10){
            printf("   ");
        }
        else{
            printf("  ");
        }
        if (p == i){
            printf("\n");
        }
    }
}

有人知道制表符可以用来对齐文本，因此会想用'\t' 来规范这里的输出 (参见 [17.10](#17.10 逃逸字符))。在他们的认知中，制表符的宽度就是 4 字符，因为很多文本编辑器的制表符宽度就是 4。

对吗？并不对。如果你通过命令行来编辑、编译并运行源代码，你会发现，在默认设置下，不论是 Windows 系统还是 Linux 系统，制表符的宽度都是 8 字符！这和题目的要求明显不符合。

16.4 统计素数并求和

• 问题描述：给定 2 个正整数$M$ 和$N$ $(1\leqslant M\leqslant N \leqslant 500)$，统计区间$[M,N]$ 内素数的个数，并对它们求和。两个输出结果间以空格分隔。

计算方面：

• 我们使用 13.1 的方式判断素数。由于只有范围，具体数字由程序生成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int M, N, count = 0, sum = 0;
scanf("%d %d", &M, &N);
for (int i = M; i <= N; i++){
    int isPrime = 1;
    if (i == 1){
        isPrime = 0;
        continue;
    }
    for (int p = 2; p < i; p++){
        if (i % p == 0){
            isPrime = 0;
            break;
        }
        else{
            continue;
        }
    }
    if (isPrime == 1){
        count++;
        sum += i;
    }
    else{
        continue;
    }
}
printf("%d %d", count, sum);

16.5 猜数游戏 Ver.2

• 问题描述：本题为 12.4 的升级版。目标随机正整数（保证在 100 及以内）已经由专门的系统生成。现在给定这个随机正整数和最大猜测次数$N(N>3)$，要求判断用户输入是否符合目标数字，如果偏大，提示 “Too big”；如果偏小，提示 “Too small”；如果恰好，则根据猜测次数输出文案：1 次猜出该数，提示 “Bingo!”；如果 3 次以内（不含 1 次）猜到该数，则提示 “Lucky you!”；如果超过 3 次但不超过$N$ 次猜到该数，则提示 “Good Guess!”；如果超过$N$ 次都没有猜到，或者在猜测满$N$ 次前用户输入了负数，则提示 “Game Over”，并立即结束程序。

• 输入格式：第一行给出 2 个不超过 100 的正整数，分别是系统产生的随机数和猜测的最大次数$N$。随后每行给出一个用户的输入，直到出现负数为止。

• 输出格式：在每个用户输入的下一行输出猜测对应的结果，直到输出猜对的结果，或者 “Game Over”。

• 输入样例：

  1 2 3 4 5 6 7

  58 4 70 50 56 58 60 -2

• 输出样例（穿插在用户输入中）：

  1 2 3 4

  Too big Too small Too small Good Guess!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int goal, n, x, cnt = 0;
scanf("%d %d", &goal, &n);
do{
    cnt++;
    scanf("%d", &x);
    if (x < 0 || cnt > n){
        printf("Game Over\n");
        break;
    }
    if (x > goal){
        printf("Too big\n");
    }
    else if (x < goal){
        printf("Too small\n");
    }
    else{
        if (cnt == 1){
            printf("Bingo!\n");
        }
        else if (cnt > 1 && cnt <= 3){
            printf("Lucky you!\n");
        }
        else{
            printf("Good Guess!\n");
        }
        break;
    }
} while (x > 0);

16.6 求序列的前$N$ 项和

• 问题描述：给定正整数$N$，计算序列 $\frac{2}1,\frac{3}2,\frac{5}3,\frac{8}5,...$ 的前$N$ 项和。注意该序列从第二项开始，每一项的分子是前一项分子与分母的和，分母是前一项的分子。（当然你也可以按别的方式理解）

• 输出格式：输出精确到小数点后 2 位。本题保证结果不超过双精度 (double) 范围

计算方面：

我们只讲一些关键语法点。

• 如何实现 “每一项的分子是前一项分子与分母的和，分母是前一项的分子”？来写写看！

  1 2 3

  //令p为分子，q为分母，*p表示第n项，p表示第n-1项 *p = p + q *q = p

  我们发现，这两个操作都需要前一项的分子。但 *p = p + q 这一步会覆盖掉前一项的分子，于是我们需要中间量 t 帮我们存储前一项的分子。

• 如何控制小数点位？我们之前需要输出浮点数时，都是让计算机按默认位数输出，其实 printf 函数有控制小数点位的字符。如果要用 printf 来控制小数点位，需要这么写：“%.nlf”。其中 n 表示你希望保留的小数点位。这个输出是四舍五入的。

1
2
3
4
5
6
7
8
9
10
11

int n;
double sum = 2.0, p = 2.0, q = 1.0;
scanf("%d", &n);
for (int i = 1; i < n; i++){
    double t;
    t = p;
    p = p + q;
    q = t;
    sum += p / q;
}
printf("%.2lf", sum);

16.7 化简分式

• 问题描述：在计算器的线性输入模式中，分数表示为 “分子 / 分母” 的形式。现在给定一个分数，输出它的最简分式。例如，6/12 可以被化简成为 1/2. 当分子大于分母时，表示为假分数形式，如 11/8 仍表示为 11/8；当分子和分母相同时，表示为 1/1.

• 输入格式：在一行中给出一个分数，分子和分母中间以斜杠 “/” 分隔。分子和分母都是正整数。

  TIP: 请让 scanf 函数处理 “/”。

• 输出格式：输出最简分式，格式与输入时相同。

计算方面：

• 如果我们想一步到位把分数约分到最简，就需要求出分子与分母的最大公约数。这个问题的算法可见于 15.2.

1
2
3
4
5
6
7
8
9
10
11
12

int p, q, a, b, t;
scanf("%d/%d", &p, &q);
a = p;
b = q;
while (b != 0){
    t = a % b;
    a = b;
    b = t;
}
p /= a;
q /= a;
printf("%d/%d\n", p, q);

16.8 念数字

• 问题描述：输入一个整数，输出每个数字对应的拼音。当整数为负数时，先输出 “fu” 字。

  十个数字对应的拼音如下：

  数字	拼音
  0	ling
  1	yi
  2	er
  3	san
  4	si
  5	wu
  6	liu
  7	qi
  8	ba
  9	jiu

输入格式：输入在一行中给出一个整数

输出格式：在一行内输出这个整数对应的拼音，每个数字的拼音之间用空格分开，行末不需以空格结尾。

计算方面：

• 核心就是正序分离各位数字。参考 15.3 的解法。
• 对于负数，可以先判断输出 “fu”，然后去掉这个负号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

int x, n, mask = 1;
scanf("%d", &x);
if (x < 0){
    printf("fu ");
    x = -x;
}
n = x;
while (n > 9){
    mask *= 10;
    n /= 10;
}
do{
    int d = x / mask;
    switch (d){
           case 0:
            printf("ling");
            break;
           case 1:
            printf("yi");
            break;
           case 2:
            printf("er");
            break;
           case 3:
            printf("san");
            break;
           case 4:
            printf("si");
            break;
           case 5:
            printf("wu");
            break;
           case 6:
            printf("liu");
            break;
           case 7:
            printf("qi");
            break;
           case 8:
            printf("ba");
            break;
           default:
            printf("jiu");
            break;
    }
    if (mask > 9){
        printf(" ");
    }
    x %= mask;
    mask /= 10;
} while (mask > 0);
printf("\n");

16.9 求$a$ 的连续和

• 问题描述：输入两个整数 $a$ 和 $n$ ，$a∈[0,9]$，$n∈[1,8]$，求数列之和 $S=a+aa+aaa+...+aaa...a (n 个 a)$。例如，当 $a=2,n=8$ 时，应输出 $2+22+222+...+22222222$ 的和。

1
2
3
4
5
6
7
8
9

int a, n;
scanf("%d %d", &a, &n);
int sum = a;
int t = a;
for (int i = 1; i < n; i++){
    a = a * 10 + t;
    sum += a;
}
printf("%d\n", sum);

Lesson 17 数据类型综合

17.1 C 语言数据类型概述

C 语言是一个有类型的语言，它的变量必须在使用前定义，并确定类型。

现代编程语言在类型问题上分化出两种发展路径：

• C++/Java 等更强调类型，对类型的检查更加严格。
• JavaScript、Python、PHP 等不看重类型，甚至不需要事先定义变量。

这两种发展路径对应着学界对于类型安全的两种不同的观点，这两种观点不分对错：

• 支持强类型的观点认为明确的类型有助于尽早发现程序中的简单错误
• 支持弱类型的观点认为过于强调类型迫使程序员面对底层、实现而非逻辑

总的来说，早期语言或者面向底层的语言强调类型。

参见：什么是类型安全？- Adano1

类型转换和类型安全 | Microsoft Learn

C 语言有以下几种类型：

• 整数：char、short、int、long、long long
• 浮点数：float、double、long double
• 逻辑：bool
• 指针
• 自定义类型

不同的类型有不同的特点：

• 名称：int、long、double
• 格式化字符串：%d、%ld、%lf
• 取值范围：char < short < int < float < double
• 所需内存大小：从 1 个字节到 16 个字节
• 存储形式：二进制数（补码）、编码

我们可以使用 sizeof() 运算符来查看某个类型或变量在内存中占据的字节数。注意 sizeof() 内对变量的其他运算结果不会被存储。

17.2 整数类型

• char：1 字节（8 比特）
• short：2 字节
• int：取决于 CPU 和编译器，通常的意义是 “1 个字长” 或者 4 字节
• long：取决于 CPU 和编译器，通常的意义是 “1 个字长” 或者 4 字节
• long long：8 字节

参考：字，字节，字长，位的概念与区分 - dengshuo7412

17.3 整数的内部表达

本节在《计算机导论（第四版）》中亦有记载！

计算机使用二进制表达数据。对于非负整数，计算机可以直接转为二进制数。那负数呢？

我们有三种方案：

• 1. 仿照十进制，有一个特殊的标志表示负数
• 2. 取中间值为 0，比它小的为负数，比它大的为正数
• 3. 补码

前两种方案都需要计算机定义一个新运算，比较麻烦。因此计算机使用补码来表示负数。

补码的工作原理是这样的：

• 假设该数据类型仅能存储 1 字节的二进制数，对于$11111111+00000001=100000000$，由于计算机内 1 字节 = 8 比特，所以计算机会截断结果$100000000$，变成$(1)00000000$，就是$0$ 了。
• 由于$0-1=-1$，所以$-1=(1)00000000-00000001=11111111$。$11111111$ 被当作纯二进制数看待时，是$255$；被当作补码看待时，是$-1$
• 同理，对于任意$-a$，即$0-a$，其补码表示为$2^n-a$，$n$ 是这种类型的存储位数。

补码的意义就是拿补码和原码可以加出一个溢出的 “0”

17.4 整数的范围

对于一个字节，可以表达的二进制数的范围是$00000000\sim11111111$. 其中：

• $00000000=0$
• $11111111\sim10000000:-1\sim-128$
• $00000001\sim 01111111:1\sim 127$

实际上，对于所有类型的整数，其范围都是$-2^{n-1}\sim 2^{n-1}-1$，其中$n$ 表示这种类型的存储位数

如果我们不需要负数，只需要尽量大的非负整数范围，我们可以将变量声明为 **unsigned(无符号)**。对于常量，还可以在具体数据后面加个 u 或 U。

要对常量声明 long 或 long long 时，也可以在具体数据后面加个 l 或 L。例如：12L 说明 12 这个常量是以 long long 类型存储的。

实际上 unsigned 的目的是为了向计算机说明这里只做纯二进制运算，只是呈现的效果就像扩展了整数表达范围。

现在我们搞懂了整数的范围。需要说明的是，如果存储的数据超过了这个范围，就会出现 ** 整数越界（或者整数溢出）** 现象。

灯神：我允许你在许愿前先说明你认为的最大许愿次数。但是不要贪心，如果你太贪婪，我有权立即停止许愿，那样你一个愿望都别想许！😈

小 L：我想许 -129 个愿望！

灯神：好的，你可以许下 127 个愿望！诶​​(⊙_⊙)？等等！是不是哪里出错了？！

0-1=-1 和 - 1+1=0，很正常，没什么好说的。但对于 127+1 和 - 128-1，我们的认知是 128 和 - 129，但计算机会存储为 - 128 和 127.

整数越界是一个危险的操作，它会导致一些数值敏感的操作输出意料之外的结果，或者直接无法运行。

参考：什么是整数溢出？溢出方式 (回绕，截断），表现，危害 - jopny

PWN 学习 - 整数溢出 - Amsterdamnit

17.5 整数的格式化

请确保整数类型和格式化字符串是一一对应的，否则会出现意想不到的结果。

有的时候，程序还要处理 8 进制或者 16 进制的数据（比如：调色盘）。使用以上格式输入输出，编译器会自动将其转换为 10 进制数，然后转为二进制数据。

如果需要输出 8 进制或者 16 进制数：

• 对于 8 进制（以 0 开始的数字字面量）：使用 %o。
• 对于 16 进制（以 0x 开始的数字字面量）：使用 %x 或者 %X

⚠️此时输出不含前缀 0 或者 0x。如果需要，请在输出时先输出前缀，如 printf("0x%x", var)

17.6 选择整数类型

日常使用直接 **all in int** 就行了，要处理字符时用 char，要处理比较大的数据时使用 long long。没有必要使用其他整数类型。C 语言区分这么多整数类型是出于底层硬件的需要。

17.7 浮点数类型

%e 表示科学记数法输出。输出的样例：

printf 中的 double 输出，有的人坚决反对使用 %lf，但也有人认为无伤大雅，也可以用。实际上在 C90 及之前的 C 语言标准中，明确不支持输出时写 %lf，未使用 GNU 扩展语法的编译器会将其定义为 “未定义行为” 而报警告 warning: ISO C90 does not support the "%lf" printf。但 C99 及之后的标准的态度有所缓和：遵循这些标准的编译器会忽略掉 %lf 的 l。正确写法仍是 %f，%lf 也依然是未定义的写法，只不过编译器帮你自动纠了错。

根据 printf, fprintf, sprintf, snprintf, printf_s, fprintf_s, sprintf_s, snprintf_s - cppreference.com，从 C99 开始，标准允许使用 %lf 表示 double 类型。

一个验证方式是，使用 VSCode+Clangd，开启 -Wformat-invalid-specifier，这样实时分析会报告 Invalid conversion specifier 警告。对于 %lf，实时分析没有警告。

具体的支持情况参见编译器手册。

如果你真的想要使用 lf，一个合法的方式是 %Lf，只不过它实际上对应输出的是 long double 而不是我们想要的 double，因此会发生隐式类型转换，参见 [17.11 类型转换](#17.11 类型转换)。

---

摘抄 LLVM 对 printf 格式字符串的一条规定：

Any conversion specification that contains a flag or option that it does not have defined behavior for will ignore that flag or option (e.g. %.5c is the same as %c).

——Printf Behavior Under All Conditions — The LLVM C Library

如果格式字符串中含有未定义行为的格式化标志，那么编译器将忽略这些标志，仅识别剩下的有定义的格式字符串。

---

对于 GCC ，可以参考以下文档：

Floating-Point Conversions (The GNU C Library)

Table of Output Conversions (The GNU C Library)

也可以参考这篇 2012 年的 issue:

52818 – printf format %lf is erroneously rejected by C++11

“C99, and thus C++11, allow %lf as a synonym (同义词，别名) for %f as a printf format specifier.”

17.8 浮点数的范围和精度

对于不在浮点数范围内的数据，printf 会输出两种不同的字符串：

• 对于超出范围的浮点数，输出 inf
• 对于不存在的浮点数，输出 nan

浮点数是有精度的。我们输入的看似精确的数据在计算机中会被存储为一个近似的值。

Unfortunately, most decimal fractions cannot be represented exactly as binary fractions. A consequence is that, in general, the decimal floating-point numbers you enter are only approximated by the binary floating-point numbers actually stored in the machine.

不幸的是，大多数的十进制小数都不能精确地表示为二进制小数。这导致在大多数情况下，你输入的十进制浮点数都只能近似地以二进制浮点数形式储存在计算机中。

——15. 浮点算术：争议和限制 — Python 3.12.7 文档

另可参见：C/CPP 中关于浮点数计算精度问题及解决办法 | SeaEpoch

如果我们想要比较两个浮点数的大小，不能直接比较。我们必须去适应计算机存储浮点数的方式，使用作差法，在可以接受的误差范围内认定它们的大小：

1

fabs(f1 - f2) < 1E-12//fabs()是绝对值函数，使用前需要include math.h

浮点数的存储特点决定了它难以用于对数值敏感的操作（如数据比较等），这时请使用整数或者 BCD 运算。不得不使用浮点数时，要留意对特殊情况进行特殊处理（比如 PTA 上的解一元二次方程问题，0.00 会输出为 -0.00）

BCD 运算可以参见：BCD or Binary Coded Decimal - GeeksforGeeks

那么浮点数在计算机内是怎么表达的？

浮点数在计算机内有专门的浮点运算器进行运算。而浮点数的二进制表达方式由 IEEE 负责制定标准。

以下是 IEEE 对浮点数表达的规定：

（来源：IEEE Standard 754 Floating Point Numbers - GeeksforGeeks）

你可以在 IEEE Standard 754-2019 for Floating Point Arithmetic 下载该标准的原始文件。

在实践中，如果没有特殊需求，应该使用 **double类型的浮点数。实际上，除非明确声明，否则编译器会将所有浮点数自动按 double 类型 ** 处理。

17.9 字符类型

char 是一种整数，也是一种特殊的类型：字符。

我们可以用‘’表示字符的字面量，在运算时直接使用字符本身作为算子。在 printf 和 scanf 中，我们需要用 %c 来输入输出字符。

前面我们说，char 也是一种整数。那如果我用 %d 来输出 char 类型的数据呢？

程序输出了整数！或者更准确地说，输出了该字符对应的 ASCII 码。

如果想要了解 ASCII 码，可参阅：ASCII - Wikipedia

ASCII Table (7-bit) - ASCII Code (ascii-code.com)

ASCII Table - ASCII Character Codes, HTML, Octal, Hex, Decimal

ASCII 码给了我们比较和计算字符的途径。例如，我们需要检查大写字母时，我们可以写：

1
2
3

c >= 'A' && c <= 'Z'
    或者
c >= 65 && c <= 90

这两者是等价的。

这里还有一个混合输入的问题：

• 对于 scanf("%d %c", &a, &c);，前面的整数会将其后的空格（如有）一起读入，而将最后一位输入的字符传入字符变量 c 中。

  1 2 3 4 5 6 7 8 9 10

  scanf("%d %c", &a, &c); //Terminal >>12 1 >>a = 12, c = 49, c = '1' --- >>12a >>a = 12, c = 97, c = 'a' --- >>12 1 >>a = 12, c = 49, c = '1'

• 对于 scanf("%d%c", &a, &c);，前面的整数不会读入空格，整数输入结束后的第一个字符会被传入字符变量 c 中。

  1 2 3 4 5 6 7 8

  scanf("%d %c", %a, &c); //Terminal >>12 1 >>a = 12, c = 32, c = ' ' >>12a >>a = 12, c = 97, c = 'a' >>12 1 >>a = 12, c = 32, c = ' '

对于字符运算，我们有以下规律：

• 一个字符加一个数字得到 ASCII 码表中整数结果对应的字符
• 两个字符的减，得到它们在表中的距离

根据以上规定，我们可以进行字母的大小写转换。

• 问题描述：给定任意英文字母，请输出该字母对应的大小写字母。

计算方面：

• 字母在 ASCII 表中是顺序排列的，不过大写字母和小写字母在表中是分开排列的，并不在一起。
• ‘a’-‘A’可以得到大写字母和小写字母之间的距离。由 ASCII 表可知这个距离是 32.
• 大写字母加上这个距离可以变成小写字母；小写字母减去这个距离可以变成大写字母。

1
2
3
4
5
6
7
8
9

int c;
scanf("%c", &c);
if (c < 91){//判断为大写字母
    c = c + 'a' - 'A';
}
else{
    c = c + 'A' - 'a';
}
printf("%c", c);

如果我们需要读入字符串呢？字符串，本质就是数个字符的集合。在计算机中，字符串的读入其实是字符的循环读入，学了数组之后，你就可以自己来实现字符串的读入。

• 问题描述：输入一行字符，请分别统计出其中英文字母、空格、数字和其他字符的个数。

• 输入格式：输入仅包含一行字符串，包含空格。字符串长度小于 100。

• 输出格式：输出包括 4 个数字，分别表示英文字母、空格、数字和其他字符的个数，以空格隔开。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

  #include <stdio.h> int main(void) { char c; int alpha = 0, number = 0, space = 0, others = 0; scanf("%c", &c); while (c != '\n') { if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')) { alpha++; } else if (c == ' ') { space++; } else if (c >= '0' && c <= '9') { number++; } else { others++; } scanf("%c", &c); } printf("%d %d %d %d", alpha, space, number, others); }

17.10 逃逸字符

** 逃逸字符（也叫转义字符）** 用来表示无法印出来的控制字符或者需要输出的特殊字符。它由一个反斜杠 “\” 开头，后面跟上另一个字符，这两个字符组合起来形成一个字符。

以下是一些常用的的逃逸字符：

（来源：Escape Sequence in C - GeeksforGeeks）

如果你想在输出中显示一个百分号，你需要使用 %% 来表示。

如果你不知道制表符是干什么的，可以参考这篇文章：What is a Tab Character?

17.11 类型转换

当运算符的两边出现不一致的数据类型，编译器会自动转换为范围较大的数据类型。这个过程是隐式的 (Implicit)。

大致的转换顺序如图，从高到低

（来源：Type Conversion in C - GeeksforGeeks）

对于 printf，所有范围小于 int 类型的值都会被转换成 int 类型；float 类型会被转换成 double。

scanf 不能自动转换类型。如果你要输入 short 类型变量，就要格式化为 %hd；要输入 long long 类型，就要格式化为 ld；要输入 double，就需要格式化为 %lf。

另请参考：常用算术转换 | Microsoft Learn

赋值转换 | Microsoft Learn

Implicit conversions - cppreference.com

但我们也可以强制转换类型，这个过程需要写出，因此是显式的 (Explicit)。格式为：(<类型>)值。

一般来说，强制转换是由范围较大的类型转换为范围较小的类型：

（来源：Type Conversion in C - GeeksforGeeks）

在这个过程中，需要注意转换的安全性，尽量保证数据可以使用转换后的类型存储。因为从较大的类型转换成较小的类型，可能会出现 ** 数据丢失 (Data Loss)** 的情况：

（来源：C Type Conversion (With Examples) (programiz.com)）

强制类型转换的优先级比四则运算符的高。

显式的类型转换比隐式的类型转换要可控的多，因为编译器可以很明确地知道程序员需要以什么方式存储数据，而不是它自己在那边猜。因此有人认为就算是赋值语句，它的完整写法也应该是：

1

x = (int) 10;

另可参考：C 强制类型转换 | 菜鸟教程 (runoob.com)

类型强制转换的转换 | Microsoft Learn

Explicit Type Conversion (GNU C Language Manual)

Lesson18 函数

18.1 初见 (?) 函数

14.1 中我们说：“我们可以把 13.1 的程序抽象成一个判断素数的函数 Prime。” 但实际上，它的实现还是完全写在 main 里的。现在我们要把这段代码分离出来，写成我们可以调用的函数 (Function)。

1
2
3
4
5
6
7
8
9
10

int Prime(int i){
    int isPrime = 1;
    for (int p = 2; p < i; p++){
        if (i % p == 0){
            isPrime = 0;
            break;
        }
    }
    return isPrime;
}

那么 14.1 的代码就可以被改造成这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int Prime(int i){
    int isPrime = 1;
    for (int p = 2; p < i; p++){
        if (i % p == 0){
            isPrime = 0;
            break;
        }
    }
    return isPrime;
}

// ...

for (int i = 2; i < 100; i++){
    if ( Prime(i) ){
        printf("%d ", i);
    }
    else{
        continue;
    }
}

函数可以被重复调用，延缓 Ctrl 键、C 键、V 键的磨损减少代码重复。例如：

• 问题描述：请输出 1 到 10、20 到 30 以及 35 到 45 的三个和

请比较两个方案：

• 方案 1

1
2
3
4
5
6
7
8
9
10
11
12
13

int i, sum;
for (int i = 1, sum = 0; i <= 10; i++){
    sum += i;
}
printf("%d\n", sum); // Ctrl+C
for (int i = 20, sum = 0; i <= 30; i++){
    sum += i;
}
printf("%d\n", sum); // Ctrl+V
for (int i = 35, sum = 0; i <= 45; i++){
    sum += i;
}
printf("%d\n", sum); // Ctrl+V

• 方案 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int sum(int begin, int end){
    int sum = 0;
    for (int i = begin; i <= end; i++){
        sum += i;
    }
    printf("%d\n", sum);
}
return sum;

int main(void){
    sum(1, 10);
    sum(20, 30);
    sum(35, 45);
    return 0;
}

参见：代码重构：代码重复 - 云社区 - 华为云

Duplicate code - Wikipedia

Duplicate Code (refactoring.guru)

c++ - Any valid reason for code duplication? - Stack Overflow

在上面的例子中，方案 1 称为 “内联”(inline)，方案 2 称为 “函数”。

“内联” 指功能代码直接插入主函数，不做分离。对于不需要重复调用的功能，直接在主函数里插入代码的运行效率多半会高一点。

有一种建议是：如果一块具有一定功能的代码在主函数中复用了 3 次，就需要考虑将这块代码分离出来称为一个独立函数。

为什么我要为小节标题的 “初见” 打上 “?” ？其实 C 语言就是一个函数化的语言。事实上，C 语言本身其实只能做很有限的事，大部分操作都由库函数（或者叫内置函数）实现。也就是说，我们已经在利用函数了。这些函数的定义放在头文件中，用户可以开箱即用。头文件就是我们在程序开头#include 的文件。

18.2 函数的定义和调用

Q：动漫里的人物放大招前为什么要先喊出大招的名字呢？

A：因为函数要先声明再调用啊！

函数是一块代码，接受 0 个、1 个或多个参数，做一件事情，并返回 0 个、1 个或多个值。函数实际上就是一种算法。

关于函数的其他定义：

A function in C is a set of statements that when called perform some specific task. It is the basic building block of a C program that provides modularity (模块化) and code reusability. The programming statements of a function are enclosed (围上) within { } braces, having certain meanings and performing certain operations.

——C Functions - GeeksforGeeks

A function is a C language construct that associates a compound statement (the function body) with an identifier (the function name). Every C program begins execution from the main function, which either terminates (终止), or invokes (调用) other, user-defined or library functions.

——Functions - cppreference.com

在 C 语言中使用用户定义函数分三步：

• 1. 函数声明

  声明一个函数一般需要函数名、返回类型和参数名称及其类型：

  

  （来源：C Functions - GeeksforGeeks）

  1	return_type name_of_the_function (parameter_1, parameter_2);

  在 C 语言中，声明函数时并不一定需要提供参数名。你可以仅仅声明参数的类型而不提供名称。但在函数定义时，还是需要提供参数名称来使用这些参数。我们仍建议提供参数名以提高可读性和可维护性。(由 Fitten Code 生成)

  如果函数没有返回值，return_type可使用 void 类型。

  C 语言中的函数在调用之前必须始终全局声明。你需要在程序的某个地方（通常是文件的顶部，因为编译器自上而下顺序分析你的代码）声明该函数的原型，以便编译器知道它的存在。这样做可以确保在函数实际定义之前，调用它的代码段能够正确地识别和使用它。(由 Kimi 生成)

• 2. 函数定义

  函数定义由实际的语句组成，这些语句在被调用时执行。函数定义总是以函数声明开头，因此很多人将函数定义和函数声明一并完成：

  

  （来源：C Functions - GeeksforGeeks）

  1 2 3 4

  return_type function_name (para1_type para1_name, para2_type para2_name) { // body of the function } //不需要结尾的';'

  也有人将声明放在开头，而定义放在末尾，比如 Harvard CS50 的讲师 David J. Malan。这样写是为了代码美观（不会头重脚轻）和应对较长的函数定义。

• 3. 函数调用

  定义完参数后，我们就可以像使用 scanf、printf 那样使用我们定义的函数了。函数的调用以 () 为标志，就算函数没有参数，也许要写这个 ()。原因在指针那一节 (Week5 Lesson20) 来讲。

  如果有参数，需要按你声明、定义的参数输入格式来输入，给出正确的数据和顺序。你输入的数据会被用于函数内参数的初始化。

  函数的工作流程如下图所示：

  

  （来源：C Functions - GeeksforGeeks）

18.3 从函数中返回

我们用 return 语句表示停止执行函数，并返回一个值。一个函数里可以出现几个 return。但一般情况下，当函数停止执行时，应当只有一个返回值。

这是结构化编程的单一出口 (Single Exit) 原则的体现。该原则的定义是：每个函数应该只有一个明确的路径来终止执行并返回结果。

采用单一出口原则的好处是易维护性，并保证垃圾资源得到清理。

单一出口原则诞生于 20 世纪 70 年代左右，到今天已经被视为是一个不再适合当代编程语言的设计模式，招致一些猛烈批评；但在一些具体问题上，也有其拥护者。

可参见：单一出口原则 - Peter87；

Where did the notion of “one return only” come from? - Stack Exchange

也有让函数同时返回多个值的方法，但现在我们的知识还没法解决。

函数的返回值可以赋值给变量，可以传递给其他函数，甚至可以直接丢弃。

如果函数没有返回值，我们可以在声明时将返回类型定义为 **void**。这个关键字指定函数不返回值。此时不能使用带返回值的 return 语句，可以只写 return; 或者不写；也不能为变量赋值，因为函数要给变量赋值，必须使用带返回值的 return。

Functions in C is a highly useful feature of C with many advantages as mentioned below:

1. The function can reduce the repetition of the same statements in the program.
2. The function makes code readable by providing modularity (模块化) to our program.
3. There is no fixed number of calling functions it can be called as many times as you want.
4. The function reduces the size of the program.
5. Once the function is declared you can just use it without thinking about the internal working of the function.

——C Functions - GeeksforGeeks

18.4 函数原型

函数原型 (Function Prototype) 与函数定义具有相同的形式，只不过前者由紧跟在右括号后的分号结尾，因此没有函数体。若要作为原型，函数声明还必须为函数的参数确定类型和名称。编辑器会按原型中声明的参数类型自动转换传入的数据类型，例如，函数参数声明为 double，用户输入 int 类型数据，则程序自动将 int 转换成 double。

其实和函数声明是一个东西…… 但别人用 “原型” 这个词的时候，你要知道它的意思。

参考：函数原型 | Microsoft Learn

18.5 参数传递

如果函数有参数，调用函数时必须传递给它数值、类型正确的值。这个值可以是表达式的结果，包括字面量、变量、函数的返回值、计算的结果。

如 18.4 所说，如果传递的值与原型声明的参数类型不一致，编译器会自动转换成原型声明的类型。但这种转换并不始终尽如人意，因为这是隐式的，我们很难控制。

我们在自定义函数里没有写任何的读取语句。那么函数的参数是怎么传递进函数里的？

• 问题描述：请你改造 6.3 的程序，使交换变量的部分独立成一个函数。

  1 2 3 4 5 6 7 8 9 10 11 12

  void swap(int a, int b){ int t = a; a = b; b = t; } int main(void){ int a = 5; int b = 6; swap(a, b); printf("a = %d, b = %d\n", a, b); return 0; }

发现错误了没有？我们的函数根本不起作用！这是为什么？

为了方便接下来的描述，我们有如下定义：

• 假设我们在函数 A() 中调用了函数 B()，我们称函数 A() 为 “调用方函数”，函数 B() 为 “被调用函数”

• 在函数 A() 中调用函数 B() 时，向函数 B() 传入的的参数为实际参数（实参）；函数 B() 的参数为形式参数（形参）

  作为一名小镇做题家，我的类比是这样的：实参相当于你考试时在答题卡上写的数值，形参相当于你在草稿纸上写的数值。

• 将信息从调用方传递到被调用方的方式称为 “IN-Mode”。这个过程是单向的。

• 每个函数有自己的函数空间，拥有单独的存储位置。参数处于这个独立的空间中，和其他函数没有任何关系。

在函数 swap 中，我们输入的是具有具体值的变量，因此 C 语言会使用按值传递 (Pass by value, OR Call by value) 方式将参数传递给函数。

（来源：Parameter Passing Techniques in C - GeeksforGeeks）

如图所示，在主函数中调用 geek_func() 时，会复制一份实参，将副本拷贝到函数的变量空间中，作为 geek_func() 的形参。函数内部的任何操作都在形参上进行，对形参所作的任何修改都不会传回调用方，更不会影响实参。

18.6 本地变量

函数的每次运行，都会产生一个独立的变量空间，在这个空间中的变量，是函数的这次运行所独有的，称作本地变量 (Local Variable)。因此，定义在函数内部的变量就是本地变量，函数的参数也是本地变量。

由 18.5 可知，自定义函数内的变量用完一次就再也不见。因此这个变量有它的生存期 (duration) 和作用域 (scope)。生存期指变量从出现到消亡的时间，作用域指变量可以被访问的代码范围。

对于本地变量而言，它的生存期和作用域都局限在 {} 里的代码块，因此也叫局部变量。

本地变量有以下的规则：

• 本地变量是定义在代码块里的。它可以定义在函数的块里、语句的块里，甚至单纯的一对大括号里。
• 程序进入代码块前，块内定义的本地变量不存在；离开代码块后，块内的本地变量自动消亡。
• 块外定义的变量可以在块内使用。
• 块内外有同名变量的，块内变量会覆盖块外变量【即本地变量优先，这被称为变量遮蔽 (Variable Shadowing)】；块内不能有同名变量。
• 本地变量不会被默认初始化为 0，但参数在进入函数时会被初始化为实参。

在 C 语言中，一般的局部变量也叫自动变量 (Automatic Variable)，使用 auto 关键字标示。但由于编译器会隐式地为 int a = 10 加上 auto（即所有局部变量默认为 auto），所以基本没有 C 程序员使用 auto。在 C++11 标准中，auto 关键字的作用已经改变。为了避免混淆，请忽略 C 中的 auto。

许多其他特性，除了类型系统外，都是为了 C 编译器编写者的便利而放入 C 语言中的。对于其他（C 语言）程序员来说，auto 是没用的，因为这是默认提供的。

——Expert C Programming - by Peter van der Linden - 1994.

auto 在 C 语言中是隐含的。由于实际代码中很少用到（甚至没看到过），它的显式用法的含义已经在 C++11 和 C23 中发生变换。

——variable auto in C - Stack Overflow

另可参考 c++ - Is there any reason to use the ‘auto’ keyword in C++03? - Stack Overflow

18.7 全局变量

与本地变量相反，全局变量 (Global Variable) 定义在所有函数（包括 main）之外。按照惯例，全局变量在文件顶部声明，位于 include 语句之后。

全局变量具有全局作用域（有时非正式地称为文件作用域），这意味着它们的生存期很长，从声明位置开始，一直到声明它们的文件结束。一旦声明，全局变量就可以在文件内声明位置之后的任何地方使用。

全局变量有以下规则：

• 全局变量在程序开始时创建（在 main() 开始执行之前），在结束时销毁。这被称为静态生存期 (Static Duration)。具有静态生存期的变量有时被称为静态变量 (Static Variables)。

• 全局变量默认初始化为 0，但声明为常量的全局变量必须由用户初始化。

• 全局变量仍会被同名的本地变量覆盖。

  为了避免变量遮蔽，我们可以为全局变量名加上 g_ (global) 前缀。这也有助于我们将全局变量和其他变量区分开，并意识到变量的作用域。

  ——7.4 — Introduction to global variables – Learn C++ & 7.5 — Variable shadowing (name hiding) – Learn C++ (have been edited)

早期全局变量的滥用现象十分普遍，以至于之后对它的批评进化到有程序员认为：“全局变量建议全部杀光！”

18.8 一些细节问题

• Q: 函数没有参数时，留空还是用 void？

  A:void 明确告知编译器不接受任何参数，留空则告诉编译器所需参数不定。如果参数留空而后续又输入参数，程序也会将参数传入函数。注意此时如果数据类型不匹配，编译器不会自动转换类型。

  因此我们建议，不要留空！要参数就写上参数，不要参数就写 void。

  对于 main 函数，我们在 3.2 就有给出参考文章，你可以返回去看一看。

• Q: 函数可以以表达式的结果作为参数，而我们在 9.4 学过逗号运算，那函数怎么知道逗号是不是运算符？

  A: 函数直接将参数中的逗号视为分隔符号，没有运算作用。

  如果需要使用逗号运算，请套一个 ()。

• Q: 函数里可以定义函数吗？

  A:C 语言不允许函数嵌套定义。编译器会告诉你：function definition is not allowed here.。

  GCC 允许嵌套声明函数，但这是编译器扩展语法，可能会遇到兼容性问题。

  关于嵌套函数

  参考 Nested functions in C - GeeksforGeeks。

  Nested function (嵌套函数) is not supported by C because we cannot define a function within another function in C. We can declare a function inside a function, but it’s not a nested function.

  An extension of the GNU C Compiler allows the declarations of nested functions. The declarations of nested functions under GCC’s extension need to be prefix (前缀)/start with the auto keyword.

  如果你硬要使用嵌套定义，这里提供 GCC 的文档：Nested Functions (Using the GNU Compiler Collection (GCC))

  根据 Nested functions in Clang? - LLVM Discussion Forums，Clang 不支持函数嵌套定义。

  这里给出一些讨论：疑惑：C 语言不允许函数嵌套定义，main 函数里面可以么？-CSDN 社区；

  C 语言函数嵌套定义问题_int 和 void 嵌套函数 - CSDN 博客；

  可以在函数内声明函数吗？-CSDN 社区；

  Functions inside functions in C - Stack Overflow

  我们可以嵌套调用函数，这件事还是正常的。

Lesson19 数组

19.1 认识数组

• 问题描述：本题为 12.3 的升级版。请你写一个程序，让用户输入一系列的正整数，最后输入 - 1 表示输入结束。程序计算出这些数字的平均数，然后输出所有大于平均数的数。

计算方面：

• 前半部分可以照搬 12.3，但后半部分就有难度了。原数据丢不了，又不能一个一个输出去，必须存在手里。然而我们目前没有暂存输入数据的适应性方法。我们当然可以定义好几个变量，但是，要定义几个呢？定义少了放不下，定义多了又浪费。

鉴于此，C 语言提供了数组 (Array) 数据结构，可以在同一个变量名称下存储多个数据。数组中的数据称为元素 (Element)。

就像月饼套装，每一小包都装着不同的月饼，但几包月饼整成一盒，这一整盒月饼就有了新的名字。管它是什么口味，反正这一盒拿出来就叫福袋月饼。

Array types are characterized by their element type and by the number of elements in the array.

——ISO/IEC 9899:2024

使用数组，我们只需要抓住它的两个主要特点：元素的数据类型和元素个数。

接下来我们以实际案例来说明数组的用法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int x;
double sum = 0;
int count = 0;
int num[100];//定义数组
scanf("%d", &x);
while (x != -1){
    num[count] = x;//对数组中的元素赋值
    sum += x;
    count++;
    scanf("%d", &x);
}
for (int i = 0; i < count; i++){
    //遍历数组
    if (num[i] > sum / count){//使用数组元素
        printf("%d ", num[i]);
    }
    else{
        continue;
    }
}

这个程序还有 bug。我们将数组 num[] 的大小（可以存储的数据个数）定义为 100，那如果输入的数据个数超过了这个大小，会发生什么事？数组变大变高？直接丢掉超负荷的数据？会引来不可名状之物？还是无事发生？我们先卖个关子，后面会讲到。

19.2 数组的使用

数组是一种容器，数组内的所有元素具有相同的数据类型。数组一旦创建，大小和分配的内存空间确定，就不能再更改大小。

数组是一种线性数据结构，所有元素按顺序存储在连续的内存位置。

在使用数组前，我们需要先声明数组。语法如下：

1

data_type array_name [size];//一维数组

我们规定：

• size 必须为正整数。

  Zero-length array declarations are not allowed, even though some compilers offer them as extensions.

  ——Array declaration - cppreference.com

  C 语言标准不允许定义 0 长度数组，尽管一些编译器的扩展语法支持该特性。

• 从 C99 标准开始，允许使用变量作为 size。​⚠️这并不说明数组大小可以随意更改。​

下面来看一个数组声明的例子：

1

int a[10];

• 这是一个 int 类型的数组，数组的大小为 10.
• 数组的内部空间被划分为 10 个单元：a[0], a[1], a[2], ..., a[9]。每个单元就代表一个 int 类型的变量，[] 里的数字叫做下标（或索引，index）。下标从 0 开始计数。⚠️数组的大小不等于数组的最大有效下标。​
• 数组可以出现在赋值表达式的左边和右边。在左边的叫做左值，在右边的叫做右值。

编译器不会检查数组下标的有效性（或者说，不会强制要求下标的有效性），也就是说，实际的数组下标可能会超过声明的数组大小，产生数组越界。越界的数组访问可能会出现问题，导致程序崩溃，也有可能无事发生。但是，“君子不立于危墙之下”，确保数组下标的有效性是程序员的责任。有效的数组下标范围为：$[0, 数组大小 - 1]$

这就是 19.1 的例子中出现 bug 的原因。我们不能低估用户行为。为了通过用户输入情况来 “调整” 数组大小，C99 引入了 VLA (Variable Length Array，变长数组)。变长数组允许在编译后、程序运行时再为数组设定大小和分配内存。这并不是说我们可以随时改变数组大小，而是说在程序获取到用于表示数组的变量的值前，数组大小不定。一旦变量获取到值，数组大小也就确定下来。

但 VLA 不是强制性标准。查看 C compiler support - cppreference.com 会发现，仅 GCC 和 Clang 支持 VLA 特性，其他编译器并不支持 VLA。在不支持 VLA 的编译器上不要使用变长数组。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int x;
double sum = 0;
int cnt;
scanf("%d", &cnt);
if (cnt > 0){
    int num[cnt];
    int i = 0;
    scanf("%d", &x);
    while (x != -1){
        num[i] = x;
        sum += x;
        i++;
        scanf("%d", &x);
    }
}

参见：C 语言中的变长数组 - 笛若心生

根据 Array declaration - cppreference.com 的说法，VLA 属于 “可变修改类型”（Variably-modified Types）。任何可变修改类型的对象只能声明于块作用域或函数原型作用域中。

由 Constant expressions - cppreference.com 可知，用 const 修饰的全局变量作为长度的数组属于 VLA。

19.3 数组的例子 —— 统计个数

• 问题描述：输入数量不定的$[0,9]$ 范围内的整数，统计输入的每一种数字的个数，输入 -1 表示输入结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

int x, i;
int cnt[10];
//初始化数组
for (i = 0; i < 10; i++){
    cnt[i] = 0;
}
scanf("%d", &x);
while (x != -1){
    if (x >= 0 && x <= 9){
        cnt[x]++;//用数组下标代表数字种类
    }
    scanf("%d", &x);
}
for (i = 0; i < 10; i++){
    printf("%d:%d\n", i, cnt[i]);
}

通常而言，使用数组的程序会有这些环节：

决定数组大小 ➡️ 声明数组 ➡️ 初始化数组 ➡️ 数组参与运算 ➡️ ​遍历数组，输出

19.4 数组运算

• 问题描述：给出一个整数，在已有数组（数据自定，写死在程序中，保证无重复数字）中查询该数。如果查询到该数，返回其在数组中的位置；如果查询不到，返回 “不存在”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int search(int key, int a[], int length);

int main(void){
    int a[] = {1, 3, 32, 4, 6, 9, 0, 12};
    int x, loc;
    scanf("%d", &x);
    loc = search(x, a, sizeof(a)/sizeof(a[0]));
    if (loc != -1){
        printf("%d在第%d个位置上\n", x, loc);
    }
    else{
        printf("%d不存在", x);
    }
}

int search(int key, int a[], int length){
    int ret = -1;
    int i;
    for (i = 0; i < length; i++){
        if (a[i] == key){
            ret = i;
            break;
        }
    }
    return ret;
}

这里有好几个疑惑点，展开讲讲：

• 我们在第 4 行对数组进行了集成初始化。如果用户没有为数组指定大小，编译器会自动为数组分配与初始化数据的个数相符的大小；如果用户有为数组指定大小，而初始化数据的个数不够时，编译器自动补零。

  对于初始化数据，编译器自动从下标 0 开始、从小到大排列。从 C99 开始，支持初始化数据的定位。用户在初始化时，用 [n] 给出想要初始化的位置，没有定位的数据接在前一个数据后面。

  1 2 3

  int a[10] = {[0] = 2, [2] = 3, 6}; >>2, 0, 3, 6, 0, 0, 0, 0, 0, 0

  该方法适合初始数据比较稀疏的情况。

• 第 7 行我们用 sizeof(a)/sizeof(a[0]) 来表示数组大小。sizeof() 用于计算任何数据类型所占用的字节大小。由于同一个数据类型所占用的字节数相同，因此$\frac {数组总占用}{单个数据的占用}= 数据量$。

  参考：C 语言基础 ——sizeof 的用法总结 - CSDN 博客；

  sizeof operator in C - GeeksforGeeks

• 在 search 函数中，我们使用 for 循环遍历数组，让循环变量 i 从 0 递增到 < 数组的长度。这样循环体内的 i 正好是数组的最大有效下标。

  Warning

  这里有两个常见错误：

  • 将循环结束条件定义为 ≤ 数组长度
  • 离开循环后，继续用 i 的值来做数组元素的下标

  以上错误均会导致数组越界。

• 第 7 行我们为什么只用传入 a 这个数组名？换句话说，为什么不能把整个数组传入函数？后一个问题可以用 18.5 的知识来回答：再复制一份太费空间了。而前一个问题其实是后面指针的内容。如果你等不及了，可以参见：看完这篇文章一定弄懂 C 语言数组作为函数参数的用法_c 语言数组在函数参数中的表示 - CSDN 博客。

19.5 优化素数问题

我们 13.1 不是已经解决素数问题了吗？怎么还来！

我们之前采用的方案是遍历所有可能可以整除的数。如果要判断的数（假定为$n$）很大，那么我们就需要循环判断$n-1$ 次，逼近$n$ 次。这样的程序效率是比较低的。我们能不能减少循环判断次数呢？

一个方案是排除那些一眼就能确认不是素数的输入。我们知道，“在素数范畴里 2 是唯一的一个偶素数，其余素数都是奇数”。因此我们可以先把除了 2 之外的所有偶数判断为非素数，这样只有奇数进入循环判断。接下来从 3 开始，遍历所有奇数作为除数。偶数的判断次数为 1，奇数的判断次数为$\frac{n+3}{2}-1$，逼近$\frac{n}2$次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int isPrime(int x){
    int ret = 1;
    if (x <= 1 || (x % 2 == 0 && x != 2))
    {
        ret = 0;
    }
    else
    {
    	for (int i = 3; i < x; i += 2){
        	if (x % i == 0){
            	ret = 0;
        	}
    	}
    }

    return ret;
}

后面又有数学家证明：不需要遍历到$n-1$，** 只需要遍历到$\sqrt{n}$** 就行了。优化后的算法可以接受的数据大小至多为$10^{18}$，如果要判断$> 10^{18}$ 的数据，需要更换其他算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

// Function to check whether a number is prime or not
bool isPrime(int n) {
    // Numbers less than or equal to 1 are not prime
    if (n <= 1){
        return false;
    }

    // Check divisibility from 2 to the square root of n
    for (int i = 2; i <= sqrt(n); i++){
        if (n % i == 0){
            return false;
        }
    }

    // If no divisors were found, n is prime
    return true;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d", isPrime(n));
    return 0;
}

该方法称为试除法（Trial Division），也用于直接搜索质因数（Direct Search Factorization）。

我们还可以将除数的范围缩小到素数，即只遍历已知的小于$n$ 的素数作为除数。这是因为除了数字 1 之外，每个正整数$a$ 都可以唯一地表示为至少一个质数的乘积，且这种表示方式不涉及质数的重新排列（Fundamental Theorem of Arithmetic – from Wolfram MathWorld）

这种方法适合用于编制素数表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

int main(void){
    const int number = 100;
    int prime[number] = {2};//提供已有素数表
    int count = 1;
    int i = 3;
    while (count < number){
        if (isPrime(i, prime, count)){
            prime[count++] = i;
            /*
            prime[count] = i;
            count++;
            */
        }
        i++;
    }
    for (i = 0; i < number; i++){
        printf("%d", prime[i]);
        if ((i + 1) % 5)
            printf("\t");//同一行内两数之间的排列
        else
            printf("\n");//每5个数为一行
    }
    return 0;
}

int isPrime(int x, int KnownPrimes[], int LocationOfKnownPrimes){
    int ret = 1;
    int i;
    for (i = 0; i < LocationOfKnownPrimes; i++){
        if (x % KnownPrimes[i] == 0){
            ret = 0;
            break;
        }
    }
    return ret;
}

我们还可以这样构造素数表：

• 欲构造$n$ 以内（包含$n$）的素数表
  1. 令$x$ 为 2
  2. 将$2x$、$3x$、$4x$ 直至$ax<n$ 的数标记为非素数
  3. 令$x$ 为下一个没有被标记为非素数的数，重复步骤 2；直到所有的数都已经尝试完毕
• 欲构造$n$ 以内（不含$n$）的素数表
  1. 开辟 prime[n]，初始化其所有元素为 1，prime[x] 为 1 表示 x 是素数
  2. 令 x 为 2
  3. 如果 x 是素数，则对于 (i = 2; x * i < n; i++)，令 prime[i * x] = 0
  4. 令 x++，如果 x < n，重复步骤 3，否则结束

这被称为埃拉托斯特尼筛法（Sieve of Eratosthenes）。

19.6 二维数组

前面我们讲的都是一维数组，点动成线。现在我们讲二维数组，线动成面。也有更高维的数组，现在还用不到，需要的话参考下面引用的一篇文章。

常用的多维数组就是二维数组和三维数组。更高维的数组会变得非常复杂，并且耗费更大的空间。

——C Arrays - GeeksforGeeks

声明二维数组：data_type array_name[size1][size2];。其中 size1 通常认为是该数组的行，size2 通常认为是该数组的列，这考虑了二维数组的实际存储方式。例如，下图示意数组 a[3][5]：

对于二维数组的初始化，我们有以下方式：

• 使用大括号分隔每行。要求每行一个 {}，} 后加一个 ,。最后一行的 , 可以保留。

  1 2 3 4

  int a[2][5] = { {0,1,2,3,4}, {2,3,4,5,6}, };

  也可以空出行数，让编译器来数（但列数必须由用户给出）

  1 2 3 4

  int a[][5] = { {0,1,2,3,4}, {2,3,4,5,6}, };

  如果有未初始化的元素，编译器自动补零。

• 不使用大括号分隔每行。元素将从左到右、从上到下存储在数组中。

  1	int arr[3][4] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

注意：初始化的元素数应始终小于或等于声明的数组中的元素总数。

我们还需要解决二维数组的遍历。一维数组只有一个下标，因此我们只用一个循环就可以遍历；但二维数组有两个下标，因此我们需要两个嵌套的循环来遍历数组。一个循环从上到下遍历每一行，另一个嵌套在其中的循环从左到右访问当前行中的每个元素。

对于二维数组中的元素，我们用 a[i][j] 来表示。注意，a[i, j] 中的逗号被认为是逗号运算。

• 问题描述：小 L 和小 H 在一节没有老师看守的自习课上拿出了方格作业纸，来了几把井字棋。现在请你写一个程序，每次读入一个 3×3 的矩阵，矩阵中的数字 1 表示该位置上有一个 X，数字 0 表示该位置上有一个 O。程序判断这个矩阵中是否有获胜的一方，输出代表获胜一方的字符 X 或 O，或者两人平局。
• 井字棋规则：两个玩家，一个打圈（◯），一个打叉（✗），轮流在 3 乘 3 的格上打自己的符号，最先将 3 个符号以横、直、斜连成一线则为胜。如果双方都下得正确无误，棋盘将会被填满而和局。（来源：井字棋 - 维基百科）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

const int size = 3;
int board[size][size];
int i, j;
int NumOfX, NumOfO;
int result = -1;//-1:平局 1:X胜 0:O胜
//读入矩阵
for (i = 0; i < size; i++){
    for (j = 0; j < size; j++){
        scanf("%d", &board[i][j]);
    }
}
//按行检查
for (i = 0; i < size && result == -1; i++){
    NumOfO = NumOfX = 0;
    for (j = 0; j < size; j++){
        if (board[i][j] == 1){
            NumOfX++;
        }
        else{
            NumOfO++;
        }
    }
    if (NumOfO == size){
        result = 0;
    }
    else if (NumOfX == size){
        result = 1;
    }
}
//按列检查
if (result == -1){
    for (j = 0; j < size && result == -1; j++){
        NumOfO = NumOfX = 0;
        for (i = 0; i < size; i++){
            if (board[i][j] == 1){
                NumOfX++;
            }
            else{
                NumOfO++;
            }
        }
        if (NumOfO == size){
            result = 0;
        }
        else if (NumOfX == size){
            result = 1;
        }
    }
}
//按正对角线检查
if (result == -1){
    NumOfO = NumOfX = 0;
    for (i = 0; i < size; i++){
        if (board[i][i] == 1){
            NumOfX++;
        }
        else{
            NumOfO++;
        }
    }
    if (NumOfO == size){
        result = 0;
    }
    else if (NumOfX == size){
        result = 1;
    }
}
//按反对角线检查
if (result == -1){
    NumOfO = NumOfX = 0;
    for (i = 0; i < size; i++){
        if (board[i][size - i - 1] == 1){
            NumOfX++;
        }
        else{
            NumOfO++;
        }
    }
    if (NumOfO == size){
        result = 0;
    }
    else if (NumOfX == size){
        result = 1;
    }
}
//输出结果
if (result == 1){
    printf("X\n");
}
else if (result == 0){
    printf("O\n");
}
else{
    printf("Tie\n");
}

其中，行和列的检查可以在一个两重循环中完成。形象点说就是把矩阵 “转” 个 90°，让列变成行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

for (i = 0; i < size && result == -1; i++){
    NumOfO = NumOfX = 0;
    for (j = 0; j < size; j++){
        if (board[i][j] == 1){
            NumOfX++;
        }
        else{
            NumOfO++;
        }
        if (board[j][i] == 1){ // Notice this!
            NumOfX++;
        }
        else{
            NumOfO++;
        }
    }
    if (NumOfO == size){
        result = 0;
    }
    else if (NumOfX == size){
        result = 1;
    }
}

19.7 排序算法

第 11 章 排序 - Hello 算法

19.7.0 排序算法简介

** 排序算法（sorting algorithm）** 用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有序数据通常能够被更高效地查找、分析和处理。

排序算法中的数据类型可以是整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定，如数字大小、字符 ASCII 码顺序或自定义规则，如下图所示：

B 站上有一些排序算法可视化的视频，可以去看看：

计算机专业不得不看的 15 种排序算法，7 分钟动画演示 - 哔哩哔哩 - bilibili

256 种排序算法，全网最全的排序算法 - 哔哩哔哩 - bilibili

本节开头提供的算法教程也有可视化。

基于谭书，我们只在这里介绍选择排序和冒泡排序。如要了解其他排序方法，可以参考给出的参考链接。

19.7.1 选择排序

选择排序（selection sort）的工作原理非常简单：开启一个循环，每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾。

• 算法流程

​ 设数组的长度为 $n$ ，则：

1. 初始状态下，所有元素未排序，即未排序（索引）区间为 $[0,n−1]$ 。
2. 选取区间 $[0,n−1]$ 中的最小元素，将其与索引 $0$ 处的元素交换。完成后，数组前 1 个元素已排序。
3. 选取区间 $[1,n−1]$ 中的最小元素，将其与索引 $1$ 处的元素交换。完成后，数组前 2 个元素已排序。
4. 以此类推。经过 $n−1$ 轮选择与交换后，数组前 $n−1$ 个元素已排序。
5. 仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。

• C 语言实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  /* 选择排序 */ void selectionSort(int nums[], int n) { // 外循环：未排序区间为 [i, n-1] for (int i = 0; i < n - 1; i++) { // 内循环：找到未排序区间内的最小元素 int min = i; for (int j = i + 1; j < n; j++) { if (nums[j] < nums[min]) min = j; // 记录最小元素的索引 } // 将该最小元素与未排序区间的首个元素交换 int temp = nums[i]; nums[i] = nums[min]; nums[min] = temp; } }

19.7.2 冒泡排序

冒泡排序（bubble sort）通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

• 算法流程

  设数组的长度为 $n$ ，则：

  1. 首先，对 n 个元素执行 “冒泡”，将数组的最大元素交换至正确位置。
  2. 接下来，对剩余 n−1 个元素执行 “冒泡”，将第二大元素交换至正确位置。
  3. 以此类推，经过 n−1 轮 “冒泡” 后，前 n−1 大的元素都被交换至正确位置。
  4. 仅剩的一个元素必定是最小元素，无须排序，因此数组排序完成。
  

• C 语言实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  /* 冒泡排序 */ void bubbleSort(int nums[], int size) { // 外循环：未排序区间为 [0, i] for (int i = size - 1; i > 0; i--) { // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端 for (int j = 0; j < i; j++) { if (nums[j] > nums[j + 1]) { int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } } }

• 优化实现

  我们发现，如果某轮 “冒泡” 中没有执行任何交换操作，说明数组已经完成排序，可直接返回结果。因此，可以增加一个标志位 flag 来监测这种情况，一旦出现就立即返回。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  /* 冒泡排序（标志优化）*/ void bubbleSortWithFlag(int nums[], int size) { // 外循环：未排序区间为 [0, i] for (int i = size - 1; i > 0; i--) { bool flag = false; // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端 for (int j = 0; j < i; j++) { if (nums[j] > nums[j + 1]) { int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; flag = true; } } if (!flag) break; } }