广义记数系统 / 进制

· · 算法·理论

记数列 a_0,a_1,a_2,\cdots 为严格递增的正整数数列,且 a_0=1。对任意正整数 x,将其表示为 a_i 的线性组合:

x=\sum_{i=0}^n c_ia_i

其中,c_i 为系数,属于某个集合 S_i。n 为满足 a_n \le x < a_{n+1} 的最大的 n。

称 x 对应的 c_0,c_1,\cdots,c_n 为 x 的编码。一般地,我们希望 x 的编码唯一,这可以通过限制 S_i 实现。

一些常见的进制系统:

事实上,只要 \forall k, \sum \limits_{i=0}^k c_i a_i < a_{k+1},使用贪心算法进行编码和解码,则编码唯一。