姓名、学号：第 1 页
Alwin Berger
多特蒙德，2025 年 11 月 14 日

编程导论课程实验 —— 2025/26 冬季学期 第 4 次实验作业
满分：11 分

习题 1：ISBN 编号校验（4 分）

需要对 10 位 ISBN 编号（国际标准书号）进行校验。具体方法如下：
将前 9 位数字 $ z_1 $ 到 $ z_9 $ 从左到右依次乘以因子 1, 2, 3, ..., 9，并将结果求和。然后将该总和除以 11，所得余数必须等于第 10 位数字 $ z_{10} $。
如果余数为 10，则用字符 'x' 表示；否则用数字 0 到 9 表示。前 9 位只能包含数字 0 到 9。

用于计算校验位的公式如下：

$ z_{10} = \left( \sum_{i=1}^{9} i \cdot z_i \right) \bmod 11 $

例如，对于正确的 ISBN 编号 349913599x，计算过程如下：

$ 1 \cdot 3 + 2 \cdot 4 + 3 \cdot 9 + 4 \cdot 9 + 5 \cdot 1 + 6 \cdot 3 + 7 \cdot 5 + 8 \cdot 9 + 9 \cdot 9 = 285 \ 285 \bmod 11 = 10 \quad (\text{即 } 'x') $

请创建一个新文件夹 Praktikum_4/Aufgabe_1，并将模板中的源文件 isbn.cpp 放入其中。

a)（2 分）

由于校验 ISBN 编号时需使用整数运算，因此必须将类型为 char 的数字字符转换为整数。
请补充函数 umwandlung，该函数接收一个 char 类型的参数，并将其转换为 int 类型：

• 字符 '0' 到 '9' 应分别转换为整数 0 到 9；
• 字符 'x' 应转换为整数 10；
• 其他任何字符应返回 -1。

提示：可借助 ASCII 表完成 char 到 int 的转换。

b)（2 分）

请补充另一个函数 isbn10check，该函数接收一个 ISBN 编号（以字符数组形式传入），根据前 9 位计算校验位，并与第 10 位进行比较。函数应返回 bool 类型：

• 若 ISBN 编号正确，返回 true；
• 否则返回 false。

注意：只要需要将 char 转换为 int，就必须调用 umwandlung 函数。若在 ISBN 中发现非法字符，也应返回 false。

姓名、学号：第 2 页

习题 2：使用位模式实现集合操作（7 分）

本题要求你实现一个利用位模式（bit patterns）和位运算来表示与处理字符集合的系统。

基本思想：有限集合的一个子集可以用一个位向量（二进制数）表示，其中每一位指示对应元素是否包含在子集中。

限制条件：我们只考虑 ASCII 码 33（'!'）到 ASCII 码 90（'Z'）之间的字符。这最多包含 58 个不同字符，可以容纳在一个 64 位整数中。小写字母不在该范围内，需转换为对应的大写字母。

请创建一个新文件夹 Praktikum_4/Aufgabe_2，并将模板中的源文件 mengenoperationen.cpp 放入其中。

模板已包含以下内容： - 用于读取两个字符串的 main() 函数； - 辅助函数 normalisiere_zeichen()，用于根据上述限制过滤并标准化字符； - 多种集合操作的测试输出。

a)（3 分）

实现函数：

uint64_t zeichen_zu_menge(const char str[], int length)

该函数应： - 遍历字符串 str（长度为 length）中的每个字符； - 使用 normalisiere_zeichen() 对字符进行标准化； - 对每个有效字符（ASCII 33–90），在 uint64_t 类型（等价于 unsigned long long int）中设置对应的位； - 返回表示该字符集合的 uint64_t 值。

b)（2 分）

实现函数：

void ausgabe_menge(uint64_t menge)

该函数应输出集合中包含的所有字符： - 遍历全部 64 个位位置； - 检查每一位是否被设置； - 若是，则计算对应的 ASCII 字符并输出； - 输出格式应为花括号包围，字符之间用逗号分隔。

示例输出：{A, H, L, O}

c)（1 分）

实现函数：

uint64_t schnittmenge(uint64_t menge1, uint64_t menge2)

