Код, связанный с уравнением Хофштадтера в python

Question

Был такой вопрос в университетском задании, связанном с последовательностью Хофштадтера. Это в основном говорит, что это целочисленная последовательность, бла-бла, и есть два значения для данного индекса n. Мужское значение [M (n)] и женское значение [F (n)].

Они определены как:

• М (0) = 0
• Р (0) = 1
• М (п) = п-Р (М (п-1))
• Р (п) = п-М (Р (п-1))

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

Итак, код, который я написал, был:

def female(num):
    if num == 0:
        return 1
    elif num >0:
        return num - male(female(num-1))
def male(num):
    if num==0:
        return 0
    elif num >0:
        return num - female(male(num-1))

И при выполнении такой командой, как print male(5)
Работает без суеты. Но когда я пытаюсь найти значение n = 300, программа не выдает никаких результатов. Поэтому я добавил метод print внутри одной из функций, чтобы выяснить, что происходит со значением num

[elif num>0: print num ...]

И это показывает, что значение num уменьшается до 1 и продолжает переключаться между 1 и 2, иногда достигая значений, таких как 6.

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

Answer 1

Код теоретически в порядке. Что вы недооцениваете, так это сложность вычислений. Формула

M(n)=n-F(M(n-1))

на самом деле означает

tmp = M(n-1)
M(n) = n - F(tmp)

Таким образом, если вы представляете эти вычисления в виде дерева необходимых вызовов, вы можете увидеть, что это двоичное дерево, и вам нужно пройти через все его узлы для вычисления результатов. Учитывая, что M(n) и F(n) равны n/2, я бы оценил общее число узлов порядка 2^(n/2), которое становится огромным числом, когда вы положите туда n = 300. Таким образом, код работает, но это займет очень очень много времени, чтобы закончить.

Единственный способ обойти это - использовать кэширование в форме памятка . Код вроде этого:

femCache = dict()
def female(num):
      #print("female " + str(num))
      global femCache
      if num in femCache:
        return femCache[num];
      else:
        res = 1 # value for num = 0
        if num > 0:
             res = num - male(female(num-1))
        femCache[num] = res
        return res

maleCache = dict()
def male(num):
      #print("male " + str(num))
      global maleCache
      if num in maleCache:
        return maleCache[num];
      else:
        res = 0 # value for num = 0
        if num > 0:
             res = num - female(male(num-1))
        maleCache[num] = res
        return res

print(male(300))

должен уметь вычислять male(300) в кратчайшие сроки.