将一个数列编码为一个单独的数字——使用中国余数定理

Question

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

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

I did it so (in lisp):

• 假设序列S有n个元素e1，…在

• 生成前n个素数p1…pn

• write K = p1^e1 + p2 ^ e2 +…+ pn ^ en

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

我知道可以用chinese remainder theorem来解决这个问题，所以得到的K并没有那么大。

谁能帮我用这个定理来编码一个序列?

编辑:

我希望看到使用ch r th编码的算法使用一个具体的简单的例子。我无法理解维基百科和其他网络资源的理论思想

Answer 1

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