★ FEATURED ARTICLE 第一题进制减半——数字魔法转换器一、故事背景数字王国的翻译任务想象一下我们生活在一个十进制王国。平常使用的数字是0、1、2、3、4、5、6、7、8、9但是数字王国里还有其他进制的居民。例如二进制只有0和1。八进制使用07。十进制使用09。十六进制使用09和AF。现在国王给了我们一个任务把一个以 m * n 为进制的数字转换成以 n为进制的数字。原题将这个转换称为“进制减半”并要求按照从高位到低位的顺序输入各个数位。举个例子假设n 2 m 2那么原来的进制就是m*n 2*2 4也就是说我们要把一个四进制数转换成二进制数。例如四进制数123它表示而27的二进制表示是11011所以四进制 123 二进制 11011这就是我们要完成的魔法。二、为什么不能直接使用普通整数原题给出的数字最多有18位而且可能超过普通整数类型的表示范围。所以程序没有直接把整个数字存进一个int或long long变量而是采用了数组。程序的核心数组是long long b[N];我们可以把它想象成一排数字储物柜b[0] b[1] b[2] b[3] b[4] ...每个格子保存一位数字。注意程序把最低位放在b[0]而不是最高位。例如数字123存入数组后数组下标012数组内容321对应数位个位十位百位这样设计有什么好处因为进制转换的过程中需要反复进行除法和取余而从最低位开始处理非常方便。三、核心魔法为什么要不断除以n我们先不看代码理解数学原理。假设有一个十进制数27想把它转换成二进制。不断除以2当前数字除以2的商余数271311361630311101把余数从下往上读11011这就是二进制结果。因此进制转换的基本思想是不断除以目标进制。记录每次除法的余数。当商变成0时停止。把余数倒过来读。但是原题的数字可能非常大不能直接使用普通整数进行除法。所以程序采用一种更巧妙的方法把原来的每一位数字保存到数组中再模拟“整个数除以n”的过程。四、程序整体结构原题程序如下空缺处用①⑤表示#include iostream constexpr int N 100005; long long b[N]; int main() { long long n, m, d; std::cin n m d; int len 1; for (int i 0; i d; i) { long long x; std::cin x; for (int j len; j 1; j--) b[j] ①; b[0] ②; len; for (int j 0; j len; j) if (b[j] n) { b[j 1] ③; b[j] ④; if (j 1 len) len; } } while (⑤) len--; for (int i len - 1; i 0; i--) std::cout b[i] ; return 0; }我们先抓住整个程序的主线读入一位原数 → 更新数组 → 对整个数组进行除法处理 → 去掉前导零 → 输出结果。下面逐个填空。五、第34题①处应该填什么原题选项A.b[j] * nB.b[j] * mC.b[j - 1] * nD.b[j - 1] * m1. 先看这段代码for (int j len; j 1; j--) b[j] ①;它的作用是什么每次读入一个新的数位后程序需要把原来保存的数字整体向高位移动一格再把新读入的数位放到最低位。例如原来数组保存b[2] b[1] b[0] 1 2 3现在读入新数位4。我们需要得到b[3] b[2] b[1] b[0] 1 2 3 4注意数组实际是倒着保存的所以原来的每个数位都要向更大的下标移动一格。2. 应该怎样移动原来b[2] 1; b[1] 2; b[0] 3;移动后b[3] b[2]; b[2] b[1]; b[1] b[0];因此正确的移动方式是b[j] b[j - 1] ;答案第34题D、b[j - 1] * m输入的是 m*n 进制的要转换成n进制的,所以要乘 m.记忆口诀数组整体向高位移动b[j] b[j - 1] ;就是把前一个格子的内容搬到后一个格子里。六、第35题②处应该填什么原题选项A.x * nB.xC.0D.m1. 看看新读入的数字放在哪里代码b[0] ②;我们刚才已经知道原来的数字整体向高位移动。新读入的数位应该放在最低位也就是b[0]。假设刚刚读入x 7那么最低位就应该保存7。因此b[0] x;答案第35题B。记忆口诀新数字放最低位b[0] x;七、第36题③处应该填什么原题选项A.b[j] / mB.b[j] % nC.b[j] % mD.b[j] / n1. 先理解数组中的进位我们要把一个数转换成n进制。在n进制中每一位只能是0、1、2、……、n-1如果某一位达到n或超过n就必须向高位进位。例如在二进制中2 10二进制所以当前位留下0 向高位进1对于一般的n进制当前位的数值 原数值 % n 进位 原数值 / n2. 看看原题代码if (b[j] n) { b[j 1] ③; b[j] ④; }其中b[j 1] ③;是把进位加到更高一位。因此③应该计算当前数位能够向高位贡献多少个n。也就是b[j] / n答案第36题D。八、第37题④处应该填什么原题选项A.b[j] / mB.b[j] % nC.b[j] % mD.b[j] / n1. 当前位需要留下什么假设我们正在处理一个二进制数位。当前格子里有b[j] 5二进制中5 101二进制所以当前位留下1 向高位进2一般情况下当前位留下 b[j] % n进位则是b[j] / n因此b[j] b[j] % n;答案第37题B。记忆口诀进制转换中的除法与取余进位 b[j] / n; 当前位 b[j] % n;这与十进制竖式加法中的“满十进一”是同一个思想只不过这里变成了“满n进一”。九、第38题⑤处应该填什么原题选项A.len 0 b[len - 1] 0B.len 0 b[0] 0C.len 1 b[len - 1] 0D.len 1 b[0] 01. 为什么需要删除前导零例如某个结果在数组中保存为b[3] 0 b[2] 0 b[1] 1 b[0] 1从高位到低位输出0011但是我们通常希望输出11因此程序需要把最高位多余的0去掉。2. 最高位在哪里由于数组是倒着保存的b[0]最低位 b[1]次低位 b[2]更高位 ……所以当前最高位是b[len - 1]如果它等于0就可以把长度减1len--;3. 为什么必须保证len 1假设转换结果是0。如果不限制长度程序可能不断删除最高位最后长度变成0导致输出循环无法正确输出一个0。因此必须保留至少一位。正确条件是len 1 b[len - 1] 0答案第38题C。十、第一题完整答案与代码答案汇总题号空格正确选项填入内容34①Db[j - 1] * m35②Bx36③Db[j] / n37④Bb[j] % n38⑤Clen 1 b[len - 1] 0填空后的完整程序#include iostream constexpr int N 100005; long long b[N]; int main() { long long n, m, d; std::cin n m d; int len 1; for (int i 0; i d; i) { long long x; std::cin x; for (int j len; j 1; j--) b[j] b[j - 1] * m; b[0] x; len; for (int j 0; j len; j) if (b[j] n) { b[j 1] b[j] / n; b[j] b[j] % n; if (j 1 len) len; } } while (len 1 b[len - 1] 0) len--; for (int i len - 1; i 0; i--) std::cout b[i] ; return 0; }第一题通关口诀先整体乘m再加新数位满n就进位余数留当前最后去前导零从高位向低位输出。
阅读完成 · 觉得有帮助？
