Balanced Ternary

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

这里有几个例子：

    0    0
    1    1
    2    1Z
    3    10
    4    11
    5    1ZZ
    6    1Z0
    7    1Z1
    8    10Z
    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 转换成平衡三进制。

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

\text 64_{10} = 02101_3

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

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

最终的结果是 1Z101。

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

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

应用二

把 237 转换成平衡三进制。

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

\text 237_{10} = 22210_3
  • 0 和 1 被跳过（因为在平衡三进制中允许 0 和 1)；
  • 2 变成 Z，左边的数字加 1，得到 23Z10；
  • 3 变成 0，左边的数字加 1，得到 30Z10；
  • 3 变成 0，左边的数字（默认是 0）加 1，得到 100Z10；
  • 1 被跳过，得到 100Z10。

最终的结果是 100Z10。

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

\texttt{ 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 。分情况讨论：

  1. 当 Y_{10}=0 ，显然 A_3 = B_3 = 0_3 ，与假设矛盾。

  2. 当 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,... 对于 A_3' 的值的贡献为 S_1 = a_1 \times 3^1 + a_2 \times 3^2+ \dots ， B_3' 的位 i=1,2,3,... 对于 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, Div1-250

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

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments