第十八单元：进制转换 · 除基取余算法

欢迎来到计算机科学 5 的第十八单元！这一单元你将潜入计算机最底层的语言——数制。我们平时数数用的是十进制，但计算机的世界建立在二进制之上。在关卡"形状和性状"里，你要命令魔法机器人处决食人魔，而机器人只听得懂二进制和三进制的命令。于是你必须写出一套算法，把十进制数字翻译成机器人能理解的进制字符串。这背后的核心，是计算机科学中最经典的算法之一：除基取余（divide and take remainder）。

18.1.1 基数与数字系统（Base and Number Systems）

18.1.1.1 "基数"决定了有几个数字符号 The base determines how many digits exist

关卡说明讲得很生动：我们日常用的是十进制（decimal），dec 表示 10，就像 decade（十年）。此外还有二进制（binary，bi = 2）和三进制（trinary，tri = 3）。每种数字系统的"底数"就叫基数（Base）：十进制是 Base 10，二进制是 Base 2。基数决定了这个系统里一共有几种数字符号：

18.1.2 同一个数的多种写法（One Number, Many Notations）

18.1.2.1 数字 9 在各进制里长得都不一样 The number 9 looks different in each base

同一个"量"，在不同进制里写法完全不同。关卡用数字 9 做了绝妙的演示——它在十进制是 9，但在三进制变成 100，在二进制变成 1001。数量没变，只是"记数的规则"变了。

18.2.1 除法与余数（Division and Remainder）

18.2.1.1 用目标基数当除数，反复相除 Divide repeatedly by the target base

把十进制数转成别的进制，核心方法是：用想要的基数作为除数，反复相除，并记下每一步的余数。关卡原话是："将一个十进制数字转换成另一个进制的方法是用想要的基数作为除数，并观察余数。"每次相除产生一个余数（这一位的数字）和一个商（下一轮要继续处理的数），如此循环，直到商变成 0。

18.2.2 手算示例（Working It Out by Hand）

18.2.2.1 把 9 转成三进制和二进制 Converting 9 to base 3 and base 2

跟着关卡的例子手算一遍，算法就一目了然了。转换时不断除以基数、记录余数，直到商为 0；最后把所有余数从下往上（从最后到最先）读，就是答案。

9 ÷ 3 = 3 ... 余 0
3 ÷ 3 = 1 ... 余 0
1 ÷ 3 = 0 ... 余 1

# 从下往上读：100 ✓

9 ÷ 2 = 4 ... 余 1
4 ÷ 2 = 2 ... 余 0
2 ÷ 2 = 1 ... 余 0
1 ÷ 2 = 0 ... 余 1

# 从下往上读：1001 ✓

18.3.1 while 迭代到商为 0（Loop Until Zero）

18.3.1.1 只要 number 不是 0，就继续 Keep going while number is not zero

手算里"反复相除直到商为 0"这个过程，用代码写就是一个 while 循环。循环条件是 while number != 0——只要 number 还没被除到 0，就继续处理下一位。每循环一次就处理一位数字，当 number 终于变成 0，说明所有位都处理完了，循环自然结束。

def toTernary(number):
    string = ""              # 从空字符串开始
    while number != 0:       # 只要还没除到 0，就继续
        # ...取余、更新 number、拼字符串...
        pass
    return string

18.3.2 取余与更新 number（Remainder and Update）

18.3.2.1 取余得到这一位，整除得到下一轮 Remainder gives a digit; division gives the next number

循环体里做两件算术：先用取余运算符 % 算出这一位的数字 remainder = number % 3；再把 number 更新为它除以基数的商，准备下一轮。关卡用了一个巧妙的写法：number = (number - remainder) / 3——先减掉余数让它能整除，再除以基数，确保得到的是干净的整数商。

# 1. 取余数：这一位的数字
remainder = number % 3

# 2. 更新 number：减掉余数后除以基数（得到商）
number = (number - remainder) / 3

18.3.3 字符串前置拼接（Prepending to the String）

18.3.3.1 新余数拼在旧字符串"前面" The new digit goes in front

