Pull to refresh

Вывод формулы n-ного члена для рекуррентной последовательности на примере задачи из квеста Амнезия

Reading time 6 min
Views 37K
Пеленгский фермер Бух'ерик разводит хрякоплюхов. Эти животные размножаются так быстро, что их поголовье ежедневно возрастает в 3 раза. Но, начиная со второго дня, на ферму повадилась нападать стая страшных зверей долбогрызов, каждый вечер пожирающих вдвое больше хрякоплюхов, чем их было в предыдущий день. Сколько хрякоплюхов будет у фермера на 7-й вечер, если вначале их было 10?


Вы спросили у гаальца, что он думает по поводу этой задачки. После некоторого размышления тот ответил:
— В начале было 10 хрякоплюхов. В первый день они размножились, и к началу второго дня их стало 30. Во второй день они опять размножились (их стало 90), но вечером пришли долбогрызы и съели вдвое больше хрякоплюхов, чем было вчера (в первый день), т.е. 20 штук. Итого, в начале третьего дня получаем 70 хрякоплюхов. Мне кажется, что, продолжая решать таким образом, можно вычислить число хрякоплюхов в любой день.

Это задача из игры «Космические Рейнджеры 2», квест Амнезия.
Попробуем вывести формулу для количества хрякоплюхов на n-ный день, и посчитать для примера количество хрякоплюхов на 32-й день.

Посмотрим на первые несколько дней (я добавил день «0» только для удобства формулы, можно все делать и без него)

День «0» День 1 День 2 День 3
Утро 0 10 30 70
После размножения 0 10 * 3 = 30 30 * 3 = 90 70 * 3 = 210
После долбогрызов (вечер) 0 10 * 3 — 0 * 2 = 30 30 * 3 — 10 * 2 = 70 70 * 3 — 30 * 2 = 150

Нас будет интересовать количество хрякоплюхов на утро n-ного дня, и, несмотря на то, что в задаче спрашивается про вечер, верным будет утреннее количество.
Таким образом, количество хрякоплюхов (на утро) являет собой последовательность

$F = (0, 10, 30, 70, ...)$



Про эту последовательность мы знаем (по условию задачи) что $F_0 := 0$ и $F_1 := 10$

Так же, по условию задачи, ночью ничего не происходит, поэтому хрякоплюхи вечером в полном составе без изменений переносятся на утро следующего дня (т.е. количество хрякоплюхов утром равно их количеству вечером предыдущего дня).

Т.е. на утро второго дня их стало $F_2 = 30 = 3 * 10 - 2 * 0 = 3 * F_1 - 2 * F_0$.
На утро третьего дня их уже $F_3 = 70 = 3 * 30 - 2 * 10 = 3 * F_2 - 2 * F_1$.

День n-2 День n-1 День n
Утро $F_{n-2}$ $F_{n-1}$ $F_{n} = 3*F_{n-1} - 2*F_{n-2}$
После размножения $3 * F_{n-2}$ $3 * F_{n-1}$ $3 * F_{n}$
После долбогрызов (вечер) $3 * F_{n-2} - 2 * F_{n-3}$ $3 * F_{n-1} - 2 * F_{n-2}$ $3 * F_{n} - 2 * F_{n-1}$

Начиная со второго дня $n=2$ действует такая рекуррентная формула:

$F_{n} = 3 * F_{n-1} - 2 * F_{n-2}$


Итого, ещё раз всё вместе

$ F_0 := 0 \\ F_1 := 10 \\ F_{n} = 3 * F_{n-1} - 2 * F_{n-2} $


Мы получили формальное определение последовательности и этого уже достаточно чтобы можно было вручную посчитать сколько будет хрякоплюхов на какой день. Более того, если у нас магическим образом появилась какая-то формула для $F_n$, и эта формула выполняется для этих 3-х условий, то эта формула будет тем, что нам нужно.

Мы же будем пытаться получить эту формулу.

