algorithm - 将数字序列编码为单个数字——使用中国余数定理

Question

我需要用整数 K 对任意数量的元素(但有限)的序列 S 进行编码，并且能够解码 K 以取回初始序列。

我需要这样做，以便计算机能够很好地处理数字 K。

我是这样做的(用 lisp 语言):

• 假设序列S有n个元素e1, ... en

• 生成前n个质数p1 ... pn

• 写 K = p1^e1 + p2 ^ e2 + ... + pn ^ en

我试过这个方法。然而，我得到了巨大的数字。

我知道可以用中国余数定理来解决这个问题，而且这样得到的K并没有那么大。

有人可以帮助我使用这个定理来编码一个序列吗？

编辑:

我希望通过一个具体的简单示例来了解使用ch r th 进行编码的算法。我无法理解来自维基百科和其他网络资源的理论思想。

Answer 1

您正在寻找Gödel numbering of sequences .这是一种将(有限)数字序列编码为单个数字的方法。中国剩余定理给出了一种递归的构造方法。