第1章：程序设计入门（Programming Basics）

一、导读

1.1 本章学习目标

第1章是《算法竞赛入门经典》的开篇之作，它的使命非常明确：帮助你从零开始建立编程的基本能力，为后续所有章节的学习打下坚实的基础。算法竞赛的世界精彩纷呈，但一切精彩都建立在一个前提之上——你能熟练地用代码表达你的想法。本章就是训练这种基本功的起点。

本章的核心学习目标包括：

掌握基本数据类型和变量：理解 int、long long、double、char 的取值范围和适用场景，知道什么时候该用哪种类型。
熟练使用输入输出函数：掌握 scanf/printf 的格式化用法，理解为什么在竞赛中它们比 cin/cout 更高效。
理解条件语句的逻辑：能够用 if-else 和三元运算符实现各种分支判断逻辑。
掌握循环结构的运用：熟练使用 for 和 while 循环解决迭代计算、枚举等问题。
了解数组的基本用法：能够声明、初始化和遍历一维数组，理解数组越界的危险。
建立调试的基本能力：学会使用 g++ 编译程序和 gdb 调试程序，这是独立解题的前提。

1.2 为什么第一章如此重要

很多有编程经验的读者会倾向于跳过第一章，觉得"变量、循环、条件"这些东西太基础了。这种想法在算法竞赛的学习中是极其危险的。算法竞赛对编程基本功的要求远高于普通软件开发——你不仅要把代码写对，还要写得快、写得准确、写得没有边界错误。

竞赛中的很多"诡异错误"，归根结底都是基本功不扎实：int 溢出导致答案错误、scanf 格式符写错导致读入失败、循环边界差一导致 WA（Wrong Answer）、数组开小导致 RE（Runtime Error）。这些错误在赛场上是致命的——它们不会给你任何提示，只会默默地在评测系统上返回一个红色的 Wrong Answer。

本章的另一个重要使命是帮你建立数据范围意识。在算法竞赛中，每一道题都有明确的数据范围，你需要根据数据范围选择合适的类型和算法。输入是 10^5 还是 10^9？答案会不会超过 int 的范围？这些判断必须在读题后的几秒钟内完成。这种意识，需要从第一章就开始培养。

1.3 核心问题引导

在阅读本章时，请带着以下问题思考：

int 的最大值是多少？什么时候必须使用 long long？溢出的后果是什么？

scanf 的返回值是什么？如何利用返回值判断输入是否结束？

for 循环和 while 循环各自适合什么场景？它们之间如何相互转换？

数组下标为什么从 0 开始而不是从 1 开始？数组越界会发生什么？

如何系统地调试一个有 bug 的程序？gdb 的基本操作有哪些？

什么是"枚举法"？什么时候可以用枚举法解决问题？

二、核心概念详解

2.1 变量与数据类型

2.1.1 基本数据类型

C/C++ 提供了多种基本数据类型，在算法竞赛中，你最常打交道的有以下几种：

类型	大小	取值范围	格式符
`int`	4 字节	-2,147,483,648 ~ 2,147,483,647（约 ±2×10⁹）	`%d`
`long long`	8 字节	约 ±9.2×10¹⁸	`%lld`
`double`	8 字节	约 ±1.8×10³⁰⁸，精度约15位	`%lf`
`char`	1 字节	-128 ~ 127（或 0 ~ 255）	`%c`

int n = 1000000000;       // 10^9，在 int 范围内
long long sum = 1LL * n * n; // 10^18，必须用 long long
double pi = 3.14159265358979;
char grade = 'A';

2.1.2 数据范围意识

在算法竞赛中，数据范围决定了你的类型选择。这是一条铁律。

考虑一个经典的例子：计算 1 到 n 的和。当 n = 100,000 时，答案是 5,000,050,000，超过了 int 的最大值（约 21 亿）。如果你用 int 来存储结果，就会发生溢出，得到一个错误的负数。

// 错误示范：int 溢出
int n = 100000;
int sum = 0;
for (int i = 1; i <= n; i++) {
    sum += i;  // 当 sum 超过 2^31 - 1 时溢出！
}
printf("%d\n", sum);  // 输出错误结果

// 正确做法：使用 long long
long long sum2 = 0;
for (int i = 1; i <= n; i++) {
    sum2 += i;
}
printf("%lld\n", sum2);  // 输出 5000050000

经验法则：当题目中 n ≤ 10⁵ 时，n² 可能达到 10¹⁰，超过 int；当 n ≤ 10⁹ 时，n 本身就在 int 的边界，任何涉及 n 的乘法运算都需要 long long。

2.1.3 常量定义

竞赛中经常需要定义常量，有两种方式：

const double PI = 3.14159265358979323846;  // 方式一：const 限定符
#define MAXN 100005                          // 方式二：宏定义

const 有类型检查，推荐使用；#define 是简单的文本替换，不进行类型检查，但在定义数组大小时很方便（因为数组大小必须是编译时常量）。

2.2 输入输出

2.2.1 scanf 和 printf

