Вывод Формулы N-Го Члена Рекуррентной Последовательности На Примере Задачи Из Квеста «Амнезия»

Пеленгский фермер Бухьерик разводит кабанов-хряков.
Эти животные размножаются настолько быстро, что их численность увеличивается в 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

Утро

После размножения

После дебилов (вечер)

Начиная со второго дня

Применяется следующая рекуррентная формула:

Итак, снова все вместе

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

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

— это то, что мы хотим найти (точнее, мы хотим получить формулу для его членов).
Составим уравнение из последовательностей.
Для этого придумаем сложение для последовательностей:

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

мы как бы говорим: возьми день 0, возьми день 1, а затем медленно, шаг за шагом, считай следующие дни, пока не достигнешь того, что тебе нужно.
О сумме последовательностей говорим: если вам нужен 100-й член суммы, то возьмите 100-й член из слагаемых последовательностей и сложите их.
Нужна миллионная - тоже, возьмите туда миллионную, возьмите туда миллионную, сложите эти цифры и получите то, что вам нужно.
Это похоже на суммирование полиномов, например:

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

Где

- просто некоторые символы.
А если сложить два таких «бесконечных слагаемых», то их сумма будет в точности суммой последовательностей (именно так мы определили сумму последовательностей).
Здесь важно понимать, что бесконечных многочленов на самом деле не существует, это просто другое, но более удобное обозначение бесконечной последовательности: пишем

, но мы видим

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

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

Другими словами, каждый член первого многочлена умножается на каждый член второго.
Каждый со всеми.
Это нельзя так просто обобщить на бесконечные последовательности – опять же, потому что никто не может умножать бесконечное количество раз на бесконечное число элементов.
Здесь важно сказать правильно, а именно: пусть n-й член произведения последовательностей равен

Почему это так На самом деле, если вам интересно, что находится на 100-м месте, т. е.
какой коэффициент

, то вы вполне можете сказать:

может случиться, если умножить

.
Также

может случиться, если умножить

.
Можно сосчитать и назвать все 101 пару слагаемых, которые при умножении дадут

.
И после этого упомянуть, что больше нет

в работе он работать не может. Теперь мы знаем, как складывать бесконечные последовательности, а также умеем их умножать.
Вы можете заметить некоторые хорошие свойства, например, что

;

;

.
Это сложение и умножение мы придумали, необходимо проверить, выполняются ли такие свойства (это «группа» и «кольцо»).
Проверить это несложно, и, в общем-то, все эти свойства вполне естественны, особенно для тех, кто владеет хоть каким-то сложением и умножением конечных многочленов.
Давайте теперь попробуем посчитать на примере

.
По определению умножения получаем

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

Важная заметка:

, где соответственно

Теперь давайте посчитаем

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

Те.

Что, собственно, и совпадает с

Мы также получаем это

.
Это основные операции над нашей последовательностью, и теперь неплохо бы все это собрать и применить к исходной рекуррентной формуле

:

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

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

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

Это уравнение, и мы его решим.
Мы не можем просто разделить на

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

, и в конечном итоге слева останется одинокая буква F. На данный момент из того, что мы имеем, мы не можем достоверно сказать, существует ли такая вещь вообще.

(хотя оно существует, и мы сейчас это сделаем).
Почему можно на что-то умножить обе части уравнения? Если у нас есть какие-либо

И

, и притом такой, что

, Что

Но из этого совершенно не следует, что если

, Что

.
Например, из того, что

из этого вовсе не следует

.
Для того, чтобы это было правдой

такой элемент должен существовать

, Что

.
Тогда вы можете получить то, что

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

Это опять-таки не просто так, а потому, что последовательность

умножается на

и умноженный на

приводит к

Теперь немного проще, теперь было бы неплохо найти такой

И

, и умножим на них наше уравнение.
Существуют такие обратные последовательности, и вот их формула

Как я могу это получить? Сначала давайте рассмотрим простой случай, когда

:

Ясно, что

, тут без вариантов.
Теперь посмотрим, что может произойти с 1-й степенью х:

(Я просто умножаю первую последовательность на вторую покомпонентно).
Ясно, что

.
Далее мы получаем, что

.
Для общего случая

мы действуем аналогичным образом.
Таким образом, умножаем обе части уравнения:

Давайте посмотрим поближе

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

Откуда взялся последний шаг? Это обычная сумма членов конечной геометрической прогрессии.
Быстро получить его можно так: Позволять

.
Затем

.
В то же время,

следовательно

Тотальное приравнивание

мы получаем

.
Заменяем полученный продукт

При умножении на

все члены умножаются на 10 и сдвигаются на 1 вправо.
Итого получаем результат

Именно эту формулу необходимо использовать для выполнения квеста, и именно ее можно найти в подсказках в квесте.
Например, на 32-й день мы получаем

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

 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;
     }
 

   

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