python中与Hofstadter方程相关的代码

Question

在一份与霍夫斯塔特序列有关的大学作业中就有这个问题。它基本上说它是一个整数序列blah blah，对于给定的索引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编写一个程序来找出给定整数序列的男性和女性值。在

我是这样写的：

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，并且在达到6这样的值时一直在1和2之间跳跃。在

我不明白为什么会这样。任何洞察力都会很好。我应该怎么做才能找到与大整数相关的值。提前谢谢。干杯。在

Answer 1

从理论上讲，这个代码是好的。你低估了计算的复杂性。公式

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

实际上意味着

^{pr2}$

因此，如果您将此计算表示为必要调用的树，您可能会看到它是一个二叉树，您应该遍历它的所有节点来计算结果。假设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)。在