平衡三进制,也称为对称三进制。这是一个不太标准的 计数体系。正规的三进制的数字都是由 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
转换成平衡三进制。
首先,我们用标准三进制数来重写这个数:
让我们从对整个数影响最小的数字(最低位)进行处理:
101
被跳过(因为在平衡三进制中允许0
和1
);2
变成了Z
,它左边的数字加1
,得到1Z101
;1
被跳过,得到1Z101
。
最终的结果是 1Z101
。
我们再把它转换回十进制:
把 237
转换成平衡三进制。
首先,我们用标准三进制数来重写这个数:
0
和1
被跳过(因为在平衡三进制中允许0
和1
);2
变成Z
,左边的数字加1
,得到23Z10
;3
变成0
,左边的数字加1
,得到30Z10
;3
变成0
,左边的数字(默认是0
)加1
,得到100Z10
;1
被跳过,得到100Z10
。
最终的结果是 100Z10
。
我们再把它转换回十进制:
对于一个平衡三进制数
答案是肯定的。
我们利用 反证法 来求证:
假设一个十进制数
当
$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,...$ 对于$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$ 相同。
故对于任意十进制