Как правило, чтобы что-то найти нужно составить уравнение, поэтому так и поступим.
Наша последовательность $F$ — это то, что мы хотим найти (точнее, мы хотим получить формулу для её членов).

Будем делать уравнение из последовательностей. Для этого изобретём сложение для последовательностей:

$"A+B"=(A_0 + B_0, A_1 + B_1, ....)$


Т.е. сумма последовательностей есть тоже последовательность.

Важно упомянуть что наши последовательности вообще-то бесконечные, и так просто что-то с ними делать нельзя. Нельзя, к примеру, безо всяких оговорок просуммировать все члены последовательности — никто не может бесконечное время сидеть и суммировать.

Бесконечная последовательность — это то, где для любого номера члена мы можем сказать как его посчитать за конечное время. В случае последовательности $F$ мы как бы говорим: возьмите день0, возьмите день1 и далее потихоньку, шаг за шагом, считайте следующие дни пока не дойдёте до нужного вам.

Для суммы последовательностей мы говорим: если вам нужен 100-й член суммы, то возьмите по 100-му члену из слагаемых последовательностей и сложите их. Нужен миллионный — так же, возьмите миллионный там, возьмите миллионный сям, сложите эти числа и получите что вам нужно.

Это похоже на то, как суммируются многочлены, к примеру:

$(3 + 2x + x^2) + (6 + 4x^2) = (3+6) + (2+0)x + (1+4)x^2$

.

Можно даже представить себе бесконечный многочлен

$A = A_0 + A_1*x + A_2 * x^2 + A_3 * x^3 + ... $


где $x, x^2, x^3, ..., x^n, ... $ — просто какие-то символы. И если мы складываем два таких «бесконечночлена», то их сумма будет как раз сумма последовательностей (мы так определили сумму последовательностей).

Тут важно понимать что на самом деле нет никаких бесконечных многочленов, это просто иная но более удобная запись бесконечной последовательности: пишем $F = 10x + 30x^2 + 70x^3 + ...$, а видим $F = (0, 10, 30, 70, ...)$.

Теперь придумаем умножение для последовательностей. Просто попарно перемножить члены так же как со сложением не пойдёт — хотя это и будет похоже на умножение, интересных свойств это не даст. Да и хочется чтобы умножение было бы похоже на умножение многочленов.

К примеру, вот так умножаются обычные конечные многочлены:

$(a_0 + a_1*x + a_2*x^2) * (b_0 + b_1*x + b_2*x^2) = ???$


Берутся и перемножаются: раскрываются скобки, и группируются члены с одной и той же степенью икса

$ (a_0 + a_1*x + a_2*x^2) * (b_0 + b_1*x + b_2*x^2) = \\ a_0 * (b_0 + b_1*x + b_2*x^2) + a_1*x * (b_0 + b_1*x + b_2*x^2) + \\ a_2*x^2 * (b_0 + b_1*x + b_2*x^2) = \\ a_0 * b_0 +\\ x(a_0*b_1 + a_1*b_0) + \\ x^2*\text{(...что-то длинное...)} + \\ x^3*\text{(...что-то длинное...)} + \\ x^4*\text{(...что-то длинное...)} $


Другими словами, каждый член первого многочлена умножается на каждый член второго.
Каждый с каждым.

Так просто это обобщить на бесконечные последовательности нельзя — опять же, потому что никто не может бесконечное количество раз умножить на бесконечное количество элементов. Тут важно правильно сказать, а именно что пускай n-ный член произведения последовательностей равен

$"A*B"_n := A_0*B_n + A_1*B_{n-1} + A_2 * B_{n-2} + ... + A_n * B_0 = \sum_{i=0}^{i=n} A_i*B_{n-i}$


