第1章 数据编码

​ 在计算机中，数值是以二进制形式存储的，而原码、反码、补码是表示符号整数的三种编码方式。它们的设计目的是解决计算机中负数的表示和运算问题，尤其是如何通过加法运算实现减法操作。

1.1 机器数与真值

在了解原码、反码、补码之前，需先明确两个基本概念： （1）机器数：一个数在计算机中的二进制表示形式，包含符号位和数值位。通常用最高位表示符号（0 表示正数，1 表示负数），其余位表示数值的绝对值。 （2）真值：机器数所对应的实际数值。 示例：

• 机器数 00000101 的真值是 +5
• 机器数 10000101 的真值是 -5

1.2 原码、反码、补码的概念

1.2.1 原码

定义： 最直接的机器数表示方法

数值类型	符号位	数值位
正数	0	该数的二进制绝对值
负数	1	该数绝对值的二进制
8位二进制示例：

• +5 的原码：00000101
• -5 的原码：10000101
• 0 的原码有两种形式：00000000（+0）和 10000000（-0）

1.2.2 反码

定义： 原码向补码过渡的编码方式

数值类型	转换规则
正数	与原码相同
负数	符号位保持1，数值位按位取反
8位二进制示例：

• +5 的反码：00000101
• -5 的反码：11111010
• 0 的反码有两种形式：00000000（+0）和 11111111（-0）

1.2.3 补码

定义： 计算机中表示符号整数的标准方式 | 数值类型 | 转换规则 | | :------- | :------------------------------------------ | | 正数 | 与原码、反码相同 | | 负数 | 反码 + 1 | 8位二进制示例：

• +5 的补码：00000101
• -5 的补码：11111011
• 0 的补码只有一种形式：00000000

1.2.4 三种编码对比表

数值	原码	反码	补码
+5	00000101
0	00000000 / 10000000	00000000 / 11111111	00000000
-5	10000101	11111010	11111011

1.2.5 补码的表示范围

对于 n 位二进制补码：

• 表示范围： -2ⁿ⁻¹ ~ 2ⁿ⁻¹-1
• 8位补码范围： -128 ~ 127
• 特殊规定： 10000000 表示 -128（无对应的原码和反码）

1.3 补码的运算规则

1.3.1 基本运算规则

​ 加法： [A+B]补 = [A]补 + [B]补 ​ 减法： [A-B]补 = [A]补 + [-B]补

关键点： 将减法转换为加法

1.3.2 运算示例

示例1：计算 5 + 3

+5 的补码：00000101
+3 的补码：00000011
相加：     00000101 + 00000011 = 00001000
结果：00001000（补码）→ +8 ✅

示例2：计算 5 - 3（即 5 + (-3)）

+5 的补码：00000101
-3 的补码：11111101
相加：     00000101 + 11111101 = 100000010（忽略进位）
结果：00000010（补码）→ +2 ✅

示例3：计算 3 - 5（即 3 + (-5)）

+3 的补码：00000011
-5 的补码：11111011
相加：     00000011 + 11111011 = 11111110
结果：11111110（补码）→ -2 ✅

1.4 三种编码的转换关系

1.4.1 正数的转换

对于正数：[X]原 = [X]反 = [X]补

1.4.2 负数的转换

转换路径：

原码 →（数值位取反）→ 反码 →（+1）→ 补码

补码求原码的方法：

1. 方法1： 对补码求补码（按位取反+1）
2. 方法2： 补码-1 得到反码，再取反得到原码
3. 示例（X = -5）：

原码：10000101
    ↓ 数值位取反
反码：11111010
    ↓ +1
补码：11111011

补码求原码：
11111011 → 取反：00000100 → +1：00000101 → 符号位1：10000101

1.5 补码的溢出检测

1.5.1 溢出的判断方法

方法1：双符号位法

• 00：正数
• 11：负数
• 01：正溢出（结果 > +127）
• 10：负溢出（结果 < -128）

方法2：单符号位法

• 正数 + 正数 → 负数：正溢出
• 负数 + 负数 → 正数：负溢出
• 异号数相加：不会溢出

1.5.2 溢出示例

计算 120 + 10（8位补码）：

120 的补码：01111000
10 的补码：00001010
相加：     01111000 + 00001010 = 10000010

结果： 符号位为 1，实际结果 130 > 127，发生正溢出

1.6 补码的优势总结

1. 唯一的零表示 - 避免了原码和反码中 +0 与 -0 的双重表示 2. 减法变加法 - 简化计算机硬件设计，只需实现加法器 3. 表示范围更大 - 相比原码和反码，能多表示一个最小负数 4. 运算统一 - 所有加减运算都统一为补码加法

1.7 实际应用与练习

1.7.1 快速转换技巧

负数补码快速求法：

从右往左找到第一个1，这个1及其右边的位保持不变，左边的位全部取反
示例：-5的补码
5的二进制：00000101
从右找到第一个1：00000101
            ↑
保持该1及其右边：101
左边全部取反：11111
结果：11111011

第2章 计算机的数制

2.1 数制的基本概念

2.1.1 基数

​ 基数是指在某种数制中，每个数位上所能使用的数字符号的个数。 | 数制 | 基数 | 数字符号 | 应用场景 | | ------------------------------------------- | ---- | -------- | ------------------ | | 十进制 | 10 | 0-9 | 日常生活计算 | | 二进制 | 2 | 0, 1 | 计算机内部处理 | | 八进制 | 8 | 0-7 | 简化二进制表示 | | 十六进制 | 16 | 0-9, A-F | 程序设计和内存地址 |

2.1.2 位权

位权是指在某种数制中，每个数位所具有的价值，其大小等于数字符号 × 基数的位置次方。 示例： 十进制数 123.45

• 数字 1：百位，位权 $10^2 = 100$，值 $1 × 100 = 100$
• 数字 2：十位，位权 $10^1 = 10$，值 $2 × 10 = 20$
• 数字 3：个位，位权 $10^0 = 1$，值 $3 × 1 = 3$
• 数字 4：十分位，位权 $10^{-1} = 0.1$，值 $4 × 0.1 = 0.4$
• 数字 5：百分位，位权 $10^{-2} = 0.01$，值 $5 × 0.01 = 0.05$ 总值： $100 + 20 + 3 + 0.4 + 0.05 = 123.45$

2.2 计算机中常用的数制

2.2.1 二进制（Binary）

1. 表示方法： 后缀 B，如：1011B
2. 特点： 逢二进一，借一当二
3. 计算机应用： 所有数据在计算机内部都以二进制形式存储
4. 优势： 只有0和1两种状态，易于用电子元件实现
5. 运算规则：

• 加法： 0+0=0；0+1=1；1+0=1；1+1=10（向高位进1）
• 减法： 0-0=0；1-0=1；1-1=0；10-1=1（向高位借1当2）

2.2.2 八进制（Octal）

1. 表示方法： 后缀 O 或 Q，如：123O、123Q
2. 特点： 逢八进一，借一当八
3. 应用： 3位二进制对应1位八进制，简化二进制表示

2.2.3 十进制（Decimal）

1. 表示方法： 后缀 D（通常省略），如：123D 或 123
2. 特点： 逢十进一，借一当十
3. 应用： 人类日常使用

2.2.4 十六进制（Hexadecimal）

1. 表示方法：
   • 后缀 H：1A3H、ABC.H
   • 前缀 0x（编程）：0x1A3、0xFF
   • 前缀 #（网页颜色）：#FF5733
2. 特点： 逢十六进一，借一当十六
3. 应用： 4位二进制对应1位十六进制，程序设计广泛使用

2.3 数制之间的转换

2.3.1 二进制与八进制、十六进制的转换

1. 二进制 → 八进制/十六进制
   • 整数部分： 从右向左分组（八进制3位一组，十六进制4位一组），不足补0
   • 小数部分： 从左向右分组，不足补0
