如何在Python中使用很长的字符串？

Question

我正在处理ProjectEuler的problem 220（看起来很简单，与一些 其他人——我想换个更大的号码！）在

到目前为止，我已经：

D = "Fa"

def iterate(D,num):
    for i in range (0,num):
        D = D.replace("a","A")
        D = D.replace("b","B")
        D = D.replace("A","aRbFR")
        D = D.replace("B","LFaLb")
    return D

instructions = iterate("Fa",50)

print instructions

现在，这个方法对于低值很好，但是当你把它放在更高的值时，你只会得到一个“内存错误”。有人能提出一个克服这个问题的方法吗？我真的需要一个包含下一步指令的字符串/文件。在

Answer 1

如果你考虑一下在D（0）、D（1）等中有多少个“a”和“b”字符，你会发现字符串很快变得很长。计算一下D（50）中有多少个字符，然后再想想你应该把这些数据存储在哪里。我将其设为4.5*10^15个字符，即每个字符一个字节的容量为4500 TB。在

想想看，你不需要计算——问题告诉你至少有10^12个步骤，每字符一个字节的数据是1兆字节，如果你用技巧把每个字符降到2位，那就是四分之一。我认为这会导致我可以访问的任何类型的存储介质的一分钟时间限制问题：-）

Answer 2

诀窍在于注意在每次迭代中运行字符串时出现了哪些模式。尝试计算1到10之间的n的iterate(D,n)，看看是否能找到它们。还要通过一个计算结束位置和步数的函数来输入字符串，并在那里寻找模式。在

然后，您可以使用这些知识将算法简化为根本不使用这些字符串的内容。在

Answer 3

Python字符串不是这个问题的答案。字符串存储为不可变数组，因此每一个替换都会在内存中创建一个全新的字符串。更不用说，如果将10^12步之后的指令集存储为字符，那么它们的大小将至少为1TB（这还包括一些小的压缩）。在

理想情况下，应该有一种在数学上（提示，有）动态生成答案的方法，这样你就不需要存储序列了。在

只是作为一个向导来确定使用哪一个方法来创建一个字符串。在