2

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

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

我这样做了(在 lisp 中):

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

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

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

我试过这个方法。但是,我得到了巨大的数字。

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

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

编辑:

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

4

1 回答 1

2

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

于 2013-01-16T12:16:16.813 回答