Как обработать очень глубокий рекурсивный вызов в игровом примере - PullRequest
Новая
       6

Как обработать очень глубокий рекурсивный вызов в игровом примере

1 голос
/ 28 января 2020

У меня есть следующий код, решающий проблему с игрушкой с помощью рекурсии: 

import math
import sys

def b_step(n):
    if n > 2:
        return a_step(math.floor(n+1)/2) or a_step(n-1)
    return True

def a_step(n):
    if n > 2:
        return b_step(math.floor((n+1)/2)) and b_step(n-1)
    return False

print(a_step(1000000000000))

Проблема в том, что А и В по очереди играют в игру, заменяя число n токенов либо floor((n+1)/2) или n-1. Игрок, который может оставить один жетон, выигрывает. Функция a_step(n) должна возвращать True, если B, возможно, сможет выиграть игру (без учета того, чей ход занимает A).

Моя реализация, кажется, работает, но, к сожалению, она завершается на очень большом n. У кого-нибудь есть идея получить более высокую производительность реализации? Я думаю о развертывании рекурсии, но не думаю, что это возможно, поскольку мы должны вызывать каждый метод.

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

Ответы [ 2 ]

1 голос
/ 29 января 2020

, поскольку ваши функции используют предыдущие результаты, вы можете использовать lru_cache из functools

import math
import sys
from functools import lru_cache

@lru_cache(256)
def b_step(n):
    if n > 2:
        return a_step(math.floor(n+1)/2) or a_step(n-1)
    return True

@lru_cache(256)
def a_step(n):
    if n > 2:
        return b_step(math.floor((n+1)/2)) and b_step(n-1)
    return False

print(a_step(1_000_000_000_000))

выход: 

False

этот подход действительно быстрый, и он показывает, что для 687194767359 и 1374389534719 ваша функция возвращает True (относится к предыдущему ответу)

1 голос
/ 28 января 2020

забавный факт, я протестировал вашу a_step функцию по первым 100_000 числам и получил следующие числа, когда ваша функция вернула True: 

[(i, a_step(i)) for i in range(100000) if a_step(i)]

вывод: 

[(3, True),
 (9, True),
 (19, True),
 (39, True),
 (79, True),
 (159, True),
 (319, True),
 (639, True),
 (1279, True),
 (2559, True),
 (5119, True),
 (10239, True),
 (20479, True),
 (40959, True),
 (81919, True)]

кроме первого элемента (3), все остальные числа ведут себя как последовательность, в которой n-й член можно описать как a(n) = a(n-1) + (a(n-1) - a(n-2)) * 2

a1, a2 = 9, 19

for index in range(3, 15):
    a1, a2 = a2, a2 + (a2 - a1) *2
    print(f'a{index} = {a2}')

вывод: 

a3 = 39
a4 = 79
a5 = 159
a6 = 319
a7 = 639
a8 = 1279
a9 = 2559
a10 = 5119
a11 = 10239
a12 = 20479
a13 = 40959
a14 = 81919

Предполагая, что формула прогрессии может дать вам следующие True (я этого не доказал):

  • для a_step(1000000000000), ответ будет False, поскольку a(37) = 687194767359 и a(38) = 1374389534719
...