# GESP 三级编程能力认证讲义

## 第一模块：数据编码与进制转换

### 1. 知识点拆解
*   **进制转换**：
    *   **N进制转十进制**：按权展开法（如二进制 $1011 = 1\times 2^3 + 0\times 2^2 + 1\times 2^1 + 1\times 2^0$）。
    *   **十进制转N进制**：除N取余法。
    *   **二进制与八/十六进制**：3位二进制对应1位八进制；4位二进制对应1位十六进制。
*   **原码、反码、补码**：
    *   计算机内部使用**补码**存储整数。
    *   **正数**：三码合一（全部相同）。
    *   **负数**：
        *   原码：最高位为1表示负数。
        *   反码：原码符号位不变，其余各位取反。
        *   补码：反码 $+ 1$。

### 2. 具体例子
**例子 1.1**：求 $-5$ 的补码（假设用 8 位二进制表示）。
1.  正数 $5$ 的原码：`0000 0101`
2.  $-5$ 的原码：`1000 0101`
3.  $-5$ 的反码：`1111 1010`
4.  $-5$ 的补码：`1111 1011`（即反码+1）

### 3. 练习巩固
1.  **【简单】单选题**：十六进制数 `0x1F` 转换成十进制数是（ ）。
    A. 15  B. 25  C. 31  D. 32
2.  **【中等】对错题**：在 8 位二进制下，补码 `1111 1111` 对应的十进制整数是 $-1$。（ ）
3.  **【困难】填空题**：一个十进制整数 $-13$，在计算机内部用 8 位补码表示为 `____________`。

---

## 第二模块：位运算

### 1. 知识点拆解
*   **常用运算符**：
    *   `&`（按位与）：同为 1 则为 1。
    *   `|`（按位或）：有一个为 1 则为 1。
    *   `^`（按位异或）：相同为 0，不同为 1（**重要特性：a^a=0, a^0=a**）。
    *   `~`（按位非）：0变1, 1变0。
    *   `<<`（左移）：$a << n$ 相当于 $a \times 2^n$。
    *   `>>`（右移）：$a >> n$ 相当于 $a / 2^n$。

### 2. 具体例子
**例子 2.1**：利用异或交换两个变量 `a` 和 `b` 的值（不使用临时变量）。
```cpp
a = a ^ b;
b = a ^ b; // 此时 b = (a^b)^b = a
a = a ^ b; // 此时 a = (a^b)^a = b
```

### 3. 练习巩固
1.  **【简单】单选题**：表达式 `5 & 3` 的值是（ ）。
    A. 1  B. 7  C. 0  D. 5
2.  **【中等】填空题**：若 `int n = 8;`，则 `n >> 2` 的结果是 ______，`n << 1` 的结果是 ______。
3.  **【困难】阅读程序写结果**：
    ```cpp
    int a = 12, b = 10;
    int res = (a ^ b) & a;
    cout << res;
    ```
    输出：__________

---

## 第三模块：一维数组与字符串

### 1. 知识点拆解
*   **一维数组**：连续空间，下标从 0 开始。`int a[10]` 的有效下标是 0-9。
*   **字符串（string）**：
    *   `s.size()` 或 `s.length()`：获取长度。
    *   `s[i]`：访问单个字符。
    *   `s1 + s2`：拼接字符串。
    *   `getline(cin, s)`：读入带空格的一整行。

### 2. 具体例子
**例子 3.1**：统计字符串中数字字符出现的次数。
```cpp
string s = "GESP2024";
int cnt = 0;
for(int i = 0; i < s.size(); i++) {
    if(s[i] >= '0' && s[i] <= '9') cnt++;
}
```

### 3. 练习巩固
1.  **【简单】对错题**：定义 `int a[5];` 后，访问 `a[5]` 会导致数组下标越界错误。（ ）
2.  **【中等】单选题**：已知 `string s = "ABCDE";`，执行 `s = s.substr(1, 3);` 后，`s` 的值是（ ）。
    A. "ABC"  B. "BCD"  C. "CDE"  D. "BCDE"
3.  **【困难】阅读程序填空**：以下程序的功能是倒置数组元素，请补全代码。
    ```cpp
    int a[5] = {1, 2, 3, 4, 5};
    for(int i = 0; i < 5 / 2; i++) {
        int temp = a[i];
        a[i] = ___________;
        a[4-i] = temp;
    }
    ```

---

## 第四模块：算法初步（枚举与模拟）

### 1. 知识点拆解
*   **枚举法（暴力法）**：根据已知条件，逐一列举所有可能的答案并验证。
    *   三要素：范围、约束条件、结果判定。
*   **模拟法**：题目怎么说，代码就怎么写。用代码逻辑“复现”题目的过程。
*   **算法描述**：
    *   自然语言：大白话。
    *   流程图：图形化。
    *   伪代码：类代码格式，不强调语法，强调逻辑。

