北航刷题笔记其五

fufhaha2025-02-092025-04-06

3.函数及应用

1.自然常数e（math.h）

exp(1)

2.三次方根（math.h）

cbrt(x)

3.全错位排序公式：

全错位排序（Derangement） 是指一个排列中，所有元素的位置都不与其原位置相同的排列方式。换句话说，对于一个有 n 个元素的排列，要求每个元素都不出现在其原本的位置上。

全错位排序的递推公式

对于给定的 n，全错位排序的数目可以通过递推公式来计算，公式为：
$$
D_n = (n - 1) \times (D_{n-1} + D_{n-2})
$$
其中：

D_n 表示有 n 个元素的全错位排列数。
D_0 = 1，即零个元素的全错位排列数为 1（通常定义为1）。
D_1 = 0，即一个元素没有全错位排列。

4.while中用于没给出具体循环个数但要读取数的情况：

~scanf("%d", &n) 是一个常见的用法，通常用于读取整数输入直到输入结束。让我们详细分析一下这个表达式的含义。

`scanf` 的返回值

scanf 函数用于从标准输入读取数据，并将读取到的数据存储到指定的变量中。scanf 的返回值是成功读取的输入项的数量。例如：

如果成功读取了一个整数，scanf 会返回 1。
如果输入无法匹配格式，或者读取失败，scanf 会返回 EOF（通常是 -1）。

`~` 运算符

~ 是按位取反运算符，它将操作数的每一位反转。对于 scanf 的返回值 1 或 EOF，~scanf 将会执行如下操作：

如果 scanf 返回 1（表示成功读取了一个整数），那么 ~1 等于 -2，这是一个真值（非零），表示循环继续。
如果 scanf 返回 EOF（表示输入结束或错误），那么 ~EOF 等于 0，这是假值，表示循环终止。

结合起来的效果

while (~scanf("%d", &n)) 这个循环的含义是：（一般用于读1个数）

如果 scanf 成功读取一个整数，那么 ~scanf("%d", &n) 为非零值，条件成立，循环继续。
如果 scanf 读取失败（如遇到输入结束或错误），~scanf("%d", &n) 为零，循环终止

5.动态规划：

动态规划（Dynamic Programming，简称 DP）是一种求解复杂问题的算法思想，适用于具有重叠子问题和最优子结构性质的问题。它通过将问题分解为更小的子问题，存储子问题的解并加以重用，从而避免重复计算，提高效率。

动态规划的基本思想：

重叠子问题
将原问题拆分成多个子问题，许多子问题会重复出现。通过记忆化（Memoization）或者表格化（Tabulation），存储已解决的子问题结果，避免重复计算。
最优子结构
问题的全局最优解可以通过子问题的最优解来构造。例如，最短路径问题的某条路径如果是最优路径，那么它的任意子路径也是最优的。
状态转移方程
动态规划通过状态转移方程从较小规模的问题推导出较大规模问题的解。状态转移方程是动态规划的核心。

动态规划的解题步骤：

明确状态
定义子问题的状态，用状态描述当前所处的子问题。
状态转移方程
推导状态之间的递推关系，找到如何通过子问题的解得到当前问题的解。
初始化
为状态表或记忆化数组设置初始条件。
填表或递归
通过递归或迭代的方式求解问题。
返回结果
通常结果在状态表的最后一格，或者通过递归的返回值获取。

动态规划的常见应用场景：

线性问题
- 最长公共子序列（LCS）
- 最长递增子序列（LIS）
- 背包问题
区间问题
- 戳气球问题
- 石子合并问题
路径问题
- 矩阵最小路径和
- 最短路径问题
字符串问题
- 最小编辑距离
- 正则匹配

举个简单的例子：斐波那契数列

斐波那契数列的递推关系为：
$$
F(n) = F(n-1) + F(n-2)
$$
我们可以用动态规划的方法来求解：

递推法：

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) return n;  // 初始化
    int dp[n + 1];
    dp[0] = 0; 
    dp[1] = 1; 
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];  // 状态转移方程
    }
    return dp[n];  // 返回结果
}