2. 八进制/十六进制 → 二进制
   • 每位转换为对应的二进制数（八进制转3位，十六进制转4位）
3. 转换示例
   • 二进制转八进制： 1101101.1011B
     • 整数部分： 001 101 101 → 1 5 5 → 155O
     • 小数部分： 101 100 → 5 4 → .54O
     • 结果： 155.54O
   • 十六进制转二进制：B5.A3H
   • 整数部分： B → 1011, 5 → 0101
   • 小数部分： A → 1010, 3 → 0011
   • 结果： 10110101.10100011B

2.3.2 转换规则总结表

转换方向	整数部分分组方式	小数部分分组方式	每组位数	不足位处理
二进制 → 八进制	从右向左	从左向右	3位	整数左补0，小数右补0
八进制 → 二进制	每位单独处理		转3位	整数去前导0，小数保尾0
二进制 → 十六进制	从右向左	从左向右	4位	整数左补0，小数右补0
十六进制 → 二进制	每位单独处理		转4位	整数去前导0，小数保尾0

2.4 非十进制数转换为十进制数

转换方法： 按位权展开相加，即把非十进制数的每个数位上的数字符号乘以该数位的位权，然后将所有结果相加，得到对应的十进制数。

2.4.1 二进制转十进制

示例： 将二进制数1011B转换为十进制数
[1011B = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 = 8 + 0 + 2 + 1 = 11] 结果： 11D

2.4.2 八进制转十进制

示例： 将八进制数123O转换为十进制数
[123O = 1 \times 8^2 + 2 \times 8^1 + 3 \times 8^0 = 64 + 16 + 3 = 83] 结果： 83D

2.4.3 十六进制转十进制

示例： 将十六进制数1A3H转换为十进制数
[1A3H = 1 \times 16^2 + 10 \times 16^1 + 3 \times 16^0 = 256 + 160 + 3 = 419] 结果： 419D

2.4.4 含小数的非十进制转十进制

示例： 将十六进制数B5.AH转换为十进制数
[B5.AH = 11 \times 16^1 + 5 \times 16^0 + 10 \times 16^{-1} = 176 + 5 + 0.625 = 181.625] 结果： 181.625D

2.5 十进制数转换为非十进制数

转换方法： 整数部分和小数部分分别转换，最终合并结果。

• 整数部分： 除基取余法（除基数→取余数→商继续除基，直到商为0→余数逆序排列）
• 小数部分： 乘基取整法（乘基数→取整数部分→小数部分继续乘基，直到小数部分为0或达到所需精度→整数部分顺序排列）

2.5.1十进制转二进制

示例： 将十进制数11.625D转换为二进制数

• 整数部分（除2取余）：
• 11 ÷ 2 = 5 余 1 5 ÷ 2 = 2 余 1 2 ÷ 2 = 1 余 0 1 ÷ 2 = 0 余 1 → 余数逆序：1011B
• 小数部分（乘2取整）： 0.625 × 2 = 1.25 → 取1，小数部分0.25 0.25 × 2 = 0.5 → 取0，小数部分0.5 0.5 × 2 = 1.0 → 取1，小数部分0 → 整数顺序：.101B
• 最终结果： 1011.101B

2.6 数制转换综合示例与注意事项

2.6.1 综合示例：将十进制数181.625D转换为十六进制数

1. 整数部分： 181 ÷ 16 = 11 余 5；11 ÷ 16 = 0 余 11（B） → 逆序：B5H
2. 小数部分： 0.625 × 16 = 10.0 → 取10（A）→ 顺序：.AH
3. 结果： B5.AH（与2.3.1节示例相互验证）

注意事项

1. 部分十进制小数无法转换为有限位非十进制小数（如0.1D = 0.000110011...B），需按需求保留精度（通常保留4-6位）
2. 十六进制中A-F不区分大小写，书写时建议大写（如B5.AH），编程中常用0x前缀（如0xB5A）
3. 转换时可通过二进制作为中间桥梁（如十进制→二进制→十六进制），降低复杂数制转换难度

2.7 数制转换总结表

转换方向	核心方法	关键步骤
非十进制 → 十进制	按位权展开相加	确定每位位权→符号×位权→求和
十进制 → 非十进制	整数：除基取余（逆序）小数：乘基取整（顺序）	分两部分转换→合并结果→添加数制后缀
二进制 ↔ 八进制/十六进制	分组转换法	整数右分组、小数左分组→不足位补0→组内转换
核心要点：

1. 二进制是计算机底层的核心数制，八进制/十六进制是其简化表示形式
2. ** 位权**和基数是所有数制转换的理论基础，理解后可灵活应对各类转换场景
3. 实际应用中，十六进制因与二进制转换高效（4位一组），在编程、硬件开发中应用最广泛

第3章 位运算

3.1 位运算的基本概念

位运算是指对二进制数的各个位进行操作的运算，直接作用于数据的二进制位，具有运算速度快、效率高的特点。 核心特点：

1. **操作对象：**整数的二进制表示形式
2. 忽略符号位，仅对各个二进制位进行操作
3. 在计算机底层编程、数据压缩、加密算法等领域广泛应用

3.2 常用的位运算符

3.2.1 按位与（&）

运算规则： 两个二进制位都为1时，结果位为1；否则为0 真值表： | 输入A | 输入B | 输出 | | ----- | ----- | ---- | | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 |

• **示例：**5 & 3 = 1 计算过程： 5的二进制：00000101 3的二进制：00000011 **第1位：**1 & 1 = 1 **第2位：**0 & 1 = 0 **第3位：**1 & 0 = 0 **其余位（第4-7位）：**0 & 0 = 0 **结果：**00000001，即十进制1。
• 应用场景： (1) 清零：将一个数与0进行按位与运算，结果为0。例如，a & 0 = 0。 (2) 取一个数的指定位：例如，要取整数a的低4位，可进行a & 0x0F（十六进制0x0F对应二进制00001111）。

3.2.2 按位或（|）

运算规则： 两个二进制位中至少有一个为1时，结果位为1 真值表： | 输入A | 输入B | 输出 | | ----- | ----- | ---- | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 |

• **示例：**5 | 3 = 7 计算过程： 5的二进制：00000101 3的二进制：00000011 **第1位：**1 | 1 = 1 **第2位：**0 | 1 = 1 **第3位：**1 | 0 = 1 **其余位（第4-7位）：**0 | 0 = 0 **结果：**00000111，即十进制7。
• 应用场景： 置位：将一个数的指定位置为1。例如，要将整数a的第3位置为1，可进行a | (1 << 3)。

3.2.3 按位异或（^）

运算规则： 两个二进制位不同时，结果位为1；相同时为0 真值表： | 输入A | 输入B | 输出 | | ----- | ----- | ---- | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 |

• **示例：**5 ^ 3 = 1 计算过程： 5的二进制：00000101 3的二进制：00000011 **第1位：**1 ^ 1 = 0 **第2位：**0 ^ 1 = 1 **第3位：**1 ^ 0 = 1 **其余位（第4-7位）：**0 ^ 0 = 0 **结果：**00000110，即十进制6。
• 应用场景： 交换两个数的值（不使用临时变量）：a=a∧b；b=a∧b；a=a∧b。

3.2.4 按位取反（~）

1. 运算规则： 对二进制位进行取反操作，0变为1，1变为0
2. 示例：~5 (00000101) = -6 (11111010)
3. 特点： 对于有符号数，按位取反后结果为原数的相反数减1（即~a=-a-1）。
4. 应用场景：
   • 成掩码: 例如，~0可生成全1的掩码（在32位系统中为0xFFFFFFFF）。

3.2.5 左移（<<）

3.2.5.1 基本概念

​ 左移运算将数字的二进制表示向左移动指定的位数。

3.2.5.2 运算规则

1. 移动方向：二进制位向左移动
2. 高位处理：移出边界的位被丢弃
3. 低位处理：空出的低位用0填充
4. 适用性：适用于所有整数（正数和负数）

