python -高时间消耗和低效率的编程挑战

Question

我想解决这个问题。

最近，奥兹发现了一根由个位数"1“组成的神奇字符串。在对字符串进行实验之后，Oz发现了该字符串的一个奇怪的神奇属性，即每当他触摸该字符串时，每一个字符串的数字"1“变为数字"0”，而字符串的每一个数字"0“都更改为"01”。奥兹发现这个属性很有趣，并立即向RK提出一个问题：“如果他触摸M次字符串，有多少个1和0会在这个神奇的字符串中?”

我为它编写了以下代码：

l = [] #List of values

for x in range(int(raw_input())):
    l.append(int(raw_input()))

def after_touchs(n, string): #Main function finds the no. of 0's and 1's
    for x in range(n):
        string = string.replace('1', '2').replace('0', '01').replace('2', '0')

    return map(str, [string.count('1'), string.count('0')])

for num in l:
    print ' '.join(after_touchs(num, '1'))

我不明白为什么这段代码要花很多时间。在我看来，这是完全正常的，而且不需要太多的时间。由于它不能在网站上运行，并且在我的计算机上使用解释器运行代码，甚至50的输入看起来都很大。string.replace函数是否占用了太多时间？那么，我能用什么替代方案呢？请帮助我减少时间消耗，提高代码的效率。

Answer 1

您只需计算1和0的数目，字符串操作总是很重，所以我想这就是使您慢下来的原因。

number1 = 1
number0 = 0
for i in xrange(M):
    # 0 -> 01
    newnumber1 = number0
    # 1 -> 0 and 0 -> 01
    number0 += number1
    # we replace the number1 with the new number
    number1 = newnumber1
print "%d %d"%(number0,number1)

编辑

我在Tim的评论中看到了一个更有效的解决方案。

事实上，在第一次变化之后，0和1的数目遵循一个斐波纳契序列。

1: 101123

0: 011235

男性: 012345

这意味着O(1)解决方案是：

if M>0:
    number1 = Fibo(M-1)
    number0 = Fibo(M)

但是，您必须用在维基百科中找到的公式来逼近斐波纳契序列的值。

Answer 2

这可能是因为每次编辑字符串。您基本上是在实现斐波纳契序列，第50位数是50: 12586269025 =52x11x101x151x3001

因此，您有一个长度为这个长度的字符串，并对其应用了几个字符串操作。这可能会导致这一过程放慢。

希望我能帮上忙。

Answer 3

根据这个问题，前6步的字符串应该如下所示：

"1“、"0”、"01“、"010”、"01001“、"01001010”、"0100101001001“

计数是1，0，1，1，12，2，2，3，3，3，5，5，5，5，8，这让我想起斐波那契级数。斐波那契数增长很快，所以你最终会得到很长的字符串，占用了大量的内存，而且操作速度也很慢。

如果你需要速度，那么只需计算斐波纳契数。您还可以通过缓存已经计算的值来加快原始fibonacci的速度，因此，如果您已经知道该系列的第4和第5元素，则可以快速计算第6元素。