交集仅包含同时出现在两个集合中的字符。

示例： - 集合 1：{A, B, C} - 集合 2：{B, C, D} - 交集：{B, C}

d)（1 分）

实现函数：

uint64_t vereinigung(uint64_t menge1, uint64_t menge2)

并集包含至少出现在其中一个集合中的所有字符。

示例： - 集合 1：{A, B, C} - 集合 2：{B, C, D} - 并集：{A, B, C, D}

#include <iostream>
using namespace std;

// 全局变量：用于存储用户输入的 ISBN 号码（10位 + 结尾 '\0'）
char isbn[11];

/**
 * 将一个字符（char）转换为对应的整数值（int）。
 * 
 * - 如果是 '0' 到 '9'，返回 0 到 9；
 * - 如果是 'x' 或 'X'，返回 10；
 * - 其他字符返回 -1（表示非法）。
 * 
 * @param ziffer 要转换的字符
 * @return 对应的整数值，非法字符返回 -1
 */
int umwandlung(char ziffer) {
    if (ziffer >= '0' && ziffer <= '9') {
        // 利用 ASCII 码：'0' = 48, '1' = 49, ..., 所以 '5' - '0' = 5
        return ziffer - '0';
    } else if (ziffer == 'x' || ziffer == 'X') {
        // 校验位为 10 时用 'x' 或 'X' 表示
        return 10;
    } else {
        // 非法字符
        return -1;
    }
}

/**
 * 验证一个 10 位 ISBN 编号是否有效。
 * 
 * 规则：
 * - 前 9 位必须是数字（'0'-'9'）；
 * - 第 10 位可以是数字或 'x'/'X'；
 * - 计算加权和：1*z1 + 2*z2 + ... + 9*z9；
 * - 加权和 mod 11 的结果必须等于第 10 位（10 用 'x' 表示）。
 * 
 * @param isbn_nummer 输入的 ISBN 字符数组（长度为 10）
 * @return true 表示 ISBN 有效，false 表示无效
 */
bool isbn10check(char isbn_nummer[]) {
    int sum = 0; // 用于存储加权和

    // 遍历前 9 位（索引 0 到 8）
    for (int i = 0; i < 9; i++) {
        int digit = umwandlung(isbn_nummer[i]);
        // 前 9 位不能是 'x'，也不能是其他非法字符
        if (digit < 0 || digit > 9) {
            return false;
        }
        // 权重为 i+1（因为 i 从 0 开始）
        sum += (i + 1) * digit;
    }

    // 计算期望的校验位（0 到 10）
    int expected_check_digit = sum % 11;

    // 获取实际的第 10 位（索引 9）
    int actual_check_digit = umwandlung(isbn_nummer[9]);
    if (actual_check_digit == -1) {
        // 第 10 位是非法字符
        return false;
    }

    // 比较期望值和实际值
    return (expected_check_digit == actual_check_digit);
}

/**
 * 主函数：读取用户输入并验证 ISBN
 */
int main() {
    printf("请输入一个10位的ISBN号码: ");
    // 读取最多10个字符（自动添加 '\0'，所以 char[11] 足够）
    if (scanf("%10s", isbn) != 1) {
        // 输入失败（如 EOF）
        return 1;
    }

    // 调用验证函数并输出结果
    if (isbn10check(isbn)) {
        printf("ISBN号码 %s 是有效的。\n", isbn);
    } else {
        printf("ISBN号码 %s 是无效的。\n", isbn);
    }

    return 0;
}

#include <stdio.h>      // 标准输入输出库
#include <stdint.h>     // 提供 uint64_t 等固定宽度整数类型
#include <ctype.h>      // 字符处理函数（本例中未直接使用，但保留）
#include <string.h>     // 字符串操作函数（如 strlen）