3.2.5.3 运算效果

左移n位相当于原数乘以2的n次方（在数值范围内有效）

3.2.5.4 示例说明

正数左移
数字5的二进制：00000101
向左移动2位：  00010100 （结果为20）

计算验证：5 × 2² = 5 × 4 = 20

负数左移
数字-5的二进制补码：11111011
向左移动2位：      11101100 （结果为-20）

计算验证：-5 × 2² = -5 × 4 = -20

3.2.5.5 应用场景

1. 快速计算2的幂次倍数
2. 某些算法中的性能优化

3.2.5.6 注意事项

1. 移动位数不应超过数据类型的位数
2. 左移可能导致数值溢出
3. 对于负数，左移运算基于补码表示法进行

3.2.6 右移（>>）

3.2.6.1 基本概念

​ 右移运算将数字的二进制表示向右移动指定的位数。

3.2.6.2 运算规则

1. 无符号数 高位处理：空出的高位用0填充 **低位处理：**移出边界的位被丢弃
2. 有符号数 ​ 高位处理：空出的高位用符号位填充（正数补0，负数补1） ​ 低位处理：移出边界的位被丢弃

3.2.6.3 运算效果

​ 右移n位相当于原数除以2的n次方（向下取整）

3.2.6.4 示例说明

正数右移
正数8的二进制：00001000
向右移动2位：  00000010 （结果为2）

计算验证：8 ÷ 2² = 8 ÷ 4 = 2

负数右移
负数-8的二进制补码：11111000
向右移动2位：      11111110 （结果为-2）

计算验证：-8 ÷ 2² = -8 ÷ 4 = -2

3.2.6.5 特殊情况

-1的二进制补码：11111111
向右移动1位：  11111111 （结果仍为-1）

-3的二进制补码：11111101
向右移动1位：  11111110 （结果为-2）

3.2.6.6 应用场景

1. 快速计算2的幂次除法
2. 某些算法中的性能优化

3.2.7.7 注意事项

1. 移动位数不应超过数据类型的位数
2. 有符号数右移时，符号位会被保留
3. 对于负数，右移结果不一定等于数学上的除法（由于补码表示和向下取整）

3.3 用位运算交换变量值

利用按位异或（^）的特性，可以在不使用临时变量的情况下交换两个变量的值，具体步骤如下：

1. a = a ^ b；此时 a 存储了 a 和 b 的差异信息。
2. b = a ^ b；将 a（已存储差异信息）与 b 进行异或，得到原来的 a 的值，并赋值给 b，此时 b 的值已更新为原来的 a。
3. a = a ^ b；将 a（存储差异信息）与新的 b（原来的 a）进行异或，得到原来的 b 的值，并赋值给 a，完成交换。
4. 示例：

 #include <stdio.h>
 int main() {
     int a = 5, b = 10;
     printf("交换前：a = %d, b = %d\n", a, b);
     a = a ^ b;
     b = a ^ b;
     a = a ^ b;
     printf("交换后：a = %d, b = %d\n", a, b); // 输出：交换后：a = 10, b = 5
     return 0;
 }

注意事项： 1. 这种方法仅适用于整数类型的变量，不适用于浮点型等其他类型。 2. 当两个变量指向同一块内存（即 a 和 b 是同一个变量）时，使用这种方法会导致变量值变为 0，因此需确保交换的是两个不同的变量。

3.4 位运算的优先级

优先级从高到低：

1. ** 按位取反（~）**
2. 左移（<<）、右移（>>）
3. 按位与（&）
4. ** 按位异或（^）**
5. 按位或（|） 建议： 复杂表达式中使用括号明确运算顺序 示例：

int a = 5, b = 3;
int c = a & b | 1; // 先计算 a & b，结果为 1，再计算 1 | 1，结果为 1
int d = a & (b | 1); // 先计算 b | 1，结果为 3，再计算 5 & 3，结果为 1

3.5 位运算的应用场景

• 数据压缩与加密
  • 哈夫曼编码、对称加密算法等
• 嵌入式编程
  • 操作硬件寄存器特定位
  • 控制GPIO引脚输入输出模式
• 图形处理
  • 取像素RGB分量
  • 调整颜色通道
• 高效计算
  • 判断奇偶：a & 1 比 a % 2 更快
  • 计算2的n次方：1 << n 比 pow(2, n) 更快

3.6 使用位运算的注意事项

• 符号位问题
  • 有符号数右移是算术右移
  • 建议使用无符号类型
• 溢出问题
  • 左移可能导致数据溢出
  • 不同编译器处理方式可能不同
• 可读性问题
  • 代码可读性较差
  • 应添加详细注释
• 跨平台兼容性
  • 注意不同平台的数据类型长度
  • 避免因位数差异导致错误

第4章 算法与算法描述

4.1 什么是算法

​ 算法是解决一个问题的一系列明确、可执行的步骤。就像做一道菜需要按照食谱一步步操作一样，算法也需要清晰的指令，才能解决问题。 一个算法应当具有以下特点： ​ （1） 有明确的输入和输出 ​ （2） 步骤清晰、不模糊
​ （3） 能在有限步骤内完成

4.2 算法的五大特性

特性	说明	举例
有穷性	算法必须在有限步骤后结束	计算1到100的和，只需100次加法
确定性	每个步骤的含义明确，没有歧义	"将a和b相加"是确定的
可行性	每一步都可以实际完成	计算平方和可行，计算无限小数不可行
输入	算法需要处理的数据	求最大值需要输入两个数
输出	算法处理后的结果	排序算法输出有序序列

4.3 如何评价算法好坏

• 正确性：能正确解决问题
• 可读性：容易理解和修改
• 时间效率：执行速度快慢
• 空间效率：占用内存多少

4.4 描述算法的四种方法

4.4.1 自然语言描述

用日常语言描述算法步骤，示例：求两个数的最大值

1. 输入两个数a和b
2. 比较a和b的大小
3. 如果a大于b，输出a；否则输出b
   • 优点：容易理解
   • 缺点：不够精确

4.4.2 流程图描述

用图形符号表示算法流程。 示例：求1到n的和

4.4.3 伪代码描述

​ 伪代码是一种介于自然语言和编程语言之间的算法描述方式。它忽略编程语言的语法细节，用简洁的语言描述算法的逻辑结构。伪代码更接近程序代码，便于将算法转换为具体的程序。 ​ **示例：**选择排序算法

算法：选择排序
输入：一个包含 n 个元素的数组 arr
输出：按升序排列的数组 arr
    
步骤：
1. 对于 i 从 0 到 n-2 执行：
     a. 设置 min_index = i
     b. 对于 j 从 i+1 到 n-1 执行：
           如果 arr[j] < arr[min_index]，则：
              设置 min_index = j
     c. 交换 arr[i] 和 arr[min_index] 的值
2. 返回排序后的数组 arr

###23.4.4 编程语言描述

用实际的编程语言实现算法。 示例：求最小公倍数(C++)

#include <iostream>
using namespace std;

int main() {
    int num1, num2;
    cout << "请输入两个整数：";
    cin >> num1 >> num2;
    
    int a = num1, b = num2;
    // 求最大公因数
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    int gcd = a;
    // 计算最小公倍数
    int lcm = (num1 * num2) / gcd;
    cout << "最小公倍数是：" << lcm << endl;
    return 0;
}

4.5 常见的算法思想

1. 枚举法
   • 核心思想：列出所有可能解，逐个检查验证
   • 适用场景：问题规模较小，解空间有限
   • 典型例子：找出1-100中的所有素数
   • 特点：简单直观，但效率较低
2. 递推法
   • 核心思想：从已知初始条件出发，根据递推关系逐步推导后续结果
   • 适用场景：具有明显递推关系的问题
   • 典型例子：斐波那契数列：1, 1, 2, 3, 5, 8...
   • 特点：顺序推进，避免重复计算
