Бесконечная теорема обезьяны: максимальная глубина рекурсии превышена

Question

Я пытался решить Бесконечную теорему обезьяны, которая является частью задания программирования, с которым я столкнулся в Интернете.

Постановка задачи:

теорема утверждает, что обезьяна поражая ключи случайным образом на клавиатуре пишущей машинки для бесконечного количества времени, почти наверняка ввести данный текст, например, полное собрание сочинений Уильяма Шекспир. Ну, предположим, мы заменим обезьяну на функцию Python. Как долго вы думаете, что для функции Python потребуется генерировать только одно предложение Шекспира? Приговор мы будем стрелять так: «Мне кажется, это как ласка»

Я пытаюсь увидеть), будет ли это возможно генерировать строку б) Через сколько итераций были строка генерируется

Я установил предел рекурсии как 10000, глядя на предыдущий вопрос SO, но я все еще получаю ошибку времени выполнения для достижения максимальной глубины рекурсии.

Я все еще нахожу свой путь вокруг питона. Я надеюсь увидеть предложения о том, как я мог бы сделать это лучше, не сталкиваясь с проблемой глубины рекурсии.

Вот мой код до сих пор:

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

Было бы лучше не называть verify() от generate() (и наоборот) в вероятном случае, что обезьяны не писал Шекспир.

Имеет две функции, которые неоднократно звонят друг другу, не возвращаясь, если что вызывает превышение глубины рекурсии.

Вместо использования рекурсии вы можете просто проверить, было ли вы подготовлено предложение с помощью итеративного подхода. Например, есть цикл, который принимает случайное предложение, а затем проверяет, соответствует ли оно вашему требуемому предложению, и если да, выводит количество попыток (и если они не возвращаются к началу).

Answer 2

Это случай, когда лучше подумать, прежде чем делать. Если мы игнорируем капитализацию и пунктуацию, ваша строка состоит из 28 символов, каждая из которых может в принципе быть любой из 26 букв алфавита или пробела. Количество комбинаций составляет 27 , что составляет 11972515182562019788602740026717047105681. Если вы можете перечислить миллиард догадок в секунду, 27/1E9 (попытки/сек)/3600 (сек/час)/24 (час/день))/365,25 (дней/год)/14E9 (год/текущий возраст Вселенной) => 27099008032844.297. Хорошей новостью является то, что вы можете наткнуться на ответ в любой момент, поэтому ожидаемое количество времени составляет лишь половину 27 триллионов раз в текущем возрасте Вселенной.

Выдувание стека является наименьшей из ваших проблем.

Причина, по которой она называется бесконечной теоремой обезьяны, состоит в том, что вы можете разделить на число обезьян, которые могут обрабатывать это параллельно, и если это бесконечность, время решения становится для обезьяны временем, чтобы создать предположение, 1 миллиард второй.

Answer 3

done = False 
count = 1 
while not done: 
    msg = generate() 
    if verify(msg): 
     print 'success, count = ', count 
     done = True 
    count += 1 

Answer 4

Возможно, что-то вроде следующего. Он работает на CPython 2. [67], CPython 3. [], pypy 2.4.0, pypy3 2.3.1 и jython 2.7b3.Это должно занимать очень много времени, чтобы работать с --production, даже на pypy или pypy3.

#!/usr/local/cpython-3.4/bin/python 

'''Infinite monkeys randomly typing Shakespeare (or one monkey randomly typing Shakespeare very fast''' 

# pylint: disable=superfluous-parens 
# superfluous-parens: Parentheses are good for clarity and portability 

import sys 
import itertools 


def generate(alphabet, desired_string, divisor): 
    '''Generate matches''' 
    desired_tuple = tuple(desired_string) 
    num_possibilities = len(alphabet) ** len(desired_string) 
    for candidateno, candidate_tuple in enumerate(itertools.product(alphabet, repeat=len(desired_string))): 
     if candidateno % divisor == 0: 
      sys.stderr.write('checking candidateno {0} ({1}%)\n'.format(candidateno, candidateno * 100.0/num_possibilities)) 
     if candidate_tuple == desired_tuple: 
      match = ''.join(candidate_tuple) 
      yield match 


def usage(retval): 
    '''Output a usage message''' 
    sys.stderr.write('Usage: {0} --production\n'.format(sys.argv[0])) 
    sys.exit(retval) 


def print_them(alphabet, quote, divisor): 
    '''Print the matches''' 
    for matchno, match in enumerate(generate(alphabet, quote, divisor)): 
     print('{0} {1}'.format(matchno, match)) 


def main(): 
    '''Main function''' 
    production = False 

    while sys.argv[1:]: 
     if sys.argv[1] == '--production': 
      production = True 
     elif sys.argv[1] in ['--help', '-h']: 
      usage(0) 
     else: 
      sys.stderr.write('{0}: Unrecognized option: {1}\n'.format(sys.argv[0], sys.argv[1])) 
      usage(1) 

    if production: 
     print_them(alphabet='abcdefghijklmnopqrstuvwxyz ', quote='methinks it is like a weasel', divisor=10000) 
    else: 
     print_them(alphabet='abcdef', quote='cab', divisor=10) 


main()