斯特恩双原子序列的高效生成

Question

Stern的双原子序列可以更详细地阅读over here；但是，为了我的目的，我现在将定义它。在

---

Stern双原子序列的定义

让n是生成fusc函数的数字。表示为fusc(n)。在

如果n为0，则返回值为0。
如果n为1，则返回值为1。在

如果n为偶数，则返回值为fusc(n / 2)。
如果n为奇数，则返回值为fusc((n - 1) / 2) + fusc((n + 1) / 2)。在

---

目前，我的Python代码在大部分的生成过程中都是蛮力的，除了除以两部分之外，因为它永远不会产生任何变化。在

def fusc (n):
    if n <= 1:
        return n

    while n > 2 and n % 2 == 0:
        n /= 2

    return fusc((n - 1) / 2) + fusc((n + 1) / 2)

但是，我的代码必须能够处理大小为1000s百万位的数字，并且递归地运行函数数千数百万次似乎不是非常有效或实用的。在

有没有什么方法可以在算法上改进我的代码，使大量的数字可以通过而不必递归调用函数那么多次？在

Answer 1

对于一百万位的记忆，递归堆栈将非常大。我们可以先看看一个足够大的数字，我们可以用手来计算，fusc(71)在这种情况下：

fusc(71) = fusc(35) + fusc(36)

fusc(35) = fusc(17) + fusc(18)
fusc(36) = fusc(18)

fusc（71）=1*fusc（17）+2*fusc（18）

fusc(17) = fusc(8) + fusc(9)
fusc(18) = fusc(9)

fusc（71）=1*fusc（8）+3*fusc（9）

fusc(8) = fusc(4)
fusc(9) = fusc(4) + fusc(5)

fusc（71）=4*fusc（4）+3*fusc（5）

fusc(4) = fusc(2)
fusc(3) = fusc(1) + fusc(2)

fusc（71）=7*fusc（2）+3*fusc（3）

fusc(2) = fusc(1)
fusc(3) = fusc(1) + fusc(2)

fusc（71）=11*fusc（1）+3*fusc（2）

fusc(2) = fusc(1)

fusc（71）=14*fusc（1）=14

我们意识到在这种情况下，我们可以完全避免递归，因为我们总是可以用a * fusc(m) + b * fusc(m+1)的形式来表达fusc(n)，同时将m的值减少到0。从上面的示例中，您可能会发现以下模式：

if m is odd:
a * fusc(m) + b * fusc(m+1) = a * fusc((m-1)/2) + (b+a) * fusc((m+1)/2)
if m is even:
a * fusc(m) + b * fusc(m+1) = (a+b) * fusc(m/2) + b * fusc((m/2)+1)

因此，您可以使用一个简单的循环函数在O（lg（n））时间内解决问题

def fusc(n):
  if n == 0: return 0
  a = 1
  b = 0
  while n > 0:
    if n%2:
      b = b + a
      n = (n-1)/2
    else:
      a = a + b
      n = n/2
  return b