3. 递归法
   • 核心思想：将复杂问题分解为相似但规模较小的子问题
   • 关键要点：必须有明确的递归终止条件
   • 典型例子：计算阶乘：5! = 5 × 4 × 3 × 2 × 1
   • 特点：代码简洁，但需要注意栈溢出风险
4. 贪心算法
   • 核心思想：每一步都选择当前最优的解
   • 适用场景：局部最优能导致全局最优的问题
   • 典型例子：零钱兑换问题、活动安排问题
   • 特点：效率高，但不一定能得到全局最优解
5. 分治法
   • 核心思想：分而治之，将大问题分解为相互独立的子问题
   • 基本步骤：分解 → 解决 → 合并
   • 典型例子：快速排序、归并排序、二分查找
   • 特点：适合并行计算，能有效降低问题复杂度

第5章 一维数组

​ 在程序设计中，当需要处理多个相同类型的数据时，使用变量逐个存储会显得繁琐且低效。一维数组作为一种数据结构，能够存储一系列相同类型的元素，通过索引可以方便地访问和操作这些元素，是处理批量数据的重要工具。

5.1 一维数组的基本概念

​ 一维数组是由相同数据类型的元素组成的有序集合，这些元素在内存中连续存储，通过唯一的索引（下标） 来标识每个元素的位置。 重要特性：

• 索引从 0 开始，依次递增
• 例如一个包含5个元素的数组，其索引分别为 0、1、2、3、4

5.2 一维数组的定义

5.2.1 定义格式

基本格式： 数据类型 数组名[数组长度]； 各组成部分：

• 数据类型： 指定数组中元素的类型，可以是基本数据类型（如int、float、char等），也可以是构造数据类型
• 数组名： 遵循变量命名规则，用于标识数组
• 数组长度： 必须是一个正整数常量或常量表达式，用于指定数组中元素的个数 示例：

int scores[5];        // 定义一个包含5个int类型元素的数组scores
float weights[10];    // 定义一个包含10个float类型元素的数组weights
char letters[26];     // 定义一个包含26个char类型元素的数组letters

5.3 一维数组的初始化

​ 数组的初始化是指在定义数组的同时为其元素赋初值，这样可以避免数组元素初始值的不确定性。

5.3.1 完全初始化

​ 在定义数组时，为所有元素都赋予初值，此时可以省略数组长度，编译器会根据初值的个数自动确定数组长度。 示例：

int c[5] = {10, 20};          // 数组c的前2个元素分别为10、20，后3个元素均为0
char d[4] = {'A', 'B'};       // 数组d的前2个元素为'A', 'B', 后2个元素为'\0'

5.3.2 部分初始化

​ 在定义数组时，只为部分元素赋予初值。未被赋值的元素会被自动初始化为0（对于数值类型）或空字符（对于char类型）。 示例：

int c[5] = {10, 20};          // 数组c的前2个元素分别为10、20，后3个元素均为0
char d[4] = {'A', 'B'};       // 数组d的前2个元素为'A', 'B', 后2个元素为'\0'

5.4 一维数组元素的访问与修改

数组元素通过 "数组名[索引]" 的方式进行访问和修改。 ⚠️ 重要警告： 索引的取值范围是 0 到 数组长度-1，超出该范围的访问会导致数组越界，可能引发程序错误。

5.4.1 访问数组元素

示例：

int arr[3] = {100, 200, 300};
printf("%d\n", arr[0]);      // 访问数组arr的第0个元素，输出100
printf("%d\n", arr[2]);      // 访问数组arr的第2个元素，输出300

5.4.2 修改数组元素

示例：

float values[2] = {3.14, 1.59};
values[1] = 2.71;            // 将数组values的第1个元素修改为2.71
cout << values[1] << endl;   // 输出修改后的值2.71

5.5 一维数组的长度计算

​ 在C语言和C++语言中，可以通过size或者length运算符得到数组的长度。 示例：

int numbers[5] = {1, 2, 3, 4, 5};
int length = numbers.size()/numbers.length() // 一般使用size

5.6 一维数组的应用场景

5.6.1 存储批量数据

​ 存储一个班级学生的成绩、一组商品的价格等。 示例：

int scores[30];  // 存储30名学生的成绩

5.6.2 数据统计与分析

​ 计算数组中元素的总和、平均值、最大值、最小值等。 示例：

int sum = 0;
int arr[] = {6, 3, 8, 2};
for (int i = 0; i < 4; i++) {
    sum += arr[i];
}
// 计算得到数组元素的总和sum为19

5.6.3 排序与查找

​ 一维数组是排序和查找算法的常用数据结构，如对数组元素进行冒泡排序、选择排序，或在数组中查找指定元素等。 示例：选择排序（升序）

int nums[5] = {8, 1, 4, 2, 5};
for (int i = 0; i < 4; i++) {
    int minIndex = i;
    for (int j = i + 1; j < 5; j++) {
        if (nums[j] < nums[minIndex]) {
            minIndex = j;
        }
    }
    int temp = nums[i];
    nums[i] = nums[minIndex];
    nums[minIndex] = temp;
}
// 排序后数组为 {1, 2, 4, 5, 8}

5.7 使用一维数组的注意事项

1. 数组越界问题

   • 访问数组时，索引不能超出 0 到 数组长度-1 的范围
   • 超出范围会导致数组越界，可能修改其他变量的值或引发程序崩溃

2. 初始化问题

   • 局部数组若不初始化，元素值为随机值，使用前需确保已正确赋值
   • 全局数组和静态数组未初始化时，元素会被自动初始化为 0

3. 数组名的特性

   • 数组名代表数组的首地址，是一个常量指针

   • 不能对数组名进行赋值操作

   • 错误示例：

     int arr[3] = {1, 2, 3};
     arr = {4, 5, 6};  // ❌ 错误！数组名是常量指针，不能赋值
     

5.8 重点总结

要点	说明
定义格式	数据类型 数组名[长度];
索引范围	0 到 长度-1
初始化	完全初始化可省略长度，部分初始化未赋值元素为0
注意事项	防止越界、注意初始化、数组名是常量指针
核心优势	一维数组提供了高效、统一的方式来处理批量同类型数据，是程序设计中最基础且重要的数据结构之一。

第6章 字符串与字符数组

​ 在程序设计中，字符串是由字符组成的序列，常用于表示文本信息。在C语言中，字符串通常通过字符数组来实现；而在C++语言中，除了字符数组外，还提供了更便捷的string类来处理字符串。

6.1 字符数组与字符串的基本概念

6.1.1 字符数组

• 定义：元素类型为char的数组，用于存储多个字符；
• 特点：可以存储任意字符序列，包括不包含结束标志的字符集合；
• 示例：

char arr[3] = {'A', 'B', 'C'};  // 存储字符'A', 'B', 'C'的字符数组，无结束标志

6.1.2 字符串

• 定义：由字符组成的、以空字符'\0'（ASCII码值为0）作为结束标志的字符序列
• 实现方式：
  • C语言：通过字符数组实现
  • C++：既可以使用字符数组，也可以使用string类对象
• 示例：

char str1[6] = {'H', 'e', 'l', 'l', 'o', '\0'};  // 字符数组表示的字符串
char str2[] = "World";  // 直接赋值字符串常量，自动添加'\0'

6.2 字符数组的定义与初始化

6.2.1 C语言字符数组的定义与初始化

1. 逐个字符初始化
   • 指定每个元素的值，可包含'\0'作为结束标志
   • 示例：

char c1[6] = {'C', 'h', 'i', 'n', 'a', '\0'};  // 包含结束标志的字符数组（字符串）
char c2[3] = {'a', 'b', 'c'};  // 不包含结束标志的字符数组

1. 字符串常量初始化
   • 直接使用字符串常量赋值，编译器会自动在末尾添加'\0'
   • 数组长度可以省略，编译器会根据字符串长度自动确定（包含'\0'）
   • 示例：

