C++学习笔记教程：GESP编程题详解（图像压缩与打印数字）

一、4012：【GESP2306四级】图像压缩

1. 题目理解

核心需求：将256级灰阶（0-255，十六进制00-FF）的灰度图像压缩为16级灰阶（0-F），具体规则如下：

• 统计所有灰阶的出现次数，取前16种（次数多的优先，次数相同则灰阶值小的优先）；
• 前16种灰阶直接映射为0-F（次数最多的为0，依次类推）；
• 其他灰阶转换为“最近”的16种之一（绝对值差最小，差相同则选编号小的）。

2. 解题思路

1. 数据准备：用结构体存储灰阶值及其出现次数；
2. 统计频率：解析输入的十六进制像素，转换为十进制后统计每种灰阶的出现次数；
3. 筛选前16种：按规则排序灰阶，选取前16种作为保留灰阶；
4. 转换输出：
   • 第一行输出16种保留灰阶的十六进制编码（共32个字符）；
   • 后续行输出压缩后的图像，每个像素用0-F表示。

3. 完整代码与详细注释

#include<iostream>
#include<algorithm>  // 包含排序函数sort
using namespace std;

// 结构体：存储灰阶信息（bm为灰阶值，cs为出现次数）
struct huiJie {
    int bm = 0;  // 灰阶值（十进制0-255）
    int cs = 0;  // 出现次数（初始为0）
};

huiJie huiJies[300];  // 存储256种灰阶的数组（开300确保足够）
string words[30];      // 存储输入的图像行（每行是十六进制字符串）

// 初始化灰阶数组：为0-255所有灰阶设置初始值
void huiJieInit() { 
    for (int i = 0; i <= 255; i++) {
        huiJies[i].bm = i;  // 灰阶值从0到255依次赋值
    }
}

// 统计指定灰阶的出现次数
void CntHuiJie(int t) { 
    for (int i = 0; i <= 255; i++) {
        if (huiJies[i].bm == t) {  // 找到目标灰阶
            huiJies[i].cs += 1;    // 次数+1
            break;  // 找到后退出循环，提高效率
        }
    }
}

// 十六进制转十进制：将两个字符（如"CF"）转换为十进制数
int hexTo10(char t1, char t2) { 
    int res = 0;
    // 处理低位字符（右边的字符，如"CF"中的'F'）
    if (t2 >= 'A') {  // 若为字母（A-F）
        res = t2 - 'A' + 10;  // A→10，B→11，…，F→15
    } else {  // 若为数字（0-9）
        res = t2 - '0';
    }
    // 处理高位字符（左边的字符，如"CF"中的'C'），并乘以16（十六进制进位）
    if (t1 >= 'A') {
        res += (t1 - 'A' + 10) * 16;
    } else {
        res += (t1 - '0') * 16;
    }
    return res;  // 例如"CF"→12*16+15=207
}

// 十进制转十六进制：将十进制数转换为两位十六进制字符串（如160→"A0"）
string decTo16(int n) { 
    string str = "";
    // 特殊情况：n=0时直接返回"00"（避免空字符串）
    if (n == 0) {
        return "00";
    }
    while (n != 0) {
        int t = n % 16;  // 取余得到低位（0-15）
        if (t >= 10) {
            str += char(t - 10 + 'A');  // 10-15→A-F
        } else {
            str += char(t + '0');  // 0-9→0-9
        }
        n /= 16;  // 处理高位
    }
    // 若结果长度为1，补前导0（确保每个灰阶用2个字符表示）
    if (str.size() == 1) {
        str = "0" + str;  // 例如3→"03"
    }
    reverse(str.begin(), str.end());  // 反转得到正确顺序（例如计算时先得低位，反转后高位在前）
    return str;
}

// 排序规则：用于sort函数，先按出现次数降序，次数相同按灰阶值升序
bool cmp(huiJie a, huiJie b) {
    if (a.cs != b.cs) {
        return a.cs > b.cs;  // 次数多的排在前
    } else {
        return a.bm < b.bm;  // 次数相同，灰阶值小的排在前
    }
}

