Unsigned C(int n, int m)

{

if (m > n / 2)

m = n - m;

unsigned a = 1, b = 1;

for (int i = n; i >= n - m + 1; -- i)

a *= i;

for (int i = 1; i <= m; ++ i)

b *= i;

return a / b;

}

Нетрудно заметить, что этот алгоритм быстро приводит к выходу значений числителя или знаменателя за пределы диапазона значений типа данных unsigned. И действительно, эксперименты с этим вариантом функции показывают, что точное вычисление биномиальных коэффициентов возможно только при n < 17.

Найдем следующее соотношение:

.

То есть:

.

Тогда справедливо следующее рекуррентное соотношение, позволяющее вычислять очередное значение биномиального коэффициента через его предыдущее значение:

приm = 0 приm > 0

Это рекуррентное соотношение реализуется с помощью следующей рекурсивной функции: