Пеленгский фермер Бух'ерик разводит хрякоплюхов. Эти животные размножаются так быстро, что их поголовье ежедневно возрастает в 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-ного дня, и, несмотря на то, что в задаче спрашивается про вечер, верным будет утреннее количество.
Таким образом, количество хрякоплюхов (на утро) являет собой последовательность
Про эту последовательность мы знаем (по условию задачи) что и
Так же, по условию задачи, ночью ничего не происходит, поэтому хрякоплюхи вечером в полном составе без изменений переносятся на утро следующего дня (т.е. количество хрякоплюхов утром равно их количеству вечером предыдущего дня).
Т.е. на утро второго дня их стало .
На утро третьего дня их уже .
День n-2 | День n-1 | День n | |
---|---|---|---|
Утро | |||
После размножения | |||
После долбогрызов (вечер) |
Начиная со второго дня действует такая рекуррентная формула:
Итого, ещё раз всё вместе
Мы получили формальное определение последовательности и этого уже достаточно чтобы можно было вручную посчитать сколько будет хрякоплюхов на какой день. Более того, если у нас магическим образом появилась какая-то формула для , и эта формула выполняется для этих 3-х условий, то эта формула будет тем, что нам нужно.
Мы же будем пытаться получить эту формулу.
Как правило, чтобы что-то найти нужно составить уравнение, поэтому так и поступим.
Наша последовательность — это то, что мы хотим найти (точнее, мы хотим получить формулу для её членов).
Будем делать уравнение из последовательностей. Для этого изобретём сложение для последовательностей:
Т.е. сумма последовательностей есть тоже последовательность.
Важно упомянуть что наши последовательности вообще-то бесконечные, и так просто что-то с ними делать нельзя. Нельзя, к примеру, безо всяких оговорок просуммировать все члены последовательности — никто не может бесконечное время сидеть и суммировать.
Бесконечная последовательность — это то, где для любого номера члена мы можем сказать как его посчитать за конечное время. В случае последовательности мы как бы говорим: возьмите день0, возьмите день1 и далее потихоньку, шаг за шагом, считайте следующие дни пока не дойдёте до нужного вам.
Для суммы последовательностей мы говорим: если вам нужен 100-й член суммы, то возьмите по 100-му члену из слагаемых последовательностей и сложите их. Нужен миллионный — так же, возьмите миллионный там, возьмите миллионный сям, сложите эти числа и получите что вам нужно.
Это похоже на то, как суммируются многочлены, к примеру:
.
Можно даже представить себе бесконечный многочлен
где — просто какие-то символы. И если мы складываем два таких «бесконечночлена», то их сумма будет как раз сумма последовательностей (мы так определили сумму последовательностей).
Тут важно понимать что на самом деле нет никаких бесконечных многочленов, это просто иная но более удобная запись бесконечной последовательности: пишем , а видим .
Теперь придумаем умножение для последовательностей. Просто попарно перемножить члены так же как со сложением не пойдёт — хотя это и будет похоже на умножение, интересных свойств это не даст. Да и хочется чтобы умножение было бы похоже на умножение многочленов.
К примеру, вот так умножаются обычные конечные многочлены:
Берутся и перемножаются: раскрываются скобки, и группируются члены с одной и той же степенью икса
Другими словами, каждый член первого многочлена умножается на каждый член второго.
Каждый с каждым.
Так просто это обобщить на бесконечные последовательности нельзя — опять же, потому что никто не может бесконечное количество раз умножить на бесконечное количество элементов. Тут важно правильно сказать, а именно что пускай n-ный член произведения последовательностей равен
Теперь мы умеем складывать бесконечные последовательности и так же умеем их перемножать. Можно заметить некоторые хорошие свойства, к примеру что ; ; . Мы придумали это сложение и умножение, нужно обязательно проверять что такие свойства выполняются (это «группа» и «кольцо»). Это несложно проверить, и, в целом-то, эти все свойства довольно естественны, особенно для тех кто хоть сколько-то складывал и умножал конечные многочлены.
Попробуем теперь для примера посчитать . Согласно определению умножения получаем
Выглядит логично — умножение последовательности на число даст умножение каждого члена на это число. И это сходится с
Важное замечание: , где соответственно
Теперь посчитаем . Так же согласно определению умножения получаем
Т.е.
Что, собственно, так же сходится с
Так же получаем что .
Это базовые операции над нашей последовательностью, и теперь вот это всё хорошо бы собрать и применить к начальной рекуррентной формуле :
Из первой строчки вычитаем вторую и прибавляем третью:
Итого получаем (используя хорошие свойства сложения и умножения):
что, напомню еще раз, на самом деле
Это и есть уравнение, и его мы будем решать. Мы не можем взять так просто и поделить на , хотя бы потому что мы не определяли операцию деления. Вместо этого мы будем умножать обе части уравнения на что-то такое, что как бы является , и в конечном итоге оставим одинокую F слева.
На текущий момент из того что мы имееем мы не можем достоверно сказать существует ли вообще такое (хотя так-то оно существует, и мы его сейчас сделаем).
Но из этого абсолютно не следует что если , то . К примеру, из того что вовсе не следует что .
Для того, чтобы было верно
нужно чтобы существовал такой элемент , что .
Тогда можно получить что
Немного преобразуем наше уравнение:
Это, опять же, не просто так, это потому что последовательность умноженная на и умноженная на
даёт в результате
Вот теперь уже чуть легче, теперь хорошо бы отыскать такие $inline$"(1-x)^{-1}"$inline$ и $inline$"(1/2-x)^{-1}"$inline$, да и умножить на них наше уравнение.
Такие обратные последовательности есть, и вот их формула
Ясно что , тут без вариантов. Теперь посмотрим что может получится у 1-й степени x: (я просто покомпонентно перемножаю первую последовательность на вторую). Ясно что . Так же далее получаем что .
Для общего случая действуем подобным образом.
Таким образом, умножаем обе части уравнения:
Посмотрим повнимательней на
По определению произведения получаем формулу для n-ного члена:
Пусть . Тогда .
В то же время, следовательно
Итого приравнивая получаем .
Подставляем полученное произведение
При умножении на все члены умножились на 10 и сдвинулись на 1 вправо.
Итого получаем результат
Именно эту формулу нужно использовать для прохождения квеста, и именно её можно найти в подсказках в квесте.
К примеру на 32-й день получаем .
Глядя на формулу можно сказать что хрякоплюхам долбогрызы не помеха — они даже будучи поедаемыми успевают экспоненциально размножаться.
Таким же образом можно вывести формулу для n-ного члена последовательности Фибоначчи, правда там числа будут пострашней — с корнями, и при этом при любом n формула даст натуральное число.
А вот если по формуле — то тут можно и поспорить, будет ли это O(n) либо O(1). Зависит как мы считаем 2**n — это O(1) или O(n). С одной стороны, это битовый сдвиг, с другой стороны при n больших чем разрядность процессора потребуется больше времени на вычисления.
К примеру, если сделать Ethereum контракт, который будет считать этих хрякоплюхов, и посмотреть что получится по потреблению gas в зависимости от алгоритма:
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).
Автор: Рогин Василий