这是整个算法的点睛之笔，也呼应了"余数要倒着读"的规律。每算出一个余数，就把它拼在已有字符串的前面：string = remainder + string。因为最先算出的是最低位、最后算出的是最高位，所以后来的余数要不断"挤到前面去"，最终字符串的顺序就自然正确了。

# 把新余数拼在字符串的【前面】（不是后面！）
string = remainder + string

18.4.1 换个除数就换个进制（Change the Divisor）

18.4.1.1 同一套算法，只改基数 Same algorithm, just a different base

除基取余算法最优雅的地方在于它的通用性：转成几进制，就把除数改成几。toTernary（三进制）用 % 3 和 / 3；toBinary（二进制）只需把它们全换成 % 2 和 / 2，其余逻辑一字不差。关卡也提示："再次重复这些步骤：获取余数、减去余数和追加字符串。记住二进制用另一种方式表示 2！"——这里"另一种方式"就是指把基数从 3 改成 2。

while number != 0:
    remainder = number % 3
    number = (number-remainder)/3
    string = remainder + string

while number != 0:
    remainder = number % 2
    number = (number-remainder)/2
    string = remainder + string

这一节聚焦关卡的策略、思路与算法设计，只展示用于说明的关键片段，完整通关程序请你自己动手完成。

关卡 · 形状和性状

🤖 形状和性状 —— 让机器人听懂进制命令

图2：形状和性状——找出最危险的食人魔，把它的血量转成三进制、类型转成二进制，说给机器人步行者听

策略：把敌人属性翻译成机器人的语言

本关是本单元唯一的关卡，也是进制转换的综合实战。魔法机器人步行者能替你处决食人魔，但它只接受进制字符串命令：命令由两部分组成——敌人血量的三进制表示，加上敌人类型的二进制表示。策略是：持续找出场上最危险的敌人（血量最高者），把它的血量和类型分别转换成对应进制，拼成命令字符串说给机器人听。

思路拆解

算法有三块。第一，补全 toBinary 函数：关卡已给好三进制版 toTernary，你要照着写二进制版——逻辑完全相同，只把 % 3 改成 % 2、/ 3 改成 / 2。第二，找最危险的敌人：辅助函数 findMostDangerous 遍历所有敌人，记录血量最高的那一个（血量越多越强）。第三，在主循环里下命令：把 toTernary(血量) 和 toBinary(类型) 拼接成机器人认得的格式，用 hero.say(...) 说出来。

# 关键片段一：补全 toBinary（除数从 3 改成 2）
def toBinary(number):
    string = ""
    while number != 0:
        remainder = number % 2
        number = (number - remainder) / 2
        string = remainder + string
    return string

# 关键片段二：找到最危险者，拼接进制命令
while True:
    enemies = hero.findEnemies()
    dangerous = findMostDangerous(enemies)
    if dangerous:
        # 命令格式：三进制(血量) + " " + 二进制(类型)
        hero.say(toTernary(dangerous.health) + " " + toBinary(dangerous.type))

toBinary 是 toTernary 的"复制改数"：本关最省力的做法，就是把已给好的 toTernary 整段逻辑复制过来，只把两个基数 3 改成 2。这也印证了除基取余算法的通用性——同一个骨架，改个除数就适配新进制。

findMostDangerous 的思路：这个辅助函数用了经典的"打擂台"求最值算法：先假设没有最危险者（mostDangerous = None、mostHealth = 0），遍历每个敌人，谁的血量比当前记录更高，就把它换上擂台。遍历结束，擂台上的就是血量最高、最危险的敌人。

两部分命令别弄反：命令的顺序是"血量三进制在前、类型二进制在后"，中间用空格分隔。如果把 toTernary 和 toBinary 用错了对象（比如给血量用二进制），机器人就会误解命令、攻击错误的目标。

18.6.1 新手最容易踩的坑（Pitfalls for Beginners）

18.6.1.1 进制转换的典型问题 Typical issues with base conversion

图3：字符串拼错方向、循环条件写错、除数用错、忘记 return，是本单元最常见的失误