История одного маленького открытия

РЕКУРСИИ

1.  ИСТОРИЯ ОДНОГО МАЛЕНЬКОГО ОТКРЫТИЯ.

Существует рассказ о маленьком Карле-Фридрихе Гауссе[1]

При решении многих задач (особенно геометрических) особую роль играет графическое представление условия. Если рисунок сделан верно (на нем представлены все детали, необходимые для решения задачи, и отсутствуют все ненужные).

Покажем, как решается эта задача.

Выпишем последовательно эту формулу для всех n

Теперь сложим все равенства. Получим

Мы нашли

А ранее

( Легко видеть, что S0=n)

Причем для расчета S2 мы использовали рассчитанные ранее значения S1 (и S0). Получилась некая схема расчета, опробованная на расчете S1 и S2 .

Обобщим задачу. Найдем

используя уже опробованный метод[2]

Запишем, как и ранее

Складывая получаем

Этот метод принадлежит Паскалю.

2.  АБРАКАДАБРА

Переформулировать задачу можно следующим образом: найти в городе, схема улиц которого представлена на рисунке, число различных кратчайших маршрутов из пункта А в пункт А.

Начните с верхней точки А и в каждом перекрестке поставьте число маршрутов, которыми можно попасть на этот перекресток.

Заметим, что

И так далее. Действительно, в точку X можно попасть либо из точки Y, либо из точки Z.

Представив полученные данные на рисунке, найдем интересующий нас ответ.

3.  Треугольник Паскаля

Числа, стоящие в верхней части квадрата образуют треугольник Паскаля.

Мы можем

Паскаль также предложил формулу для вычисления

Эта формула для вычисления биномиальных коэффициентов (число сочетаний из n по r ). Эта формула доказывается методом математической индукции

Задача Иосифа.

Задача Иосифа названа по имени Иосифа Флавия – историка, участника восстания евреев против римлян в 66-70 гг. Иосиф в течение 47 дней командовал обороной крепости Иотапата, и после того, как она пала, укрылся вместе с 40 фанатиками в пещере неподалеку. Здесь повстанцы решили покончить с собой, чтобы не сдаться римлянам. Иосиф предложил, чтобы все встали в круг и по очереди каждый убивал своего соседа (т. е. каждого второго), пока не останется один человек, который должен совершить самоубийство. Решивший сдаться Иосиф поставил себя и своего единомышленника в такие места в круге, что они остались последними.

Удобно рассматривать четные и нечетные значения n отдельно. Если n четно, т. е. n=2k, то после первого прохода мы получаем экземпляр той же задачи, но половинного размера. Единственное отличие – в нумерации: например, человек номер 3 на втором проходе находится в позиции 2, номер 5 - в позиции 3 и т. д. Легко увидеть, что для того, чтобы получить начальную позицию человека, надо просто умножить его новую позицию на 2 и вычесть 1. Эти соотношения выполняются, в частности, для уцелевшего человека, так что

Рассмотрим случай нечетного n=2kПри первом проходе удаляются все люди в четных позициях. Если мы добавим сюда и человека номер 1, то получим экземпляр задачи размера k. В этот раз, чтобы получить начальную позицию человека по его новой позиции, мы должны умножить новую позицию на 2 и прибавить 1.

4.  Задача

Задана квадратная таблица из N2 чисел, которую можно представить матрицей A[i, j]. За каждый проход через клетку (i, j) взимается штраф A[i, j]. Необходимо определить минимальный суммарный штраф, с которым можно пройти из какой-либо клетки первой строки в какую-нибудь клетку в последней строке. При этом из текущей клетки можно переходить в любую из 3-х соседних клеток, стоящих в строке с номером, на 1 большим текущего номера строки.

Решение.

РЕШЕНИЕ

Пусть матрица В[i, j] определяет минимальный штраф, который можно получить, дойдя до клетки (i, j).

Ясно, что В[1, j]= А[i, j] и

Так как в клетку (i, j) можно попасть только из клеток (i-1, j-1), (i-1, j), и (i-1, j+1), то

С помощью этого рекуррентного соотношения рассчитываем элементы матрицы В[i, j]. Минимальное значение В[n, j] и есть решение нашей задачи.

[1]

[2]