在算法竞赛中，scanf/printf 是首选的输入输出方式，因为它们比 cin/cout 快得多。当输入数据量达到 10⁵ 级别时，这种速度差异可能导致 TLE（Time Limit Exceeded）。

#include <cstdio>

int main() {
    int n;
    double x;
    char s[100];
    
    scanf("%d", &n);        // 读入整数
    scanf("%lf", &x);       // 读入浮点数
    scanf("%s", s);         // 读入字符串（不含空格）
    
    printf("n = %d\n", n);
    printf("x = %.2f\n", x); // 保留两位小数
    printf("s = %s\n", s);
    
    return 0;
}

常见格式符：

格式符	含义
`%d`	十进制整数
`%lld`	`long long` 整数
`%f` / `%lf`	浮点数
`%c`	单个字符
`%s`	字符串
`%x`	十六进制整数
`%.2f`	保留两位小数
`%5d`	至少占5位宽度

2.2.2 scanf 的返回值

scanf 的返回值是成功读入的变量个数。这个特性经常被用来判断输入是否结束：

int n;
while (scanf("%d", &n) == 1) {
    // 成功读入一个整数，处理 n
    printf("%d\n", n * n);
}

当到达文件末尾（EOF）时，scanf 返回 EOF（值为 -1），不等于 1，循环结束。这种写法在竞赛中极为常见，用于处理"多组测试数据，直到文件末尾"的输入格式。

2.2.3 字符的读入陷阱

scanf("%c", &c) 会读入所有字符，包括空格和换行符。这经常导致意想不到的 bug：

int n;
char c;
scanf("%d", &n);  // 用户输入 "42\n"
scanf("%c", &c);  // c 读到的是 '\n'，不是下一个字符！

// 解决方案：在 %c 前加空格，跳过空白字符
scanf(" %c", &c);  // 注意 %c 前面的空格

2.3 条件语句

2.3.1 if-else 分支

条件语句是程序逻辑控制的基础。在竞赛中，条件判断无处不在：

int score;
scanf("%d", &score);

if (score >= 90) {
    printf("A\n");
} else if (score >= 80) {
    printf("B\n");
} else if (score >= 70) {
    printf("C\n");
} else {
    printf("D\n");
}

2.3.2 三元运算符

三元运算符 ? : 是 if-else 的简洁替代，在竞赛中非常实用：

int a, b;
scanf("%d%d", &a, &b);
int max_val = (a > b) ? a : b;  // 等价于 if-else 求最大值
printf("max = %d\n", max_val);

2.3.3 常见陷阱

浮点数比较：由于精度问题，不能直接用 == 比较浮点数：

double x = 0.1 + 0.2;
// x 并不精确等于 0.3！

// 正确做法：使用 eps 容差
const double EPS = 1e-9;
if (fabs(x - 0.3) < EPS) {
    printf("Equal\n");
}

短路求值：&& 和 || 具有短路特性——如果前面的条件已经能确定结果，后面的表达式不会执行：

int a[10] = {0};
int i = 10;
// if (i < 10 && a[i] > 0)  // 安全：i < 10 为假，a[i] 不会被访问
// if (a[i] > 0 && i < 10)  // 危险！先访问 a[10]，数组越界

2.4 循环结构

2.4.1 for 循环

for 循环是竞赛中最常用的循环结构，适用于已知循环次数的场景：

// 基本形式
for (int i = 0; i < n; i++) {
    // 循环体
}

// 枚举所有二元组 (i, j)，其中 0 <= i < j < n
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        // 处理 (i, j)
    }
}

枚举法是竞赛中最朴素的解题策略：当问题规模较小时，可以枚举所有可能的解，逐一验证。

// 例题：找出所有三位水仙花数
// 水仙花数：一个三位数，等于其各位数字的立方和
for (int i = 100; i <= 999; i++) {
    int a = i / 100;        // 百位
    int b = i / 10 % 10;    // 十位
    int c = i % 10;         // 个位
    if (a * a * a + b * b * b + c * c * c == i) {
        printf("%d\n", i);
    }
}
// 输出：153, 370, 371, 407

2.4.2 while 循环

while 循环适用于循环次数不确定的场景：

// 辗转相除法求 GCD
int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

// 模拟过程：角谷猜想（Collatz）
int n;
scanf("%d", &n);
while (n != 1) {
    printf("%d -> ", n);
    if (n % 2 == 0) n = n / 2;
    else n = 3 * n + 1;
}
printf("1\n");

2.4.3 do-while 循环

do-while 保证循环体至少执行一次，在竞赛中使用较少，但在某些模拟场景中有用：

// 反复读入直到读入特定值
int x;
do {
    scanf("%d", &x);
    process(x);
} while (x != -1);

2.5 数组基础

2.5.1 一维数组

数组是相同类型元素的有序集合，通过下标访问：

int a[100];           // 声明：100 个 int，下标 0~99
int b[5] = {1, 2, 3, 4, 5};  // 初始化
int c[100] = {0};     // 全部初始化为 0

