无限猴子定理:超出最大递归深度

Question

我试图解决无限猴子定理,这是我在网上遇到的编程任务的一部分.

问题陈述是:

该定理指出,猴子在打字机键盘上随机敲击键无限时间几乎肯定会输入一个给定的文本,例如威廉·莎士比亚的全集.好吧,假设我们用Python函数替换猴子.你认为Python函数生成莎士比亚的一个句子需要多长时间？我们要拍的句子是:"它就像狡猾的人一样"

我试图看a)是否有可能生成字符串b)生成字符串后迭代次数

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

我仍然在寻找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万亿倍的一半.

吹掉堆栈是你遇到的最少问题.

它被称为无限猴子定理的原因是你可以除以可以并行处理它的猴子的数量,如果那是无穷大,那么求解时间就变成每猴子产生猜测的时间量,十亿分之一秒.