Идеи реализации

Подходящим способом перебора биномиальных коэффициентов, составляющих треугольник Паскаля, будет двойной цикл. Во внешнем цикле перебираются строки треугольника, во внутреннем — числа в строке.

Сразу отвергнем вычисление биномиальных коэффициентов по формуле с факториалами. Для нахождения факториала числа потребуется умножение, причём многократное, кроме того, формула содержит также и деление. Факториалы одних и тех же чисел пришлось бы считать по многу раз, что привело бы к крайне неэффективной программе.

Тут самое время упомянуть о том, как можно было бы ускорить подобные дорогостоящие вычисления. Вместе с вычислениями факториалов чисел ведётся таблица, куда заносятся результаты вычислений. В таблице две колонки: число и его факториал. Как только потребовалось вычислить очередной факториал, следует первым делом поискать число в первой колонке таблицы: вдруг точно такое же вычисление было проделано раньше, и тогда останется лишь из правой колонки факториал. Если же число отсутствует в таблице, факториал придётся считать «честно», и уже после этого заносить результат в таблицу. Такой метод ускорения вычислений годится не только для факториалов, но и во всех тех случаях, когда есть потребность в многократных вычислениях при одних и тех же входных данных. Метод называется кешированием. Разумеется, обязательным условием применимости является детерминированность (предопределённость) вычислительного алгоритма: результат вычисления должен полностью определяться входными данными. Вычисления факториала детерминированно: n ! зависит только от n. Чтобы от кеширования была польза, необходимо, чтобы поиск в таблице давался бы дешевле, чем повторное вычисление.

Однако мы обойдёмся и без кеширования, и вообще без факториалов. Сам способ построения треугольника Паскаля подсказывает нам простой алгоритм. Чтобы найти следующую строку в треугольнике, нужно взять предыдущую, и прибавить к ней точно такую же, но сдвинутую на одну колонку вправо. Вот пример того, как из двенадцатой строки получается тринадцатая: 1 11 55 165 330 462 462 330 165 55 11 1 1 11 55 165 330 462 462 330 165 55 11 1 1 12 66 220 495 792 924 792 495 220 66 12 1

Информатика-54© А. Н. Швец