问题

设$a$、$b$的最大公因数为$m$，最小公倍数为$n$（$a,b,m,n \in N^+$），求证$ab = mn$。

证明

先证明$\frac{ab}{m}$是$a$、$b$的公倍数。

设$a = pm$（$p \in N^+$），$b = qm$（$q \in N^+$）。

可知$p$、$q$互质。因为如果$p$、$q$不互质，即$p$、$q$存在大于$1$的公因数，则$m$就不是$a$、$b$的最大公因数了。

$\frac{ab}{m} = \frac{pm \cdot qm}{m} = pqm$。$p$、$q$、$m$都是正整数，则$\frac{ab}{m}$也是正整数。

因为$\frac{ab}{m} = pm \cdot q = a \cdot q$，所以$\frac{ab}{m}$是$a$的倍数。

因为$\frac{ab}{m} = qm \cdot p = b \cdot p$，所以$\frac{ab}{m}$是$b$的倍数。

所以，$\frac{ab}{m}$是$a$、$b$的公倍数。

再证明$\frac{ab}{m}$是$a$、$b$的所有公倍数中最小的。

反证法。假设存在$x$也是$a$、$b$的公倍数，且$x<\frac{ab}{m}$。

设$x = ar$（$r \in N^+$），则有$x = pmr$。

因为$x < \frac{ab}{m}$，即$pmr < pmq$，所以$r<q$。

设$x = bs$（$s \in N^+$），则有$x = qms$。

因为$\frac{x}{m} = pr = qs$，所以$\frac{x}{m}$是$p$、$q$、$r$、$s$的倍数。

对于$\frac{x}{m} = pr$，它是$q$的倍数，$p$、$q$互质，有以下2种情况：

1. $q > 1$，则$p$不可能是$q$的倍数，那么$r$一定是$q$的倍数，则有$r \ge q$，这与$r<q$矛盾；
2. $q = 1$，则$p$是$q$的倍数，同时$r$也是$q$的倍数，同样有$r \ge q$，与$r < q$矛盾。

同理，有$s<p$和$s \ge p$的矛盾。

所以不存在比$\frac{ab}{m}$更小的公倍数，即$\frac{ab}{m}$就是最小公倍数，即$n = \frac{ab}{m}$。

即得$ab = mn$。

C99标准的C语言支持可变长度数组，可以用变量作为数组长度创建二维数组。那么，在C89标准的C语言中如何实现动态创建二维数组？

用一维数组代替二维数组

内存是线性（一维）的，不管数组是几维，最终在内存中都是线性存储的。二维数组的内存模型如图：

C语言通过计算与数组首地址的偏移字节数来定位到数组元素。例如在数组int array[M][N]中，访问元素array[i][j]时，计算地址的方式为：

1
2
3
4
5
6

单位字节数 = sizeof (int)
第二维每个元素的单位数 = 1
第一维每个元素的单位数 = 第二维每个元素的单位数 × 第二维的长度N
偏移单位数 = 第一维每个元素的单位数 × i + 第二维每个元素的单位数 × j
偏移字节数 = 单位字节数 × 偏移单位数
元素的地址 = 数组首地址 + 偏移字节数

由此想到，我们分配一维数组，然后自己计算偏移量（以sizeof (int)为单位），将二维数组下标转换为一维数组下标，就能正确访问到数组元素了。

1
2
3

int rows = 3, cols = 4;
int *array = malloc(sizeof (int) * rows * cols);
array[cols * i + j]; // 访问元素

缺点：不能用array[i][j]的语法访问数组元素，可读性较差。

规则的动态二维数组

1. 先动态分配一个指针数组（第一维数组）
2. 再为指针数组的每个指针分配元素数组（第二维数组）

1
2
3
4
5
6

int rows = 3, cols = 4;
int **array = malloc(sizeof (int *) * rows);
for (i = 0; i < rows; i++) {
    array[i] = malloc(sizeof (int) * cols);
}
array[i][j]; // 访问元素

内存模型如图：

可通过array[i][j]的语法访问数组元素，其本质是两级指针解引用，即等同于*(*(array + i) + j)。

