python - 用指数有效地计算数学公式

Question

我正在执行一个计算方程式的程序:F(n) = F(n-1) + 'a' + func1(func2(F(n-1)))。

func1 将每个“a”变成“c”，每个“c”变成“a”。

func2 反转字符串(例如“xyz”变为“zyx”)。

我想计算 F(10**2017) 的第 K 个字符。 基本规则为 F(0) = ""(空字符串)，示例为 F(1) = "a"、F(2) = "aac"等。

我如何有效地做到这一点？

我的代码的基本部分是这样的:

def op1 (str1):
     if str1 == 'a':
          return 'c'
     else:
          return 'a'

def op2 (str2):
     return str2[::-1]

sinitial = ''

while (counter < 10**2017):
    Finitial = Finitial + 'a' + op1(op2(Finitial))
    counter += 1

print Finitial

Answer 1

让我们首先修复您的原始代码并定义一个函数来计算 F(n)对于小n .我们还将打印出 F 的前几个值。 .以下所有代码均适用于 Python 3；如果您使用的是 Python 2，则需要进行一些小的更改，例如替换 str.maketrans与 string.maketrans和 range与 xrange .

swap_ac = str.maketrans({ord('a'): 'c', ord('c'): 'a'})

def F(n):
    s = ''
    for _ in range(n):
        s = s + 'a' + s[::-1].translate(swap_ac)
    return s

for n in range(7):
    print("F({}) = {!r}".format(n, F(n)))

这给出了以下输出:

F(0) = ''
F(1) = 'a'
F(2) = 'aac'
F(3) = 'aacaacc'
F(4) = 'aacaaccaaaccacc'
F(5) = 'aacaaccaaaccaccaaacaacccaaccacc'
F(6) = 'aacaaccaaaccaccaaacaacccaaccaccaaacaaccaaaccacccaacaacccaaccacc'

此时的一些观察:

1. F(n)是一个长度为 2**n-1 的字符串.这意味着 F(n)成长快。计算 F(50)已经需要一些重要的硬件:即使我们每位存储一个字符，我们也需要超过 100 TB 的空间来存储完整的字符串。 F(200)具有比太阳系中估计的原子更多的特征。所以计算的想法F(10**2017)直接是可笑的:我们需要一种不同的方法。

2. 通过构造，每个 F(n)是 F(n+1) 的前缀.所以我们真正拥有的是一个定义良好的 infinite 字符串，其中每个 F(n)仅仅给了我们第一个2**n-1该无限字符串的字符，我们正在计算它的 k第字符。出于任何实际目的，F(10**2017)还不如那个无限字符串:例如，当我们进行计算时，我们不需要检查 k < 2**(10**2017)-1 , 因为 k超过这个甚至不能用这个宇宙中的正常二进制表示法表示。

幸运的是，字符串的结构很简单，可以计算k。第一个字符直接是直截了当的。当我们查看偶数和奇数位置的字符时，就会出现主要线索:

>>> F(6)[::2]
'acacacacacacacacacacacacacacacac'
>>> F(6)[1::2]
'aacaaccaaaccaccaaacaacccaaccacc'

偶数 位置的字符只是在 a 之间交替和 c (并且根据构造可以直接证明这是真的)。所以如果我们的 k是偶数，我们可以简单看一下是否k/2是奇数还是偶数来确定我们是否会得到 a或 c .

奇怪的位置呢？嗯F(6)[1::2]应该看起来有点眼熟:它只是 F(5) :

>>> F(6)[1::2] == F(5)
True

同样，可以直接证明(例如，通过归纳法)这不仅仅是巧合，而且 F(n+1)[1::2] == F(n)对于所有非负 n .

我们现在有一种有效的方法来计算 k无限字符串中的第 th 个字符:if k是偶数，我们只看k/2的奇偶性.如果k是奇数，那么我们就知道位置k的字符等于位置(k-1)/2 .所以这是计算该字符的第一个解决方案:

def char_at_pos(k):
    """
    Return the character at position k of the string F(n), for any
    n satisfying 2**n-1 > k.
    """
    while k % 2 == 1:
        k //= 2
    return 'ac'[k//2%2]

并检查这是否正确:

>>> ''.join(char_at_pos(i) for i in range(2**6-1))
'aacaaccaaaccaccaaacaacccaaccaccaaacaaccaaaccacccaacaacccaaccacc'
>>> ''.join(char_at_pos(i) for i in range(2**6-1)) == F(6)
True

但我们可以做得更好。我们有效地盯着 k 的二进制表示, 删除所有尾随 '1' s 和下一个 '0' ，然后简单地查看下一位以确定我们是否有 'a'或 'c' .识别尾随的 1 可以通过位操作技巧来完成。这为我们提供了以下半混淆的无循环解决方案，我将其留给您展开:

def char_at_pos2(k):
    """
    Return the character at position k of the string F(n), for any
    n satisfying 2**n-1 > k.
    """
    return 'ac'[k//(1+(k+1^k))%2]

再次，让我们检查一下:

>>> F(20) == ''.join(char_at_pos2(i) for i in range(2**20-1))
True

最后的评论:这是一个非常著名且研究充分的序列:它被称为龙曲线序列，或 regular paper-folding sequence , 并且是 sequence A014577在整数序列的在线百科全书中。某些 Google 搜索可能会为您提供许多其他方法来计算其元素。另见 this codegolf question .