C, Code::Blocks, расчет количества сочетаний из n по k

[Limit79]

Здравствуйте!

Подскажите, пожалуйста, можно ли как-нибудь посчитать

$$C_{n}^{k} = \frac{n!}{k! \cdot (n-k)!}$$

при $n>20$ (хотя бы на чуть-чуть по-больше)?

Хотелось бы найти решение без использования сторонних библиотек.

При $k \leqslant n \leqslant 20$ считается нормально, но, так как $21!$ в unsigned long long int уже не влезает, то после $21$ считается некорректно.

Исходное задание -- проверка локальной теоремы Муавра-Лапласа с использованием формулы Бернулли для большого кол-ва испытаний.

Спасибо!

[Progger]

Вам не надо считать $n!$ целиком. При $k \geqslant \frac{n}{2}$ сначала посчитайте $\frac{n!}{k!}$, что соответствует $(k + 1) \cdot (k + 2) \cdot ... \cdot n$, и разделите на $(n-k)!$. При $k < \frac{n}{2}$ наоборот.

[Pphantom]

Во-первых, можно не считать в лоб три факториала, а выкинуть $k!$ (если $k > n-k$) сверху и снизу, если нужно "на чуть-чуть", то этого уже хватит. Если нужно больше, то при подсчете оставшегося выражения (в котором сверху и снизу одинаковое количество сомножителей) можно по очереди добавлять по сомножителю в числитель и знаменатель, сразу же сокращая результат на НОД.

Хотя, если задача состоит в том, чтобы получить результат, а не задолбаться (как в анекдоте про новобранцев и старшину), то я бы просто сменил C на что-то с поддержкой арифметики бесконечной точности.

[Skeptic]

Можно использовать формулу $C_n^k=\prod\nolimits_{i=1}^k \frac{n-k+i}{i}$

[Limit79]

Progger
Pphantom
Skeptic
Спасибо!

Я наткнулся на рекуррентную формулу

$${n\choose k}=\frac{n}{n-k}{n-1\choose k}$$

при начальном условии

$${k\choose k}=1$$

Она хорошо работает, но, например, $C_{150}^{80}$, уже в unsigned long long int не помещается.

Но вероятность

$$p_{150}(80) = C_{150}^{80} \cdot 0.6^{80} \cdot 0.4^{150-80} \approx 0.0166$$

вполне нормальное число.

Не подскажите ли, как тут быть? Как посчитать эту вероятность, при условии, что $C_{150}^{80}$ уже никуда не влезает.

[Pphantom]

Так Вам в итоге нужны только вероятности в виде числа с плавающей точкой? Тогда попросту воспользоваться формулой Стирлинга (причем считать сначала логарифм вероятности).

[Limit79]

Pphantom
Дело в том, что мне нужно сравнить результаты вычисления вероятности по формуле Бернулли и по локальной формуле Муавра-Лапласа при большом количестве испытаний, а при выводе формулы Муавра-Лапласа как раз используется формула Стирлинга, поэтому мне этот вариант не подходит

[Pphantom]

Limit79 в сообщении #956517 писал(а):

Дело в том, что мне нужно сравнить результаты вычисления вероятности по формуле Бернулли и по локальной формуле Муавра-Лапласа при большом количестве испытаний, а при выводе формулы Муавра-Лапласа как раз используется формула Стирлинга, поэтому мне этот вариант не подходит

В общем, цель таки задолбаться, я понял. Тогда воспользуйтесь вариантом, который я описывал выше, но модифицируйте его - на каждом шаге надо будет умножать числитель и знаменатель на соответствующие множители от вероятностей. Боюсь, правда, что конечная обыкновенная дробь все равно окажется такой, что ее числитель и знаменатель никуда не влезут, даже при сокращениях по дороге.

-- 04.01.2015, 23:15 --

P.S. Да, правильно боялся - не лезет. Следовательно, нужна либо полноценная длинная арифметика (либо самописная, либо с использованием внешней библиотеки), либо в какой-то момент придется отказаться от целочисленного счета.

Ну или таки сменить язык (что в каком-то смысле эквивалентно использованию внешней библиотеки).

[Limit79]

Pphantom
У меня была похожая идея. Я вычисляю биномиальный коэффициент рекурсивно, и, может быть можно на каждом шаге домножать на какую-либо вероятность, дабы числа не получились такими большими, а потом просто просуммировать их, и получить искомую вероятность.

Целые числа мне не нужны, разумеется

[Pphantom]

Limit79 в сообщении #956525 писал(а):

Целые числа мне не нужны, разумеется

Тогда Вам принципиально ничего не мешает считать все в лоб, используя какой-нибудь long double (включая факториалы). Самое неприятное, что получится - небольшая потеря точности.

[Limit79]

Pphantom

Limit79 в сообщении #956436 писал(а):

При $k \leqslant n \leqslant 20$ считается нормально, но, так как $21!$ в unsigned long long int уже не влезает, то после $21$ считается некорректно.

-- 05.01.2015, 00:46 --

Например:

Используется синтаксис C++

typedef unsigned long long int ulli;

ulli fact(unsigned int n)
 {
     return n>=1 ? n * fact(n-1) : 1;
 }

int main()
{
    printf("%llu\n",fact(20));
    return 0;
}

 

При $20!$ я получаю вполне верное $2432902008176640000$.

А при $21!$ я получаю уже какое-то неверное значение $14197454024290336768$

-- 05.01.2015, 00:54 --

В unsigned long long int можно хранить числа в диапозоне

$$0...18446744073709551615$$

$20!$ влезает в этот диапазон, а $21!$ уже нет.

[Pphantom]

Limit79 в сообщении #956534 писал(а):

В unsigned long long int можно хранить числа в диапозоне

Pphantom в сообщении #956532 писал(а):

используя какой-нибудь long double (включая факториалы)

Зачем Вы так цепляетесь за целочисленную арифметику, если она, как оказывается, Вам просто не нужна?

[Limit79]

Pphantom

Я думал, что если не влезает в целое число, то не влезет и в число с плавающей точкой...

Целый день с этим сидел, а оно вот как элементарно получается

Спасибо Вам огромное! Все работает!

[Alexu007]

Количество сочетаний вроде как всегда целое число, нет?

[Limit79]

Alexu007
Да, всегда целое.