V2008n Jan 11 2016 at 23:38

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

1 min

4.2K

Algorithms*Entertaining tasksMathematics*

-3

Comments 8

myxo Jan 11 2016 at 23:55

Ждем следующую статью «как умножать целые числа, используя сложение».

MichaelBorisov Jan 12 2016 at 01:44

Умножать целые числа лучше всего используя преобразование Фурье (пруф). Ну и вообще, компьютеры умножают числа (как короткие, так и длинные), сводя это действие к сложению (так как ничего проще нет). Проблема сложна и многогранна.

dom1n1k Jan 12 2016 at 01:12

Вот если бы все эти сокращения формализовать и вывести алгоритм в общем виде — это было бы ценно.
А так… почти что капитанство.

rhaport Jan 12 2016 at 01:30

Ну и в чем оригинальность? Такие операции выполняет любой первокурсник, узнав что такое биномиальный коеффициент… я не понял…

MichaelBorisov Jan 12 2016 at 01:45

Первокурсник первокурснику рознь. Вы вот почитайте две предыдущие статьи, на которые ссылается автор, и поймете, что проблема не так уж проста. А еще попробуйте формализовать алгоритм, описанный автором.

rhaport Jan 12 2016 at 02:27

Да, как раз прочитал. Обе интересные, а вторая ещё и оригинальная. Проблема известна и сложность её я не оспариваю. А вот как раз формализации проблемы у автора не видно.

zagayevskiy Jan 12 2016 at 10:53

Первокурсник? По-моему, сокращать дроби учат в начальной школе…

V2008n Jan 12 2016 at 23:01

Всем спасибо! Недоумение и потребность разобраться в задаче побудила меня к написанию сей заметки. Автор первой статьи сетовал на переполнения и сложность вычислений для сколько-нибудь больших n. Автор второй вообще пугает общественность Фурье-преобразованиями. (Вот хоть убейте, но чтобы перемножить десяток-два не более чем трехзначных десятичных чисел как-то совсем не хочется использовать Фурье туда-сюда.) Оказалось что задача-то довольно элементарна и не слишком трудоемка даже для относительно больших n. Что я и проиллюстрировал. Формализация требует отдельного времени для проверки некоторых идей. Созреет, может быть отпишусь.