// 辅助函数：标准化字符
// - 将小写字母转换为大写字母
// - 若字符 ASCII 值不在 33 ('!') 到 90 ('Z') 范围内，则视为无效，返回 0
char normalisiere_zeichen(char c) {
    // 如果是小写字母（'a' 到 'z'），转换为对应的大写字母
    if (c >= 'a' && c <= 'z') {
        c = c - 'a' + 'A';  // 例如 'a' -> 'A'
    }

    // 如果字符 ASCII 值小于 33 或大于 90，则视为无效字符，返回 0
    if (c < 33 || c > 90) {
        c = 0;  // 0 表示无效字符
    }

    return c;
}

// ===== 任务 a) =====
// 将字符串转换为一个集合（用 uint64_t 的位模式表示）
// 每个有效字符对应一个位：'!' 对应第 0 位，'"' 对应第 1 位，……，'Z' 对应第 57 位
uint64_t zeichen_zu_menge(const char str[], int length) {
    uint64_t menge = 0;  // 初始化集合（所有位为 0）

    // 遍历字符串中的每个字符
    for (int i = 0; i < length; i++) {
        char norm = normalisiere_zeichen(str[i]);  // 标准化当前字符
        if (norm != 0) {  // 如果是有效字符
            int bit_pos = norm - 33;               // 计算对应的位位置（'!' = 33 → 位 0）
            menge |= (1ULL << bit_pos);            // 设置该位为 1（1ULL 表示 64 位无符号常量）
        }
    }
    return menge;  // 返回表示集合的位掩码
}

// ===== 任务 b) =====
// 输出集合中包含的所有字符
// 格式：{A, B, C}，字符按 ASCII 顺序从小到大输出（因为从低位到高位遍历）
void ausgabe_menge(uint64_t menge) {
    printf("{");                     // 输出左花括号
    int first = 1;                   // 标记是否是第一个元素（用于控制逗号）

    // 遍历 64 个可能的位（0 到 63）
    for (int bit = 0; bit < 64; bit++) {
        // 检查第 bit 位是否为 1
        if (menge & (1ULL << bit)) {
            char c = (char)(bit + 33);  // 由位位置反推 ASCII 字符（位 0 → '!'）
            if (!first) {
                printf(", ");           // 不是第一个元素，先输出逗号和空格
            }
            printf("%c", c);            // 输出字符
            first = 0;                  // 标记已输出过元素
        }
    }
    printf("}");  // 输出右花括号
}

// ===== 任务 c) =====
// 计算两个集合的交集（Schnittmenge）
// 交集：只保留在两个集合中都存在的元素
uint64_t schnittmenge(uint64_t menge1, uint64_t menge2) {
    return menge1 & menge2;  // 按位与：只有两个位都为 1 时结果才为 1
}

// ===== 任务 d) =====
// 计算两个集合的并集（Vereinigung）
// 并集：包含在任一集合中出现的元素
uint64_t vereinigung(uint64_t menge1, uint64_t menge2) {
    return menge1 | menge2;  // 按位或：只要有一个位为 1，结果就为 1
}

// ===== 主函数（不要修改）=====
int main() {
    char str1[256] = {0};  // 存储第一行输入
    char str2[256] = {0};  // 存储第二行输入

    printf("=== 使用位模式进行集合运算 ===\n");
    printf("\n");

    // 读取用户输入的两个字符串
    printf("请输入第一个字符串: ");
    scanf("%255s", str1);  // 最多读取 255 个字符，防止缓冲区溢出

    printf("请输入第二个字符串: ");
    scanf("%255s", str2);

    printf("\n");

    // 将字符串转换为集合（位掩码）
    uint64_t menge1 = zeichen_zu_menge(str1, strlen(str1));
    uint64_t menge2 = zeichen_zu_menge(str2, strlen(str2));

    // 输出两个原始集合
    printf("集合 1: ");
    ausgabe_menge(menge1);
    printf("\n");

    printf("集合 2: ");
    ausgabe_menge(menge2);
    printf("\n");

    printf("\n");

    // 输出交集
    printf("交集 (集合 1 ∩ 集合 2): ");
    ausgabe_menge(schnittmenge(menge1, menge2));
    printf("\n");

    // 输出并集
    printf("并集 (集合 1 ∪ 集合 2): ");
    ausgabe_menge(vereinigung(menge1, menge2));
    printf("\n");

    printf("\n");

    return 0;
}

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