author: Enter-tainer, Falicitas, HeRaNO, iamtwz, ImpleLee, Tiphereth-A, Xeonacid, Yanjun-Zhao

## 定义

平衡三进制，也称为对称三进制．这是一个广义进位系统．

正规的三进制的数字都是由 `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` 转换成平衡三进制．

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

$$
\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}$，是否 **唯一对应一个平衡三进制数** 呢？

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

???+ note "证明"
    我们利用 **反证法** 来求证：
    
    假设一个十进制数 $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'$
    3.  当 $Y_{10}<0$，证法与 $Y_{10}>0$ 相同．
    
    故对于任意十进制 $Y_{10}$，均有唯一对应的平衡三进制 $X_3$．

## 练习题

[Topcoder SRM 604 PowerOfThree](https://archive.topcoder.com/ProblemStatement/pm/12917)

**本页面部分内容译自博文 [Троичная сбалансированная система счисления](http://e-maxx.ru/algo/balanced_ternary) 与其英文翻译版 [Balanced Ternary](https://cp-algorithms.com/algebra/balanced-ternary.html)．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．**
