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

Question

Stern 的双原子序列可以阅读更多详细信息 over here ;但是，出于我的目的，我现在将定义它。

---

斯特恩双原子序列的定义

设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 百万位数量级的数字，并且递归地通过函数thousands 数百万次似乎不是很高效或实用。

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

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