1

我正在考虑编写一个程序,它将随机生成一串 N 个字符,其中 N 是本书 X 中的字符数,包括空格、正确的标点符号和大写。在每次随机字符生成期间,我都会检查输出是否与书 X 的实际文本匹配。

假设使用英文字母,并在生成器中编码了一些健全的语法规则,编写一个程序来随机生成书 X 的文本在计算上是否可行?

可以实施什么样的优化来使问题更容易解决?

使用现代四核 (i5) 台式计算机需要多长时间。使用超级计算机怎么样?

粗略来说,一本标准格式的精装书每页大约有300-350个字,每个字是五个字符加一个空格。因此,典型的书页有 1,500 到 1,800 个字符(不算空格)。如果我们将 250 页视为标准的书本长度,那么如果不计算空格,您所说的可能是 400,000 个字符;如果你这样做,500,000。资源

因此,假设书 X 有 500,000 个字符,而我们的字母表大小为 30。有人能做得比 30^500,000 ~(4.2 × 10^738560) 更好吗?

4

3 回答 3

3

如果您正在寻找一个如此疯狂以至于没有其他人尝试过的想法,那么您将不得不更加努力:-) - 请参阅http://www.bbc.co.uk/news/technology-15060310 ,,

几百万只虚拟猴子通过在虚拟打字机上随机敲击键,接近重现莎士比亚的全集。

他们做得如何的运行总和表明重新创建已完成 99.990%。

完成的第一首单曲是《情人的抱怨》这首诗。

该项目由美国程序员 Jesse Anderson 建立,通过家用 PC 协调坐在亚马逊 EC2 云计算系统上的虚拟猴子。

(+ 更多信息,包括与真正猴子的实践经验)

于 2013-06-30T04:52:07.950 回答
1

您可以将其建模为单词的排列,而不是字符的排列——大多数书籍使用的新词很少(如果有的话)(例外是像 Lewis Carroll 的“Through thelooking Glass”这样的书籍——你可能需要对这首诗“Jabberwocky”进行建模"作为字符的排列)。此外,字典中的大多数单词都没有在文学中使用,因此您可以将自己限制在一个字典中,比如 10,000 个最常用的单词,并且仍然占大多数书籍。

使用语法来限制单词的顺序比较棘手,因为很多书籍使用非法的单词顺序(尤其是在对话中)。也许您可以对不在引号中的句子(即非对话)使用标准英语解析器,以过滤掉非法的词序,然后对引号中的句子使用直词排列。显然,这不适用于像《尤利西斯》这样语法法则被扔出窗外的书。

于 2013-06-29T22:46:30.473 回答
0

我会为此使用 遗传算法

于 2013-06-29T22:40:26.040 回答