平衡三進制

定義

平衡三進制，也稱為對稱三進制。這是一個不太標準的 計數體系。

正規的三進制的數字都是由 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}\)，是否 唯一對應一個平衡三進制數 呢？

答案是肯定的，這種性質被叫做平衡三進制的唯一性。

證明

我們利用 反證法 來求證：

假設一個十進制數 \(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, Div1-250

本頁面部分內容譯自博文 Троичная сбалансированная система счисления 與其英文翻譯版 Balanced Ternary。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用