Пространственно-временной компромисс

Биномиальный коэффициент можно вычислить по формуле `C_n^k=(n!)/(k!(n-k)!)`, но потребуется `Theta(n)` умножений.

Вывод коэффициентов для формулы
`(a+b)^n=C_n^0 a^n+...+C_n^k a^{n-k} b^k + ... + C_n^n b^n`
требует `Theta(n^2)` умножений.

Рассмотрим другую формулу:
`C_n^k=C_{n-1}^{k-1}+C_{n-1}^k` для `n>k>0`, и `C_0^n=C_n^n=1`.

Будем записывать вычисленные значения биномиальных коэффициентов в таблицу с `n+1` строками и `k+1` столбцами.

Алгоритм Binomial(`n, k`)
// Входные данные: Пара неотрицательных целых чисел `n >= k >= 0`
// Выходные данные: Значение `C_n^k`
if `C[n,k]=0`
`quad` if `n = 0 or n = k`
`quad quad C[n,k] larr 1`
`quad` else
`quad quad C[n,k] larr "Binomial"(n-1, k-1)+"Binomial"(n-1, k)`
return `C[n,k]`

Здесь использован приём запоминающей функции, часто используемый в реализации алгоритмов динамического программирования через рекурсию. Если значение уже ранее вычислялось, то оно просто извлекается из таблицы; в противном случае оно вычисляется при помощи рекурсивного вызова, и полученный результат записывается в таблице.
Сколько сложений будет выполнено в задаче о выводе коэффициентов уравнения?

Задания для практики

1. Какой из способов вычисления биномиальных коэффициентов наиболее эффективен?
   а) по формуле `C_n^k={n!}/{k!(n-k)!}`
   б) по формуле `C_n^k={n(n-1)...(n-k+1)}/{k!}`
   в) по формуле `C_n^k=C_{n-1}^k+C_{n-1}^{k-1}`, где `C_0^0=C_n^n=1`
   г) с использованием динамического программирования
2. Как переписать алгоритм вычисления таблицы `C[n,k]` без использования рекурсии?