广义记数系统 / 进制 stripe_python · 2026-05-02 16:55:30 · 算法·理论 记数列 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 实现。 一些常见的进制系统: Fibonacci 编码:a_i=\text{Fib}(i),且 S_i=\{0,1\} \land c_i \times c_{i+1}=0; 阶乘进制:a_i=i!,且 S_i=\{0,1,\cdots,i\}。 事实上,只要 \forall k, \sum \limits_{i=0}^k c_i a_i < a_{k+1},使用贪心算法进行编码和解码,则编码唯一。