Ранее в двух статьях была затронута тема вычисления биномиальных коэффициентов с помощью компьютера.
Расчет биномиальных коэффициентов на Си (С++)
Расчет биномиальных коэффициентов с использованием Фурье-преобразований
По их прочтению может сложиться мнение что это сложная и ресурсоемкая задача.
Прежде чем программировать что-то, попробуем разобраться что здесь к чему.
Факториальная формула:
Раскроем ее:![](https://habrastorage.org/r/w1560/files/672/a9c/bf6/672a9cbf660f4d688a2e256dbaebc44d.png)
Очевидно, что
и тогда ![](https://habrastorage.org/r/w1560/files/baf/7dc/cb0/baf7dccb02924c11ba7b41a5ab4c35d0.png)
А теперь попробуем посчитать например
:
![](https://habrastorage.org/r/w1560/files/8a2/35c/973/8a235c9738d44e41b777490d17e3ec91.png)
Сразу видно, что 10, 9 и 8 взаимно сокращаются, приводя нас к
Поглядев внимательнее, видим что на этом сокращения не заканчиваются. 14 делится на 7, 12 на 6, 15 на 5, 16 на 4. Оставшиеся от 15 три делится на три, и оставшиеся от 7 2 делится на последнюю двойку. Произведя все эти сокращения мы избавляемся от знаменателя, получаем такое произведение:![](https://habrastorage.org/r/w1560/files/e4c/a20/598/e4ca20598fd349289fea362fc4875a97.png)
Попробуем посчитать![](https://habrastorage.org/r/w1560/files/00a/405/7b1/00a4057b1a99476999a6192f5dee0fa1.png)
![](https://habrastorage.org/r/w1560/files/71e/7eb/2d9/71e7eb2d9cf04ecebdb45eeca9976dea.png)
Первое сокращение:![](https://habrastorage.org/r/w1560/files/3c6/fd9/5ce/3c6fd95ce14749b5bb97e47d1474cc53.png)
Далее нетрудно видеть что 114/57=2, 112/56=2, 110/55=2 и так далее, до 62/31=2
Второе сокращение:![](https://habrastorage.org/r/w1560/files/624/cfd/838/624cfd8386d4414f92a4b908ab704551.png)
Так, мы получили в числителе 27 двоек, которые попробуем сократить со знаменателем. Для начала вычеркнем все степени двойки из знаменателя и соответствующее число двоек из числителя. ( 2, 4, 8, 16 = 10 двоек, осталось 17 )
![](https://habrastorage.org/r/w1560/files/ae9/01d/810/ae901d8100804829bf2491e8335cb3e4.png)
В знаменателе есть еще 11 четных чисел, некоторые из них кратно четные. После всех сокращений в знаменателе не остается четных чисел, а в числителе останутся две двойки.
![](https://habrastorage.org/r/w1560/files/e67/f69/b9f/e67f69b9f5ec411f80d2aa464bac78d1.png)
Примемся теперь за тройки.
![](https://habrastorage.org/r/w1560/files/2e0/eb5/851/2e0eb58511db43658eaeed8ebc509fb2.png)
Ну и далее, сокращаем на 5, 7, 11, 17, 19, 23, 29
Остается:![](https://habrastorage.org/r/w1560/files/15a/63e/61a/15a63e61a9e6465c8ac3c43de4a75371.png)
что равно 23 544 809 717 399 465 172 377 319 715 292 496.
Расчет биномиальных коэффициентов на Си (С++)
Расчет биномиальных коэффициентов с использованием Фурье-преобразований
По их прочтению может сложиться мнение что это сложная и ресурсоемкая задача.
Прежде чем программировать что-то, попробуем разобраться что здесь к чему.
Факториальная формула:
![image](https://habrastorage.org/getpro/habr/post_images/01d/df4/164/01ddf4164554f2f65f67842dd8ea7dbf.png)
Раскроем ее:
![](https://habrastorage.org/files/672/a9c/bf6/672a9cbf660f4d688a2e256dbaebc44d.png)
Очевидно, что
![](https://habrastorage.org/files/8c2/4c5/dfb/8c24c5dfb1644635ba87c07cc47add69.png)
![](https://habrastorage.org/files/baf/7dc/cb0/baf7dccb02924c11ba7b41a5ab4c35d0.png)
А теперь попробуем посчитать например
![](https://habrastorage.org/files/ace/a73/910/acea739101d14d598d9e2ca61db10c53.png)
![](https://habrastorage.org/files/8a2/35c/973/8a235c9738d44e41b777490d17e3ec91.png)
Сразу видно, что 10, 9 и 8 взаимно сокращаются, приводя нас к
![](https://habrastorage.org/files/b9b/803/4bf/b9b8034bf76b475585f2725896f78ec0.png)
Поглядев внимательнее, видим что на этом сокращения не заканчиваются. 14 делится на 7, 12 на 6, 15 на 5, 16 на 4. Оставшиеся от 15 три делится на три, и оставшиеся от 7 2 делится на последнюю двойку. Произведя все эти сокращения мы избавляемся от знаменателя, получаем такое произведение:
![](https://habrastorage.org/files/e4c/a20/598/e4ca20598fd349289fea362fc4875a97.png)
Попробуем посчитать
![](https://habrastorage.org/files/00a/405/7b1/00a4057b1a99476999a6192f5dee0fa1.png)
![](https://habrastorage.org/files/71e/7eb/2d9/71e7eb2d9cf04ecebdb45eeca9976dea.png)
Первое сокращение:
![](https://habrastorage.org/files/3c6/fd9/5ce/3c6fd95ce14749b5bb97e47d1474cc53.png)
Далее нетрудно видеть что 114/57=2, 112/56=2, 110/55=2 и так далее, до 62/31=2
Второе сокращение:
![](https://habrastorage.org/files/624/cfd/838/624cfd8386d4414f92a4b908ab704551.png)
Так, мы получили в числителе 27 двоек, которые попробуем сократить со знаменателем. Для начала вычеркнем все степени двойки из знаменателя и соответствующее число двоек из числителя. ( 2, 4, 8, 16 = 10 двоек, осталось 17 )
![](https://habrastorage.org/files/ae9/01d/810/ae901d8100804829bf2491e8335cb3e4.png)
В знаменателе есть еще 11 четных чисел, некоторые из них кратно четные. После всех сокращений в знаменателе не остается четных чисел, а в числителе останутся две двойки.
![](https://habrastorage.org/files/e67/f69/b9f/e67f69b9f5ec411f80d2aa464bac78d1.png)
Примемся теперь за тройки.
![](https://habrastorage.org/files/2e0/eb5/851/2e0eb58511db43658eaeed8ebc509fb2.png)
Ну и далее, сокращаем на 5, 7, 11, 17, 19, 23, 29
Остается:
![](https://habrastorage.org/files/15a/63e/61a/15a63e61a9e6465c8ac3c43de4a75371.png)
что равно 23 544 809 717 399 465 172 377 319 715 292 496.