An autogram http://en.wikipedia.org/wiki/Autogram是一个描述其包含的字符的句子,通常枚举字母表中的每个字母,但也可能枚举它包含的标点符号。这是 wiki 页面中给出的示例。
这句话使用了两个a、两个c、两个d、二十八个e、五个f、三个g、八个h、十一个i、三个l、两个m、十三个n、九个o、两个p、五个r、二十五个s、23 个 t、6 个 v、10 个 w、2 个 x、5 个 y 和 1 个 z。
想出一个字母是很困难的,因为在你完成句子之前你不知道它包含多少个字母。这促使我问:是否可以编写一种可以创建亲笔签名的算法?例如,给定参数将作为输入的句子的开头,例如"This sentence employs"
,并假设它使用与上面相同的格式"x a's, ... y z's"
.
我并不是要求你真正编写一种算法,尽管无论如何我很想看看你是否知道存在一个算法或者想尝试编写一个算法;相反,我很好奇这个问题首先是否可以计算。
你在问两个不同的问题。
"is it possible to write an algorithm which could create an autogram?"
有一些算法可以找到亲笔签名。据我所知,他们使用随机化,这意味着这样的算法可能会找到给定起始文本的解决方案,但如果找不到,那么这并不意味着不存在。这将我们带到第二个问题。
"I'm curious as to whether the problem is computable in the first place."
可计算意味着存在一种算法,对于给定的起始文本,要么输出一个解决方案,要么指出不存在解决方案。上述算法无法做到这一点,并且穷举搜索也是行不通的。因此我想说这个问题是不可计算的。然而,这颇具学术兴趣。在实践中,随机算法工作得足够好。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)