char s1[] = "Hello";    // 数组长度为6 ('H', 'e', 'l', 'l', 'o', '\0')
char s2[10] = "Hi";     // 数组长度为10，前2个元素为'H', 'i', 其余为'\0'

6.2.2 C++语言中字符数组的定义与初始化

• 方式：与C语言相同
• 示例：

char cppStr1[] = "C++";                    // 自动添加'\0', 数组长度为4
char cppStr2[5] = {'P', 'r', 'o', 'g', '\0'};  // 包含结束标志的字符数组

6.3 字符串的输入与输出

6.3.1 C++语言中的输入输出

6.3.1.1 输出

1. 使用cout输出字符串
2. 直接使用<<运算符
3. 示例：

#include <iostream>
using namespace std;

int main() {
    char str[20] = "Hello";
    cout << str << endl;  // 输出: Hello
    return 0;
}

6.3.1.2 输入

#####6.3.1.2.1 cin-输入

1. 使用>>运算符输入字符串
2. 遇到空格或换行符停止
3. 自动添加'\0'
4. 示例：

char input[20];
cin >> input;        // 输入: C++, input存储"C++\0"
cout << input << endl;  // 输出: C++

#####6.3.1.2.2 getline函数

• 可以输入包含空格的完整字符串
• 遇到换行符停止
• 自动添加'\0'
• 示例：

char line[50];
cin.getline(line, 50);  // 输入: I love programming, line存储对应字符串
cout << line << endl;   // 输出: I love programming

#####6.3.1.2.3 string类的getline函数

• 用于C++的string类对象
• 需要包含<string>头文件
• 示例：

#include <string>
string s;
getline(cin, s);  // 输入包含空格的字符串到s

####6.3.1.2 输入安全注意事项

1. 对于字符数组，推荐使用cin.getline()而不是cin >>
2. cin.getline()可以指定最大读取长度，防止数组越界
3. 对于string类，使用getline(cin, str)更加安全方便

// 安全输入示例
char buffer[100];
cin.getline(buffer, 100);  // 安全，限制输入长度

string str;
getline(cin, str);         // 更安全，自动处理内存

6.4 字符串的处理函数

​ C语言的<string.h>头文件（C++中为<cstring>）提供了一系列用于处理字符串的函数：

6.4.1 求字符串长度：strlen

• 功能：计算字符串的长度（不包含结束标志\0）
• 格式：size_t strlen(const char *str);
• 示例：

	#include <string.h>
char s[] = "Hello";
int len = strlen(s);  // len的值为5

6.4.2 字符串复制：strcpy

• 功能：将源字符串复制到目标字符数组中，包括\0
• 格式：char *strcpy(char *dest, const char *src);
• 注意：⚠️ 目标字符数组必须有足够的空间容纳源字符串
• 示例：

char dest[20];
char src[] = "Copy me";
strcpy(dest, src);  // dest存储"Copy me\0"

6.4.3 字符串连接：strcat

• 功能：将源字符串连接到目标字符串的末尾
• 格式：char *strcat(char *dest, const char *src);
• 注意：⚠️ 目标字符数组必须有足够的空间容纳连接后的字符串
• 示例：

char dest[20] = "Hello";
char src[] = "World";
strcat(dest, src);  // dest存储"Hello World\0"

6.4.4 字符串比较：strcmp

• 功能：按照ASCII码值比较两个字符串的大小
• 格式：int strcmp(const char *s1, const char *s2);
• 返回值：
  • 若s1大于s2，返回正整数
  • 若s1等于s2，返回0
  • 若s1小于s2，返回负整数
• 示例：

int res1 = strcmp("apple", "banana");  // res1为负 ("apple" < "banana")
int res2 = strcmp("hello", "hello");   // res2为0（相等）

6.4.5 字符串比较（指定长度）：strncmp

• 功能：比较两个字符串的前n个字符
• 格式：int strncmp(const char *s1, const char *s2, size_t n);
• 示例：

int res = strncmp("abcde", "abcfg", 3);  // 比较前3个字符，res为0 ("abc" == "abc")

6.5 C++中的string类

​ C++的<string>头文件提供了string类，封装了字符串的操作，使用更便捷、安全。

6.5.1 string对象的定义与初始化

#include <string>
using namespace std;

string s1;                  // 空字符串
string s2 = "Hello";        // 初始化字符串为"Hello"
string s3(s2);              // 复制s2的值给s3
string s4(5, 'A');          // 初始化为由5个'A'组成的字符串"AAAAA"

6.5.2 string类的常用操作

1. 长度与容量操作

   • length()或size()方法：返回字符串长度

   • empty()方法：判断字符串是否为空

   • 示例：

     string s = "Hello";
     int len = s.length();        // len = 5
     bool isEmpty = s.empty();    // isEmpty = false
     

2. 字符串连接操作

   • 使用+运算符进行字符串拼接

   • 使用+=运算符进行字符串追加

   • 示例：

     string s1 = "Hello", s2 = "World";
     string s3 = s1 + s2;        // s3 = "Hello World"
     s1 += s2;                   // s1 = "Hello World"
     

3. 字符串访问操作

   • 使用[]运算符通过索引访问字符

   • 使用at()方法访问字符（会检查越界，更安全）

   • 示例：

     string s = "Test";
     char c1 = s[1];             // c1 = 'e'
     char c2 = s.at(2);          // c2 = 's'
     

4. 字符串比较操作

   • 直接使用关系运算符：==, !=, <, >, <=, >=

   • 按字典序比较字符串大小

   • 示例：

     string s1 = "apple", s2 = "banana";
     bool equal = (s1 == s2);    // equal = false
     bool less = (s1 < s2);      // less = true
     

5. 字符串查找操作

   • find()方法：查找子串，返回子串起始位置

   • 未找到时返回string::npos

   • 示例：

     string s = "Hello World";
     size_t pos = s.find("World");  // pos = 6
     if (pos != string::npos) {
         // 找到子串的处理逻辑
     }
     

6.6 使用字符数组与字符串的注意事项

1. 结束标志'\0'的重要性

   • 使用字符数组处理字符串时，必须确保字符串以'\0'结尾
   • 缺少结束标志会导致字符串处理函数出现不可预测的行为
   • 字符串常量初始化时会自动添加'\0'

2. 数组越界防护

   • 字符数组的长度必须足够容纳字符串内容及'\0'
   • 使用strcpy、strcat等函数前要确保目标数组有足够空间
   • 推荐使用strncpy等安全版本函数

3. 安全的字符串输入

   • 对于字符数组输入，推荐使用cin.getline()而不是cin >>

   • cin.getline()可以指定最大读取长度，防止数组越界

   • 对于string类，使用getline(cin, str)更加安全方便

   • 安全输入示例：

     // 字符数组安全输入
     char buffer[100];
     cin.getline(buffer, 100);
     
     // string类安全输入
     string str;
     getline(cin, str);
     

4. string类与字符数组的转换

   • string类可以通过c_str()方法转换为C风格字符串

   • 转换后的指针是只读的，不能修改其内容

   • 示例：

     string s = "Hello";
     const char *cstr = s.c_str();  // 转换为const char*类型的字符数组
     

5. string类的优势

   • 自动管理内存，无需担心数组越界
   • 提供丰富的成员函数，操作更便捷
   • 支持运算符重载，语法更直观
   • 推荐在C++程序中使用string类替代字符数组

6.7 重点总结

要点	说明
基本概念	字符数组存储字符序列，字符串以\0结尾
初始化	字符串常量初始化自动添加\0
输入输出	C语言用printf/scanf，C++用cout/cin，注意安全输入
处理函数	strlen、strcpy、strcat、strcmp等
string类	C++中更安全便捷的字符串处理方式
注意事项	确保\0结尾、防止越界、注意输入安全
核心要点	理解字符数组与字符串的区别，掌握C风格字符串函数的使用，熟练运用C++的string类进行字符串操作。

