![>](style_images/1/nav_m.gif)
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.220.182.13] |
![]() |
|
Сообщ.
#1
,
|
|
|
Знаю, существует рекурсивный алгоритм определния числа сочетаний.
![]() ![]() 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>} Вопрос: помогите вспомнить рекурсивный алгоритм вычисления количества сочетаний |
Сообщ.
#2
,
|
|
|
не могу, честно говоря, понять, откуда там 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 млн вызовов ![]() |
Сообщ.
#3
,
|
|
|
да, надо заводить дополнительный массив для уже вычеслиных сочетаний, и на каждой глубине рекусрии проверять, не вычислено ли уже, если да, то возвращаться и брать из массива. так быстрее будет! ;D
|
Сообщ.
#4
,
|
|
|
Благодарю.
|
Сообщ.
#5
,
|
|
|
yo! пожалуйста! ;D
|