Пользователь
0,0
рейтинг
11 января в 23:38

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

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

Факториальная формула: 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.
@V2008n
карма
23,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (8)

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

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