WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数学部分简介
符号
复数
位运算
快速幂
进位制
高精度计算
平衡三进制
素数
最大公约数
欧拉函数
筛法
欧拉定理 & 费马小定理
类欧几里德算法
裴蜀定理
乘法逆元
线性同余方程
中国剩余定理
二次剩余
BSGS
原根
卢卡斯定理
莫比乌斯反演
杜教筛
Min_25 筛
分解质因数
多项式部分简介
拉格朗日插值
快速傅里叶变换
快速数论变换
快速沃尔什变换
多项式求逆
多项式开方
多项式除法|取模
多项式对数函数|指数函数
多项式牛顿迭代
多项式多点求值|快速插值
多项式三角函数
多项式反三角函数
常系数齐次线性递推
生成函数简介
普通生成函数
指数生成函数
向量
矩阵
高斯消元
线性基
线性规划简介
单纯形算法
排列组合
卡特兰数
斯特林数
贝尔数
伯努利数
康托展开
容斥原理
抽屉原理
概率初步
置换群
斐波那契数列
博弈论
牛顿迭代法
数值积分
分段打表
64 objects
本站非官方,所收集资源均来源于网络。
平衡三进制 - 数学
平衡三进制,也称为对称三进制。这是一个不太标准的 **计数体系** 。正规的三进制的数字都是由 `0` , `1` , `2` 构成的,而平衡三进制的数字是由 `-1` , `0` , `1` 构成的。它的基数也是 `3` (因为有三个可能的值)。由于将 `-1` 写成数字不方便,我们将使用字母 `Z` 来代替 `-1` 。 这里有几个例子: ```text 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 -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'$ > 3. 当 $Y_{10}<0$ ,证法与 $Y_{10}>0$ 相同。 故对于任意十进制 $Y_{10}$ ,均有唯一对应的平衡三进制 $X_3$ 。 ## 练习题 [Topcoder SRM 604, Div1-250](https://community.topcoder.com/stat?c=problem_statement&pm=12917&rd=15837) **本页面部分内容译自博文 [Троичная сбалансированная система счисления](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。**