2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 21:09 


29/08/11
1759
Здравствуйте!

Подскажите, пожалуйста, можно ли как-нибудь посчитать $$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 


27/08/14
206
Вам не надо считать $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 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 22:03 


01/12/11

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

 Профиль  
                  
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 22:35 


29/08/11
1759
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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 23:07 


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

 Профиль  
                  
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 23:13 
Заслуженный участник


09/05/12
25179
Limit79 в сообщении #956517 писал(а):
Дело в том, что мне нужно сравнить результаты вычисления вероятности по формуле Бернулли и по локальной формуле Муавра-Лапласа при большом количестве испытаний, а при выводе формулы Муавра-Лапласа как раз используется формула Стирлинга, поэтому мне этот вариант не подходит

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

-- 04.01.2015, 23:15 --

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

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

 Профиль  
                  
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 23:20 


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

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

 Профиль  
                  
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 23:34 
Заслуженный участник


09/05/12
25179
Limit79 в сообщении #956525 писал(а):
Целые числа мне не нужны, разумеется
Тогда Вам принципиально ничего не мешает считать все в лоб, используя какой-нибудь long double (включая факториалы). Самое неприятное, что получится - небольшая потеря точности.

 Профиль  
                  
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение04.01.2015, 23:37 


29/08/11
1759
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 
Заслуженный участник


09/05/12
25179
Limit79 в сообщении #956534 писал(а):
В unsigned long long int можно хранить числа в диапозоне
Pphantom в сообщении #956532 писал(а):
используя какой-нибудь long double (включая факториалы)
:D

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

 Профиль  
                  
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение05.01.2015, 00:22 


29/08/11
1759
Pphantom
:facepalm:
Я думал, что если не влезает в целое число, то не влезет и в число с плавающей точкой...

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

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

 Профиль  
                  
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение05.01.2015, 07:47 


24/05/09

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

 Профиль  
                  
 
 Re: C, Code::Blocks, расчет количества сочетаний из n по k
Сообщение09.01.2015, 06:04 


29/08/11
1759
Alexu007
Да, всегда целое.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group