Почему именно так
В самом деле, если вам интересно что стоит на 100-м месте, т.е. какой коэффициент у $x^{100}$, то вы вполне можете сказать: $x^{100}$ может получиться если умножились $a_0 * b_{100}*x^{100}$. Также $x^{100}$ может получиться если умножились $a_1*x * b_{99}*x^{99}$. Можно сообразить и привести всю 101 пару членов, которые при перемножении дадут $x^{100}$. И после этого упомянуть что больше никак $x^{100}$ в произведении не может получится.

Теперь мы умеем складывать бесконечные последовательности и так же умеем их перемножать. Можно заметить некоторые хорошие свойства, к примеру что $A+B = B+A$; $A*B = B*A$; $A*(B+C)=A*B + A*C$. Мы придумали это сложение и умножение, нужно обязательно проверять что такие свойства выполняются (это «группа» и «кольцо»). Это несложно проверить, и, в целом-то, эти все свойства довольно естественны, особенно для тех кто хоть сколько-то складывал и умножал конечные многочлены.

Попробуем теперь для примера посчитать $100 * F = (100, 0, 0, 0, .....)*(F_0, F_1, F_2, F_3, ...)$. Согласно определению умножения получаем

$ "100*F"_n = \sum_{i=0}^{i=n} (100, 0, 0, 0, 0, ....)_i*F_{n-i} = 100*F_{n} $


Выглядит логично — умножение последовательности на число даст умножение каждого члена на это число. И это сходится с

$ 100 * (F_0 + F_1x + F_2x^2 + ...) = 100F_0 + 100F_1x + 100F_2x^2 + ... $


Важное замечание: $1 * F = F * 1 = F$, где соответственно $ 1 = (1, 0, 0, 0, ....)$

Теперь посчитаем $x * F = (0, 1, 0, 0, .....)*(F_0, F_1, F_2, F_3, ...)$. Так же согласно определению умножения получаем

$ "x*F"_n = \sum_{i=0}^{i=n} (0, 1, 0, 0, 0, ....)_i*F_{n-i} = F_{n-1} \text{при n > 0, либо 0 при n = 0} $


Т.е.

$ "x*F" = (0, F_0, F_1, F_2, F_3, ...) $


Что, собственно, так же сходится с

$ x * (F_0 + F_1x + F_2x^2 + ...) = F_0x + F_1x^2 + F_2x^3 + ... $



Так же получаем что $x^2 * F = (0, 0, F_0, F_1, F_2, ...)$.

Это базовые операции над нашей последовательностью, и теперь вот это всё хорошо бы собрать и применить к начальной рекуррентной формуле $F_{n} - 3 * F_{n-1} + 2 * F_{n-2} = 0$:

$ F = (F_0, F_1, F_2, ...)\\ 3 * x * F = (0, 3F_0, 3F_1, 3F_2, ....)\\ 2 * x^2 * F = (0, 0, 2F_0, 2F_1, 2F_2, ....) $


Из первой строчки вычитаем вторую и прибавляем третью:

$ F - 3 * x * F + 2 * x^2 * F = \\ (F_0 - 0 + 0, F_1 - 3F_0 + 0, F_2 - 3F_1 + 2F_0, ...., F_{n} - 3 * F_{n-1} + 2 * F_{n-2}) = \\ (F_0, F_1 - 3F_0, 0, 0, 0, ....) = F_0 + (F_1 - 3F_0)x = 10x $


Итого получаем (используя хорошие свойства сложения и умножения):

$ F*(1 - 3x + 2x^2) = 10x $


что, напомню еще раз, на самом деле

$ (F_0, F_1, F_2, ....)*(1, -3, 2, 0, 0, ....) = (0, 10, 0, 0, ....) $


Это и есть уравнение, и его мы будем решать. Мы не можем взять так просто и поделить на $(1 - 3x + 2x^2)$, хотя бы потому что мы не определяли операцию деления. Вместо этого мы будем умножать обе части уравнения на что-то такое, что как бы является $(1 - 3x + 2x^2)^{-1}$, и в конечном итоге оставим одинокую F слева.
На текущий момент из того что мы имееем мы не можем достоверно сказать существует ли вообще такое $(1 - 3x + 2x^2)^{-1}$ (хотя так-то оно существует, и мы его сейчас сделаем).
Почему можно умножить обе части уравнения на что-то
Если у нас есть какие-то $A$ и $B$, да и при том такие что $A=B$, то

