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

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

Раскроем ее:

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

А теперь попробуем посчитать например :



Сразу видно, что 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)


  1. myxo
    11.01.2016 23:55
    +13

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


    1. MichaelBorisov
      12.01.2016 01:44
      +2

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


  1. dom1n1k
    12.01.2016 01:12
    +2

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


  1. rhaport
    12.01.2016 01:30
    +1

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


    1. MichaelBorisov
      12.01.2016 01:45
      +1

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


      1. rhaport
        12.01.2016 02:27

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


    1. zagayevskiy
      12.01.2016 10:53
      +1

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


  1. V2008n
    12.01.2016 23:01

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