// 遍历
for (int i = 0; i < 100; i++) {
    a[i] = i * i;
}

数组越界是竞赛中最常见的错误之一。访问 a[100]（下标超出 0~99 的范围）不会报错，但会读写不属于你的内存区域，可能导致不可预测的行为。

2.5.2 数组作为计数器

利用数组做频率统计是竞赛中的常用技巧：

// 统计 1~n 中每个数字出现的次数
int cnt[10] = {0};
int n = 12345;
int tmp = n;
while (tmp > 0) {
    cnt[tmp % 10]++;
    tmp /= 10;
}
for (int i = 0; i < 10; i++) {
    if (cnt[i] > 0)
        printf("数字 %d 出现 %d 次\n", i, cnt[i]);
}

三、实战案例

3.1 案例一：韩信点兵

问题描述：相传韩信才智过人，从不直接清点军队人数，而是让士兵先后以三人一排、五人一排、七人一排变换队形，每次只观察排尾的人数（不足一排的余数），就能算出总人数。给定三个余数 a、b、c（a < 3, b < 5, c < 7），求满足条件的最小总人数（范围为 10~100）。

#include <cstdio>

int main() {
    int a, b, c;
    while (scanf("%d%d%d", &a, &b, &c) == 3) {
        int ans = -1;
        for (int i = 10; i <= 100; i++) {
            if (i % 3 == a && i % 5 == b && i % 7 == c) {
                ans = i;
                break;
            }
        }
        if (ans != -1)
            printf("%d\n", ans);
        else
            printf("No answer\n");
    }
    return 0;
}

解析：这是一个典型的枚举问题。由于范围很小（10~100），直接遍历每一个数，检查是否同时满足三个条件即可。这种方法虽然"暴力"，但在数据范围允许的情况下是完全可行的。算法竞赛的一个重要思维就是：先想暴力解法，再考虑优化。

3.2 案例二：输出固定图案

问题描述：输入 n，输出 n 层的倒三角形图案。

输入：5
输出：
#########
 #######
  #####
   ###
    #

#include <cstdio>

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        // 输出前导空格
        for (int j = 0; j < i; j++)
            printf(" ");
        // 输出 # 号
        for (int j = 0; j < 2 * (n - i) - 1; j++)
            printf("#");
        printf("\n");
    }
    return 0;
}

解析：图案输出题的关键是找到行号与各部分数量的数学关系。第 i 行（从 0 开始）有 i 个前导空格，有 2*(n-i)-1 个 #。这种找规律的能力是编程基本功的重要组成部分。

3.3 案例三：子序列的和

问题描述：输入 n 和 m，计算 1/n² + 1/(n+1)² + ... + 1/m² 的值，保留 5 位小数。

#include <cstdio>

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2 && (n || m)) {
        double sum = 0.0;
        for (int i = n; i <= m; i++) {
            sum += 1.0 / (long long)i / i;
        }
        printf("%.5f\n", sum);
    }
    return 0;
}

解析：注意 1.0 / (long long)i / i 的写法。如果直接写 1.0 / i / i，当 i 较大时 i * i 可能溢出 int。先转为 long long 再做除法，可以避免这个问题。另外，当 n 和 m 都很大时，这个级数的和会非常小，double 的精度是足够的。

四、本章小结

本章是算法竞赛的起点，我们学习了编程的基本工具：

数据类型：int、long long、double、char 各有其适用场景，数据范围意识是竞赛编程的第一课。

输入输出：scanf/printf 是竞赛中的首选，scanf 的返回值可以用来判断输入结束。

条件语句：if-else 和三元运算符实现了程序的分支逻辑，浮点数比较要用 eps 容差。

循环结构：for 循环适合已知次数的迭代，while 循环适合条件驱动的迭代，枚举法是最朴素的解题策略。

数组基础：数组是有序元素的集合，注意下标从 0 开始，警惕数组越界。

这些看似简单的工具，在算法竞赛中会反复用到。熟练掌握它们，才能在后续章节中把精力集中在算法思维上，而不是被语法细节绊住脚步。

五、思考与练习

思考题

为什么 scanf("%d", &n) 需要传地址 &n 而不是直接传 n？如果忘记写 & 会发生什么？

for (int i = 0; i < n; i++) 和 for (int i = 1; i <= n; i++) 有什么区别？在什么场景下你会选择后者？

如果题目保证 n ≤ 10⁹，计算 n×(n+1)/2 应该用什么类型？如果先算 n×(n+1) 再除以 2，会不会有问题？

scanf("%s", s) 遇到空格会怎样？如果要读入包含空格的整行，应该用什么函数？

编程练习

水仙花数：找出所有三位数中，各位数字立方和等于该数本身的数。

韩信点兵：实现本章案例中的韩信点兵程序，并尝试用中国剩余定理的公式直接计算答案。

阶乘计算：输入 n（n ≤ 20），计算 n! 的值。注意选择合适的类型。

回文判断：输入一个正整数，判断它是否是回文数（正读反读相同）。