编程题
三、编程题（每题 25 分，共 50 分）
1. 幸运数
【问题描述】
小明发明了一种“幸运数”。一个正整数，其偶数位不变（个位为第 1 位，十位为第 2 位，以此类推），奇数位做如下变换：将数字乘以 7，如果不大于 9 则作为变换结果，否则把结果的各位数相加，如果结果不大于 9 则作为变换结果，否则（结果仍大于 9）继续把各位数相加，直到结果不大于 9，作为变换结果。变换结束后，把变换结果的各位数相加，如果得到的和是 8 的倍数，则称一开始的正整数为幸运数。
例如，16347：第 1 位为 7，乘以 7 结果为 49，大于 9，各位数相加为 13，仍大于 9，继续各位数相加，最后结果为 4；第 3 位为 3，变换结果为 3；第 5 位为 1，变换结果为 7。最后变化结果为 76344，对于结果 76344 其各位数之和为 24，是 8 的倍数。因此 16347 是幸运数。
【输入描述】
输入第一行为正整数，表示有个待判断的正整数。约定 $1≤N ≤20$ 。
从第 2 行开始的 $N$ 行，每行一个正整数，为待判断的正整数。约定这些正整数小于 $10^{12}$。
【输出描述】
输出$N$行，对应$N$个正整数是否为幸运数，如是则输出'T'，否则输出'F'。
提示：不需要等到所有输入结束再依次输出，可以输入一个数就判断一个数并输出，再输入下一个数。
【样例输入 1】
2
16347
76344
【样例输出 1】
T
F
【题目大意】
对正整数的奇数位进行乘以 7，进行若干次数位求和小于等于 9 之后，再与偶数位求和，判断结果是否能被 8 整除。
【考纲知识点】
模拟法(三级)，函数的定义与调用（四级）
【解题思路】
- 首先读入所有待判断的正整数，并依次进行判断，注意使用 long long 类型。
- 接着通过将一个数不停整除 10 来得到它的每一位。
- 对其中的奇数位按照题目的要求进行变换，偶数位则不变。奇数位的变换可以按题目文字循环处理，也可以找到等价的更简洁的表达式。
- 累加每一位并判断总和是否能被 8 整除。
【参考程序】
#include <iostream>
using namespace std;
// 奇数位要做的数字变换
int trans(int t) {
if (t == 0)
return 0;
return (t * 7 - 1) % 9 + 1;
}
// 判断是否为幸运数
bool judge(long long x) {
int sum = 0;
for (int d = 1; x > 0; d++, x /= 10) {
int t = (int)(x % 10);
if (d % 2 == 0)
sum += t;
else
sum += trans(t);
}
return (sum % 8 == 0);
}
int main() {
int N = 0;
cin >> N;
for (int n = 0; n < N; n++) {
long long x = 0;
cin >> x;
if (judge(x))
cout << "T" << endl;
else
cout << "F" << endl;
}
return 0;
}
2. 图像压缩
【问题描述】
图像是由很多的像素点组成的。如果用 0 表示黑，255 表示白，0 和 255 之间的值代表不同程度的灰色，则可以用一个字节表达一个像素（取值范围为十进制 0-255、十六进制 00-FF）。这样的像素组成的图像，称为 256 级灰阶的灰度图像。
现在希望将 256 级灰阶的灰度图像压缩为 16 级灰阶，即每个像素的取值范围为十进制 0-15、十六进制 0-F。压缩规则为：统计出每种灰阶的数量，取数量最多的前 16 种灰阶（如某种灰阶的数量与另外一种灰阶的数量相同，则以灰阶值从小到大为序），分别编号 0-F（最多的编号为 0，以此类推）。其他灰阶转换到最近的 16 种灰阶之一，将某个点灰阶数与 16 种灰阶种的一种相减，绝对值最小即为最近，如果绝对值相等，则编号较小的灰阶更近。
【输入描述】
输入第 1 行为一个正整数 $N$，表示接下来有 $N$ 行数据组成一副 256 级灰阶的灰度图像。约定 $10≤N≤20$。
第 2 行开始的 $N$ 行，每行为长度相等且为偶数的字符串，每两个字符用十六进制表示一个像素。约定输入的灰度图像至少有 16 种灰阶。约定每行最多 20 个像素。
【输入描述】
第一行输出压缩选定的 16 种灰阶的十六进制编码，共计 32 个字符。
第二行开始的 $N$ 行，输出压缩后的图像，每个像素一位十六进制数表示压缩后的灰阶值。
【样例输入 1】
10
00FFCFAB00FFAC09071B5CCFAB76
00AFCBAB11FFAB09981D34CFAF56
01BFCEAB00FFAC0907F25FCFBA65
10FBCBAB11FFAB09981DF4CFCA67
00FFCBFB00FFAC0907A25CCFFC76
00FFCBAB1CFFCB09FC1AC4CFCF67
01FCCBAB00FFAC0F071A54CFBA65
10EFCBAB11FFAB09981B34CFCF67
01FFCBAB00FFAC0F071054CFAC76
1000CBAB11FFAB0A981B84CFCF66
【样例输出 1】
ABCFFF00CB09AC07101198011B6776FC
321032657CD10E
36409205ACC16D
B41032657FD16D
8F409205ACF14D
324F326570D1FE
3240C245FC411D
BF4032687CD16D
8F409205ACC11D
B240326878D16E
83409205ACE11D
【样例解释 1】
灰阶‘AB’、‘CF’和‘FF’出现 14 次，‘00’出现 10 次，‘CB’出现 9 次，‘09’出现 7次，‘AC’出现 6 次，‘07’出现 5 次，‘10’、‘11’和‘98’出现 4 次，‘01’、‘1B’、‘67’、‘76’ 和‘FC’出现 3 次。
【题目大意】
先根据输入将输入的十六进制两两成对转换为十进制 0~255 之间的数，再取出现次数较多的前 16 个数作为标准“灰阶”，将其他的数根据与标准“灰阶”作差的绝对值大小就近转换为对应“灰阶”，最后再将灰阶转换为 16 进制输出。
【考纲知识点】
多层循环（二级），模拟法(三级)，函数的定义与调用（四级）
【解题思路】
- 模拟题，我们按照题目的要求进行模拟即可，首先将数据输入，并把 16 进制转换为 10 进制。
- 接着我们找出出现次数最多的 16 种灰阶，并给它们编号为 0-F。
- 然后遍历所有的灰阶，找出距离它们各自最近的 16 种灰阶之一。
- 先输出出现次数最多的 16 种灰阶，记得转换为 16 进制，再输出压缩后的图像，即所有的灰阶都输出距离它们各自最近的 16 种灰阶之一。
【参考程序】
#include <iostream>
#include <cstring>
using namespace std;
int image[20][20];
int cpimg[20][20];
int his[256];
int color[16];
int trans(char a) {
if (a <= '9')
return (a - '0');
return (a - 'A' + 10);
}
char itrans(int n) {
if (n >= 10)
return (char)(n - 10 + 'A');
return (char)(n + '0');
}
int compress(int c) {
int dis = 256, res = -1;
for (int i = 0; i < 16; i++) {
int d = c - color[i];
if (d < 0)
d = -d;
if (d < dis) {
dis = d;
res = i;
}
}
return res;
}
int main() {
int N = 0, M = 0;
cin >> N;
for (int i = 0; i < 256; i++)
his[i] = -1;
for (int i = 0; i < N; i++) {
char line[50];
cin >> line;
M = strlen(line) / 2;
for (int j = 0; j < M; j++) {
int c = trans(line[j * 2]) * 16 + trans(line[j * 2 + 1]);
image[i][j] = c;
his[c]++;
}
}
for (int c = 0; c < 16; c++) {
int max = 0, max_id = -1;
for (int i = 0; i < 256; i++)
if (his[i] > max) {
max = his[i];
max_id = i;
}
color[c] = max_id;
his[max_id] = -1;
}
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
cpimg[i][j] = compress(image[i][j]);
for (int c = 0; c < 16; c++)
cout << itrans(color[c] / 16) << itrans(color[c] % 16);
cout << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++)
cout << itrans(cpimg[i][j]);
cout << endl;
}
return 0;
}
