Pull to refresh

Расчет биномиальных коэффициентов на Си (С++) и Python

Python *C++ *C *
При решении задач комбинаторики часто возникает необходимость в расчете биномиальные коэффициентов. Бином Ньютона, т.е. разложение image также использует биномиальные коэффициенты. Для их расчета можно использовать формулу, выражающую биномиальный коэффициент через факториалы: image или использовать рекуррентную формулу:image Из бинома Ньютона и рекуррентной формулы ясно, что биномиальные коэффициенты — целые числа. На данном примере хотелось показать, что даже при решении несложной задачи можно наступить на грабли.
Читать дальше →
Total votes 28: ↑19 and ↓9 +10
Views 46K
Comments 73

Вычисление биномиальных коэффициентов… вручную

Entertaining tasks Algorithms *Mathematics *
Ранее в двух статьях была затронута тема вычисления биномиальных коэффициентов с помощью компьютера.
Расчет биномиальных коэффициентов на Си (С++)
Расчет биномиальных коэффициентов с использованием Фурье-преобразований
По их прочтению может сложиться мнение что это сложная и ресурсоемкая задача.
Прежде чем программировать что-то, попробуем разобраться что здесь к чему.

Факториальная формула: image

Раскроем ее:

Очевидно, что и тогда

А теперь попробуем посчитать например :
Читать дальше →
Total votes 29: ↑13 and ↓16 -3
Views 3.9K
Comments 8

Вычисление биномиальных коэффициентов… всё-таки программно

C++ *Algorithms *Mathematics *
Sandbox
Ранее, в трёх статьях была затронута тема вычисления биномиальных коэффициентов.

Расчет биномиальных коэффициентов на Си (С++)
Расчет биномиальных коэффициентов с использованием Фурье-преобразований
Вычисление биномиальных коэффициентов… вручную

В последней статье автор продемонстрировал чисто математическую оптимизацию вычисления биномиальных коэффициентов. Оказалось, что для их вычисления и компьютер-то не особенно нужен. Хватит бумаги, ручки, калькулятора и пива. Однако, если одной из вышеперечисленных вещей под рукой не окажется, но в области досягаемости будет простаивающий компьютер, то можно сделать то же самое и на компьютере.
Подробности
Total votes 19: ↑11 and ↓8 +3
Views 7.4K
Comments 10