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

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

    Факториальная формула: 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.
    Метки:
    • –3
    • 3,4k
    • 8
    Поделиться публикацией
    Похожие публикации
    Комментарии 8
    • +13
      Ждем следующую статью «как умножать целые числа, используя сложение».
      • +2
        Умножать целые числа лучше всего используя преобразование Фурье (пруф). Ну и вообще, компьютеры умножают числа (как короткие, так и длинные), сводя это действие к сложению (так как ничего проще нет). Проблема сложна и многогранна.
      • +2
        Вот если бы все эти сокращения формализовать и вывести алгоритм в общем виде — это было бы ценно.
        А так… почти что капитанство.
        • +1
          Ну и в чем оригинальность? Такие операции выполняет любой первокурсник, узнав что такое биномиальный коеффициент… я не понял…
          • +1
            Первокурсник первокурснику рознь. Вы вот почитайте две предыдущие статьи, на которые ссылается автор, и поймете, что проблема не так уж проста. А еще попробуйте формализовать алгоритм, описанный автором.
            • 0
              Да, как раз прочитал. Обе интересные, а вторая ещё и оригинальная. Проблема известна и сложность её я не оспариваю. А вот как раз формализации проблемы у автора не видно.
            • +1
              Первокурсник? По-моему, сокращать дроби учат в начальной школе…
            • 0
              Всем спасибо! Недоумение и потребность разобраться в задаче побудила меня к написанию сей заметки. Автор первой статьи сетовал на переполнения и сложность вычислений для сколько-нибудь больших n. Автор второй вообще пугает общественность Фурье-преобразованиями. (Вот хоть убейте, но чтобы перемножить десяток-два не более чем трехзначных десятичных чисел как-то совсем не хочется использовать Фурье туда-сюда.) Оказалось что задача-то довольно элементарна и не слишком трудоемка даже для относительно больших n. Что я и проиллюстрировал. Формализация требует отдельного времени для проверки некоторых идей. Созреет, может быть отпишусь.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.