阅读程序3解析

 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
#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) 
         {
             ans[m++] = (n % (-k) + k) % k;  //一个负数对正数或负数取余,结果都为负,例如:-22%5=-2,-22%-5=-2
             n = (ans[m - 1] - n) / k;    //一个正数对正数或负数取余,结果都为正,例如: 22%5=2, 22%-5=2
         }
         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(logk​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’

Scroll to Top