习题课 | Problem Practice

我们在序章中谈论什么是编程的时候，曾经提到：

编写程序，就像在Word软件里写下一篇文稿一样，就是要从0开始“造”出一个程序。

正如我们所说，在实际开发中，例如软件工程就是一门通过编程方法实现一个功能、程序、应用的工程学科。

但作为程序设计课程的考核，我们通常被“要求”实现某一功能。因此，对于一个确定的作业题目，给定固定格式的输入，如果通过我们的程序能得到期望的输出，那么则认为我们的程序通过考核。

正是由于“考核”与“开发”的些许不同，我们被要求分析给定的问题、通过基本的语句、分支和循环结构、函数等的复合，实现对应的功能。

因此我们特别地利用一节的内容，用文字的说明和代表性强的例题来熟悉这样的考核模式。

一、如何评测？

一个题目，总是至少由下面的内容组成：

• 题目描述
• 样例输入
• 样例输出

例如这样一道例题：

题目描述
任意给定 n 个整数，求这 n 个整数序列的和、最小值、最大值

测试说明
输入描述：
输入一个整数 n ，代表接下来输入整数个数，n<=100 ,接着输入 n 个整数，整数范围是-10000~10000。

输出描述：
输出整数序列的和、最小值、最大值。用空格隔开，占一行

样例输入：

2
1 2

样例输出：

3 1 2

在这道例题里，题目描述部分给定了这道题目需要我们实现的功能：即给定一个n和n个整数，求它们的和、最小值、最大值。

多数时候，题目会对输入输出的格式进行说明，这里是测试说明部分。它告诉我们输入的第一个数是n，接下来是n个整数，并且给出了输入数值的范围。输出则要求我们输出和、最小值、最大值，并且用空格隔开。

样例输入和样例输出部分则给出了一个具体的例子。要怎么判断我们的程序是否正确？对于样例输入，程序能够得到样例输出，是通过考核的必要条件。

这是很重要的思想，因为在实际的编程考核中，我们通常会被要求通过多个样例输入来验证程序的正确性，这些样例输入基本涵盖了我们的程序需要实现的所有情况。如果程序在所有样例输入（足够多）下都能得到正确的样例输出，那么“考核”的目的才达到，认为程序是正确的。

二、代表性题目

1. 例如以上面的题目为例

我们被要求实现的功能是什么？

任意给定 n 个整数，求这 n 个整数序列的和、最小值、最大值。

怎么实现？

• 首先我们需要读入一个整数n，然后读入n个整数。
  • 怎么读取整数n？用scanf。
  • 怎么读取n个整数？用一个循环n次的循环搭配上scanf。
• 怎么求和？
  • 用一个变量sum来存储和，初始值为0，每读入一个整数就加到sum上。
• 怎么求最小值和最大值？
  • 用两个变量min和max来分别存储最小值和最大值。
  • 怎么实现min最后得到最小值、max最后得到最大值？
  • 一种方法是，读入第一个整数时，先把它赋值给min和max
  • 然后从第二个整数开始，每读入一个整数，就和min、max比较
  • 如果比min小，就更新min为这个新的整数，如果比max大，就更新max为这个新的整数。
  • 有没有什么优化的方法？
  • 也可以在读入第一个整数前，先把min初始化为一个很大的数（例如10001），把max初始化为一个很小的数（例如-10001）
  • 可以这样做的原因是，这是因为在这道题里，给定了输入数值的范围是-10000~10000
  • 然后从第一个整数开始，每读入一个整数，就和min、max比较
  • 如果比min小，就更新min为这个新的整数，如果比max大，就更新max为这个新的整数。
• 怎么输出？
  • 用printf，按照题目要求的格式输出sum、min、max，中间用空格隔开。

于是我们得到：

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n); // 读入整数 n

    int sum = 0; // 用于存储和
    int min = 10001; // 初始化最小值为一个较大数
    int max = -10001; // 初始化最大值为一个较小数

    for(int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num); // 读入每个整数
        sum += num; // 累加到 sum

        if(num < min) {
            min = num; // 更新最小值
        }
        if(num > max) {
            max = num; // 更新最大值
        }
    }

    printf("%d %d %d\n", sum, min, max); // 输出结果
    return 0;
}

2. 求三位数的逆序数

程序每次读入一个正 3 位数，然后输出按位逆序的数字。注意：当输入的数字含有结尾的 0 时，输出不应带有前导的 0。比如输入 700，输出应该是 7。

输入格式：每个测试是一个 3 位的正整数。

输出格式：输出按位逆序的数。

样例输入:

123

样例输出:

321

我们被要求实现的功能是什么？

输出一个给定三位数的逆序数。

怎么实现？

• 首先我们需要读入一个整数n，题目给定了是一个三位数。
• 接着我们需要让这个三位数反序，怎么反序？
  • 反序是把每个数位倒过来写，于是我们需要提取每个数位（个、十、百）
  • 怎么提取每个数位？
  • 我们有取模（求余数）运算，任何整数对整数10取模（求余数）可以得到末尾。例如：123 % 10是3。
  • 我们有除法（对整数来说是整除），任何整数对整数10做除法，可以得到除了末尾以外的位数。例如：123 / 10是12
  • 因此，我们首先让这个三位数对整数10取模，得到个位数，并让这个三位数对整数10做除法，得到前两位数；
  • 接着重复这个过程，让这个新得到的两位数对整数10取模，得到十位数，并让这个两位数对整数10做除法，得到前一位数；
  • 这个前一位数就是百位数。
