两个变量的乘积随时间增加

Question

这是我作为练习的问题。

有两种细菌。说 x 和 y。每一秒他们都在改变他们的类型。

类型 x 变为 2 y 类型和 1 x 类型 (x -> 2y + x)。类型 y 变为 3 x 类型和 1 y 类型 (y -> 3x + y)。除此之外，1 x 型和 3 y 型自发产生（每秒 -> x + 3y）。

任务是计算给定时间后的细菌数量t。

我在这里写了一段代码：

x = 1
y = 1
t = 2

def calcFinalBacteria (x, y, t):
    for i in xrange (t):
        tempX = x + y * 3 # contribution by x bacteria (1) and y bacteria (3)
        tempY = x * 2 + y # contribution by x bacteria (2) and y bacteria (1)

        x += tempX + 1 - x # spontaneous addition of 1 x bacteria
        y += tempY + 3 - y # spontaneous addition of 3 y bacteria
    print x, y

calcFinalBacteria (x, y)

我这里代码的时间复杂度是O(t)。但是有什么改进的方法吗？对于小输入没关系。但是当我将 t 推到 10^18 并将 x, y 增加到 1000 时，要花很多时间才能找出

Answer 1

因此，如果我理解正确，x' = x+3y+1 和 y' = 2x+y+3。假设你的初始种群是 10 个 x 和 7 个 y，你想将它进化一步。这可以用以下矩阵乘法建模：

|1 3 1|   |10|
|3 1 3| x | 7|
|0 0 1|   | 1|

所以要找到答案，你需要重复矩阵乘法 t 次。

尽管按照您编写代码的方式，每个 x 变成 2y 和 0 x，而不是 2y 和 1 x。

Answer 2

一个小改进。

您正在将值添加到自身并减去它的原始值。

x = 1
y = 1
t = 2

def calcFinalBacteria (x, y, t):
    for i in xrange (t):
        tempX = x + y * 3 # contribution by x bacteria (1) and y bacteria (3)
        tempY = x * 2 + y # contribution by x bacteria (2) and y bacteria (1)

        x = tempX + 1 # spontaneous addition of 1 x bacteria
        y = tempY + 3 # spontaneous addition of 3 y bacteria
    print x, y

calcFinalBacteria (x, y)

两个变量的乘积随时间增加

Multiplication of two variables increase over time

python

multiplication