5

我正在为校验位方案实现 Verhoeff 算法，但网络资源中似乎存在一些关于哪个排列循环应该构成排列表的基础的分歧。

维基百科使用：(36)(01589427)

显然，Numerical Recipies 使用不同的循环，本书使用：(0)(14)(23)(56789)，引自 Winters 1990 年的一篇文章。它还指出 Verhoeff 使用了维基百科的引用。

现在，我的数论有点生疏了，但是维基百科的循环显然会在 8 次方之后重复，而一本书需要 10，尽管它说 s^8=s。表 2.14(b) 在 2 个周期中还有其他错误，所以无论如何这都是可疑的。

不幸的是，我没有原始文章的副本（而且我太紧张了，无法支付/厌恶出版商仍然要索取 40 年的知识），也没有要检查的数字食谱副本（并且我不愿意安装他们的妄想症引起的复制保护插件以在线查看）。

那么有人知道哪个是正确的吗？他们都正确吗？

4

2 回答 2

3

这里有一个旧版的数字食谱，以 PDF 格式提供。Verhoeff 算法在第 20.3 节中描述。它使用与维基百科文章相同的排列。

于 2010-05-20T11:05:27.007 回答
2

排列 (0)(14)(23)(56789) 优于排列 (36)(01589427)。这是因为，(36)(01589427) 只能检测到 88.89% 的单个转置错误，而 (0)(14)(23)(56789) 可以检测到所有这些。如果使用 (36)(01589427)，则考虑将数字代码 716 指定为 0 作为校验位。即，代码将是 7160。但是，如果数字 1 和 6 被调换，则此校验位方案不会给出错误，因为校验和为零。这不是 (0)(14)(23)(56789) 的情况。

于 2011-12-23T14:15:26.063 回答