Произведение факториалов равно факториалу суммы

Произведение факториалов равно факториалу суммы

Факториал – так называют часто встречающуюся в практике функцию, определённую для целых неотрицательных чисел. Название функции происходит от английского математического термина factor – «сомножитель». Обозначается она n!. Знак факториала «!» был введён в1808 году во французском учебнике Хр. Крампа.

Для каждого целого положительного числа n функция n! равна произведению всех целых чисел от 1 до n.

Для удобства полагают по определению 0! = 1. О том, что нуль – факториал должен быть по определению равен единице, писал в 1656 году Дж. Валлис в «Арифметике бесконечных».

Функция n! растёт с увеличением n очень быстро. Так,

При преобразовании выражений, содержащих факториал, по лезно использовать равенство

(n + 1)! = (n + 1) • n! = (n + 1) • n • (n – 1)! (1)

Английский математик Дж. Стирлинг в 1970г. предложил очень удобную формулу для приближённого вычисления функции n!:

где е = 2,7182. — основание натуральных логарифмов.

Относительная ошибка при пользовании этой формулой очень невелика и быстро падает при увеличении числа n.

Способы решения выражений, содержащих факториал, рассмотрим на примерах.

Пример 2. Вычислить 10! 8!

Решение. Воспользуемся формулой (1):

Решение. Согласно формуле (1) имеем

Раскрыв скобки в произведении, получаем квадратное уравнение

n 2 + 5n — 84 = 0, корнями которого являются числа n = 7 и n = -12. Од нако факториал определен только для неотрицательных целых чисел, т. е. для всех целых чисел n ≥ 0. Поэтому число n = -12 не удовлетворя ет условию задачи. Итак, n = 7.

Пример 4. Найти хотя бы одну тройку натуральных чисел х, у и z, для которой верно равенство х! = y! • z!.

Решение. Из определения факториала натурального числа n сле дует, что

Положим в этом равенстве n + 1 = у! = х, где у — произвольное нату ральное число, получим

Теперь видим, что искомые тройки чисел можно задать в виде

где y- натуральное число, больше 1.

Например, справедливы равенства

Пример 5. Определить, сколькими нулями оканчивается деся тичная запись числа 32!.

Решение. Если десятичная запись числа Р = 32! оканчивается k нулями, то число Р можно представить в виде

где число q не делится на 10. Это означает, что разложение числа q на простые множители не содержит одновременно 2 и 5.

Поэтому, чтобы ответить на поставленный вопрос, попробуем опреде лить, с какими показателями в произведение 1 • 2 • 3 • 4 • . • 30 • 31 • 32 входят числа 2 и 5. Если число k — наименьший из найденных показателей, то число Р будет оканчиваться k нулями.

Читайте также:  Как создать иерархию папок и файлов

Итак, определим, сколько чисел среди натуральных чисел от 1 до 32 делятся на 2. Очевидно, что их количество равно 32/2 = 16. Затем определим, какое количество среди найденных 16 чисел делится на 4; затем — какое количество из них делится на 8 и т. д. В результате получим, что среди тридцати двух первых натуральных чисел на 2 делится 16 чисел,

из них на 4 делятся 32/4 = 8 чисел, из них на 8 делятся 32/8 = 4 числа, из них на 16 делятся 32/16 = 2 числа и, наконец, из них на 32 делятся 32/32=1, т.е. одно число. Понятно, что сумма полученных количеств:

16 + 8 + 4 + 2 + 1 = 31

равна показателю степени, с которым число 2 входит в 32!.

Аналогично определим, сколько чисел среди натуральных чисел от 1 до 32 делятся на 5, а из найденного количества на 10. Разделим 32 на 5.

Получим 32/5 = 6,4. Следовательно, среди натуральных чисел от 1 до 32

существует 6 чисел, которые делятся на 5. Из них на 25 делится одно

число, так как 32/25 = 1,28. В результате число 5 входит в число 32! с пока зателем, равным сумме 6+1 = 7.

