Расчет биномиальных коэффициентов на Си (С++)
Расчет биномиальных коэффициентов с использованием Фурье-преобразований
По их прочтению может сложиться мнение что это сложная и ресурсоемкая задача.
Прежде чем программировать что-то, попробуем разобраться что здесь к чему.
Факториальная формула:
Раскроем ее:
Очевидно, что
и тогда 
А теперь попробуем посчитать например
:
Сразу видно, что 10, 9 и 8 взаимно сокращаются, приводя нас к
Поглядев внимательнее, видим что на этом сокращения не заканчиваются. 14 делится на 7, 12 на 6, 15 на 5, 16 на 4. Оставшиеся от 15 три делится на три, и оставшиеся от 7 2 делится на последнюю двойку. Произведя все эти сокращения мы избавляемся от знаменателя, получаем такое произведение:
Попробуем посчитать
Первое сокращение:
Далее нетрудно видеть что 114/57=2, 112/56=2, 110/55=2 и так далее, до 62/31=2
Второе сокращение:
Так, мы получили в числителе 27 двоек, которые попробуем сократить со знаменателем. Для начала вычеркнем все степени двойки из знаменателя и соответствующее число двоек из числителя. ( 2, 4, 8, 16 = 10 двоек, осталось 17 )
В знаменателе есть еще 11 четных чисел, некоторые из них кратно четные. После всех сокращений в знаменателе не остается четных чисел, а в числителе останутся две двойки.
Примемся теперь за тройки.
Ну и далее, сокращаем на 5, 7, 11, 17, 19, 23, 29
Остается:
что равно 23 544 809 717 399 465 172 377 319 715 292 496.
Комментарии (8)
dom1n1k
12.01.2016 01:12+2Вот если бы все эти сокращения формализовать и вывести алгоритм в общем виде — это было бы ценно.
А так… почти что капитанство.
rhaport
12.01.2016 01:30+1Ну и в чем оригинальность? Такие операции выполняет любой первокурсник, узнав что такое биномиальный коеффициент… я не понял…
MichaelBorisov
12.01.2016 01:45+1Первокурсник первокурснику рознь. Вы вот почитайте две предыдущие статьи, на которые ссылается автор, и поймете, что проблема не так уж проста. А еще попробуйте формализовать алгоритм, описанный автором.
rhaport
12.01.2016 02:27Да, как раз прочитал. Обе интересные, а вторая ещё и оригинальная. Проблема известна и сложность её я не оспариваю. А вот как раз формализации проблемы у автора не видно.
V2008n
12.01.2016 23:01Всем спасибо! Недоумение и потребность разобраться в задаче побудила меня к написанию сей заметки. Автор первой статьи сетовал на переполнения и сложность вычислений для сколько-нибудь больших n. Автор второй вообще пугает общественность Фурье-преобразованиями. (Вот хоть убейте, но чтобы перемножить десяток-два не более чем трехзначных десятичных чисел как-то совсем не хочется использовать Фурье туда-сюда.) Оказалось что задача-то довольно элементарна и не слишком трудоемка даже для относительно больших n. Что я и проиллюстрировал. Формализация требует отдельного времени для проверки некоторых идей. Созреет, может быть отпишусь.
myxo
Ждем следующую статью «как умножать целые числа, используя сложение».
MichaelBorisov
Умножать целые числа лучше всего используя преобразование Фурье (пруф). Ну и вообще, компьютеры умножают числа (как короткие, так и длинные), сводя это действие к сложению (так как ничего проще нет). Проблема сложна и многогранна.