Умножение двух переменных увеличивается со временем

Question

Это вопрос, который у меня возник в качестве упражнения.

Есть два типа бактерий.Скажи х и у.Каждую секунду они умножаются, изменяя свой тип.

Тип x становится типом 2 y и типом 1 x (x -> 2y + x).Тип y становится 3 типа x и 1 тип y (y -> 3x + y).Кроме этого, 1 тип и 3 тип рождаются спонтанно (каждую секунду -> 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 = 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)

Answer 2

Так что, если я правильно понимаю, x' = x+3y+1 и y' = 2x+y+3.Предположим, ваше первоначальное население составляет десять x и семь лет, и вы хотите развить его за один шаг.Это можно смоделировать с помощью следующего умножения матриц:

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

Таким образом, чтобы найти ответ, вам нужно повторить умножение матриц t раз.

Хотя, как вынаписано код, каждый х превращается в 2y и 0 х, а не 2y и один х.