Из полученных результатов следует, что 32!= 2 31 5 7 • т, где число т не делится ни на 2, ни на 5. Поэтому число 32! содержит множитель

10 7 и, значит, оканчивается на 7 нулей.

Итак, в данном реферате определено понятие факториала.

Приведена формула английского математика Дж Стирлинга для приближённого вычисления функции n!

При преобразовании выражений, содержащих факториал, по лезно использовать равенство

(n + 1)! = (n + 1) • n! = (n + 1) • n • (n – 1)!

На примерах подробно рассмотрены способы решения задач с факториалом.

Факториал используется в различных формулах в комбинаторике, в рядах и др.

Например, количество способов выстроить n школьников в одну шеренгу равняется n!.

Число n! равно, например, количеству способов, которыми можно n различных книг расставить на книжной полке, или, например, число 5! равно количеству способов, которыми пять человек можно рассадить на одной скамейке. Или, например, число 27! равно количеству способов, которыми наш класс из 27 учеников можно выстроить в ряд на уроке физкультуры.

По данному натуральном nn вычислите сумму 1!+2!+3!+…+n!. В решении этой задачи можно использовать только один цикл. Пользоваться математической библиотекой math в этой задаче запрещено.

Комментарии

n = int(input())
partial_factorial = 1
partial_sum = 0
for i in range(1, n + 1):
partial_factorial *= i
partial_sum += partial_factorial
print(partial_sum)

res = 1
sum = 0
n = int(input())
for i in range(1, n + 1):
res *= i
sum += res
print(sum)

Читайте также:  Как записать дроби в порядке возрастания

Добавить комментарий Отменить ответ

Пн Вт Ср Чт Пт Сб Вс

ЕГЭ на соточку для чайников

Прошу прощения, что так долго пропадал. Питошка вернулся, да еще и с группой в вконтакте, подписывайтесь. Помимо этого, на питошке откроется новая рубрика, в которой будут четкие объяснения всех заданий ЕГЭ и ОГЭ по информатике, внимательно прочитав которые, я уверен, вы улучшите свои баллы на экзамене 🙂

Понятие факториала известно всем. Это функция, вычисляющая произведение последовательных натуральных чисел от 1 до N включительно: N! = 1 * 2 * 3 *… * N. Факториал — быстрорастущая функция, уже для небольших значений N значение N! имеет много значащих цифр.

Попробуем реализовать эту функцию на языке программирования. Очевидно, нам понадобиться язык, поддерживающий длинную арифметику. Я воспользуюсь C#, но с таким же успехом можно взять Java или Python.

Итак, простейшая реализация (назовем ее наивной) получается прямо из определения факториала:

На моей машине эта реализация работает примерно 1,6 секунд для N=50 000.

Далее рассмотрим алгоритмы, которые работают намного быстрее наивной реализации.

Алгоритм вычисления деревом

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

Пусть нам нужно найти произведение последовательных чисел от L до R, обозначим его как P(L, R). Разделим интервал от L до R пополам и посчитаем P(L, R) как P(L, M) * P(M + 1, R), где M находится посередине между L и R, M = (L + R) / 2. Заметим, что множители будут примерно одинаковой длины. Аналогично разобьем P(L, M) и P(M + 1, R). Будем производить эту операцию, пока в каждом интервале останется не более двух множителей. Очевидно, что P(L, R) = L, если L и R равны, и P(L, R) = L * R, если L и R отличаются на единицу. Чтобы найти N! нужно посчитать P(2, N).

Посмотрим, как будет работать наш алгоритм для N=10, найдем P(2, 10):

P(2, 10)
P(2, 6) * P(7, 10)
( P(2, 4) * P(5, 6) ) * ( P(7, 8) * P(9, 10) )
( (P(2, 3) * P(4) ) * P(5, 6) ) * ( P(7, 8) * P(9, 10) )
( ( (2 * 3) * (4) ) * (5 * 6) ) * ( (7 * 8) * (9 * 10) )
( ( 6 * 4 ) * 30 ) * ( 56 * 90 )
( 24 * 30 ) * ( 5 040 )
720 * 5 040
3 628 800