int main() {
    int n = 10;
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

优化的滚动数组法（减少空间复杂度）：

cpp复制编辑int fibonacciOptimized(int n) {
    if (n <= 1) return n;
    int prev1 = 1, prev2 = 0, current;
    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}

动态规划的本质在于化繁为简，避免重复，它是一种非常强大的算法工具，广泛应用于计算机科学和工程领域！

整数划分问题到底是什么？

假设我们有一个数字 n，想把它分成若干个正整数相加，比如：

n=5

时，可以分成：
- 5
- 4 + 1
- 3 + 2
- 3 + 1 + 1
- 2 + 2 + 1
- 2 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1

我们的目标是数一数有多少种不同的划分方法。

规则：

数字的顺序不重要（比如 4+14 + 14+1 和 1+41 + 41+4 算作同一种）。
每种划分中，每个数字的大小不能超过原来的数字 n。

用动态规划来解决

核心思想

我们一步一步来拆分问题：

先只用小数字去分：比如 1。
逐渐允许更大的数字：比如允许用 2，3……直到 n。

这样，每个小问题的答案就可以帮我们解决更大的问题。

举例：划分 5

1. 定义

用 dp[i][j]dp[i][j]dp[i][j] 表示：把数字 iii 划分成最大加数不超过 jjj 的方法数。

比如：

dp[5] [5] 表示把 5 划分成最大加数不超过 5 的方法数。
dp [5] [3] 表示把 5 划分成最大加数不超3的方法数。

2. 如何划分？

对于每个 dp[i][j]dp[i][j]dp[i][j]，我们分两种情况：

不选最大加数 jjj：
- 这样的问题就变成了 “把 i 划分成最大加数不超过 j−1的方法数”，也就是
  $$
  dp[i][j−1]
  $$
选最大加数 jjj：
- 那么剩下的部分就是 i−j，问题变成了 “把 i−j划分成最大加数不超过 jjj 的方法数”，也就是
  $$
  dp[i−j][j]
  $$

3. 状态转移公式

把两种情况加起来：
$$
dp[i][j]=dp[i][j−1]+dp[i−j][j]
$$

特殊情况

如果 j>ij > ij>i：最大加数 jjj 太大了，不可能用它，所以直接继承前面的结果：dp[i][j]=dp[i][j−1]dp[i][j] = dp[i][j-1]dp[i][j]=dp[i][j−1]。

初始化

为了让计算从简单的情况开始，我们先规定几个值：

**dp[0][j] = 1**：数字 0 的划分只有一种方案——什么都不选。
**dp[i][0] = 0**：数字 i>0i > 0i>0 的划分如果不允许用任何数，是不可能的。

举例填表

假设我们要划分 n=5n = 5n=5，构造一个表格，逐步填表。

i/j	0	1	2	3	4	5
0	1	1	1	1	1	1
1	0	1	1	1	1	1
2	0	1	2	2	2	2
3	0	1	2	3	3	3
4	0	1	3	4	5	5
5	0	1	3	5	6	7

最后一格
$$
dp[5][5]=7
$$
，表示有 7 种划分方法。

表格的含义

第一列：dp[i][0] = 0，因为正整数不能划分成只有 0 的加数。
第一行：dp[0][j] = 1，因为数字 0 的划分始终只有一种方案。
右下角：dp[5][5] = 7，即最终答案。

eg2.

解题思路

核心概念：
- 背包的操作类似于一个固定大小的队列。
- 当背包未满时，直接加入新素材。
- 当背包已满时，移除最早加入的素材，腾出空间存放新素材。
算法步骤：
- 用一个队列（数组实现）模拟背包。
- 遍历每个神庙所需的素材：
  - 如果素材已经在背包中，不需要返回仓库。
  - 如果素材不在背包中：
    - 如果背包未满，将素材加入背包。
    - 如果背包已满，移除最早的素材，再将新素材加入背包。
    - 每次加入新素材，都记为一次返回仓库操作。
数据结构选择：
- 背包可以用一个数组来模拟。
- 当前背包中的素材可以通过遍历数组来查找（线性查找）。

示例

输入：

1 2	复制编辑3 7 1 2 3 4 2 1 5

解释：

初始背包为空，依次处理每个素材：
- 需要 1：返回仓库，背包变为 [1]。
- 需要 2：返回仓库，背包变为 [1, 2]。
- 需要 3：返回仓库，背包变为 [1, 2, 3]。
- 需要 4：背包满，返回仓库，移除最早的 1，背包变为 [2, 3, 4]。
- 需要 2：已经在背包中，不返回仓库。
- 需要 1：返回仓库，移除最早的 3，背包变为 [4, 2, 1]。
- 需要 5：返回仓库，移除最早的 4，背包变为 [2, 1, 5]。

输出：

1
2

复制编辑
5

C代码实现

c复制编辑#include <stdio.h>
#include <stdbool.h>

#define MAXN 1010
#define MAXM 110

int main() {
    int M, N; // 背包容量和神庙总数
    int materials[MAXN]; // 神庙所需素材列表
    int backpack[MAXM]; // 模拟背包
    int front = 0, size = 0; // 队列的起点和当前大小
    int warehouse_count = 0; // 返回仓库的次数

    // 输入背包容量和神庙数量
    scanf("%d %d", &M, &N);

    // 输入神庙所需素材
    for (int i = 0; i < N; i++) {
        scanf("%d", &materials[i]);
    }

    // 遍历每个神庙所需的素材
    for (int i = 0; i < N; i++) {
        int material = materials[i];
        bool found = false;

        // 检查当前素材是否已经在背包中
        for (int j = 0; j < size; j++) {
            if (backpack[(front + j) % M] == material) {
                found = true;
                break;
            }
        }

        // 如果不在背包中，需要返回仓库
        if (!found) {
            warehouse_count++;

            // 如果背包已满，移除最早加入的素材
            if (size == M) {
                front = (front + 1) % M; // 移动队首指针
                size--;
            }

            // 将新素材加入背包
            backpack[(front + size) % M] = material;
            size++;
        }
    }

    // 输出返回仓库的次数
    printf("%d\n", warehouse_count);
    return 0;
}

代码讲解

队列模拟：
- 使用数组 backpack 模拟固定大小的队列。
- 通过 front 指针表示队首位置。
- 用 (front + size) % M 计算新素材存放的位置。
线性查找：
- 遍历当前背包的素材，检查是否已存在。
队列操作：
- 如果背包未满，直接加入新素材。
- 如果背包已满，移动 front 指针移除最早的素材，然后加入新素材。
返回仓库计数：
- 每次加入新素材时，计数器 warehouse_count++。

6.求积分的面积：

辛普森法则（Simpson’s Rule）

辛普森法则用于数值积分，适用于计算如下形式的定积分：
$$
\int_{a}^{b} f(x) , dx \approx \frac{b - a}{6} \left( f(a) + 4f\left(\frac{a + b}{2}\right) + f(b) \right)
$$

7.计数数组（哈希表）：用于专门计数组中元素出现的次数：

开一个专门计数的数组，不过这个数组s[n]中的n是要计数数组中的元素，**即s[a[i]]，最后看看需要的次数就输出对应的a[i]**即可

8.将10进制转换为n进制：用数组（就是不断地取余，每次商更新，最后结果倒序输出）

// 函数：将十进制数转换为n进制
void decimalToBaseN(int num, int base) {
    if (num == 0) {
        printf("0");
        return;
    }

    char result[32];  // 存储转换结果的数组
    int index = 0;     // 结果数组的索引

    while (num > 0) {
        int remainder = num % base;   // 取余数
        if (remainder < 10) {
            result[index++] = remainder + '0';  // 数字直接转换为字符
        } else {
            result[index++] = remainder - 10 + 'A';  // 字母转换（如：A、B、C...）
        }
        num /= base;  // 将num更新为商
    }

    // 输出结果时，需要倒序打印
    for (int i = index - 1; i >= 0; i--) {
        printf("%c", result[i]);
    }
}

9.如果要将数字或者字母转换为字符

数字+‘0’

字母+‘A’或者字母+‘a’

'A' 的 ASCII 值是 65，所以加上 'A' 后，remainder - 10 + 'A' 就会得到正确的字符：

当 remainder == 10 时，remainder - 10 + 'A' 就是 0 + 'A' = 'A'；
当 remainder == 11 时，remainder - 10 + 'A' 就是 1 + 'A' = 'B'；
当 remainder == 12 时，remainder - 10 + 'A' 就是 2 + 'A' = 'C'；
依此类推。

10.遇到整体错位问题，可以往矩阵方向想（二维数组赋值与初始化一起）

11.双指针3.2.9

12.<string.h>:

用**strlen(s)**可以直接返回不包括‘\0’的字符数量

13.通过 `islower` 和 `isupper` 来分别判断字符是小写字母还是大写字母（ctype.h）

这类函数都是基于字符而操作的

所以，字符串中是数字时如果最后要进行运算也要记得转换一下

14.绝对值更新：

abs() 用于整数类型，返回整数的绝对值<stdlib.h>

fabs() 用于浮动类型，返回浮动数的绝对值（math.h

15.比较两字符串是否相等：<string.h>

strncmp 是一个标准库函数，用来比较两个字符串的前 n 个字符（不考虑后续的字符）。

strncmp
1
2
3

的函数原型是：


int strncmp(const char *str1,  const char *str2,   size_t n);
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

  它会逐字符比较 **str1 和 str2 的前 n个字符**：

  - 如果这两个字符串相等，返回值为 `0`。
  - 如果不同，它返回一个非零值（具体值取决于字符串的差异）。

### 参数：

- `&A[i]`：表示从 `A` 字符串的第 `i` 个位置开始的子字符串。
- `B`：表示第二个字符串。
- `b`：表示要比较的字符数，也就是字符串 `B` 的长度。

```c
#include <stdio.h>
#include <string.h>

int main() {
    char str1[] = "hello";
    char str2[] = "hell";
    
    // 比较前4个字符
    if (strncmp(str1, str2, 4) == 0) {
        printf("The first 4 characters are equal.\n");
    } else {
        printf("The first 4 characters are not equal.\n");
    }

    return 0;
}

16.质数，也叫素数：是大于1的自然数，只能被1和它本身整除的数

17.对于回形二维数组方位问题3.1.14

18.指针所代表的地址的值是只有一个的，所以更改就算再函数中也会更改到本体

++指针值的时候，指针要有括号，不然会先解指针。（*p）++

19.动态内存分配

20<string.h>头文件中查找数组中的某部分和替换数组中的某部分

`strstr()`

原型：

1	char strstr(const char haystack, const char *needle);

功能：在 haystack（目标字符串）中查找第一次出现的 needle（子字符串）。
返回值：返回指向第一次出现的 needle 在 haystack 中的位置的指针。如果没有找到，返回 NULL。

示例：

while (fgets(buf, sizeof(buf), stdin)) {
        // 查找是否有 "_xy_"
        p = strstr(buf, "_xy_");
        if (p) {
            // 替换 "_xy_" 为 "_ab_"
            strncpy(p, "_ab_", 4);
        }
        // 输出替换后的字符串
        printf("%s", buf);
    }

`strncpy()`

原型：

1	char strncpy(char dest, const char *src, size_t n);

功能：将 src 字符串中的前 n 个字符复制到 dest 字符串中。
参数

：
- dest：目标字符串数组。
- src：源字符串。
- n：复制的字符数量。
返回值：返回 dest 字符串的指针。

注意事项：

如果 src 的长度小于 n，strncpy 会将剩余的空间用 \0 填充。
如果 src 的长度大于或等于 n，strncpy 只会复制前 n 个字符，可能不会在 dest 字符串末尾添加 \0，所以需要小心处理。

21.char *month[] = { “January”, “February”, “March”, “April”, “May”, “June”, “July”, “August”, “September”, “October”, “November”, “December” };

char *month[] 是一个指向字符串的指针数组。这里的 char 是字符类型，但 *month[] 是指向字符数组（即字符串）的指针数组，因此每个元素可以存储一个指向字符串的指针。具体来说，char *month[] 的每个元素是一个字符串的首地址，而这个字符串是由多个字符组成的。

字符串与字符的区别：

字符（char）：一个字符变量 char 用来存储单个字符（例如：’a’、’b’、’1’）。它占用 1 个字节的内存空间。

示例：
1
char c = 'A';
字符串（char 数组）：一个字符串是由多个字符组成的字符数组，最后会以一个空字符 '\0' 结尾来标志字符串的结束。一个字符串是一个字符的集合。

示例：
1
char str[] = "Hello"; // 字符串 "Hello"，包含 6 个字符（包括 '\0'）
指向字符串的指针（char*）：char* 是指向字符的指针，可以指向一个字符，也可以指向一个字符串（即字符数组的首地址）。在 C 语言中，字符串是通过指向字符数组的指针来处理的。

示例：（用的时候还是直接打数组[]就好）
1
char *str = "Hello"; // 指向字符串 "Hello"

22.strtok(buffer, “ \n”); // 分割输入字符串为单词，strcpy(strArray[n], word); // 复制单词到 strArray

23.取余%会一直除，除到底

24.汉诺塔

递归关系：

递归的基本思想是：
- 如果只有一个盘子，移动一次即可。
- 对于 n > 1，先将 n-1 个盘子从源柱子移动到辅助柱子，再将第 n 个盘子从源柱子移动到目标柱子，最后再将 n-1 个盘子从辅助柱子移动到目标柱子。

因此，递归公式为：

T(n) = 2 * T(n-1) - 1，其中 T(n) 表示移动 n 个盘子所需的最少次数。

25.约瑟夫问题：

约瑟夫问题通俗解释

场景：
- 有 n个人围成一个圈，每个人都有一个编号 1 到 n。
- 从第 s 个人开始报数。
- 数到 m 的人出列（从圈中移除）。
- 然后从被移除的下一个人继续报数。
- 这样一直重复，直到所有人都出列。
目标：
输出所有人出列的顺序。

解法思路

可以用数组或列表模拟这个过程。

核心步骤

初始化：
使用一个数组（或列表）circle 表示所有人，初始时存储每个人的编号 1 到 n。
从第 sss 个人开始：
调整索引，让数组从s−1 开始报数。
循环报数：
- 每次从当前起始位置数 m 个。
- 找到被移除的人的索引。
- 输出被移除的编号，并从数组中删除该人。
调整起点：
移除一个人后，从下一位继续。
终止：
当数组中只剩下一个人时，问题结束。

伪代码

定义一个数组 circle，长度为 n，存放编号 1 到 n。
起始位置 pos = s-1（数组索引从 0 开始）。
循环执行：
- 计算出列位置：pos = (pos + m - 1) % 当前数组长度。
- 输出 circle[pos]，并移除该元素。
- 从 pos 开始继续。
当数组为空时，停止。

示例

输入：
n=5, s=2, m=3

执行过程：

初始队列：[1, 2, 3, 4, 5]，从编号 2 开始。
第 1 次：数到 3，出列 4。剩余：[1, 2, 3, 5]，下一个从 5 开始。
第 2 次：数到 3，出列 3。剩余：[1, 2, 5]，下一个从 5 开始。
第 3 次：数到 3，出列 2。剩余：[1, 5]，下一个从 1 开始。
第 4 次：数到 3，出列 5。剩余：[1]，下一个从 1 开始。
第 5 次：数到 1，出列 1。剩余：[]。

输出：
4 3 2 5 1

C代码实现

#include <stdio.h>

int main() {
    int n, s, m;
    scanf("%d%d%d", &n, &s, &m);
    
    int circle[102];  // 定义数组表示圈中人数
    for (int i = 0; i < n; ++i) {
        circle[i] = i + 1;  // 初始化每个人的编号
    }

    int pos = s - 1;  // 起始位置（从 0 开始）
    for (int remaining = n; remaining > 0; --remaining) {
        pos = (pos + m - 1) % remaining;  // 计算出列的位置
        printf("%d\n", circle[pos]);     // 输出出列编号
        for (int j = pos; j < remaining - 1; ++j) {//从出列的那个位置开始再循环
            circle[j] = circle[j + 1];   // 移动数组，移除出列的人，这样，虽然数组大小没变，但是被踢出去的数移到了最后面
        }
    }
    return 0;
}

关键点讲解

数组模拟圈：
用一个数组来存放剩余的编号，通过移动数组来实现“移除”的效果。
模运算：
pos = (pos + m - 1) % remaining 确保索引不会越界，同时实现环状结构。
调整数组：
每次有人出列后，将后续元素往前移动，模拟“移除”的操作。
输出顺序：
每次出列后直接输出该编号，最终的输出顺序就是所求结果。

26.方向数组（面对具有方向的二维问题时）

这个问题要求我们生成一个 n×n 的蛇形矩阵，矩阵的填充方式是从右上角开始，按照顺时针方向填充数字 1 到 n×n。要实现这一点，我们需要根据矩阵的规律进行填充。

解题思路

蛇形矩阵的特点：
- 从右上角开始填充数字 1，2，3，…，直到 n×n。
- 填充规则是顺时针方向，开始时从右上角填充，接着是下方、左方，再上方，依此循环。
如何实现：
- 我们可以用一个二维数组来表示矩阵，使用变量来跟踪当前的填充位置。
- 初始化位置为右上角 (0, n-1)。
- 然后按照顺时针方向移动。我们可以定义一个方向数组来表示顺时针方向的移动顺序（上、右、下、左）。
边界处理：
- 在填充过程中，要确保每次移动都在矩阵内部，如果遇到已经填充的格子，应该改变方向。

代码实现

#include <stdio.h>
#define MAXN (25)
int main()
{
    /**********Begin**********/
    int n, i, j, x = 0, y, dir = 0;
    int mat[MAXN][MAXN] = { 0 };
    //预处理方向为向下、向左、向上、向右时，横纵坐标的偏移量dx，dy
    int dx[4] = { 1, 0, -1, 0 };
    int dy[4] = { 0, -1, 0, 1 };
    scanf("%d", &n);
    y = n - 1;
    for (i = 1; i <= n * n; ++i)
    {
        mat[x][y] = i;
        //在dir 方向上走一步
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        //如果当前坐标(dx,dy) 超过了边界，或者是已经填了数字
        if (!(0 <= nx && nx < n && 0 <= ny && ny < n) || mat[nx][ny])
        {
            //顺时针旋转一个方向，然后再走一步
            dir = (dir + 1) % 4;
            nx = x + dx[dir];
            ny = y + dy[dir];
        }
        x = nx;
        y = ny;
    }
    for (i = 0; i < n; ++i) {
        for (j = 0; j < n; ++j)
            printf("%d ", mat[i][j]);
        printf("\n");
    }
    /**********End**********/
}

代码解析

初始化：
- matrix 数组用来存储最终的蛇形矩阵，所有元素初始化为 0。
- directions 数组表示顺时针方向的移动顺序，分别对应上、右、下、左。
- x 和 y 分别表示当前填充位置的行和列，初始位置为右上角 (0, n-1)。
- num 从 1 开始，表示当前要填充的数字。
- dir 表示当前的方向，初始为 0（向上）。
填充过程：
- 使用 while 循环填充矩阵，直到填充到 n*n。
- 每次填充一个数字后，计算下一个位置 (nx, ny)。
- 如果下一个位置越界或已经被填充，就改变方向（顺时针改变方向）。
- 更新当前位置为 nx 和 ny。
输出：
- 完成填充后，输出矩阵中的所有元素，每行输出 n 个数字。

27.dfs（3.2.28）

void dfs(int x, int y) {
    // 标记当前陆地为已访问（0代表海洋，1代表陆地）
    grid[x][y] = '0'; 

    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + directions[i][0];
        int ny = y + directions[i][1];
        
        // 检查是否越界且是否是陆地
        if (nx >= 0 && nx < row_n && ny >= 0 && ny < col_n && grid[nx][ny] == '1') {
            dfs(nx, ny); // 递归访问相连的陆地
        }
    }
}

28.计算一个已知各顶点的多边形面积：

要计算一个凸多边形的面积，可以使用**”叉积法”**，即多边形的面积公式。具体来说，如果你有一个凸多边形的顶点序列 (x1, y1), (x2, y2), …, (xn, yn)，则面积计算公式如下：
$$
\text{面积} = \frac{1}{2} \times \left| \sum_{i=1}^{n} (x_i \cdot y_{i+1} - x_{i+1} \cdot y_i) \right|
$$
其中，
$$
(xn+1, yn+1)
$$

是 (x1, y1)，即环绕一圈计算。

29.结构体排序

int compareStudents(const void *a, const void *b) {
    Student *sa = (Student *)a; // 将 void 指针类型强制转换为 Student 指针类型
    Student *sb = (Student *)b;

    // 按月份升序排序
    if (sa->month != sb->month) 
        return sa->month - sb->month;

    // 如果月份相同，按日期升序排序
    if (sa->day != sb->day) 
        return sa->day - sb->day;

    // 如果日期也相同，按姓名字典序升序排序
    return strcmp(sa->name, sb->name);
}
//多条件的

单条件的：

int compareByMonth(const void *a, const void *b) {
    Student *sa = (Student *)a;
    Student *sb = (Student *)b;

    return sa->month - sb->month; // 按月份升序排序
}

等于-1就是排序的方向

用于字符串的比较：

// 比较函数，用于qsort排序
int compare(const void *a, const void *b) {
    char *strA = *(char **)a;
    char *strB = *(char **)b;

    int lenA = strlen(strA);
    int lenB = strlen(strB);

    // 按长度从长到短排序
    if (lenA != lenB) {
        return lenB - lenA;
    }

    // 如果长度相同，按首字母字典序排序（区分大小写）
    return strcmp(strA, strB);
}

30.链表：

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
struct Node {
    int num;                // 记录人的编号
    struct Node* next;      // 指向下一个节点
};

int main() {
    int n, count = 0;
    scanf("%d", &n);

    // 创建循环链表
    struct Node *head = NULL, *prev = NULL, *temp = NULL;

    for (int i = 1; i <= n; i++) {
        temp = (struct Node*)malloc(sizeof(struct Node));
        temp->num = i;
        temp->next = NULL;

        if (head == NULL) {
            head = temp;    // 第一个节点
        } else {
            prev->next = temp;  // 链接到前一个节点
        }
        prev = temp;
    }
    prev->next = head;  // 链表首尾相连，形成循环链表

    // 模拟约瑟夫环
    struct Node* current = head;
    struct Node* previous = prev;

    while (current->next != current) { // 直到只剩下一个节点
        count++;
        if (count == 3) {  // 报数到 3 时
            // 删除当前节点
            previous->next = current->next;
            printf("Person %d is out\n", current->num);
            free(current);
            current = previous->next; // 移动到下一个节点
            count = 0; // 重置计数
        } else {
            previous = current;
            current = current->next; // 移动到下一个节点
        }
    }

    // 输出最后剩下的人
    printf("The winner is: %d\n", current->num);

排序算法：

在 C 的
1
qsort
函数中，比较函数的返回值控制排序规则：
- 返回负值：第一个元素排在前面。
- 返回正值：第二个元素排在前面。
- 返回 0：两个元素位置不变。

31.哈希表：

哈希表（Hash Table）是一种数据结构，用于以 键值对（key-value pair） 的形式存储数据，能够快速查找、插入或删除数据。

在这个问题中，我们用到的是一个简单的哈希表（通过数组模拟），用来存储字符和它们的“权重”或“优先级”（称为哈希索引）。我们通过这些权重，定义一个新的字符比较规则，用来对单词进行排序。

哈希表的核心概念

键（Key）：唯一标识某个数据。例如，这里我们用字母 'a' 到 'z' 和 'A' 到 'Z' 作为键。
值（Value）：与键相关联的数据。例如，这里用输入的整数表示每个字母的哈希索引值。

哈希表的功能：快速根据键找到对应的值。在这道题中，哈希表就是一个简单的数组：

c


复制编辑
int hash[256];

这里我们用 hash 数组记录每个字符的哈希值（优先级），hash[i] 存储字符 i 对应的优先级。

这段代码中哈希表的具体用途

输入哈希索引表：

输入包含 52 个整数，分别代表 'a'-'z' 和 'A'-'Z' 的优先级。

通过下面的代码将这些优先级存入

hash

数组：

c复制编辑for (int i = 'a'; i <= 'z'; i++) {
    scanf("%d", &hash[i]);
}
for (int i = 'A'; i <= 'Z'; i++) {
    scanf("%d", &hash[i]);
}

例如：

1 2	bash复制编辑输入：-1 2 3 ... 52 意味着：hash['a'] = -1, hash['b'] = 2, ..., hash['Z'] = 52

比较两个字符的优先级：
- 我们可以通过 hash[字符] 找到这个字符对应的优先级。
- 比较两个字符
  1
  x
  和
  1
  y
  时：
  1
  2
  3
  c复制编辑if (hash[x] != hash[y]) {
  return hash[x] - hash[y];
  }
单词排序：
- 每次比较两个单词时，按字典规则逐字符比较，但字典顺序被 hash 优先级表替代。
- 例如：
  1
  2
  3
  c复制编辑假设输入：
  hash['a'] = -1, hash['b'] = 2, hash['A'] = 27
  单词列表：aaa, aAb, bbb
  排序结果：
  - 'aaa' -> -1, -1, -1
  - 'aAb' -> -1, 27, 2
  - 'bbb' -> 2, 2, 2 按优先级依次为：aaa < aAb < bbb。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char word[505][1050]; // 存储单词的数组
int hash[256];        // 哈希索引表

// 自定义比较函数，根据哈希值排序
int cmps(const void *a, const void *b) {
    char *wordA = (char *)a;
    char *wordB = (char *)b;
    int i = 0;

    // 按照字符逐个比较哈希值
    while (wordA[i] && wordB[i]) {
        if (hash[(unsigned char)wordA[i]] != hash[(unsigned char)wordB[i]]) {
            return hash[(unsigned char)wordA[i]] - hash[(unsigned char)wordB[i]];
        }
        i++;
    }

    // 若所有字符的哈希值都相同，较短的单词排在前面
    return strlen(wordA) - strlen(wordB);
}

int main() {
    int n;
    
    // 输入哈希索引表
    for (int i = 'a'; i <= 'z'; i++) {
        scanf("%d", &hash[i]); // 对应 'a'-'z' 的哈希值
    }
    for (int i = 'A'; i <= 'Z'; i++) {
        scanf("%d", &hash[i]); // 对应 'A'-'Z' 的哈希值
    }

    // 输入单词总数
    scanf("%d", &n);

    // 输入所有单词
    for (int i = 0; i < n; i++) {
        scanf("%s", word[i]);
    }

    // 使用 qsort 按照自定义比较函数排序
    qsort(word, n, sizeof(word[0]), cmps);

    // 输出排序后的单词
    for (int i = 0; i < n; i++) {
        printf("%s\n", word[i]);
    }

    return 0;
}

3.函数及应用

1.自然常数e（math.h）

2.三次方根（math.h）

3.全错位排序公式：

全错位排序的递推公式

4.while中用于没给出具体循环个数但要读取数的情况：

scanf 的返回值

~ 运算符

结合起来的效果

5.动态规划：

动态规划的基本思想：

动态规划的解题步骤：

动态规划的常见应用场景：

举个简单的例子：斐波那契数列

递推法：

优化的滚动数组法（减少空间复杂度）：

整数划分问题到底是什么？

用动态规划来解决

核心思想

举例：划分 5

1. 定义

2. 如何划分？

3. 状态转移公式

特殊情况

初始化

举例填表

表格的含义

eg2.

解题思路

示例

输入：

解释：

输出：

C代码实现

代码讲解

6.求积分的面积：

辛普森法则（Simpson’s Rule）

7.计数数组（哈希表）：用于专门计数组中元素出现的次数：

8.将10进制转换为n进制：用数组（就是不断地取余，每次商更新，最后结果倒序输出）

9.如果要将数字或者字母转换为字符

10.遇到整体错位问题，可以往矩阵方向想（二维数组赋值与初始化一起）

11.双指针3.2.9

12.<string.h>:

13.通过 islower 和 isupper 来分别判断字符是小写字母还是大写字母（ctype.h）

14.绝对值更新：

15.比较两字符串是否相等：<string.h>

16.质数，也叫素数：是大于1的自然数，只能被1和它本身整除的数

17.对于回形二维数组方位问题3.1.14

18.指针所代表的地址的值是只有一个的，所以更改就算再函数中也会更改到本体

19.动态内存分配

20<string.h>头文件中 查找数组中的某部分 和 替换数组中的某部分

strstr()

strncpy()

21.char *month[] = { “January”, “February”, “March”, “April”, “May”, “June”, “July”, “August”, “September”, “October”, “November”, “December” };

字符串与字符的区别：

22.strtok(buffer, “ \n”); // 分割输入字符串为单词，strcpy(strArray[n], word); // 复制单词到 strArray

23.取余%会一直除，除到底

24.汉诺塔

递归关系：

25.约瑟夫问题：

约瑟夫问题通俗解释

解法思路

核心步骤

伪代码

示例

C代码实现

关键点讲解

26.方向数组（面对具有方向的二维问题时）

解题思路

代码实现

代码解析

27.dfs（3.2.28）

28.计算一个已知各顶点的多边形面积：

29.结构体排序

30.链表：

31.哈希表：

哈希表的核心概念

这段代码中哈希表的具体用途

32.田忌赛马策略（贪心）：如果我方最强大于敌方最强，则+，否则用我方最弱消耗对方最强

`scanf` 的返回值

`~` 运算符

13.通过 `islower` 和 `isupper` 来分别判断字符是小写字母还是大写字母（ctype.h）

20<string.h>头文件中查找数组中的某部分和替换数组中的某部分

`strstr()`

`strncpy()`