第7章 枚举算法

​ 枚举算法（Enumeration Algorithm）也称为穷举算法。它通过逐一列举问题所有可能的解，并对每个可能的解进行验证，从而找出符合条件的解。这种算法思路简单直接，在解决规模较小或解空间有限的问题时非常有效。

7.1 枚举算法的基本概念

1. 算法定义
   • 枚举算法通过遍历所有可能解来寻找问题的答案
   • 按照一定的顺序或规则，不重复、不遗漏地列出所有候选解
   • 根据问题的约束条件判断每个候选解是否为有效解
2. 典型应用场景
   • 找出1到100之间所有能被7整除的数
   • 求解百钱百鸡等经典数学问题
   • 寻找素数、水仙花数等特殊数字

7.2 枚举算法的核心思想与基本步骤

7.2.1 核心思想

1. 利用计算机运算速度快的特点
2. 通过全面排查所有可能的情况来寻找问题的解
3. 不需要复杂的逻辑推理，只需明确解空间和判断条件

7.2.2 基本步骤

1. 确定解的范围
   • 明确问题中可能解的取值范围
   • 确定枚举的对象和上下边界
   • 确保不遗漏任何可能的解，同时避免不必要的范围扩大
2. 确定判断条件
   • 根据问题的要求，制定判断候选解是否为有效解的条件
3. 枚举并验证
   • 按照一定的顺序遍历解的范围中的每个候选解
   • 将候选解代入判断条件进行验证
4. 收集有效解
   • 将符合判断条件的候选解收集起来
   • 作为问题的最终结果输出

7.3 枚举算法的优缺点

7.3.1 优点

1. 思路简单
   • 容易理解和实现
   • 不需要复杂的算法设计技巧
   • 适合初学者掌握
2. 可靠性高
   • 只要解的范围确定准确，且判断条件正确
   • 就能保证找到所有符合条件的解
   • 不会遗漏任何有效解
3. 适用范围广
   • 可用于解决多种类型的问题
   • 如查找、计数、判断等各类问题

7.3.2 缺点

1. 效率较低
   • 当解的范围较大时，需要遍历大量的候选解
   • 运算量会急剧增加
   • 可能导致程序运行时间过长
2. 资源消耗大
   • 在处理大规模问题时，会占用较多的计算机资源
   • 包括CPU时间和内存等资源

7.4 枚举算法的应用示例

7.4.1 找出1到100之间的所有素数

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    cout << "1到100之间的素数有：" << endl;
    
    // 枚举1到100之间的每个数
    for (int num = 1; num <= 100; num++) {
        int isPrime = 1; // 假设当前数是素数，初始化为1
        
        // 判断该数是否为素数
        if (num <= 1) {
            isPrime = 0; // 1及以下不是素数
        } else {
            // 从2到sqrt(num)依次判断是否能整除
            for (int i = 2; i <= sqrt(num); i++) {
                if (num % i == 0) {
                    isPrime = 0; // 能被整除，不是素数
                    break; // 跳出内层循环，无需继续判断
                }
            }
        }
        
        // 若是素数则输出
        if (isPrime) {
            cout << num << " ";
        }
    }
    cout << endl;
    return 0;
}

7.4.2 求解百钱百鸡问题

问题描述：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？

#include <iostream>
using namespace std;

int main() {
    int x, y, z; // x为鸡翁数量，y为鸡母数量，z为鸡雏数量
    
    // 枚举鸡翁可能的数量（0到20，因为5*20=100）
    for (x = 0; x <= 20; x++) {
        // 枚举鸡母可能的数量（0到33，因为3*33≈100）
        for (y = 0; y <= 33; y++) {
            z = 100 - x - y; // 鸡雏数量由总数量得出
            
            // 验证是否满足钱数条件
            if (5 * x + 3 * y + z / 3 == 100 && z % 3 == 0) {
                cout << "鸡翁：" << x << ", 鸡母：" << y << ", 鸡雏：" << z << endl;
            }
        }
    }
    return 0;
}

7.4.3 找出1到50之间所有能同时被3和5整除的数

#include <iostream>
using namespace std;

int main() {
    cout << "1到50之间能同时被3和5整除的数有：" << endl;
    
    // 枚举1到50之间的每个数
    for (int i = 1; i <= 50; i++) {
        // 验证是否能同时被3和5整除
        if (i % 3 == 0 && i % 5 == 0) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

7.4.4 求解水仙花数

问题描述：水仙花数是指一个三位数，其各位数字的立方和等于该数本身（如153 = 1³ + 5³ + 3³）。

#include <iostream>
using namespace std;

int main() {
    cout << "所有的水仙花数有：" << endl;
    
    // 枚举所有三位数（100到999）
    for (int num = 100; num <= 999; num++) {
        int hundreds = num / 100;        // 百位数字
        int tens = (num / 10) % 10;      // 十位数字
        int units = num % 10;            // 个位数字
        
        // 验证是否为水仙花数
        if (hundreds * hundreds * hundreds + 
            tens * tens * tens + 
            units * units * units == num) {
            cout << num << " ";
        }
    }
    cout << endl;
    return 0;
}

7.5 使用枚举算法的注意事项

1. 明确解的范围
   • 必须准确界定解的取值范围
   • 范围过小可能遗漏解，范围过大则会降低效率
   • 通过问题的约束条件合理缩小范围
2. 优化枚举顺序
   • 合理调整枚举的顺序可以提高算法效率
   • 优先枚举范围较小的变量
   • 可减少嵌套循环的层数和次数
3. 简化判断条件
   • 判断条件的复杂程度会影响算法效率
   • 应尽量简化判断条件，减少不必要的计算
4. 避免重复枚举
   • 确保枚举过程中每个候选解只被检查一次
   • 避免重复操作，以提高效率

7.6 重点总结

要点	说明
核心思想	遍历所有可能解，通过验证找到正确答案
适用场景	解空间有限、问题规模较小的情况
基本步骤	确定范围→制定条件→枚举验证→收集结果
主要优点	思路简单、可靠性高、适用范围广
主要缺点	效率较低、资源消耗大
优化策略	合理确定范围、优化枚举顺序、简化判断条件
核心要点：枚举算法是最简单直接的算法设计方法，虽然效率不高，但在解决小规模问题时非常实用，是算法学习的重要基础。

第8章 模拟算法

​ 模拟算法（Simulation Algorithm）是一种通过模仿现实问题的运行过程或操作步骤来求解问题的算法。它按照问题所描述的规则或流程，一步一步地进行计算和操作，最终得到问题的结果。

8.1 模拟算法的基本概念

1. 算法定义

   • 模拟算法通过模仿现实过程来求解问题
   • 严格遵循问题的实际操作流程或自然规律
   • 将问题的每一个步骤转化为对应的代码指令

2. 核心特征

   • 按部就班：严格按照步骤执行
   • 忠实再现：真实反映问题过程
   • 过程导向：关注整个执行流程

3. 典型应用场景

   • 计算物体自由下落过程
   • 模拟物理运动规律
   • 游戏逻辑实现
   • 系统流程仿真

8.2 模拟算法的核心思想与基本步骤

8.2.1 核心思想

1. 对问题的实际运行过程进行忠实再现
2. 不需要复杂的逻辑推理或数学建模
3. 将问题的步骤、规则转化为可执行的代码

8.2.2 基本步骤

1. 分析问题流程

   • 详细理解问题所描述的操作步骤、规则或过程
   • 明确每个步骤的输入、输出以及执行条件

2. 抽象关键要素

   • 提取问题中的关键变量和数据
   • 记录过程中的状态变化（如时间、位置、数量等）

3. 编写模拟逻辑

   • 将每个步骤转化为对应的代码逻辑
   • 通过循环、分支等语句实现步骤的依次执行

4. 跟踪状态变化

   • 实时更新关键变量的值
   • 记录过程中的重要状态
   • 确保与问题的实际运行一致

5. 输出结果

   • 当模拟过程达到终止条件时
   • 根据记录的状态或计算结果输出答案

8.3 模拟算法的优缺点

8.3.1 优点

1. 直观易懂

   • 直接对应问题的实际过程
   • 逻辑清晰，易于理解和实现
   • 特别适合描述性强的问题

2. 适用性广

   • 只要问题的流程明确，都可以用模拟算法求解
   • 适用于物理过程、逻辑操作、规则游戏等各类问题

3. 实现简单

   • 不需要掌握复杂的算法设计技巧
   • 只需按照步骤翻译为代码即可
   • 对初学者友好

8.3.2 缺点

1. 效率可能较低

   • 对于步骤繁多、过程复杂的问题
   • 需要执行大量的操作
   • 可能导致程序运行时间过长

2. 对细节敏感

   • 如果对问题流程的理解存在偏差
   • 或遗漏某个步骤
   • 会直接导致模拟结果错误

3. 资源消耗大

   • 当模拟的过程涉及大量状态记录
   • 或长时间的步骤推进
   • 可能占用较多的内存和CPU资源

8.4 模拟算法的应用示例

8.4.1 模拟掷骰子游戏

问题描述：掷两个骰子，记录每次掷出的点数之和，连续掷10次，输出每次的结果以及点数之和为7的次数。

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    srand(time(0)); // 初始化随机数种子
    int count = 0;  // 记录点数之和为7的次数
    
    cout << "10次掷骰子的结果：" << endl;
    
    for (int i = 0; i < 10; i++) {
        // 模拟掷两个骰子（点数为1-6）
        int dice1 = rand() % 6 + 1;
        int dice2 = rand() % 6 + 1;
        int sum = dice1 + dice2;
        
        cout << "第" << i + 1 << "次: " << dice1 << " + " << dice2 << " = " << sum << endl;
        
        if (sum == 7) {
            count++;
        }
    }
    
    cout << "点数之和为7的次数: " << count << endl;
    return 0;
}

8.4.2 模拟银行排队叫号

问题描述：银行有3个窗口，每个窗口每次只能服务1位客户，服务时间为1-5分钟。现有5位客户依次排队，按照"先到先服务"的原则，分配到当前最早空闲的窗口。

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    srand(time(0)); // 初始化随机数种子
    int windows[3] = {0}; // 记录每个窗口的空闲时间（初始为0）
    int customers = 5;     // 客户数量
    
    cout << "客户服务情况：" << endl;
    
    for (int i = 0; i < customers; i++) {
        int serviceTime = rand() % 5 + 1; // 服务时间1-5分钟
        
        // 找到最早空闲的窗口
        int minTime = windows[0];
        int windowIndex = 0;
        
        for (int j = 1; j < 3; j++) {
            if (windows[j] < minTime) {
                minTime = windows[j];
                windowIndex = j;
            }
        }
        
        int startTime = windows[windowIndex];     // 开始时间为窗口空闲时间
        int endTime = startTime + serviceTime;    // 结束时间
        windows[windowIndex] = endTime;           // 更新窗口空闲时间
        
        cout << "客户" << i + 1 << ": 窗口" << windowIndex + 1 
             << ", 开始时间" << startTime << ", 结束时间" << endTime << endl;
    }
    return 0;
}

