Опять факториал

← →
Chcnger (2004-03-17 21:07) [0]

Как вычеслить: T=N!/(K!*(K-N)!)
Подскажите, а то просто вычисляя по очереди получаются слишком большие числа(для Паскаля)

← →
Gero © (2004-03-17 21:18) [1]

T := 1;
for i := 1 to K do
T := T * (N - i + 1) div i;

← →
Chcnger (2004-03-17 21:58) [2]

А можете привести объяснение? Почему так? За ранее спасибо!!!

← →
Gero © (2004-03-17 22:51) [3]

Все очень хитро сокращается.
T * (N - i + 1) всегда будет нацело делится на i.
Точного объяснения я не дам, так как сам его не помню.
Возьмите листик и ручку и попробуйте вывести всё самостоятельно.

← →
Defunct © (2004-03-18 01:16) [4]

Chcnger (17.03.04 21:07)
Представьте факториал чисел в виде ряда, и там действительно можно много чего сократить.

Но не исключаю ситуации, что у вас результат может быть число, которое состоит из более 10 тыс. десятичных цифр. В таком случае представьте ваши данные в виде массивов десятичных цифр.

← →
Defunct © (2004-03-18 01:17) [5]

Умножение в столбик из школьного курса, надеюсь, еще не забыли

← →
Nikolay M. © (2004-03-18 08:30) [6]

> T=N!/(K!*(K-N)!)

Кстати, если это число К выборок из N, то, наверное, не (K-N)!, а (N-K)!
?

← →
KSergey © (2004-03-18 08:42) [7]

> Chcnger (17.03.04 21:58) [2]
> А можете привести объяснение? Почему так? За ранее спасибо!!!

Если не лады с иксами и игреками - возьмите любые числа вместо N и K и происведите вычисления на бумажке. Только не тупо сначала числитель, потом - знаменатель считаем, а расписать как это все будет вычисляться - и увидите, что там почти все сокращается.

> Chcnger (17.03.04 21:58) [2]
> А можете привести объяснение? Почему так? За ранее спасибо!!!

Потому, что на каждом шагу получается биномиальный коэффициент.

З.Ы. Еще одна подсказка. Иногда, чтобы избежать переполнения, выгоднее вычислять в обратную сторону - от больших значений i к меньшим. Угадай сам, когда.

← →
Chcnger (2004-03-19 13:56) [9]

>З.Ы. Еще одна подсказка. Иногда, чтобы избежать переполнения, >выгоднее вычислять в обратную сторону - от больших значений i >к меньшим. Угадай сам, когда.

Так когда же? Есть идея, но кажется не то :)

Такая формула вычисляется через Стирлинга (кажется его зовут так). Ищи формулу в учебниках по математике, что-то типа
n!=(n^n)*(e^n)*sqtr(2*pi*n). Для n>10-20 получается вполне точно.

Опять факториал Найти похожие ветки