$ A = B \Rightarrow A*C = B*C $


Но из этого абсолютно не следует что если $A*C = B*C$, то $A=B$. К примеру, из того что $4*0 = 5*0$ вовсе не следует что $4 = 5$.
Для того, чтобы было верно

$ A = B \Leftrightarrow A*C = B*C $


нужно чтобы существовал такой элемент $D$, что $C*D = 1$.
Тогда можно получить что $A*C = B*C \implies A*C*D = B*C*D \implies A = B$

Немного преобразуем наше уравнение:

$ F*(1 - 3x + 2x^2) = 10x \\ \Leftrightarrow \\ F*(1-x)(1/2-x)*2 = 10x $


Это, опять же, не просто так, это потому что последовательность $(1, -1, 0, 0, 0, ...)$ умноженная на $(1/2, -1, 0, 0, 0, ...)$ и умноженная на $(2, 0, 0, 0, ...)$
даёт в результате $(1, -3, 2, 0, 0, 0, ...)$
Вот теперь уже чуть легче, теперь хорошо бы отыскать такие $"(1-x)^{-1}"$ и $"(1/2-x)^{-1}"$, да и умножить на них наше уравнение.
Такие обратные последовательности есть, и вот их формула

$ (\alpha - x)*(1/\alpha + x/\alpha^2 + x^2/\alpha^3 + .... + x^{n-1}/\alpha^{n} + ...) = \\ \alpha * 1/\alpha - x*1/\alpha + \alpha*x/\alpha^2 + .... = 1 $


Как это можно получить
Для начала попробуем на простом случае, с $\alpha = 1$:

$ (1 - x)*(A_0 + A_1x + A_2x^2 + ...) = 1 $


Ясно что $A_0 = 1$, тут без вариантов. Теперь посмотрим что может получится у 1-й степени x: $-x*A_0 + 1*A_1x = -x*1 + 1*A_1x$ (я просто покомпонентно перемножаю первую последовательность на вторую). Ясно что $A_1 = 1$. Так же далее получаем что $A_n = 1$.
Для общего случая $(\alpha - x)$ действуем подобным образом.

Таким образом, умножаем обе части уравнения:

$ F*(1-x)(1/2-x)*2 = 10x \\ \Leftrightarrow \\ F*(1-x)(1/2-x)*2 * (1 + x + x^2 + x^3 + ...) * (2 + 4x + 8x^2 + ... + 2^{n+1}x^n + ...) * \\ (1/2) = 10x *(1 + x + x^2 + x^3 + ...) * (2 + 4x + 8x^2 + ... + 2^{n+1}x^n + ...) * (1/2) \\ \Leftrightarrow \\ F = 5x * (1 + x + x^2 + x^3 + ...) * (2 + 4x + 8x^2 + ... + 2^{n+1}x^n + ...) \\ \Leftrightarrow \\ F = 10x * (1 + x + x^2 + x^3 + ...) * (1 + 2x + 4x^2 + ... + 2^{n}x^n + ...) $


Посмотрим повнимательней на

$ (1 + x + x^2 + x^3 + ...) * (1 + 2x + 4x^2 + ... + 2^{n}x^n + ...) = \\ (1, 1, 1, ...., 1, ....) * (1, 2, 4, ...., 2^{n}, ...) $


По определению произведения получаем формулу для n-ного члена:

$ "(1, 1, 1, ...., 1, ....) * (1, 2, 4, ...., 2^{n}, ...)"_{n} = \\ "(1, 2, 4, ...., 2^{n}, ...) * (1, 1, 1, ...., 1, ....)"_{n} = \\ \sum_{i=0}^{i=n} A_i*B_{n-i} = \\ \sum_{i=0}^{i=n} 2^{i} = \\ 1 + 2 + 4 + .... + 2^n = 2^{n+1} - 1 $