8.4.3 模拟时钟走动

问题描述：模拟一个时钟，从当前时间开始，每秒更新一次时间（时、分、秒），输出10秒内的时间变化。

#include <iostream>
#include <chrono>
#include <thread>
using namespace std;

int main() {
    int h = 12, m = 30, s = 0; // 初始时间 12:30:00
    
    cout << "10秒内的时间变化：" << endl;
    
    for (int i = 0; i < 10; i++) {
        // 输出当前时间
        printf("%02d:%02d:%02d\n", h, m, s);
        
        // 等待1秒
        this_thread::sleep_for(chrono::seconds(1));
        
        // 更新时间
        s++;
        if (s == 60) {
            s = 0;
            m++;
            if (m == 60) {
                m = 0;
                h++;
                if (h == 24) {
                    h = 0;
                }
            }
        }
    }
    return 0;
}

8.4.4 模拟小球反弹

问题描述：一个小球从10米高处自由落下，每次落地后反弹回原高度的一半，再落下。模拟小球第5次落地时经过的总路程和第5次反弹的高度。

#include <iostream>
using namespace std;

int main() {
    double height = 10.0;      // 初始高度
    double totalDistance = 0.0; // 总路程
    int times = 5;             // 落地次数
    
    for (int i = 0; i < times; i++) {
        // 下落的距离
        totalDistance += height;
        
        // 反弹高度（除最后一次落地外）
        if (i < times - 1) {
            height /= 2;
            totalDistance += height; // 反弹上升的距离
        }
    }
    
    cout << "第5次落地时总路程：" << totalDistance << "米" << endl;
    cout << "第5次反弹的高度：" << height / 2 << "米" << endl;
    return 0;
}

8.5 使用模拟算法的注意事项

1. 精准理解问题
   • 模拟算法的正确性完全依赖于对问题流程的准确理解
   • 仔细分析每一个步骤，特别是初始条件和边界条件
   • 避免因遗漏或误解导致错误
2. 合理设计变量
   • 选择合适的变量记录过程中的状态
   • 变量的类型和初始值要符合问题场景
   • 确保数值的合理性（如时间不能为负）
3. 控制循环边界
   • 确保循环的开始和结束条件正确
   • 避免无限循环或提前终止
   • 正确处理边界情况
4. 优化时间复杂度
   • 对于步骤较多的问题，减少不必要的计算
   • 合并重复步骤来提高效率
   • 在保证正确性的前提下进行优化
5. 处理随机情况
   • 合理使用随机数生成函数
   • 注意初始化随机数种子以保证随机性
   • 在C++中推荐使用<random>库
6. 调试与验证
   • 通过输出中间状态来验证每一步的正确性
   • 便于排查错误和理解过程

// 调试示例：输出模拟过程中的中间状态
#include <iostream>
using namespace std;

int main() {
    int n = 5;
    int sum = 0;
    
    for (int i = 1; i <= n; i++) {
        sum += i;
        cout << "累加第" << i << "个数后，和为：" << sum << endl; // 输出中间状态
    }
    
    cout << "最终结果：" << sum << endl;
    return 0;
}

8.6 重点总结

要点	说明
核心思想	忠实再现问题的实际运行过程
适用场景	流程明确、步骤清晰的各类问题
基本步骤	分析流程→抽象要素→编写逻辑→跟踪状态→输出结果
主要优点	直观易懂、适用性广、实现简单
主要缺点	效率可能较低、对细节敏感、资源消耗大
关键技巧	精准理解问题、合理设计变量、控制循环边界、优化时间效率

核心要点：模拟算法是最贴近实际问题的算法设计方法，通过逐步执行问题描述的流程来获得解决方案，虽然效率可能不高，但在理解问题和验证方案时具有独特优势。

第9章 字符串相关算法

概述

​ 字符串算法主要用于处理文本的查找、替换、匹配等操作，在文本处理、数据解析和编程竞赛等场景中应用广泛。

9.1 字符串反转算法

**问题：**输入一个字符串，将字符串中的字符顺序颠倒： 算法步骤

1. 输入阶段
   • 读取用户输入的字符串 s
2. 准备工作
   • 获取字符串长度 n
   • 创建空字符串 c 用于存储反转结果
3. 反转操作
   • 从字符串最后一个字符开始（索引 n-1）
   • 向前遍历到第一个字符
   • 将每个字符依次添加到结果字符串 c 中
4. 输出结果
   • 输出反转后的字符串 c

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> s;           // 输入字符串   
    int n = s.size();   // 获取字符串长度
    string c = "";      // 创建空字符串用于存储反转结果
    // 从字符串末尾向前遍历（修正后的循环条件）
    for(int i = n-1; i >= 0; i--){
        c += s[i];      // 将当前字符添加到结果字符串
    }
    cout << c;          // 输出反转后的字符串
    return 0;
}

