跳转至

平衡三进制

定义

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

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

解释

这里有几个例子:

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
    0    0
    1    1
    2    1Z
    3    10
    4    11
    5    1ZZ
    6    1Z0
    7    1Z1
    8    10Z
    9    100

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

Text Only
1
2
3
4
5
    -1   Z
    -2   Z1
    -3   Z0
    -4   ZZ
    -5   Z11

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

过程

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

应用一

64 转换成平衡三进制。

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

\[ \text 64_{10} = 02101_3 \]

让我们从对整个数影响最小的数字(最低位)进行处理:

  • 101 被跳过(因为在平衡三进制中允许 01);
  • 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 \]
  • 01 被跳过(因为在平衡三进制中允许 01);
  • 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,\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, Div1-250

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