解析：阅读程序-3

代码功能

这段代码实现了一个任意进制转换的功能。它可以将一个十进制数 n 转换为 k 进制数，其中 k 的取值范围是 2 到 36。

代码解析

1. 常量定义:
   • MAXL: 定义了一个常量，表示数组 ans 的最大长度，用于存储转换后的 k 进制数的每一位。
2. 变量定义:
   • n: 待转换的十进制数。
   • k: 目标进制。
   • ans: 用于存储转换结果的数组。
3. 主函数:
   • 输入: 读取 n 和 k 的值。
   • 特判: 如果 n 为 0，直接输出 0。
   • 转换:
     • 进入 while 循环，不断将 n 除以 k，并将余数存入 ans 数组中。
     • 余数的计算方式：(n % (-k) + k) % k，这个表达式是为了保证余数始终为非负数，即使 k 为负数。
     • 商的计算方式：(ans[m - 1] - n) / k，这个表达式是为了处理负数的情况，确保商的计算正确。
   • 输出:
     • 将 ans 数组中的数字按照逆序输出，并根据数字的大小转换为相应的字符（0-9 或 A-Z）。

核心算法:

代码的核心思想是不断地将十进制数 n 除以 k，得到的余数就是 k 进制数的对应位。重复这个过程，直到 n 为 0。然后将得到的余数按照逆序排列，就得到了 k 进制数的表示。

关键点:

• 负数取余: 代码中处理了负数取余的情况，确保余数始终为非负数。
• 字符转换: 通过强制类型转换，将数字转换为对应的字符，实现进制转换的输出。
• 数组逆序: 将得到的余数存储在数组中，最后按照逆序输出，得到正确的 k 进制数。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

/**************************************************************** 
 * Description: 2022_CSP_S_3
 * Author: Alex Li
 * Date: 2023-03-25 17:10:58
 * LastEditTime: 2024-09-12 07:49:49
****************************************************************/
#include <iostream>
#include <algorithm>

  using namespace std;
  
  const int MAXL = 1000;
  
  int n, k, ans[MAXL];
  
  int main(void) 
 {
     cin >> n >> k;
     if (!n) cout << 0 << endl;  //如果n等于0，输出0
     else 
     {
         int m = 0;
         while (n) 
         {
            //一个负数对正数或负数取余，结果都为负，例如：-22%5=-2，-22%-5=-2
             ans[m++] = (n % (-k) + k) % k;  
            //一个正数对正数或负数取余，结果都为正，例如： 22%5=2, 22%-5=2
             n = (ans[m - 1] - n) / k;    
         }
         for (int i = m - 1; i >= 0; i--)
             cout << char(ans[i] >= 10 ?  //强制类型转换，整数转字符型
                          ans[i] + 'A' - 10 :
                          ans[i] + '0');
         cout << endl;
     }
      return 0;
 }

1、该算法的时间复杂度为O(log_k​n)。

正确，while循环n=(ans[m-1]-n)/k

2、删除第 23 行的强制类型转换，程序的行为不变。

错误，没有char的强制类型转换，输出的是数值，不是字符了。

3、除非输入的 n 为 0，否则程序输出的字符数为 O(⌊logk​∣n∣⌋+1)。

错误，输入n=2，k=2时，输出3个字符“110”

4、当输入为“100 7”时，输出为（ 202 ）。

n=100 k=7
while(100) ans[0]=(100%(-7)+7)%7==2
m=1
n=(ans[0]-100)/7=-14
while(-14) ans[1]=(-14%(-7)+7)%7=0
m=2
n=(ans[1]-(-14))/7=2
while(2) ans[2]=(2%(-7)+7)%7=(2+7)%7=2
m=3
n=(ans[2]-2)/7=0
while(0)结束
for循环
i=m-1=2 cout<<‘2’ i–
i=1 cout<<‘0’ i–
i=0 cout<<‘2’
显示结果：202

5、当输入为“-255 8”时，输出为（ 1401 ）。

n=-255 k=89
while(-255) ans[0]=(-255%(-8)+8)%8=1
m=1
n=(ans[0]-(-255))/8=2546/8=32
while(32) ans[1]=(32%(-8)+8)%8=0
m=2
n=(ans[1]-32)/8=-4
while(-4) ans[2]=(-4%(-8)+8)%8=(-4+8)%8=4
m=3
n=(ans[2]-(-4))/8=1
while(1) ans[3]=(1%(-8)+8)%8=(1+8)%8=1
m=4
n=(ans[3]-1)/8=0
while(0)结束
for循环
i=m-1=3 cout<<‘1’ i–
i=2 cout<<‘4’ i–
i=1 cout<<‘0’ i–
i=0 cout<<‘1’
显示结果：1401

6、当输入为“1000000 19”时，输出为（ 87GIB）。

n=1000000 k=19
while(n) ans[0]=(1000000%(-19)+19)%19=(11+19)%19=11
m=1
n=(ans[0]-(1000000))/19=-52631
while(-52631) ans[1]=(-52631%(-19)+19)%19=18
m=2
ans[0]=11 ans[0]>=10 cout<<char(ans[0]+’A’-10)=char(‘A’+1)=’B’
ans[1]=18 ans[1]>=10 cout<<char(ans[1]+’A’-10)=char(‘A’+8)=’I’