9.2字符串大小写转换

**问题：**输入一个字符串，将字符串中的每个字符在大写和小写之间进行转换： 算法步骤

1. 输入阶段
   • 读取用户输入的字符串 s
2. 准备工作
   • 获取字符串长度 n
3. 大小写互换
   • 遍历字符串中的每个字符
   • 对每个字符进行判断：
     • 如果是大写字母（A-Z）：转换为小写（ASCII码加32）
     • 否则：转换为大写（ASCII码减32）
4. 输出结果
   • 输出转换后的字符串

#include<bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;           // 输入字符串
    int n = s.size();   // 获取字符串长度

    // 遍历字符串中的每个字符
    for(int i = 0; i < n; i++) {
        // 判断当前字符是否为大写字母
        if(s[i] >= 'A' && s[i] <= 'Z'){
            s[i] = s[i] + 32;  // 大写转小写：ASCII码加32
        } else {
            s[i] = s[i] - 32;  // 小写转大写：ASCII码减32
        }
    }
    cout << s;  // 输出转换后的字符串
    return 0;
}

9.3 字符串去空格

**问题：**去除字符串中的空格（包括前导空格、尾随空格和中间连续空格）：

解题步骤：

1. 输入阶段
   • 使用 getline(cin, s) 读取整行输入，可以包含空格
   • 如果用 cin >> s 则遇到空格会停止读取
2. 准备工作
   • 获取字符串长度 n
   • 创建空字符串 c 用于存储结果
3. 去空格处理
   • 遍历原字符串中的每个字符
   • 检查当前字符是否为空格：
     • 如果不是空格：添加到结果字符串 c
     • 如果是空格：跳过，不添加到结果字符串
4. 输出结果
   • 输出去空格后的字符串 c

#include<bits/stdc++.h>
using namespace std;

int main() {
    string s;
    getline(cin, s);  // 读取整行输入（包含空格）
    int n = s.size();  // 获取字符串长度
    
    string c = "";     // 创建空字符串用于存储去空格后的结果
    
    // 遍历原字符串中的每个字符
    for(int i = 0; i < n; i++) {
        // 如果当前字符不是空格，则添加到结果字符串
        if(s[i] != ' '){
            c += s[i];  // 将非空格字符添加到结果字符串
        }
    }
    
    cout << c;  // 输出去空格后的字符串
    return 0;
}

9.4 字符串分割算法

**问题：**将字符串按照指定的分隔符拆分成多个子串： 算法步骤

1. 输入阶段
   • 使用 getline() 读取整行字符串（可包含空格）
   • 使用 cin 读取分隔符字符
2. 初始化工作
   • 获取字符串长度
   • 初始化临时字符串 c 为空
   • 初始化子串计数器 x 为 0
3. 分割处理
   • 遍历字符串中的每个字符：
     • 如果不是分隔符：将字符添加到临时字符串 c
     • 如果遇到分隔符或到达字符串末尾：
       • 将当前临时字符串 c 存入数组 arr
       • 计数器 x 加 1
       • 重置临时字符串 c 为空
4. 输出结果
   • 遍历数组 arr，输出所有分割出的子串
   • 子串之间用空格分隔

#include<bits/stdc++.h>
using namespace std;
string arr[100100];  // 定义字符串数组，用于存储分割后的子串

int main() {
    string s;
    getline(cin, s);  // 读取整行输入字符串
    char e;
    cin >> e;         // 读取分隔符字符
    
    int n = s.size(); // 获取字符串长度
    
    string c = "";    // 临时字符串，用于构建当前子串
    int x = 0;        // 计数器，记录分割出的子串数量
    
    // 遍历字符串进行分割
    for(int i = 0; i < n; i++) {
        // 如果当前字符不是分隔符，添加到临时字符串
        if(s[i] != e){
            c += s[i];
        }
        
        // 如果遇到分隔符或者到达字符串末尾，保存当前子串
        if(s[i] == e || i == n-1){
            arr[x++] = c;  // 将当前子串存入数组，并增加计数器
            c = "";        // 重置临时字符串
        }
    }
    
    // 输出所有分割出的子串，用空格分隔
    for(int i = 0; i < x; i++){
        cout << arr[i] << ' '; 
    } 
    
    return 0;
}

9.5 字符串查找算法

9.5.1 查找字符

在字符串中查找指定字符第一次出现的位置。 算法步骤

1. 初始化阶段
   • 定义要搜索的字符串 s
   • 定义要查找的目标字符 target
   • 获取字符串长度 n
2. 变量定义
   • flag：标记是否找到目标字符（0=未找到，1=找到）
   • v：存储找到的位置值
3. 遍历搜索
   • 使用for循环逐个检查字符串中的每个字符
   • 从索引0开始，到n-1结束
   • 对每个字符与目标字符进行比较
4. 匹配判断
   • 如果当前字符等于目标字符：
     • 设置flag为1（表示找到）
     • 记录位置v = i + 1（从1开始计数）
     • 立即跳出循环（break）
5. 结果输出
   • 检查flag的值：
     • 如果为1：输出找到的位置v
     • 如果为0：输出"不存在"

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "hello";  // 定义要搜索的字符串
    char target = 'l';   // 定义要查找的目标字符
    
    int n = s.size();    // 获取字符串长度
    
    // 定义标志变量
    int flag = 0;        // 标记是否找到目标字符：0-未找到，1-找到
    int v = 0;           // 存储找到的位置（从1开始计数）
    
    // 遍历字符串查找字符
    for (int i = 0; i < n; i++) {
        if (s[i] == target) {  // 如果当前字符等于目标字符
            flag = 1;          // 设置找到标志
            v = i + 1;         // 记录位置（从1开始计数）
            break;             // 找到后立即退出循环
        }
    } 
    
    // 根据查找结果输出
    if(flag){
        cout << v;             // 输出找到的位置
    }else{
        cout << "不存在";      // 输出未找到的提示
    }
    
    return 0;
}

9.6 字符串替换算法

​ 将字符串中指定的子串替换为新的子串。 解题步骤：

1. 输入处理
   • 读取三个字符串：原字符串 s、查找串 s1、替换串 s2
   • 计算各字符串的长度
2. 遍历字符串
   • 从左到右扫描原字符串 s
   • 对每个位置检查是否可能是 s1 的开始
3. 模式匹配
   • 当遇到与 s1[0] 相同的字符时
   • 提取从当前位置开始、长度为 m 的子串
   • 比较该子串是否完全匹配 s1
4. 替换操作
   • 如果匹配成功，用 s2 替换该段内容
   • 替换时逐个字符覆盖原字符串
5. 位置调整
   • 替换完成后，跳过已处理的部分
   • 避免重复检查刚刚替换的内容

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s,s1,s2;
    cin>>s>>s1>>s2;  // 输入原字符串s，要查找的子串s1，替换成的子串s2
    
    int n=s.size();    // 原字符串长度
    int m=s1.size();   // 要查找的子串长度
    int k=s2.size();   // 替换子串长度
    
    // 遍历原字符串
    for(int i=0;i<n;i++){
        // 如果当前字符与s1的第一个字符匹配
        if(s[i]==s1[0]){
            string c="";  // 临时字符串，用于存储可能的匹配子串
            
            // 从当前位置i开始，提取长度为m的子串
            for(int j=i;j<i+m;j++){
                c+=s[j];
            }
            
            // 检查提取的子串是否等于s1
            if(c==s1){
                // 如果匹配，进行替换操作
                for(int j=i;j<i+k;j++){
                    s[j]=s2[j-i];  // 用s2的字符替换原字符串中的字符
                }
                // 跳过已替换的部分，避免重复处理
                i=i+k-1;
            }
        }
    }
    cout<<s;  // 输出替换后的字符串
    return 0;
}