2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 21:09 
Здравствуйте!

Подскажите, пожалуйста, можно ли как-нибудь посчитать $$C_{n}^{k} = \frac{n!}{k! \cdot (n-k)!}$$

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

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

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

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

Спасибо!

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

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

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

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 22:03 
Можно использовать формулу $C_n^k=\prod\nolimits_{i=1}^k \frac{n-k+i}{i}$

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 22:35 
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}$ уже никуда не влезает.

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 23:04 
Так Вам в итоге нужны только вероятности в виде числа с плавающей точкой? Тогда попросту воспользоваться формулой Стирлинга (причем считать сначала логарифм вероятности).

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 23:07 
Pphantom
Дело в том, что мне нужно сравнить результаты вычисления вероятности по формуле Бернулли и по локальной формуле Муавра-Лапласа при большом количестве испытаний, а при выводе формулы Муавра-Лапласа как раз используется формула Стирлинга, поэтому мне этот вариант не подходит :-(

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 23:13 
Limit79 в сообщении #956517 писал(а):
Дело в том, что мне нужно сравнить результаты вычисления вероятности по формуле Бернулли и по локальной формуле Муавра-Лапласа при большом количестве испытаний, а при выводе формулы Муавра-Лапласа как раз используется формула Стирлинга, поэтому мне этот вариант не подходит

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

-- 04.01.2015, 23:15 --

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

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

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 23:20 
Pphantom
У меня была похожая идея. Я вычисляю биномиальный коэффициент рекурсивно, и, может быть можно на каждом шаге домножать на какую-либо вероятность, дабы числа не получились такими большими, а потом просто просуммировать их, и получить искомую вероятность.

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

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 23:34 
Limit79 в сообщении #956525 писал(а):
Целые числа мне не нужны, разумеется
Тогда Вам принципиально ничего не мешает считать все в лоб, используя какой-нибудь long double (включая факториалы). Самое неприятное, что получится - небольшая потеря точности.

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 23:37 
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!$ уже нет.

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение05.01.2015, 00:06 
Limit79 в сообщении #956534 писал(а):
В unsigned long long int можно хранить числа в диапозоне
Pphantom в сообщении #956532 писал(а):
используя какой-нибудь long double (включая факториалы)
:D

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

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение05.01.2015, 00:22 
Pphantom
:facepalm:
Я думал, что если не влезает в целое число, то не влезет и в число с плавающей точкой...

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

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

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение05.01.2015, 07:47 
Количество сочетаний вроде как всегда целое число, нет?

 
 
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение09.01.2015, 06:04 
Alexu007
Да, всегда целое.

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group