Проблема с подсчетом C(n,k)(С из n по k) в больших числах

[ZOObilo]

Имеется задача: посчитать C(n,k) в больших числах, но так, чтобы сначала производились необходимые деления, а уж потом умножения. Передумал кучу вариантов, но проблема везде одна: надо выделять массив либо из k, либо из n-k элементов (в лучшем случае битов, что тоже много), что, сами понимаете, невозможно, т.к. n и k практически не ограничены. Отсюда вопрос: как вы думаете, можно проделать необходимые операции, не прибегая к выделению массивов?

[Гром]

Что есть С - колличество сочетаний? Сумма, среднее арифметическое?? Телепаты в отпуске....

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

Для любой из этьих задач.

[RXL]

http://www.flasher.ru/forum/showthread.php?s=29b9a41443488d567f5058cd552d22b6&threadid=30824

Есть такая наука, как комбинаторика. Есть такая функция как "Цэ из эн по ка" (не по-китайски). Выглядит так: C(n,k). Означает следующее:
X=C(N,K) == X равно количеству способов выбрать K предметов из N.

Выглядит формула так: C(n,k)=n!/(k!*(n-k)!), где n! - факториал числа n.

[ZOObilo]

Гром, здесь суть не в том, что не хочется использовать массив, а в том, что не хватит памяти выделить даже по одному биту, если этих битов понадобися 'большое число' (например 10^100 бит Вам уже не выделить). Причем не важно, хранить эти биты списком, или массивом, или еще как-нибудь.

RXL, насколько я понял, там речь о треугольнике Паскаля. В принципе, можно ограничиться двумя строками, но даже они не влезут в память при БОЛЬШИХ ЧИСЛАХ.

[RXL]

ZOObilo, что за задача такая?

[ZOObilo]

RXL, задача сформулирована в первом посте. Если имеется в виду какая-то более глобальная, то таковой нет. Задача из университета...

[Гром]

Tak ya i utochnyal kombinatorika li eto...  
ZOObilo, ty ne slyshish.

Lyuboi process - vydaet reshenie - t.e. cifru. V dannom sluchae reshenie - chislo vozmozhnyh sochetaniy

Est takaya vozmozhnost' razbit ves' process vychisleniy na dostupnye etapy....

1. Zapisat formulu vichisleniya lubogo somnozhitelya (elementa massiva) v zavisimosti ot indeksa. Togda tebe ne nuzhna pamyat voobshe - vsya formula budet umeshatsya v summu ili umnozhenie...
2. Vtoroy etap - poluchit chastnye rezultaty i sohranyat ih v svyaznom spiske rezultatov, chto dast tebe vozmozhnost imet massv realnoi dliny.
3. Vychislyat rezultaty dostatochno malenkimi, a potom - poluchit obshiy rezultat finalnoi formuloi - kotoryi zapisat ne v odin tip dannyh a v svoi sobstvenny.

[ZOObilo]

Гром, действительно проблемы. Сорри.

Решение найдено!
C(n,k)=C(n-1,k)*n/(n-k)=...=П(i=k+1..n,i/(i+k)), 0<k<n-1

Я даже готов доказать, что это будет корректно работать.

Все. Спасибо всем.

[stragner]

c(n,k) = n! / (k! * (n-k)!)

А что, если не делить в лоб, а ,например, использовать сокращения чисел
Для начала надо сократить  на k!, то есть в числителе останется  не N!, а произведение чисел (k+1)*(k+2)*...*n. У нас в знаменателе есть
(n-k)! = 1*2*3*4*...*m*...*(n-k)! .  Берем число m и сокращаем его с каким-нибудь числом из числителя и т.д. В итоге останется ряд чисел, произведение которого будет давать не такое уж и большое число

[ZOObilo]

stragner, постомри внимательней на фрмулу. Там это учитывается. А тот вариант, который предлагаешь ты, как раз и приводит к хранению огромного массива. Но в любом случае спасибо за отзыв...  

[Гром]

ZOObilo, рад если натолкнул на правильную мысль, буду рад видеть тебя у нас всегда - присоединяйся.  

[ZOObilo]

Thanx.