当前位置：首页 > article >正文

CSP-S 2022 提高级第一轮阅读程序（3）

article 2024/11/15 4:56:22

【题目】

1  #include <iostream>
2  #include <algorithm>
3  
4  using namespace std;
5  
6  const int MAXL = 1000;
7  
8  int n, k, ans[MAXL];
9  
10 int main(void) 
11 {
12     cin >> n >> k;
13     if (!n) cout << 0 << endl;
14     else 
15     {
16         int m = 0;
17         while (n) 
18         {
19             ans[m++] = (n % (-k) + k) % k;
20             n = (ans[m - 1] - n) / k;
21         }
22         for (int i = m - 1; i >= 0; i--)
23             cout << char(ans[i] >= 10 ?
24                          ans[i] + 'A' - 10 :
25                          ans[i] + '0');
26         cout << endl;
27     }
28     return 0;
29 }

假设输入的 n 在 int 范围内，k 为不小于 2 且不大于 36 的正整数，完成下面的判断题和单选题：

判断题
1.该算法的时间复杂度为 $O(\log_k n)$
2.删除第 23 行的强制类型转换，程序的行为不变。
3.除非输入的 n 为 0，否则程序输出的字符数为 $\lfloor \log_k|n|\rfloor+1$
单选题
4.当输入为“100 7”时，输出为（）。
A. 202
B. 1515
C. 244
D. 1754
5.当输入为“-255 8”时，输出为（）。
A. 1400
B. 1401
C. 417
D. 400
6.当输入为“1000000 19”时，输出为（）。
A. BG939
B. 87GIB
C. 1CD428
D. 7CF1B

【题目考点】

1. 数学取模

数学取模相关概念
证明：C++中取模运算为 $\%$ ，一定有 $a\%b$ 等于 $a\%(-b)$
已知C++中除法运算的商为向0取整，设a除以b的商向0取整后为q。
所以有 $a = q * b + r$ ，其中r为 $a\%b$
设a除以b的实数商为c，c向零取整为q。
则a除以-b的实数商为-c，-c和c是相反数，相反数向零取整的结果也互为相反数，所以-c向零取整为-q。
根据 $a = q * b + r$ 有 $a = (- q) * (- b) + r$
其中-q是a除以-b向零取整的结果，r即为 $a\%(-b)$
所以 $a\%b$ 等于 $a\%(-b)$

【解题思路】

10 int main(void) 
11 {
12     cin >> n >> k;
13     if (!n) cout << 0 << endl;
14     else 
15     {
16         int m = 0;
17         while (n) 
18         {
19             ans[m++] = (n % (-k) + k) % k;
20             n = (ans[m - 1] - n) / k;
21         }
22         for (int i = m - 1; i >= 0; i--)
23             cout << char(ans[i] >= 10 ?
24                          ans[i] + 'A' - 10 :
25                          ans[i] + '0');
26         cout << endl;
27     }
28     return 0;
29 }

输入n和k，n为0时就输出0。
只要n不为0就进行循环。
ans[m++]=(n%(-k)+k) ，结合m初值为0，可以看出这是在做数组填充，填充的数在ans数组中的下标范围是0~m-1。
首先n%(-k)等于n%k（见【题目考点】）。
题目给定k是正整数，而(n%k+k)%k，就是在求数学取模 $n\ mod\ k$ 的结果（见数学取模相关概念）
所以这一句的意义是：将 $n\ mod\ k$ 填充到ans数组中。
下一句n=(ans[m-1]-n)/k;，可以转为n=-(n-ans[m-1])/k;
ans[m-1]就是上一次填充到数组中的 $n\ mod\ k$ ，根据除法定理，一定有商q满足 $n=k*q+(n\ mod\ k)$ ，q是 $\lfloor \frac{n}{k} \rfloor$ 。那么 $(n\ mod\ k))/k$ 就是q，即 $\lfloor \frac{n}{k} \rfloor$ 。
所以n=(ans[m-1]-n)/k;所做的运算为把n变为 $-\lfloor \frac{n}{k} \rfloor$ 。
以上过程是将n在k进制下进行数位分离，但是每分离出一位后，该数值的符号取反。将分离出的各个数位填入ans数组中。其中较小下标保存低位数字，较大下标保存高位数字。
而后从高位到低位遍历，输出分离出的各个数字，对于大于等于10的数字，将其转为大写字母输出，其中’A’表示10，'B’表示11，……，'Z’表示35。

【试题答案及解析】

判断题
1.该算法的时间复杂度为 $O(\log_k n)$
答：T
m是数值是n在k进制下的位数，其值 $m=\lfloor \log_k n\rfloor+1$ 。17行的while循环和22行的for循环的循环次数都是m次。总体时间复杂度为 $O(m)=O(\log_k n)$
2.删除第 23 行的强制类型转换，程序的行为不变。
答：F
由于ans数组为int类型，int类型和char类型量进行运算的表达式的类型也是int类型。因此ans[i]+'A'-10和ans[i]+'0'的值都是int类型。整个三目运算表达式ans[i]>=10 ? ans[i]+'A'-10 : ans[i]+'0'的值的类型也是int类型。
cout输出int类型的值，会输出整数，不会输出字符。强转char类型后，用cout输出可以输出字符。因此去掉强转char类型后，输出会改变。

3.除非输入的 n 为 0，否则程序输出的字符数为 $\lfloor \log_k|n|\rfloor+1$
答：T
输出m个字符，其中n的符号改变并不会改变m
第20行的操作为 $(n\ mod\ k))/k$ ，无论n是正数还是负数，操作都会去掉n的最低位，使n的位数减少1。因此该操作执行的次数就是n的位数，根据n在k进制下的位数公式，以及对数运算中真数必须大于0，有 $m=\lfloor \log_k |n|\rfloor+1$

单选题
4.当输入为“100 7”时，输出为（）。
A. 202
B. 1515
C. 244
D. 1754
答：A
该问题的计算方法为：每次取 $n\ mod\ k$ ，而后n变为n除以k的商并将符号取反，将取出的数字从后向前排列，即为结果。
其中mod运算为数学取模，即为求n/k的商向下取整时的余数，保证余数为非负整数。