C(n,k) во Флэше. Помогите с оптимизацией.

[[subway]design]

Привет!

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

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

Вопрос: как во Флэше (с учетом его тормозов) создать максимально оптимизированную функцию Цэшки? Если надо будет выбирать из 1000 предметов 659, то флеш просто обламается считать факториал 1000 (уже factorial(172)=infinity).

Я предполагаю только два трюка: массив значений факториалов и тот факт, что C(n,k)==C(n,n-k).

Вот. Жду идей.

[Тимур Старый]

Так ты еще учишься иль решил сам над собой изгольнуться?

[[subway]design]

Учусь чему?...
Мне нужно в кое-какой формуле Цешку использовать, а втупую такие факториалы считать - захлебнешься. Вот я и спрашиваю, как заоптимизировать этот процесс. Может таблицу создать arr[1000][1000], где расположены сразу значения n и k: c_array[n][k] ?...

[F_Flash]

1. Вариант заполнения массива.

1.Можно и массив, только массив 1000х1000 сколько памяти возьмет? по одному быйту на число - один метр, а флешь по моему 8 байт на число, это 8 метров а У ТЯ ТАМ такие чИСЛА ВЫЙДУТ


Ну все таки использовать "гору архимеда" короче не помню как точно называется. идея такая
1 c(1,0)
1 2 1 c(2,0) c(2,1)
1 3 3 1 c(3,0) c(3,1),c(3,2)
1 4 6 4 1
1 5 10 10 5 1

Логику уловил?

Кроме того массив у тебя будет не nхn т.к n<k.
Соответсвенно, как ты написал, выбирать1000 предметов из 692 ты не можешь, тлько наоборот.

2. Можно и влоб посчитать.
начинать умножать (n-k)(n-k+1)....n и одновременно делить
на 2 3 ......<(n-k). Или наоборот спускаться,
n/2/3 пока не будет появляться дробь, затем (n-1)/4/5/6

Ну вот что на первое на ум пришло.... Еще подумаю

P.S
Интересно нафига это надо тебе.
ты считал количсество комбинасий лотереи 6х36 с(36,6) это моему неколько несколько миллионов или десятко миллионов. Так ты посмотри какие числя детские 6 и 36ты про тысячи говоришь.....


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

[F_Flash]

Если не понятно,что с горой,Ты циферки горкой поставь, а то пробелы удалились...

Факториал числа при достаточно больших n примерно равен -

n!~sqrt(2*pi)*n^(n+1/2)*e^(-n)*(1+1/(12*n)+1/(288*n^2)+...)

подставляешь всё это в формулу для C(n,k) и пользуешься... не забывая, конечно, о приближённом значении выражения.
Удачи.

[[subway]design]

2 F_Flash: ты прав, но не "гору архимеда", а "треугольник Паскаля" надо использовать :) Я ее уже спрограммировал:

function binom(size){

for(i=0;i<size;i++) {
data[i][0]=1;
data[i][i]=1;
}
for(i=1;i<size;i++)
for(j=1;j<i;j++)
data[i][j]=data[i-1][j-1]+data[i-1][j];
}

Всем спасибо за участие :)