Сегодня тот день, когда я наконец понял реальное использование Треугольника Паскаля. Последовательность Паскаля — это то, что я запрограммировал на первом курсе университета. Это было веселое упражнение. Это была одна из задач в серии поиска шаблонов и их кодирования на C или Java.
Вопросы динамического программирования могут быть сложными. Биномиальная последовательность и ее варианты всегда были моим врагом. Решения никогда не приходят ко мне легко, и даже когда они приходят, это не всегда приводит к работающему коду. Вот почему на этот раз я решил попробовать новый источник динамического программирования и прочитать главу 8 Skiena. Пока читал, обсуждалась эта проблема, и бум все вспомнилось. Была восстановлена связь между биномиальной последовательностью, треугольником Паскаля и динамическим программированием. По иронии судьбы, решение вопроса, с которым я всегда боролся, вариантов биномиальной последовательности, — это одна из первых программ, которые я написал, Треугольник Паскаля.
Треугольник Паскаля показан выше. В нем каждый элемент ряда представляет собой сумму двух чисел «ПРЯМО НАД НИМ». Тогда возникает вопрос, что означает «прямо вверху»? Как то, что можно легко увидеть, может быть выражено в коде?
Если мы возьмем пример 6 на диаграмме, числа прямо над ним будут 3 и 3. 6 находится в 4-й строке и 3-м столбце внутри нее. Две тройки — это строка выше — строка номер 3, а также 2-й и 3-й столбец соответственно. Похожую картину можно увидеть для 10-ти в 5-м ряду. Теперь отношение, которое мы можем вывести из этого, таково: каждый [n,k]-й элемент является суммой [n-1,k] и [n-1,k-1] элементов.
Теперь, как это связано с биномиальной теоремой. Напомним, биномиальное число выглядит следующим образом -
Физический смысл этого в том, что нам нужно выбрать k элементов из n элементов. Мы можем либо выбрать n-й элемент и выбрать остальные k-1 элементов из оставшихся n-1 элементов, либо отбросить n-й элемент и выбрать все k элементов из оставшихся n-1 элементов. Здесь должна быть очевидна определенная симметрия того, что мы видели в треугольнике Паскаля.
Теперь перейдем к кодированию. Если мы представим результаты каждого nCk в матрице, то сможем эффективно вычислить более высокие порядки последовательности. Также будет ясно, что после вычисления элемента его можно использовать и в других вычислениях подпоследовательности. Это означает, что есть хороший потенциал для запоминания!
Начнем с рекурсивного решения для биномиальной последовательности. Здесь наблюдается явный рецидив. Для любой повторяющейся функции необходимы базовые случаи. Для биномиальной последовательности базовым случаем будет выбор 0 элементов из n. Такой выбор можно сделать только одним способом — NULL SET. Другим базовым случаем будет случай, когда нам нужно выбрать ВСЕ n элементов из набора n. Что опять же можно сделать 1 способом. Далее идет выбор 0 элементов из n, можно сделать 1 способом. Наконец, выбрать 1 элемент из n можно n способами. Все это базовые случаи, о которых мы должны заботиться.
Рекуррентное решение можно записать следующим образом.
Обратите внимание, что в приведенном выше решении есть много перекрывающихся подзадач, которые пересчитываются. Чтобы избежать пересчета, мы можем сохранить его в матрице. Давайте обсудим это с помощью итеративного решения. Мы начинаем с инициализации матрицы соответствующим значением для базовых случаев, которые мы обсуждали выше. (Примечание: в коде я пошел по простому пути и инициализировал ВСЕ элементы равными 1. Это расточительно.) Единственный случай, который здесь не представлен, — это выбор 1 элемента из n. Этот случай мы вычислим. Итеративное решение в python выглядит следующим образом:
Результат запуска итеративного решения следующий:
В этом посте мы обсудили биномиальную последовательность и ее связь с треугольником Паскаля. Мы прошли через мое путешествие по выяснению этих отношений и поняли, что иногда соединение точек может занять 10 лет. Мы также обсудили решение для одного и того же, как итеративного, так и рекурсивного. Я настоятельно рекомендую прочитать Skiena и CLRS для алгоритмов, если вы еще этого не сделали.
Продолжайте кодировать!