Получается своеобразное дерево, где множители находятся в узлах, а результат получается в корне

Реализуем описанный алгоритм:

Для N=50 000 факториал вычисляется за 0,9 секунд, что почти вдвое быстрее, чем в наивной реализации.

Алгоритм вычисления факторизацией

Второй алгоритм быстрого вычисления использует разложение факториала на простые множители (факторизацию). Очевидно, что в разложении N! участвуют только простые множители от 2 до N. Попробуем посчитать, сколько раз простой множитель K содержится в N!, то есть узнаем степень множителя K в разложении. Каждый K-ый член произведения 1 * 2 * 3 *… * N увеличивает показатель на единицу, то есть показатель степени будет равен N / K. Но каждый K 2 -ый член увеличивает степень еще на единицу, то есть показатель становится N / K + N / K 2 . Аналогично для K 3 , K 4 и так далее. В итоге получим, что показатель степени при простом множителе K будет равен N / K + N / K 2 + N / K 3 + N / K 4 +…

Для наглядности посчитаем, сколько раз двойка содержится в 10! Двойку дает каждый второй множитель (2, 4, 6, 8 и 10), всего таких множителей 10 / 2 = 5. Каждый четвертый дает четверку (2 2 ), всего таких множителей 10 / 4 = 2 (4 и 8). Каждый восьмой дает восьмерку (2 3 ), такой множитель всего один 10 / 8 = 1 (8). Шестнадцать (2 4 ) и более уже не дает ни один множитель, значит, подсчет можно завершать. Суммируя, получим, что показатель степени при двойке в разложении 10! на простые множители будет равен 10 / 2 + 10 / 4 + 10 / 8 = 5 + 2 + 1 = 8.

Если действовать таким же образом, можно найти показатели при 3, 5 и 7 в разложении 10!, после чего остается только вычислить значение произведения:

10! = 2 8 * 3 4 * 5 2 * 7 1 = 3 628 800

Осталось найти простые числа от 2 до N, для этого можно использовать решето Эратосфена:

Эта реализация также тратит примерно 0,9 секунд на вычисление 50 000!

Как справедливо отметил pomme скорость вычисления факториала на 98% зависит от скорости умножения. Попробуем протестировать наши алгоритмы, реализовав их на C++ с использованием библиотеки GMP. Результаты тестирования приведены ниже, по ним получается что алгоритм умножения в C# имеет довольно странную асимптотику, поэтому оптимизация дает относительно небольшой выигрыш в C# и огромный в C++ с GMP. Однако этому вопросу вероятно стоит посвятить отдельную статью.

Все алгоритмы тестировались для N равном 1 000, 2 000, 5 000, 10 000, 20 000, 50 000 и 100 000 десятью итерациями. В таблице указано среднее значение времени работы в миллисекундах.

График с линейной шкалой

График с логарифмической шкалой

Идеи и алгоритмы из комментариев

Хабражители предложили немало интересных идей и алгоритмов в ответ на мою статью, здесь я оставлю ссылки на лучшие из них

Исходные коды реализованных алгоритмов приведены под спойлерами

Ссылка на основную публикацию
Проверить принадлежит ли прямая плоскости
Предлагаю вам воспользоваться онлайн калькулятором чтобы найти уравнение плоскости. Воспользовавшись онлайн калькулятором, вы получите детальное пошаговое решение вашей задачи, которое...
Пример анализа текста публицистического стиля речи
(1) “Всё, о Люцилий, не наше, а чужое, только время наше собственность. (2) Природа предоставила в наше владение только эту...
Принцип работы пьезоэлемента в зажигалке
Многие, кто пользуются газовыми плитами, знают про такую удобную в хозяйстве вещь. Пьезозажигалка, висящая рядом с плитой, заменяет сотни коробков...
Программа мрр что это такое
Цель: изучить возможности программы МРР Скачать: Вложение Размер urok_11.zinaida_anatolevna.pptx 2.54 МБ Предварительный просмотр: Подписи к слайдам: Изучение возможностей МРР Цель...
Adblock detector