Сочетания рекурсией

[Tishaishii]

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

C(n,m)=n!/[m!(n-m)!]

Это функция, она возвращает 1 или 0 + результат рекурсии.
Типа:

long c(n,m)<br>{<br>   if(.............)return c(n_,m_)+0  else<br>   if(.............)return c(n_,m_)+1<br>}

Точно не помню.

Вопрос: помогите вспомнить рекурсивный алгоритм вычисления количества сочетаний

Сообщение отредактировано: Tishaishii - 25.10.03, 13:10

[Visitor]

не могу, честно говоря, понять, откуда там 0 и 1

вот рекуррентное соотношение: C(k, n) = C(k-1, n-1)+C(k, n-1)
Доопределены C(0,n) = C(n,n) = 1, С(k<0,n) = C(k>n,n) = 0 для любого n

тогда

unsigned long C(int k, int n)<br>{<br>    if((0 > k) || (n < k))<br>        return 0;<br>    if((1 == n) || (0 == k) || (n+0 == k))<br>        return 1;<br>    return C(k-1, n-1) + C(k, n-1);<br>}

--

Кстати, при той струкутуре рекурсивной функции, которая у тебя приведена, вычисление C(16,32) потребует глубины рекурсии примерно в 600 млн вызовов

Сообщение отредактировано: Visitor - 25.10.03, 14:55

[experimenter]

да, надо заводить дополнительный массив для  уже вычеслиных сочетаний, и на каждой глубине рекусрии проверять, не вычислено ли уже, если да, то возвращаться и брать из массива. так быстрее будет! ;D

[Tishaishii]

Благодарю.

[experimenter]

yo! пожалуйста! ;D