### 2. 具体例子
**例子 4.1（枚举）**：百钱买百鸡。公鸡5元，母鸡3元，小鸡1元3只。求所有方案。
```cpp
for(int x = 0; x <= 20; x++) { // 枚举公鸡数量
    for(int y = 0; y <= 33; y++) { // 枚举母鸡数量
        int z = 100 - x - y; // 剩余为小鸡
        if(z % 3 == 0 && 5*x + 3*y + z/3 == 100) {
            // 找到一组解
        }
    }
}
```

### 3. 练习巩固
1.  **【简单】单选题**：以下哪种算法描述方式不属于计算机程序，但能清晰表达逻辑且不受编程语言限制？
    A. 源码  B. 伪代码  C. 目标程序  D. 编译器
2.  **【中等】填空题（枚举逻辑）**：若要枚举所有的三位水仙花数（各数字立方和等于本身），循环变量 `i` 的范围应该是从 ______ 到 ______。
3.  **【困难】编程模拟逻辑填空**：模拟蜗牛爬树。树高 `H` 米，白天爬 `U` 米，晚上坠落 `D` 米。求第几天爬到顶。
    ```cpp
    int H = 10, U = 3, D = 1, day = 0, height = 0;
    while(true) {
        day++;
        height += U;
        if(height >= H) break; 
        height -= D;
    }
    // 最终 day 的值是 ______。
    ```

---

## 教练参考答案与解析

### 第一模块
1.  **C**。$1 \times 16^1 + 15 \times 16^0 = 16 + 15 = 31$。
2.  **对**。补码 `1111 1111` 为负数，逆向推导：减1得 `1111 1110`，取反得 `1000 0001`（即 $-1$）。
3.  **11110011**。13原码 `0000 1101` -> -13原码 `1000 1101` -> 反码 `1111 0010` -> 补码 `1111 0011`。

### 第二模块
1.  **A**。`101(5) & 011(3) = 001(1)`。
2.  **2**（$8/4$）；**16**（$8 \times 2$）。
3.  **4**。`12(1100) ^ 10(1010) = 0110(6)`；`0110(6) & 1100(12) = 0100(4)`。

### 第三模块
1.  **对**。长度为 5，最大下标是 4。
2.  **B**。`substr(起始位置, 长度)`，从下标 1 ('B') 开始截取 3 个，即 "BCD"。
3.  **a[4-i]**。这是经典的交换逻辑。

### 第四模块
1.  **B**。
2.  **100** 到 **999**。
3.  **5**。
    *   Day 1: 0+3=3, 3<10, 3-1=2
    *   Day 2: 2+3=5, 5<10, 5-1=4
    *   Day 3: 4+3=7, 7<10, 7-1=6
    *   Day 4: 6+3=9, 9<10, 9-1=8
    *   Day 5: 8+3=11, 11>=10, break!

---
**教练寄语**：
三级是一个分水岭！**位运算**是理解底层的钥匙，**数组与字符串**是存储数据的基石，而**枚举与模拟**是解决实际问题的第一把武器。
记住：代码不仅是写出来的，更是“模拟”出来的。遇到复杂的题，在草稿纸上手动模拟一遍变量变化，比什么都管用！加油！

GESP 三级编程能力认证讲义

第一模块：数据编码与进制转换

1. 知识点拆解

进制转换：
- N进制转十进制：按权展开法（如二进制 $1011 = 1\times 2^3 + 0\times 2^2 + 1\times 2^1 + 1\times 2^0$）。
- 十进制转N进制：除N取余法。
- 二进制与八/十六进制：3位二进制对应1位八进制；4位二进制对应1位十六进制。
原码、反码、补码：
- 计算机内部使用补码存储整数。
- 正数：三码合一（全部相同）。
- 负数：
  - 原码：最高位为1表示负数。
  - 反码：原码符号位不变，其余各位取反。
  - 补码：反码 $+ 1$。

2. 具体例子

例子 1.1：求 $-5$ 的补码（假设用 8 位二进制表示）。 1. 正数 $5$ 的原码：0000 0101 2. $-5$ 的原码：1000 0101 3. $-5$ 的反码：1111 1010 4. $-5$ 的补码：1111 1011（即反码+1）

3. 练习巩固

【简单】单选题：十六进制数 0x1F 转换成十进制数是（）。 A. 15 B. 25 C. 31 D. 32
【中等】对错题：在 8 位二进制下，补码 1111 1111 对应的十进制整数是 $-1$。（）
【困难】填空题：一个十进制整数 $-13$，在计算机内部用 8 位补码表示为 ____________。

第二模块：位运算

1. 知识点拆解

常用运算符：
- &（按位与）：同为 1 则为 1。
- |（按位或）：有一个为 1 则为 1。
- ^（按位异或）：相同为 0，不同为 1（重要特性：a^a=0, a^0=a）。
- ~（按位非）：0变1, 1变0。
- <<（左移）：$a << n$ 相当于 $a \times 2^n$。
- >>（右移）：$a >> n$ 相当于 $a / 2^n$。

2. 具体例子

例子 2.1：利用异或交换两个变量 a 和 b 的值（不使用临时变量）。

a = a ^ b;
b = a ^ b; // 此时 b = (a^b)^b = a
a = a ^ b; // 此时 a = (a^b)^a = b

3. 练习巩固

【简单】单选题：表达式 5 & 3 的值是（）。 A. 1 B. 7 C. 0 D. 5
【中等】填空题：若 int n = 8;，则 n >> 2 的结果是 __，n << 1 的结果是 ____。
【困难】阅读程序写结果： cpp int a = 12, b = 10; int res = (a ^ b) & a; cout << res; 输出：____

第三模块：一维数组与字符串

1. 知识点拆解

一维数组：连续空间，下标从 0 开始。int a[10] 的有效下标是 0-9。
字符串（string）：
- s.size() 或 s.length()：获取长度。
- s[i]：访问单个字符。
- s1 + s2：拼接字符串。
- getline(cin, s)：读入带空格的一整行。

2. 具体例子

例子 3.1：统计字符串中数字字符出现的次数。

string s = "GESP2024";
int cnt = 0;
for(int i = 0; i < s.size(); i++) {
    if(s[i] >= '0' && s[i] <= '9') cnt++;
}

3. 练习巩固

【简单】对错题：定义 int a[5]; 后，访问 a[5] 会导致数组下标越界错误。（）
【中等】单选题：已知 string s = "ABCDE";，执行 s = s.substr(1, 3); 后，s 的值是（）。 A. "ABC" B. "BCD" C. "CDE" D. "BCDE"
【困难】阅读程序填空：以下程序的功能是倒置数组元素，请补全代码。 cpp int a[5] = {1, 2, 3, 4, 5}; for(int i = 0; i < 5 / 2; i++) { int temp = a[i]; a[i] = ___________; a[4-i] = temp; }

第四模块：算法初步（枚举与模拟）

1. 知识点拆解

枚举法（暴力法）：根据已知条件，逐一列举所有可能的答案并验证。
- 三要素：范围、约束条件、结果判定。
模拟法：题目怎么说，代码就怎么写。用代码逻辑“复现”题目的过程。
算法描述：
- 自然语言：大白话。
- 流程图：图形化。
- 伪代码：类代码格式，不强调语法，强调逻辑。

2. 具体例子

例子 4.1（枚举）：百钱买百鸡。公鸡5元，母鸡3元，小鸡1元3只。求所有方案。

for(int x = 0; x <= 20; x++) { // 枚举公鸡数量
    for(int y = 0; y <= 33; y++) { // 枚举母鸡数量
        int z = 100 - x - y; // 剩余为小鸡
        if(z % 3 == 0 && 5*x + 3*y + z/3 == 100) {
            // 找到一组解
        }
    }
}

3. 练习巩固

【简单】单选题：以下哪种算法描述方式不属于计算机程序，但能清晰表达逻辑且不受编程语言限制？ A. 源码 B. 伪代码 C. 目标程序 D. 编译器
【中等】填空题（枚举逻辑）：若要枚举所有的三位水仙花数（各数字立方和等于本身），循环变量 i 的范围应该是从 __ 到 ____。
【困难】编程模拟逻辑填空：模拟蜗牛爬树。树高 H 米，白天爬 U 米，晚上坠落 D 米。求第几天爬到顶。 cpp int H = 10, U = 3, D = 1, day = 0, height = 0; while(true) { day++; height += U; if(height >= H) break; height -= D; } // 最终 day 的值是 ______。

教练参考答案与解析

第一模块

C。$1 \times 16^1 + 15 \times 16^0 = 16 + 15 = 31$。
对。补码 1111 1111 为负数，逆向推导：减1得 1111 1110，取反得 1000 0001（即 $-1$）。
11110011。13原码 0000 1101 -> -13原码 1000 1101 -> 反码 1111 0010 -> 补码 1111 0011。

第二模块

A。101(5) & 011(3) = 001(1)。
2（$8/4$）；16（$8 \times 2$）。
4。12(1100) ^ 10(1010) = 0110(6)；0110(6) & 1100(12) = 0100(4)。

第三模块

对。长度为 5，最大下标是 4。
B。substr(起始位置, 长度)，从下标 1 ('B') 开始截取 3 个，即 "BCD"。
a[4-i]。这是经典的交换逻辑。

第四模块

B。
100 到 999。
5。
- Day 1: 0+3=3, 3<10, 3-1=2
- Day 2: 2+3=5, 5<10, 5-1=4
- Day 3: 4+3=7, 7<10, 7-1=6
- Day 4: 6+3=9, 9<10, 9-1=8
- Day 5: 8+3=11, 11>=10, break!

教练寄语：三级是一个分水岭！位运算是理解底层的钥匙，数组与字符串是存储数据的基石，而枚举与模拟是解决实际问题的第一把武器。记住：代码不仅是写出来的，更是“模拟”出来的。遇到复杂的题，在草稿纸上手动模拟一遍变量变化，比什么都管用！加油！

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com