Архив форумов ЦИТФорума

[ZOObilo]

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

[grayrat]

На сколько большие числа ?

Можно считать используя рекуррентную формулу, массивы не нужны.

Можно вообще обойтись без умножений и делений используя треугольник Паскаля, но будет нужен массив длины n.

[ZOObilo]

Ну, я тут подумал, что порядок n-k не так уж и велик. Где-то порядка 10^4. Результаты в этом случае конечно здоровые, но... выделить массив из 10000 элеметнов по 100 байт не так уж сложно. Наверное, так и сделаю, хотя очень интересно, есть ли решение поставленной задачи (понятно, что в случае, когда невозможно выделить память под массив, невозможен будет и вариант с рекурсией - каждый раз на стек будет класться большое число и в итоге получим тот же массив, но не выделенный явно, да еще и больше, потому что, например, туда еще и код возврата кладется).
_________________
Бойтесь тормозного зверя IE. Слушайте Opera. ^_^

[DmitryShm1]

C(n,k) = n*(n-1)*..*(n-k+1)/k! . C(n,k) = C(n,k-1) + C(n-1, k-1);
числитель и знаменатель вычисляйте отдельно, а потом делите. Есть хорошая практика хранить вместо чисел степени их простых делителей, как спектр. И тогда проблема с умножением и делением отпадает. Тогда и производительность возрастет. Рекоммнедую все реализовать на ассемблере. Простые числа следует вычислить сразу на один проход и хранить их где-то, а потом уже запускать алгоритм. Идея с рекурсией отпадает сразу из-за граничных условий.

[grayrat]

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

C(n,k)=C(n-1,k)*n/(n-k)=...=П(i=k+1..n,i/(i+k)), 0<k<n-1
, а для k=n, понятно, C(n,n)=1.

Что касается треугольника Паскаля, то он прост как веник!

[ZOObilo]

Четко. Рекурсивная формула сработает. Я даже готов это доказать.

Всем спасибо.
_________________
Бойтесь тормозного зверя IE. Слушайте Opera. ^_^