平衡三进制

定义

平衡三进制，也称为对称三进制。这是一个不太标准的 计数体系。

正规的三进制的数字都是由 0,1,2 构成的，而平衡三进制的数字是由 -1,0,1 构成的。它的基数也是 3（因为有三个可能的值）。由于将 -1 写成数字不方便，我们将使用字母 Z 来代替 -1。

解释

这里有几个例子：

十进制	平衡三进制	十进制	平衡三进制
`0`	`0`	`5`	`1ZZ`
`1`	`1`	`6`	`1Z0`
`2`	`1Z`	`7`	`1Z1`
`3`	`10`	`8`	`10Z`
`4`	`11`	`9`	`100`

该 计数体系 的负数表示起来很容易：只需要将正数的数字倒转即可（Z 变成 1,1 变成 Z）。

十进制	平衡三进制
`-1`	`Z`
`-2`	`Z1`
`-3`	`Z0`
`-4`	`ZZ`
`-5`	`Z11`

很容易就可以看到，负数最高位是 Z，正数最高位是 1。

过程

在平衡三进制的转转换法中，需要先写出一个给定的数 x 在标准三进制中的表示。当 x 是用标准三进制表示时，其数字的每一位都是 0、1 或 2。从最低的数字开始迭代，我们可以先跳过任何的 0 和 1，但是如果遇到 2 就应该先将其变成 Z，下一位数字再加上 1。而遇到数字 3 则应该转换为 0 下一位数字再加上 1。

应用一

把 64 转换成平衡三进制。

首先，我们用标准三进制数来重写这个数：

6 4_{10} = 02101_{3}

让我们从对整个数影响最小的数字（最低位）进行处理：

101 被跳过（因为在平衡三进制中允许 0 和 1）；
2 变成了 Z，它左边的数字加 1，得到 1Z101；
1 被跳过，得到 1Z101。

最终的结果是 1Z101。

我们再把它转换回十进制：

1Z101 = 81 \times 1 + 27 \times (- 1) + 9 \times 1 + 3 \times 0 + 1 \times 1 = 64_{10}

应用二

把 237 转换成平衡三进制。

首先，我们用标准三进制数来重写这个数：

2 37_{10} = 22210_{3}

0 和 1 被跳过（因为在平衡三进制中允许 0 和 1）；
2 变成 Z，左边的数字加 1，得到 23Z10；
3 变成 0，左边的数字加 1，得到 30Z10；
3 变成 0，左边的数字（默认是 0）加 1，得到 100Z10；
1 被跳过，得到 100Z10。

最终的结果是 100Z10。

我们再把它转换回十进制：

100Z10 = 243 \cdot 1 + 81 \cdot 0 + 27 \cdot 0 + 9 \cdot (- 1) + 3 \cdot 1 + 1 \cdot 0 = 237_{10}

性质

对于一个平衡三进制数 $X_{3}$ 来说，其可以按照每一位 $x_{i}$ 乘上对应的权值 $3^{i}$ 来唯一得到一个十进制数 $Y_{10}$ 。

那对于一个十进制数 $Y_{10}$ ，是否 唯一对应一个平衡三进制数 呢？

答案是肯定的，这种性质被叫做平衡三进制的唯一性。

证明

我们利用 反证法 来求证：

假设一个十进制数 $Y_{10}$ ，存在两个 不同的平衡三进制数 $A_{3}, B_{3}$ 转化成十进制时等于 $Y_{10}$ ，即证 $A_{3} = B_{3}$ 。分情况讨论：

当 $Y_{10} = 0$ ，显然 $A_{3} = B_{3} = 0_{3}$ ，与假设矛盾。
当 $Y_{10} > 0$ ：
- 将 $A_{3}$ ， $B_{3}$ 的数位按低位到高位编号，记 $a_{i}$ 为 $A_{3}$ 的第 $i$ 位， $b_{i}$ 为 $B$ 的第 $i$ 位。在 $A_{3}, B_{3}$ 中，必存在 $i$ 使得 $a_{i} \neq b_{i}$ 。可以发现第 $i - 1, i - 2, \dots, 0$ 位均与证明无关。因此，将 $A_{3}, B_{3}$ 按位右移 $i$ 位，得到 $A_{3}^{'}, B_{3}^{'}$ ，原问题等价于证明 $A_{3}^{'} = B_{3}^{'}$ 。
- 对于 $A_{3}^{'}, B_{3}^{'}$ 第 $0$ 位， $a_{0} \neq b_{0}$ 。假设 $b_{0} > a_{0}$ （ $a_{0} > b_{0}$ 时结果相同），易知 $b_{0} - a_{0} \in {1, 2}$ 。 $A_{3}^{'}$ 的位 $i = 1, 2, 3, \dots$ 对于 $A_{3}^{'}$ 的值的贡献为 $S_{1} = a_{1} \times 3^{1} + a_{2} \times 3^{2} + \dots$ ， $B_{3}^{'}$ 的位 $i = 1, 2, 3, \dots$ 对于 $B_{3}^{'}$ 的值的贡献为 $S_{2} = b_{1} \times 3^{1} + b_{2} \times 3^{2} + \dots$ 。由于 $A_{3}^{'} = B_{3}^{'}$ ，得 $S_{1} - S_{2} = b_{0} - a_{0}$ 。 $S_{1}, S_{2}$ 有公因子 $3$ ，而 $b_{0} - a_{0}$ 不能被 $3$ 整除，与假设矛盾，因此 $A_{3}^{'} \neq B_{3}^{'}$
当 $Y_{10} < 0$ ，证法与 $Y_{10} > 0$ 相同。

故对于任意十进制 $Y_{10}$ ，均有唯一对应的平衡三进制 $X_{3}$ 。

练习题

Topcoder SRM 604 PowerOfThree

本页面部分内容译自博文 Троичная сбалансированная система счисления 与其英文翻译版 Balanced Ternary。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

本页面最近更新：2025/8/29 18:05:34，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Yanjun-Zhao, Enter-tainer, Tiphereth-A, Falicitas, HeRaNO, iamtwz, ImpleLee, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用