python - 无限猴子定理 : Maximum Recursion Depth exceeded

Question

我试图解决无限猴子定理，这是我在网上遇到的编程作业的一部分。

问题陈述是:

The theorem states that a monkey hitting keys at random on a typewriter keyboard for an infinite amount of time will almost surely type a given text, such as the complete works of William Shakespeare. Well, suppose we replace a monkey with a Python function. How long do you think it would take for a Python function to generate just one sentence of Shakespeare? The sentence we’ll shoot for is: “methinks it is like a weasel”

我正在尝试查看 a) 是否有可能生成字符串 b) 在迭代了多少次之后生成了字符串

在查看之前的 SO 问题时，我已将递归限制设置为 10000，但我仍然收到达到最大递归深度的运行时错误。

我仍在寻找使用 Python 的方法。我希望看到关于如何在不遇到递归深度问题的情况下以更好的方式做到这一点的建议。

到目前为止，这是我的代码:

import random
import sys
alphabet=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',' ']
quote="methinks  it is like a weasel"
msg='cont'
count=0

sys.setrecursionlimit(10000)

def generate(msg):
    sentence=''
    while len(sentence)!=27:
        #random.choice() prints a random element from list 'alphabet'
        sentence=sentence+random.choice(alphabet)
    if msg=='cont':
        verify(sentence)

def verify(msg2):
    global count
    if msg2.find(quote)==-1:
        count+=1
        generate('cont')

    else:
        print 'sentence is ',msg2 ,'count is',count

if __name__ == '__main__':
    generate(msg)

Answer 1

在这种情况下，最好三思而后行。如果我们忽略大写和标点符号，您的字符串由 28 个字符组成，每个字符原则上可以是 26 个字母表中的任何一个或一个空格。组合的数量是 27²⁸，恰好是 11972515182562019788602740026717047105681。如果您可以每秒枚举十亿次猜测，则 27²⁸/1E9(尝试/秒)/3600 (秒/小时)/24(小时/天)/365.25(天/年)/14E9(年/当前宇宙年龄) => 27099008032844.297。好消息是您随时可能会偶然发现答案，因此预期的时间量仅为当前宇宙年龄 27 万亿倍的一半。

耗尽堆栈是最不重要的问题。

它被称为无限猴子定理的原因是你可以除以可以并行处理这个问题的猴子的数量，如果那是无穷大，那么解决时间就变成了每只猴子产生猜测的时间，十亿分之一一秒钟。