霍夫施塔特方程相关代码在python

Question

与 Hofstadter 序列相关的大学作业中有这个问题。它基本上说它是一个整数序列等等，并且给定索引 n 有两个值。男性值 [M(n)] 和女性值 [F(n)]。

它们定义为：

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

我们被要求在 python 中编写一个程序来查找给定整数序列的 Male 和 Female 值。

所以我写的代码是：

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 的值时，程序没有给出任何输出。所以我在其中一个函数中添加了一个打印方法，以找出 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 那里。所以代码可以工作，但需要很长时间才能完成。

解决此问题的一种方法是以 memoization 的形式使用缓存。像这样的代码：

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)。

霍夫施塔特方程相关代码在python

Hofstadter equation related code in python

python

math

sequences