用gcc -std=c89编译通过，运行结果正确。

Java语言的多维数组就是这种原理，即多级一维数组。

不规则的动态二维数组

如果分配第二维数组时，长度不固定，那么二维数组就不是规则的矩形，而是每行长度不同的不规则的形状。

1
2
3
4
5
6
7

int rows = 3;
int cols[] = {4, 2, 3};
int **array = malloc(sizeof (int *) * rows);
for (i = 0; i < rows; i++) {
    array[i] = malloc(sizeof (int) * cols[i]);
}
array[i][j]; // 访问元素

内存模型如图：

同样可以通过array[i][j]访问数组元素，只不过对于不同的i，j的合法范围不同。

这种模式可以用来存储三角矩阵。

需求

设在一个Spring Boot项目中，static目录的结构如下：

1
2
3
4
5

static/
|-- the_dir/
    |-- sub_dir/
    |-- file1
    |-- file2

现在想拿到the_dir目录中的文件列表（不含子目录），读取每个文件的内容，并计算每个文件相对于static目录的路径（即浏览器访问路径）。

获取文件列表

思路一：操作文件系统（不可行）

通过Spring的工具类ResourceUtils.getFile("classpath:static/the_dir")拿到the_dir目录的File对象，再通过theDir.listFiles()拿到文件列表，文件列表中可以通过file.isDirectory()判断是普通文件还是目录。

结果：IDE中开发、Maven测试阶段都正常，但打包后运行jar包时报错：

1
2

Caused by: java.io.FileNotFoundException: class path resource [static/the_dir] cannot be resolved to absolute file path because it does not reside in the file system: jar:nested:/C:/.../target/xxx.jar/!BOOT-INF/classes/!/static/the_dir
        at org.springframework.util.ResourceUtils.getFile(ResourceUtils.java:218) ~[spring-core-6.1.2.jar!/:6.1.2]

原因：运行jar包时，static目录及其下属各文件都在jar包中，而不在文件系统上，所以ResourceUtils抛出了FileNotFoundException异常。即，不能按文件系统的方式用Java文件API去操作。

思路二：操作资源（可行）

查询Spring Framework的文档可知，Spring抽象了一个称为**“资源（Resource）”**的概念，资源既可以是文件系统中的文件，也可以是jar包中的文件。

通过资源解析器org.springframework.core.io.support.PathMatchingResourcePatternResolver，可以拿到符合指定路径模式的资源列表（相当于文件列表）。

1
2
3
4

PathMatchingResourcePatternResolver resolver = new PathMatchingResourcePatternResolver();
// `*`表示仅获取直接子目录/文件，`**`表示获取所有后代目录/文件
// 在文件系统上运行时，每个资源的类型为`FileSystemResource`；在jar包中运行时，每个资源的类型为`ClassPathResource`
Resource[] resources = resolver.getResources("classpath:static/the_dir/*");

每个资源可以通过resource.isReadable()（是否可读）判断是普通文件还是普通，true表示是普通文件，false表示是目录。

读取文件内容

Spring Boot 3可直接通过resource.getContentAsString(StandardCharsets.UTF-8)读取文件内容，Spring Boot 2则需要通过resource.getInputStream()获取输入流来读取文件内容。

计算访问路径

资源可以通过resource.isFile()判断是否在文件系统中，进而通过不同的方式拿到路径。

每个文件的路径去掉static目录的路径，就是该文件相对于static目录的访问路径。

1
2
3
4
5
6
7
8
9

Resource staticDirectoryResource = resolver.getResource("classpath:static");
String staticDirectoryPath = staticDirectoryResource.isFile()
    ? staticDirectoryResource.getFile().getAbsolutePath() // 文件系统的绝对路径，形如"C:\..."
    : ((ClassPathResource) staticDirectoryResource).getPath(); // 相对于类目录的路径，形如"static/..."
...
String filePath = fileResource.isFile()
    ? fileResource.getFile().getAbsolutePath()
    : ((ClassPathResource) fileResource).getPath();
String accessPath = filePath.replace(staticDirectoryPath, "").replace(File.separator, "/");