int main() {
    huiJieInit();  // 初始化灰阶数组（设置0-255的灰阶值）

    int n;  // 图像的行数
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> words[i];  // 读取每行的十六进制像素字符串
    }

    // 第一步：统计所有灰阶的出现次数
    int len = words[1].size();  // 每行的字符长度（确保所有行长度相同）
    for (int i = 1; i <= n; i++) {  // 遍历每行
        for (int j = 0; j < len; j += 2) {  // 每2个字符为一个像素
            char t1 = words[i][j];    // 高位字符
            char t2 = words[i][j + 1];  // 低位字符
            int gray = hexTo10(t1, t2);  // 转换为十进制灰阶值
            CntHuiJie(gray);  // 统计该灰阶的出现次数
        }
    }

    // 第二步：排序灰阶，筛选出前16种
    sort(huiJies, huiJies + 256, cmp);  // 对0-255的灰阶按规则排序

    // 第三步：输出16种保留灰阶的十六进制编码（共32个字符）
    for (int i = 0; i <= 15; i++) {
        cout << decTo16(huiJies[i].bm);
    }
    cout << endl;

    // 第四步：转换并输出压缩后的图像
    for (int i = 1; i <= n; i++) {  // 遍历每行
        for (int j = 0; j < len; j += 2) {  // 遍历每个像素
            char t1 = words[i][j];
            char t2 = words[i][j + 1];
            int gray = hexTo10(t1, t2);  // 原灰阶的十进制值

            bool isInTop16 = true;  // 标记是否属于前16种灰阶
            for (int p = 0; p <= 15; p++) {
                if (gray == huiJies[p].bm) {  // 属于前16种
                    isInTop16 = false;
                    // 输出对应的编号（0-F）
                    if (p >= 10) {
                        cout << char(p - 10 + 'A');  // 10-15→A-F
                    } else {
                        cout << char(p + '0');  // 0-9→0-9
                    }
                    break;
                }
            }

            // 若不属于前16种，找最近的保留灰阶
            if (isInTop16) {
                int minDiff = 1000;  // 最小差值（初始设为较大值）
                int bestP = 0;       // 最佳匹配的编号
                for (int p = 0; p <= 15; p++) {
                    int diff = abs(gray - huiJies[p].bm);  // 计算绝对值差
                    if (diff < minDiff) {  // 找到更小的差值
                        minDiff = diff;
                        bestP = p;
                    }
                }
                // 输出最佳匹配的编号
                if (bestP >= 10) {
                    cout << char(bestP - 10 + 'A');
                } else {
                    cout << char(bestP + '0');
                }
            }
        }
        cout << endl;  // 每行结束换行
    }

    return 0;
}

4. 关键知识点解析

• 结构体（struct）：huiJie结构体封装了灰阶值（bm）和出现次数（cs），便于批量管理数据；
• 进制转换：
  • hexTo10：将两位十六进制字符转为十进制（如"FF"→255）；
  • decTo16：将十进制转为两位十六进制字符串（如255→"FF"）；
• 排序（sort）：结合自定义比较函数cmp，实现按“次数降序+值升序”的复杂排序；
• 查找逻辑：通过循环判断灰阶是否属于前16种，或寻找最小差值的灰阶，体现了线性查找的应用。

二、4094：【GESP2412三级】打印数字

1. 题目理解

核心需求：将由0、1、2、3组成的数字n，转换为5×5网格的自定义表示形式。每个数字对应一个5×5的图案，输出时需将数字的每个字符对应的图案按列拼接（即每行输出所有数字对应行的字符）。

2. 已知图案定义

根据题目描述，0、1、2、3的5×5图案如下（每行5个字符，共5行）：

数字	第0行	第1行	第2行	第3行	第4行
0	.....	.***.			.....
1	****.	****.	****.
2	.....		.....	.****	.....
3				****.

3. 解题思路

1. 存储图案：用二维数组digitPatterns存储0-3的5×5图案（行索引0-4，数字索引0-3）；
2. 读取输入：将输入的数字n转为字符串（便于逐字符处理）；
3. 拼接输出：对5行中的每一行，依次拼接每个数字对应行的字符，组成最终的5行输出。

4. 完整代码与详细注释

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

int main() {
    // 存储0-3的5×5图案：digitPatterns[行号][数字] = 对应行的字符串
    // 行号0-4，数字0-3
    string digitPatterns[5][4] = {
        {".....", "****.", ".....", "....."},  // 第0行
        {".***.", "****.", "****.", "****."},  // 第1行
        {".***.", "****.", ".....", "....."},  // 第2行
        {".***.", "****.", ".****", "****."},  // 第3行
        {".....", "****.", ".....", "....."}   // 第4行
    };

    string n;  // 用字符串存储输入的数字（避免大数处理问题）
    cin >> n;

    // 输出5行结果：每行由所有数字的对应行拼接而成
    for (int row = 0; row < 5; row++) {  // 遍历5行
        string line = "";  // 存储当前行的拼接结果
        for (char c : n) {  // 遍历输入数字的每个字符
            int digit = c - '0';  // 字符转数字（如'1'→1）
            line += digitPatterns[row][digit];  // 拼接当前数字的对应行
        }
        cout << line << endl;  // 输出当前行
    }

    return 0;
}

5. 输入输出示例

输入样例：12230
输出逻辑：

• 数字依次为'1','2','2','3','0'；
• 第0行：1的第0行（****.）+2的第0行（.....）+2的第0行（.....）+3的第0行（.....）+0的第0行（.....）→****.....................；
• 第1行：1的第1行（.）+2的第1行（.）+2的第1行（.）+3的第1行（.）+0的第1行（.***.）→****.****.****.****..***.；
• 以此类推，最终输出与题目样例一致。

6. 关键知识点解析

• 二维数组：digitPatterns通过行和数字索引快速定位图案，体现了多维数组在结构化数据存储中的应用；
• 字符串处理：将数字转为字符串便于逐字符遍历，拼接字符串实现图案的横向组合；
• 循环嵌套：外层循环控制输出行（0-4），内层循环控制每个数字的图案拼接，体现了嵌套循环在多维数据处理中的作用。

三、总结

本文通过两个GESP编程题，讲解了C++中结构体、数组、字符串、排序、查找等核心知识点：

• 图像压缩重点在于数据统计、排序和进制转换，适合理解复杂数据的处理流程；
• 打印数字重点在于二维数组存储和字符串拼接，适合掌握结构化数据的应用。

两道题均体现了“问题拆解→数据建模→分步实现”的编程思维，初学者可通过模仿代码、修改参数（如调整排序规则、更换图案）加深理解。