签名是描述其字母的句子。例如,来自维基百科:



手动创建这些句子非常困难,因此肯定可以最适合该任务的计算机,但是如何有效地做到这一点呢? 有什么有效的算法可查找具有给定初始字符串的自动签名?链接的自动签名怎么样?前一个句子描述了下一个的内容? 尽管this线程是关于同一主题的,但它仅要求存在,而其中描述的所有算法在实践中都太慢了。

天真的方法是在可能的数字组合中搜索,例如从0到40,以寻找可能的解决方案。但是,如果有40 ^ 26的可能性,这将花费很长的时间。

通过对字母组合进行一些初始猜测,然后仅搜索在任一侧与我们的猜测相差3个字母的字母,我们可以改善搜索质量,但可能会丢失解决方案。这仍然需要6 ^ 26次。即使每秒检查一百万次,也要花费五百万年以上的时间才能完成。

进一步的改进来自于认识到a,b,c,d,j,k,m,p,q和z永远不会出现在任何数字字中,因此这十个字母的计数由初始字符串固定。我们现在只有3万亿个组合-仍然不是很好。

最好先进行初步猜测,然后...

  • 创建一个新的“autogram”,该字母描述先前的autogram
  • 的字母计数
  • 检查我们是否重复了一个自动签名。如果有,并且循环的长度为1,则操作完成。否则,请稍微修改猜测并转到步骤1。

  • ...但这有其局限性。尽管此任务看似无能为力,但其他人却找到了成功。实际上,http://autograms.net/甚至有25个链接的自动签名链。如何?

    最佳答案

    一种有效的方法是将短语替换为描述前一个短语的短语,直到它们相同为止,即该短语是一个自动重读。
    但这在许多情况下可能不起作用。

    关于algorithm - Autogram算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/33767932/

    10-09 00:46