Откуда появился последний шаг
Это обычная сумма членов конечной геометрической прогрессии. Можно по-быстрому получить вот так:
Пусть $S_n = 1 + 2 + 4 + ... + 2^n$. Тогда $S_{n+1} = 1 + 2 + .... + 2^n + 2^{n+1} = S_n + 2^{n+1}$.
В то же время, $2 * S_n = 2 + 4 + 8 + ... + 2^{n+1} = 1 + 2 + 4 + 8 + ... + 2^{n+1} - 1 = S_{n+1} - 1 $ следовательно
$S_{n+1} = 2*S_n - 1$
Итого приравнивая $S_{n+1}$ получаем $S_n + 2^{n+1} = 2*S_n - 1 \implies S_n = 2^{n+1} - 1$.

Подставляем полученное произведение

$ F = 10x * (1 + x + x^2 + x^3 + ...) * (1 + 2x + 4x^2 + ... + 2^{n}x^n + ...) \\ \Leftrightarrow \\ F = 10x * (1, 3, 7, ..., 2^{n+1} - 1, ...) \\ \Leftrightarrow \\ F = (0, 10, 30, 70, ...., 10*(2^{n} - 1), ...) $


При умножении на $10x = (0, 10, 0, 0, 0, ...)$ все члены умножились на 10 и сдвинулись на 1 вправо.
Итого получаем результат

$ F_n = 10*(2^{n} - 1) $


Именно эту формулу нужно использовать для прохождения квеста, и именно её можно найти в подсказках в квесте.
К примеру на 32-й день получаем $F_{32} = 10*(2^{32} - 1) = 42949672950$.
Глядя на формулу можно сказать что хрякоплюхам долбогрызы не помеха — они даже будучи поедаемыми успевают экспоненциально размножаться.

Таким же образом можно вывести формулу для n-ного члена последовательности Фибоначчи, правда там числа будут пострашней — с корнями, и при этом при любом n формула даст натуральное число.

Немного размышлений о сложности алгоритма
Если реализовывать алгоритм расчета хрякоплюхов согласно рекуррентному определению (необязательно при этом использовать рекурсию), то сложность получается O(n).
А вот если по формуле — то тут можно и поспорить, будет ли это O(n) либо O(1). Зависит как мы считаем 2**n — это O(1) или O(n). С одной стороны, это битовый сдвиг, с другой стороны при n больших чем разрядность процессора потребуется больше времени на вычисления.
К примеру, если сделать Ethereum контракт, который будет считать этих хрякоплюхов, и посмотреть что получится по потреблению gas в зависимости от алгоритма:

Код на solidity
pragma solidity ^0.4.0;

contract Rangers {
    /*
    10 -> 1335 gas 
    20 -> 2385 gas
    30 -> 3435 gas
    40 -> 4485 gas
    50 -> 5535 gas
    60 -> 6585 gas
    70 -> 7635 gas
    80 -> 8685 gas
    90 -> 9735 gas
    100 -> 10785 gas
    */
    function byStepByStep(uint n) public pure returns (uint) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 10;
        }
        uint result = 10;
        uint prev1 = 10;
        uint prev2 = 0;
        for (uint i = 2; i <= n; i++) {
            result = 3*prev1 - 2*prev2;
            prev2 = prev1;
            prev1 = result;
        }
        return result;
    }
	
    /*
     10 -> 310 gas
     100 -> 310 gas
     200 -> 310 gas
    */
    function byFormula(uint n) public pure returns (uint) {
        return 10*(2 ** n - 1);
    }   
}


То вполне предсказуемо получится что по шагам будет O(n), а по формуле самый настоящий O(1).
Tags:
Hubs:
+26
Comments 31
Comments Comments 31

Articles