• 接着要反序输出，怎么输出？
  • 我们可以简单地输出个位数字，再输出十位数字，再输出百位数字。
  • 这样看似方便，有什么问题？
  • 如果要舍去零（个位数是零、或是个位和十位同时为零），需要单独做判断，不输出这个零
  • 也可以把个、十、百位数字拼凑成一个新的三位数，输出这个三位数
  • 怎么拼凑？
  • 这个新三位数 = 个位数 + 十位数 10 + 百位数 100

于是我们得到：

#include <stdio.h>
int main() {
    int number;
    scanf("%d", &number); // 读入三位数

    int ones = number % 10;         // 个位
    int tens = (number / 10) % 10;  // 十位
    int hundreds = number / 100;    // 百位

    // 按逆序输出，不输出前导0
    if (ones != 0) // 若个位不为0，才输出个位；为0则不输出
        printf("%d", ones);
    if (ones != 0 || tens != 0) // 若个位或十位不为0，输出十位；只有个位和十位都为0时，才不输出十位
        printf("%d", tens);
    printf("%d\n", hundreds); //百位无论如何也要输出

    return 0;
}

输出这部分也可以用这样的逻辑实现，避免了需要判断省略零的问题：

    int reversed = ones * 100 + tens * 10 + hundreds;
    printf("%d\n", reversed);

3. 求n位数的逆序数

如果这里不限定三位数，而是n位数，怎么办？
我们仍然可以通过对10取模提取最后一位数字、通过除法去掉最后一位数字。重复这个过程就可以实现提取每一位数字。例如：

1234567 % 10 = 7 1234567 / 10 = 123456
123456 % 10 = 6 123456 / 10 = 12345
12345 % 10 = 5 12345 / 10 = 1234
1234 % 10 = 4 1234 / 10 = 123
123 % 10 = 3 123 / 10 = 12
12 % 10 = 2 12 / 10 = 1
1 % 10 = 1 1 / 10 = 0

于是我们可以用一个循环来实现这样的功能。但核心问题是，我们不知道这个数有多少位数。怎么办？
从上面对1234567的演示可以看出，重复提取每一位数这个操作，一个可行的终止条件是，直到这个数变成0为止。

我们尝试用while循环来解决这个问题：

#include <stdio.h>
int main() {
    int number;
    scanf("%d", &number); // 读入一个整数

    int reversed = 0; // 用于存储逆序数

    while (number > 0) { // 当 number 不为 0 时，继续提取每一位数字
        int digit = number % 10; // 提取最后一位数字
        reversed = reversed * 10 + digit; // 将提取的数字拼凑到逆序数的末尾
        number = number / 10; // 去掉最后一位数字
    }

    printf("%d\n", reversed); // 输出逆序数
    return 0;
}

同样，我们也可以写成for循环的形式：

#include <stdio.h>
int main() {
    int number;
    scanf("%d", &number); // 读入一个整数

    int reversed = 0; // 用于存储逆序数

    for (; number > 0; number = number / 10) { // 当 number 不为 0 时，继续提取每一位数字
        int digit = number % 10; // 提取最后一位数字
        reversed = reversed * 10 + digit; // 将提取的数字拼凑到逆序数的末尾
    }

    printf("%d\n", reversed); // 输出逆序数
    return 0;
}

这是对循环结构的一个比较好的练习。希望你能够对每一条语句完全理解。

4. 打印N阶三角形

编写一个程序，输入一个正整数 N (1 ≤ N ≤ 20)，输出一个 N 阶的三角形。
例如，N=4 时，输出如下图所示的三角形：

   *
  ***
 *****
*******

输入格式：每个测试是一个正整数 N。
输出格式：输出一个 N 阶的三角形。
样例输入:

3

样例输出:

   *
  ***
 *****

我们被要求实现的功能是什么？

输出一个给定阶数的三角形。

怎么实现？

• 首先，我们需要读入一个整数N，表示三角形的阶数。
• 接着，打印这个三角形可以一行一行地拆分，每一行需要打印一定数量的空格和星号。怎么办？
  • 这是一个相对重复的过程，因此可以用循环来实现。
  • 这个循环的次数是N次，一次循环的功能是打印一行里需要的空格和星号。
  • 每一行的空格和星号同样具有一定数量，且在变化，因此也可以通过重复打印单个空格 和星号*来实现。怎么办？
  • 我们容易发现，第i行（从1开始计数）需要打印N-i个空格和2*i-1个星号。
  • 于是我们在控制打印第i行的循环体中，再内嵌两个循环，分别打印N-i个空格和2*i-1个星号。
  • 最后，每打印完一行，需要换行。

于是我们得到：

#include <stdio.h>
int main() {
    int N;
    scanf("%d", &N); // 读入三角形的阶数

    for (int i = 1; i <= N; i++) { // 控制行数
        for (int j = 1; j <= N - i; j++) // 打印空格
            printf(" ");
        for (int j = 1; j <= 2 * i - 1; j++) // 打印星号
            printf("*");
        printf("\n"); // 换行
    }

    return 0;
}

---

以上例题涵盖了编程考核中常见的输入输出处理、循环结构、条件判断等基础知识点。建议你动手实现每个题目，理解每一步的逻辑，并尝试修改参数或输入，观察程序的行为。通过练习这些代表性问题，可以更好地掌握编程基础，为后续更复杂的题目打下坚实的基础。

下一节预告：了解了C语言的基本语法和结构后，在这一章我们将对这些知识进行系统完善，并介绍例如二进制、数据存储等更底层的内容。