Факториал числа n – это произведение чисел от 1 до n. Определён только для целых неотрицательных чисел.
Формула факториала:
n! = 1 * 2 * … * n
Математическая формула представлена восклицательным знаком «!». Термин был введен в 1800 году, а обозначение появилось только в 1808. В формуле нужно умножить все целые числа от 1 до значения самого числа, стоящего под знаком факториала.
Это очень просто, вот пример:
7! = 1 * … * 7 = 5040.
Факторизация — разложение функции на множители.
Таблица факториалов
Свойства факториалов
Рекуррентная формула
Комбинаторная интерпретация
Функция n может интерпретироваться как количество перестановок. К примеру, для 3-х элементов есть 3! = 6 перестановки.
Формула Стирлинга
Позволяет не перемножать большие числа. Обычно необходим только главный член:
Можно ли вычислить 0,5 или -3,217? Нет, нельзя. Но можно использовать нечто под названием «Гамма-функция», что намного сложнее.
Расчет по предыдущему значению
Функцию легко вычислить из предыдущего значения:
- 3! = 3 × 2! = 6;
- 41160 = 5! +8! + 6!
А как вычислить факториал нуля? Если вернуться к определению, то видно, что применять его в случае «0» нет смысла. Положительных чисел до 0 нет, поэтому 0 x 0 = 0.
Однако было решено, что в случае 0 результат будет равен 1.
Некоторые очень большие значения
Онлайн калькулятор поможет сделать вычисление – всего лишь надо найти знак, похожий на «x!» или «n!». Нужно обратить внимание, что браузеры могут испытывать затруднения при попытке отобразить более крупные числа и может произойти сбой.
Некоторые браузеры могут не позволять копировать, поэтому необходимо будет загрузить большие результаты в виде текстового файла.
Примеры вычисления факториалов больших чисел:
- 70! приблизительно 1 19785716669969869891796072783721 x 10100, что немного больше, чем «гуголь» (1 и 100 нулей);
- 100! это примерно 9 33262154444944152681699238856 x 101576 x 10157;
- 200! это примерно 7 88657867867364479050355236321393 x 103743.
Как найти функцию в Паскаль? Вычисление легко реализуется на разных языках программирования. Можно выбрать два метода: итеративный, то есть он создает цикл, в котором временная переменная умножается на каждое натуральное число от 1 до n, или рекурсивный, в котором функция вызывает себя до достижения базового варианта 0! = 1.
Программа на языке Паскаль:
На языке Си вычисления делаются с помощью рекурсивной функции. Следует заметить, что если начать вычислять факториал отрицательного числа в неаккуратно написанной функции, то это приведет к зацикливанию.
Факториал дроби (½) — это половина квадратного корня pi = (½)√π.
Примеры задач с решениями
Задание 1
Задание 2
Использование факториалов
Математика и многие ее области используют функцию. В комбинаторике функция была введена именно для расчета перестановки. Также понятие тесно связано с биномом ньютона (формула бинома Ньютона необходима для разложения степени (x + y) n в многочлен).
Источник: https://nauka.club/matematika/algebra/faktorial.html
Факториал числа
Факториал натурального числа n пишется как n! и считается как произведение всех натуральных чисел от 1 до n (включительно).
- Для n>0:
- n! = 1 * 2 * 3 * 4 … * n
- Для n=0:
- 0! = 1
Формула для определения факториала
- Примеры:
- 1! = 1
- 2! = 1*2 = 2
- 3! = 1*2*3 = 6
- 4! = 1*2*3*4 = 24
- 5! = 1*2*3*4*5 = 120
Рекуррентная формула факториала
Примеры:
5! = 5*(5-1)! = 5×4! = 5×24 = 120
7! = 7*(7-1)! = 7×6! = 5×720 = 5040
Формула Стирлинга
Используется для приблизительного нахождения факториала.
Пример:
Таблица факториалов
Число n | Факториал n! |
0 | 1 |
1 | 1 |
2 | 2 |
3 | 6 |
4 | 24 |
5 | 120 |
6 | 720 |
7 | 5040 |
8 | 40320 |
9 | 362880 |
10 | 3628800 |
11 | 3,991680×107 |
12 | 4,790016×108 |
13 | 6,227021×109 |
14 | 8,717829×1010 |
15 | 1,307674×1012 |
16 | 2,092279×1013 |
17 | 3,556874×1014 |
18 | 6,402374×1015 |
19 | 1,216451×1017 |
20 | 2,432902×1018 |
microexcel.ru
(1
Источник: https://MicroExcel.ru/faktorial/
Алгоритмы быстрого вычисления факториала
Понятие факториала известно всем. Это функция, вычисляющая произведение последовательных натуральных чисел от 1 до N включительно: N! = 1 * 2 * 3 *… * N.
Факториал — быстрорастущая функция, уже для небольших значений N значение N! имеет много значащих цифр. Попробуем реализовать эту функцию на языке программирования. Очевидно, нам понадобиться язык, поддерживающий длинную арифметику.
Я воспользуюсь C#, но с таким же успехом можно взять Java или Python.
Наивный алгоритм
Итак, простейшая реализация (назовем ее наивной) получается прямо из определения факториала: static BigInteger FactNaive(int n)
{
BigInteger r = 1;
for (int i = 2; i r)
return 1;
if (l == r)
return l;
if (r — l == 1)
return (BigInteger)l * r;
int m = (l + r) / 2;
return ProdTree(l, m) * ProdTree(m + 1, r);
}
static BigInteger FactTree(int n)
{
if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; return ProdTree(2, n); } Для N=50 000 факториал вычисляется за 0,9 секунд, что почти вдвое быстрее, чем в наивной реализации.
Алгоритм вычисления факторизацией
Второй алгоритм быстрого вычисления использует разложение факториала на простые множители (факторизацию). Очевидно, что в разложении N! участвуют только простые множители от 2 до N. Попробуем посчитать, сколько раз простой множитель K содержится в N!, то есть узнаем степень множителя K в разложении.
Каждый K-ый член произведения 1 * 2 * 3 *… * N увеличивает показатель на единицу, то есть показатель степени будет равен N / K. Но каждый K2-ый член увеличивает степень еще на единицу, то есть показатель становится N / K + N / K2. Аналогично для K3, K4 и так далее.
В итоге получим, что показатель степени при простом множителе K будет равен N / K + N / K2 + N / K3 + N / K4 +…
Для наглядности посчитаем, сколько раз двойка содержится в 10! Двойку дает каждый второй множитель (2, 4, 6, 8 и 10), всего таких множителей 10 / 2 = 5. Каждый четвертый дает четверку (22), всего таких множителей 10 / 4 = 2 (4 и 8).
Каждый восьмой дает восьмерку (23), такой множитель всего один 10 / 8 = 1 (8). Шестнадцать (24) и более уже не дает ни один множитель, значит, подсчет можно завершать.
Суммируя, получим, что показатель степени при двойке в разложении 10! на простые множители будет равен 10 / 2 + 10 / 4 + 10 / 8 = 5 + 2 + 1 = 8.
Если действовать таким же образом, можно найти показатели при 3, 5 и 7 в разложении 10!, после чего остается только вычислить значение произведения:
10! = 28 * 34 * 52 * 71 = 3 628 800
Осталось найти простые числа от 2 до N, для этого можно использовать решето Эратосфена:
static BigInteger FactFactor(int n)
{
if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; bool[] u = new bool[n + 1]; // маркеры для решета Эратосфена List p = new List(); // множители и их показатели степеней for (int i = 2; i 0) { c += k; k /= i; } // запоминаем множитель и его показатель степени p.Add(new Tuple(i, c)); // просеиваем составные числа через решето int j = 2; while (i * j = 0; —i) r *= BigInteger.Pow(p[i].Item1, p[i].Item2); return r; } Эта реализация также тратит примерно 0,9 секунд на вычисление 50 000!
Библиотека GMP
Как справедливо отметил pomme скорость вычисления факториала на 98% зависит от скорости умножения. Попробуем протестировать наши алгоритмы, реализовав их на C++ с использованием библиотеки GMP.
Результаты тестирования приведены ниже, по ним получается что алгоритм умножения в C# имеет довольно странную асимптотику, поэтому оптимизация дает относительно небольшой выигрыш в C# и огромный в C++ с GMP.
Однако этому вопросу вероятно стоит посвятить отдельную статью.
Сравнение производительности
Все алгоритмы тестировались для N равном 1 000, 2 000, 5 000, 10 000, 20 000, 50 000 и 100 000 десятью итерациями. В таблице указано среднее значение времени работы в миллисекундах. График с линейной шкалой
График с логарифмической шкалой
Идеи и алгоритмы из комментариев
Хабражители предложили немало интересных идей и алгоритмов в ответ на мою статью, здесь я оставлю ссылки на лучшие из них
lany распараллелил дерево на Java с помощью Stream API и получил ускорение в 18 раз
Mrrl предложил оптимизацию факторизации на 15-20% PsyHaSTe предложил улучшение наивной реализации Krypt предложил распараллеленную версию на C# SemenovVV предложил реализацию на Go pomme предложил использовать GMP ShashkovS предложил быстрый алгоритм на Python
Исходные коды
Исходные коды реализованных алгоритмов приведены под спойлерамиC#using System;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Collections.Generic;
using System.Collections.Specialized;
namespace BigInt
{
class Program
{
static BigInteger FactNaive(int n)
{
BigInteger r = 1;
for (int i = 2; i r)
return 1;
if (l == r)
return l;
if (r — l == 1)
return (BigInteger)l * r;
int m = (l + r) / 2;
return ProdTree(l, m) * ProdTree(m + 1, r);
}
static BigInteger FactTree(int n)
{
if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; return ProdTree(2, n); } static BigInteger FactFactor(int n) { if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; bool[] u = new bool[n + 1]; List p = new List(); for (int i = 2; i 0) { c += k; k /= i; } p.Add(new Tuple(i, c)); int j = 2; while (i * j = 0; —i) r *= BigInteger.Pow(p[i].Item1, p[i].Item2); return r; } static void Main(string[] args) { int n; int t; Console.Write(«n = «); n = Convert.ToInt32(Console.ReadLine()); t = Environment.TickCount; BigInteger fn = FactNaive(n); Console.WriteLine(«Naive time: {0} ms», Environment.TickCount — t); t = Environment.TickCount; BigInteger ft = FactTree(n); Console.WriteLine(«Tree time: {0} ms», Environment.TickCount — t); t = Environment.TickCount; BigInteger ff = FactFactor(n); Console.WriteLine(«Factor time: {0} ms», Environment.TickCount — t); Console.WriteLine(«Check: {0}», fn == ft && ft == ff ? «ok» : «fail»); } } } C++ с GMP#include
#include
#include
#include
#include
using namespace std;
mpz_class FactNaive(int n)
{
mpz_class r = 1;
for (int i = 2; i r)
return 1;
if (l == r)
return l;
if (r — l == 1)
return (mpz_class)r * l;
int m = (l + r) / 2;
return ProdTree(l, m) * ProdTree(m + 1, r);
}
mpz_class FactTree(int n)
{
if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; return ProdTree(2, n); } mpz_class FactFactor(int n) { if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; vector u(n + 1, false); vector p; for (int i = 2; i 0) { c += k; k /= i; } p.push_back(make_pair(i, c)); int j = 2; while (i * j = 0; —i) { mpz_class w; mpz_pow_ui(w.get_mpz_t(), mpz_class(p[i].first).get_mpz_t(), p[i].second); r *= w; } return r; } mpz_class FactNative(int n) { mpz_class r; mpz_fac_ui(r.get_mpz_t(), n); return r; } int main() { int n; unsigned int t; cout > n;
t = clock();
mpz_class fn = FactNaive(n);
cout
Источник: https://habr.com/post/255761/
Факториал
Факториалом в математике называют произведение всех натуральных чисел, включая указанное число. Обозначается факториал восклицательным знаком после числа, например 4!. Так что, если вы встретили восклицательный знак в математике, это совсем не означает «Вау! Число!». Это просто факториал.
Из священных математических текстов нужно выучить одну фразу «Факториал нуля равен единице». Почему факториал нуля равен единице? Читайте по ссылке. Точные значения факториалов чисел до 50 приведены на рисунке.
Факториал нуля равен единице фото. Факториал 1, 2, 3, 4, 5. Посчитать факториал, нахождение факториала. Значение факториала натурального числа. Математика для блондинок.» id=»BLOGGER_PHOTO_ID_5517996820177294226″ src=»http://4.bp.blogspot.com/_JwbCNIxiifg/TJPc31JnE5I/AAAAAAAAARU/aFyhd8WlX_M/s400/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB++%D1%82%D0%BE%D1%87%D0%BD%D1%8B%D0%B5+%D0%B4%D0%BE+50+%D0%B1%D0%BB%D0%BE%D0%BD%D0%B4%D0%B8%D0%BD%D0%BA%D0%B8.GIF»>
На картинке показано, как считать факториал для натурального числа 7. Вычисление факториала других чисел производится точно так же: все числа от одного до указанного перед восклицательным знаком перемножаются между собой.
Факториал 1 (единицы) равен единице.
1! = 1 Факториал 2 (двух) равен двум.2! = 1 · 2 = 2 Факториал 3 (трех) равен шести.3! = 1 · 2 · 3 = 6 Факториал 4 (четырех) равняется двадцати четырем.4! = 1 · 2 · 3 · 4 = 24 Факториал 5 равен ста двадцати.5! = 1 · 2 · 3 · 4 · 5 = 120 Ну и так далее.
В общем виде формулу для нахождения факториала можно записать так:
n! = 1 · 2 · 3 · 4 · … · (n — 2) · (n — 1) · n
Таблица факториалов до 255 представлена на отдельной странице.
Кстати, если вы будете ехать за рулем автомобиля и увидите восклицательный знак в треугольнике на белом или желтом фоне — это не урок математики с факториалами, это дорожный знак «Внимание!».
Здесь не нужно ничего друг на дружку умножать. Нужно отложить в сторонку косметичку, перестать болтать по мобильному телефону и крепче держаться за руль автомобиля. Внимательно смотрите не по сторонам, а на дорогу. Впереди могут быть неприятные сюрпризы. Чтобы неприятные сюрпризы на дороге не превращались в неприятные ситуации, их обозначают этим дорожным знаком.
Найти решение:
Чему равен 50 факториал — последняя строчка таблицы факториалов на картинке дает точный ответ на этот вопрос. Приблизительное значение (более короткая запись числа) можно посмотреть на отдельной странице «Таблица факториалов до 255».
Действие факториала — математически действие факториала представляет собой последовательность умножения натуральных чисел между собой. Такой себе математический междусобойчик во множестве натуральных чисел.
Факториал 15 равен — ответ можно посмотреть в таблице факториалов на картинке.
Как считать факториал — здесь в тексте написано, как считается факториал, а на картинке есть пример факториала семи (7!).
Факториал от нуля — равен единице, как бы странно это не выглядело. Но, таковы математические догмы. На картинке большими синими цифрами написано.
Как счетать факториал — вообще-то, у меня написано как «счИтать» факториал. Мне кажется, помимо факториалов, вам не помешает изучить курс «Русский язык для блондинок». А то не красиво будет смотреться фраза «Я табе лублу!» краской на асфальте.
Математика для блондинок факториал — это именно та страница, которую вы ищете. Если вы мне не верите, посмотрите вверху страницы, там написано «Математика для блондинок» и адрес этого сайта именно www.webstaratel.ru
Источник: http://www.webstaratel.ru/2010/09/blog-post_12.html
Онлайн-школа программирования в 1С
Войдите на сайт как ученик
Войдите как ученик, чтобы получить доступ к материалам школы
Упражнения по внутреннему языку программирования 1С 8.3: пузырёк и факториал
Автор упражнений и преподаватель школы: Владимир Милькин
Упражнение №3. Напишите программу, которая создаёт массив из 100 случайных чисел в диапазоне от 0 до 1000 (включительно). Затем находит и выводит:
- Минимальный элемент в массиве (самый маленький из всех).
- Максимальный элемент в массиве (самый большой из всех).
- Среднее арифметическое всех чисел массива (сумма всех элементов, разделенная на количество элементов).
- Подсказки:
- Случайные числа генерируются так:
ГСЧ = Новый ГенераторСлучайныхЧисел; // создали генератор случайных чисел СлучайноеЧисло = ГСЧ.СлучайноеЧисло(0, 1000); // сгенерировали случайное число, указав диапазон |
Используйте справочник по языку 1С при выполнении упражнения — ссылка.
Вы читаете ознакомительную версию урока, полноценные уроки находятся здесь.
Общий план
Создать массив из 100 случайных чисел от 0 до 1000.
Пробежаться по каждому из этих чисел и выбрать самое маленькое (минимум) и самое большое (максимум). Заодно подсчитать сумму всех чисел.
Разделить сумму чисел на их количество и получить среднее арифметическое.
Вывести пользователю минимальный и максимальные элементы, среднее арифметическое.
Подсказка
объявить генератор случайных чисел ГСЧ объявить пустой массив Числа цикл от 1 до 100: { генерировать случайное число (при помощи ГСЧ) от 0 до 1000 добавить это число в массив Числа } Минимум = Числа[0] Максимум = Числа[0] Сумма = 0 цикл для А от 0 до (количество элементов массива Числа) — 1: { ТекущийЭлемент = Числа[А] если ТекущийЭлемент меньше Минимум, тогда Минимум = ТекущийЭлемент если ТекущийЭлемент больше Максимум, тогда Максимум = ТекущийЭлемент Сумма = Сумма + ТекущийЭлемент } СреднееЗначение = Сумма / (количество элементов Числа) вывести Минимум, Максимум и СреднееЗначение |
Эталонное решение. Сначала пишем код сами, проверяем на компьютере (как и все примеры программ из уроков), только потом сверяемся
Войдите на сайт как ученик
Авторизуйтесь, чтобы получить доступ ко всем материалам школы
Источник: https://helpme1c.ru/uprazhneniya-po-vnutrennemu-yazyku-programmirovaniya-1s-8-3-chast-2
Как найти факториал числа
Факториал числа – математическое понятие, применимое только для целых неотрицательных чисел. Эта величина представляет собой произведение всех натуральных числе от 1 до основания факториала. Понятие находит применение в комбинаторике, теории чисел и функциональном анализе. Чтобы найти факториал числа, необходимо вычислить произведение всех чисел, в промежутке от 1 до заданного числа. Общая формула выглядит таким образом:
n! = 1*2*…*n, где n – любое целое неотрицательное число. Факториал принято обозначать восклицательным знаком.
Основные свойства факториалов:• 0! = 1;• n! = n*(n-1)! ;• n!^2 ≥ n^n ≥ n! ≥ n.
Второе свойство факториала называется рекурсией, а сам факториал – элементарной рекурсивной функцией. Рекурсивные функции часто применяются в теории алгоритмов и в написании компьютерных программ, поскольку многие алгоритмы и функции программирования имеют рекурсивную структуру.
Определить факториал большого числа можно по формуле Стирлинга, которая дает, однако, приближенное равенство, но с маленькой погрешностью. Полная формула выглядит следующим образом:n! = (n/e)^n*√(2*π*n)*(1 + 1/(12*n) + 1/(288*n^2) + …)ln (n!) = (n + 1/2)*ln n – n + ln √(2*π),
где e – основание натурального логарифма, число Эйлера, численное значение которого принято приблизительно равным 2,71828…; π – математическая константа, значение которой принято равным 3,14.
Широко распространено использование формулы Стирлинга в виде:
n! ≈ √(2*π*n)*(n/e)^n.
Существуют различные обобщения понятия факториала, например, двойной, m-кратный, убывающий, возрастающий, праймориал, суперфакториал. Двойной факториал обозначается !! и равен произведению всех натуральных чисел на интервале от 1 до самого числа, имеющих ту же четность, например, 6!! = 2*4*6. m-кратный факториал – общий случай двойного факториала для любого целого неотрицательного числа m:для n = mk – r справедливо n!…!! = ∏ (m*I — r), где r – множество целых чисел от 0 до m-1, I – принадлежит множеству чисел от 1 до k. Убывающий факториал записывается следующим образом:(n)_k = n!/(n — k)!Возрастающий:
(n)^k = (n + k -1)!/(n — 1)!
Праймориал числа равен произведению простых чисел меньше самого числа и обозначается #, например:12# = 2*3*5*7*11, очевидно, что 13# = 11# = 12#.Суперфакториал равен произведению факториалов чисел на интервале от 1 до исходного числа, т.е.:
sf(n) = 1!*2!*3*…(n — 1)!*n!, например, sf(3) = 1!*2!*3! = 1*1*2*1*2*3 = 12.
- Войти на сайт
- или
Источник: https://www.kakprosto.ru/kak-94780-kak-nayti-faktorial-chisla
Сколько нулей в конце факториала 100?
Факториал одной сотни записывается как 100! Это произведение всех натуральных чисел до ста включительно. Иногда запись факториала имеет такой вид:
100 х 99 х 98 х 97 х … х 4 х 3 х 2 х 1
Для ответа на вопрос задачи вам не обязательно находить результат умножения. От вас ждут, чтобы вы лишь определили число нулей в конце произведения, не зная, каким именно оно будет. Для решения этой задачи потребуется сформулировать несколько правил. Одно из них вы уже знаете. Взгляните на следующее выражение.
387 000 х 12 900 = 5 027 131 727
Вам не кажется, что здесь есть что-то забавное? Ведь при перемножении двух круглых чисел, то есть тех, которые оканчиваются на нули, невозможно получить некруглое число.
Это нарушило бы закон сохранения конечных нулей (закон, который я только что вывел, но, тем не менее, он является верным). Произведение всегда унаследует нулевые окончания своих составляющих.
Вот несколько верных примеров этого:
- 10 х 10 = 100
7 х 20 = 140 - 30 х 400 = 12 000
Из сомножителей факториала 100 десять заканчиваются на ноль: 10, 20, 30, 40, 50, 60, 70, 80, 90 и 100 (заканчивается на два 0). Это дает уже как минимум одиннадцать конечных нулей, которые 100! обязательно унаследует.
Предупреждение: следование только этому правилу иногда побуждает некоторых кандидатов в своем ответе заявить, что в конце факториала 100 стоят одиннадцать нулей. Такой ответ является неверным.
Иногда можно умножить два числа, не заканчивающихся на ноль, и получить произведение, имеющее в конце один или несколько нулей. Вот несколько примеров этого рода:
- 2 х 5 = 10
5 х 8 = 40
6 х 15 = 90 - 8 х 125 = 1000
Все, кроме последней пары, входят в сотню составляющих факториала 100. Поэтому ваша работа не закончилась. Теперь мы подходим к закону «сосисок и булочек».
Представьте себе ситуацию, когда на пикник одни люди приносят сосиски (в упаковках по десять штук), другие — булочки (упакованные по восемь штук), а некоторые — и то, и другое.
Есть единственный способ, позволяющий определить, сколько хотдогов из этих продуктов можно приготовить. Сосчитайте сосиски, сосчитайте булочки и выберите меньшее число из двух.
Тот же самый закон следует использовать и отвечая на наш вопрос. Для этого надо заменить «сосиски» и «булочки» на «сомножители на 2» и «сомножители на 5».
В каждом из приведенных выше уравнений число, которое делится на 2, умножается на число, которое делится на 5. Сомножители на 2 и на 5 при их перемножении «совместно» дают идеальную десятку, что добавляет еще один ноль к общему произведению. Посмотрите на последний пример, где в конце, можно сказать, из воздуха возникает три нуля.
- 8 х 125 = (2 х 2 х 2) х (5 х 5 х 5)
= (2 х 5) х (2 х 5) х (2 х 5)
= 10 х 10 х 10 - = 1000
Поэтому надо составить пары из двоек и пятерок. Возьмем, к примеру, число, равное 692 978 456 718 000 000.
- Оно оканчивается на шесть нулей. Это означает, что его можно записать следующим образом:
- 692 978 456 718 х 10 х 10 х 10 х 10 х 10 х 10,
- или так:
- 692 978 456 718 х (2 х 5) х (2 х 5) х (2 х 5) х (2 х 5) х (2 х 5) х (2 х 5).
Первая часть, 692 978 456 718, не делится на 10. В ином случае она бы оканчивалась на ноль, и можно было бы эту часть уменьшить еще в 10 раз. К тому же здесь есть шесть сомножителей, равных 10 (или 2 х 5), что соответствует шести нулям в конце числа 692 978 456 718 000 000. Ну как, убедительно?
Это дает нам надежную систему для определения количества нулей в конце любого большого числа. Выделите сомножители 2 и 5. Составьте из них пары и перемножьте их: (2 х 5) х (2 х 5) х (2 х 5) х … Число пар из двоек и пятерок равно количеству нулей в конце. Закройте глаза на все, что осталось слева.
В целом слева у вас останется двойка или пятерка, для которых не нашлось пары. Обычно это двойки. Более того, когда вы имеете дело с факториалом, это всегда двойки.
(В факториалах имеется больше четных множителей, чем множителей, которые делятся на 5.) Поэтому узким местом является число пятерок.
Из этого следует, что вопрос можно сформулировать по-другому: сколько раз 100! можно разделить без остатка на 5?
Эту арифметическую операцию можно легко проделать даже в голове. В диапазоне от 1 до 100 есть 20 чисел, которые делятся на пятерку: 5, 10, 15, …, 95, 100.
Обратите внимание, что 25 дает 2 множителя, равные 5 (25 = 5 х 5), и к тому же в этой группе есть еще три числа, в состав которых входит 25: 50, 75 и 100. В совокупности это добавляет еще четыре пятерки, а всего их 24.
24 множителя на пять дают 24 пары с равным числом двоек, в результате чего получается 24 множителя на 10 (оставляя слева еще множество двоек, для которых не оказалось пары). Таким образом, в конце 100! будет 24 нуля.
- Если вам любопытно узнать точный ответ, то значение факториала 100 равно:
- 93 326 215 443 944 152 681 699 238 856 266 700 490 715 968 264 381 621 468 592 963 895 217 599 993 229 915 608 941 463 976 156 518 286 253 697 920 827 223 758 251 185 210 916 864 000 000 000 000 000 000 000 000.
Источник: https://tproger.ru/problems/how-many-zeros-at-the-end-of-the-factorial-of-100/
Факториал
Здравствуйте, дорогие друзья! Спасибо, что читаете мой канал!
Вы когда-нибудь слышали о факториале? Сегодня расскажу Вам, что это такое и для чего он нужен.
Факториал — это математическая функция, применяемая к неотрицательным целым числам, равная произведению всех натуральных чисел от 1 до числа, для которого она вычисляется (о целых, натуральных и других числах можно почитать здесь).
Обозначается она очень просто: n! (произносится «эн факториал») — да, просто приписывается восклицательный знак к числу ? Чтобы было легче понять определение факториала, сразу приведу пример: 5!=1х2х3х4х5=120.
То есть, чтобы найти факториал числа, нужно просто поочереди перемножить все натуральные числа от единицы до самого числа включительно. Математически определение факториала выглядит так:
Определение факториала
Также из определения факториала следует следующая формула:
Факториал предыдущего числа
То есть, зная факториал числа, можно найти факториал предыдущего числа путём деления значения факториала на само число. Из этой же формулы следует, что 0!=1 при n=1. Хотя не все математики считают 0 натуральным числом (подробнее читайте в этой статье), факториал для него можно вычислить.
Вы спросите: для чего же он нужен, этот факториал? Давайте теперь расскажу Вам о его применении.
Факториал очень активно используется в различных разделах математики, особенно там, где заходит речь о различных вариантах, перестановках, комбинациях и т. п. Он применяется в комбинаторике, теории чисел, математическом анализе и других областях.
Очень хорошо становится понятным смысл факториала при изучении и применении вышеозвученной комбинаторики. В ней факториал натурального числа n интерпретируется как количество перестановок множества из n элементов.
Что это означает на практике? Разберём задачу.
В гостиной стоит стол с четырьмя стульями вокруг. В комнату заходит четыре человека. Сколько существует вариантов для рассаживания вокруг стола всех четырёх человек?
Как раз для решения подобных задач требуется факториал. Зная его определение, задача решается в одно действие: 4!=1х2х3х4=24. То есть, ответ: 24 варианта (комбинации). Для такого небольшого числа, как 4, можно проверить правильность решения. Обозначим людей первыми буквами латинского алфавита: A, B, C, D. Тогда все возможные комбинации из них будут выглядеть так:
Комбинации из четырёх объектов подтверждают, что 4!=24
В комбинаторике множество подобных задач и в них повсеместно используется факториал.
Как можно заметить, факториал — очень быстрорастущая функция: если 3!=6, то, например, 10!=3 628 800. Факториал растёт гораздо быстрее, чем, например, показательная или степенная функции. Об этих двух обязательно в будущем ещё Вам расскажу.
В среде математиков существует одна занимательная задачка. Попробуйте её решить сами. Ответ будет в конце следующей статьи. Вот сама задача: дан отрезок времени 10! секунд; сколько это будет в каких-нибудь более удобных, крупных единицах времени?
Надеюсь, теперь Вы хорошо знаете, что такое факториал числа и где он может применяться.
Спасибо, что прочитали статью! Буду благодарен за комментарии, лайки, подписки.
Предыдущая статья
Следующая статья
Источник: https://zen.yandex.ru/media/math4u/faktorial-5ca35fb52aee0400b3d1d202
Расчет больших факториалов (до 100000 !!!!!)
← →Serega_M (2002-02-14 21:58) [0]
Уважаемые мастера!!! Помогите решить проблему с расчетом факториалов больших чисел (до 100 000 может и более). При использовании типа EXTENDED, максимум что моге посчитать это факториал 1750.
Window-ый калькулятор считает!!!. Можно-ли это сделать в Дельфях. Если приведете кусочек кода буда очень признетелен. Если можете мыльте. Краткая математическая справка: Факториал числа N вычисляется по следующей формуле 1*2*3*…(N-1)*N, факториал 0 равен 1.
Заранее спасибо.С уважением Serega.
← →Kurt (2002-02-15 00:27) [1]
Используй «длинную арифметику» — число представляется масивом своих цыфр. Имееш большой масив иожеш считать любой фаеториал.
← →MBo (2002-02-15 06:52) [2]
поищи FGINT
← →Serega_M (2002-02-15 10:29) [3]
для Kurt`а ______ Если можно -поподробней !!! Как использовать массив цифр и производить вычисление? Писал процедуру расчета факториала для больших чисел. Числа представлял в виде текста или массива PCHAR.
Перемножение и сложение происходило между отдельными цифрами. По-типу умножения в 1-ом классе (столбиком). Расчет факториала 20000 занял часов 6.
Очень долго не находите ? для МВо ________ что такое FGINT? Функция API или Делфей?
← →fag2000@ok.ru (2002-02-15 10:32) [4]
А сколько цифр было получено? Может есть смысл хранить мантису и показатель степени?
← →Вячеслав (2002-02-15 10:41) [5]
Воспользуйся формулой Стирлинга.
← →Вячеслав (2002-02-15 10:47) [6]
P.S. Посмотри тут. http://algolist.by.ru/maths/count_fast/factorial.html
← →Alx2 (2002-02-15 10:53) [7]
Вот приближение десятичного логарифма факториала:
#include
double log10factorial(n)
double n;
{
double t1;
double t15;
double t17;
double t2;
double t23;
double t25;
double t3;
{
t1 = n*n;
t2 = t1*n;
t3 = t1*t1;
t15 = log(902961561600.0*t3*t2+75246796800.0*t3*t1+3135283200.0*t3*n
-2421135360.0*t3-207204480.
0*t2+707957280.0*t1+62961828.0*n-534703531.0);
t17 = log(n);
t23 = log(0.3141592653589793E1/0.4076697908635553E24);
t25 = log(10.0);
return((2.0*t15-13.0*t17+2.0*n*t17-2.0*n+t23)/t25/2.0);
}
}
Естественно, целая часть этого покажет количество знаков числа+1, а с мантиссой можно работать.
Исходная формула (аппроксимация факториала):
n! ~ 1/902961561600*sqrt(2)*sqrt(Pi)*(902961561600*n^7+75246796800*n^6+3135283200*n^5-2421135360*n^4-207204480*n^3+707957280*n^2+62961828*n-534703531)*n^(-13/2+n)*exp(-n)
← →Serega_M (2002-02-15 11:23) [8]
Какой тип переменных использовать расчетов большого факториала (например 10E+23541)?
← →Alx2 (2002-02-15 11:34) [9]
используй логарифмическую шкалу. Поправлю себя: Следует читать (пред. мое сообщение)
«Естественно, целая часть этого покажет количество знаков числа -1, а с мантиссой можно работать»
← →MBo (2002-02-15 13:26) [10]
вопрос- надо получить все верные цифры или хорошее приближение? если первое — отлично подойдет, как уже сказали, формула Стирлинга. Если второе — FGINT — это библиотека, http://triade.studentenweb.org Факториал 20000 считает 20 сек. 100 000! — 14 минут (Р600) только в строку не может преобразовать такое число ;(
← →Slinker (2002-02-17 04:03) [11]
Программа, приведенная здесь для вычисления логарифма, у меня выдает для 20000! около 74 тыс знаков, когда их всего 19тыс.
← →Slinker (2002-02-17 13:09) [12]
FGInt — ламерская тормозная либа. Расчет факториала, например, на http://algonew.manual.ru/maths/count_fast/factorial.php
← →MBo (2002-02-17 13:19) [13]
>FGInt — ламерская тормозная либа напиши лучше, народ, которому это надо, тебя не забудет, а так ламерским является твое заявление
← →Slinker (2002-02-18 01:30) [14]
Давай без личных наездов 8). Крутую либу писать не буду, так как это мне, во-первых, не интересно, а, во-вторых, они уже написаны. Например, Freelip.
Если честно — либу я написал, работает она асимптотически быстрее, чем FGInt, если нужно — дам линк, но она больше для учебных целей написана. А так — крутая либа GNU, например.
Ламерской я назвал FGInt просто потому, что под видом умных люди реализовывают «Fast» алгоритмы без сколь-ко либо серьезных попыток оптимизации.
← →Mbo (2002-02-18 06:42) [15]
ОК. Да, написаны, но приличные — на Cях. Информации мало, видимо, из-за того, что это сфера интересов криптографии.
← →Alx2 (2002-02-18 08:24) [16]
>Slinker (17.02.02 04:03) >Программа, приведенная здесь для вычисления логарифма, >у меня выдает для 20000! около 74 тыс знаков, >когда их всего 19тыс. Неверно. Знаков этого числа больше чем 68895.
Доказательство: Рассмотрим ряд: 1^(10-1)*10^(100-10)*100^(1000-100)*1000^(10000-1000)*10000^(20000-10000+1)=10^68894Slinker (17.02.02 04:03) >когда их всего 19тыс. В догонку: Еще один способ «в лоб»: просуммируем логарифмы чисел от 1 до 20000 и полученную сумму разделим на ln(10).
При этом получим десятичный логарифм факториала 20000. Это примерно 77337.26. То есть всего 77338 цифр. Откуда все-таки взялись ваши 19 тысяч?
← →Slinker (2002-02-18 15:25) [18]
Каюсь.. 19 тысяч взялись от вычислений по основанию 10000 … На самом деле там их ровно 77338, прога — 77337.259882 Длина 100000! 456574, прога — 456573.450900 Хорошо работает, собака ?
Источник: http://delphimaster.net/view/1-19184
Пределы с факториалами
Факториал числа $n!$ равен произведению чисел от 1 до $n$. Например, $5! = 1cdot 2cdot 3cdot 4cdot 5$. Для решения примеров на пределы с факториалами понадобится знать и понимать формулу разложения на множители. $$ (n+1)! = n!(n+1) qquad (1) $$
Например, $5! = 4! cdot 5 $, или $5! = 3! cdot 4 cdot 5$, а можно еще так $5! = 2! cdot 3 cdot 4 cdot 5 $.
Основная суть идеи:
- Выносим наименьший факториал числа за скобки в числителе и знаменателе
- Сокращаем факториалы, избавляя тем самым предел от них
- Вычисляем предел подходящим способом
Пример 1 |
Вычислить предел с факториалами $lim_limits{x o infty} frac{n!}{(n+1)!} $ |
Решение |
Подставляя $x=infty$ в предел получаем неопределенность бесконечность делить на бесконечность. Избавимся от факториалов. Для этого используем формулу (1) для их разложения на множители. $ (n+1)! = n! (n+1) $ Подставляем в предел полученное выражение и сокращаем на $n!$ числитель со знаменателем. $$ lim_limits{x o infty} frac{n!}{n! (n+1)} = lim_limits{n o infty} frac{1}{n+1} $$ Теперь подставляя бесконечность в предел вычисляем ответ. $$ lim_limits{n o infty} frac{1}{n+1} = (frac{1}{infty}) = 0 $$ Если не получается решить свою задачу, то присылайте её к нам. Мы предоставим подробное решение. Вы сможете ознакомиться с ходом вычисления и почерпнуть информацию. Это поможет своевременно получить зачёт у преподавателя! |
Ответ |
$$lim_limits{x o infty} frac{n!}{(n+1)!} = 0 $$ |
Пример 2 |
Решить предел с факториалом $ lim_limits{x o infty} frac{(2n+1)! + (2n+2)!}{(2n+3)!} $ |
Решение |
Определяем наименьший факториал $(2n+1)!$. Его нужно вынести за скобки. Но перед этим нужно разложить остальные факториалы на множители, одним из которых будет $(2n+1)!$. Для этого воспользуемся формулой (1). $$(2n+2)! = (2n+1)! cdot (2n+2) $$ $$ (2n+3)! = (2n+1)! cdot (2n+2)cdot(2n+3) $$ Выполняем замену в пределе на полученные выражения. $$lim_limits{x o infty} frac{(2n+1)! + (2n+1)! (2n+2)}{(2n+1)! (2n+2)(2n+3)} = $$ Выносим общий множитель с факториалом в числителе за скобки и выполняем сокращение со знаменателем. $$ lim_limits{x o infty} frac{(2n+1)! (1+ (2n+2))}{(2n+1)!(2n+2)(2n+3)} = lim_limits{x o infty} frac{1+ (2n + 2)}{(2n+2)(2n+3)} = $$ Раскрываем полученные скобки и сокращаем на $2n+3$. $$ = lim_limits{x o infty} frac{2n+3}{(2n+2)(2n+3)} = lim_limits{x o infty} frac{1}{2n+2} = (frac{1}{infty}) = 0$$ |
Ответ |
$$ lim_limits{x o infty} frac{(2n+1)! + (2n+2)!}{(2n+3)!} = 0 $$ |
Пример 3 |
Найти предел $lim_limits{x o infty} frac{3(n+1)!}{2(n+1)!-n!} $ |
Решение |
Понятно, что предел имеет неопределенность $frac{infty}{infty}$. Попробуем её устранить избавившись от факториалов. Сразу находим среди них наименьший $n!$. Его нужно будет вынести за скобки. Но перед этим остальные факториалы нужно разложить по формуле (1) и затем подставить в предел. $$ (n+1)! = n! (n+1) $$ $$ lim_limits{x o infty} frac{3n! (n+1)}{2n!(n+1) — n!} = lim_limits{x o infty} frac{3(n+1)}{2(n+1)-1} = $$
|
Ответ |
$$lim_limits{x o infty} frac{3(n+1)!}{2(n+1)!-n!} = frac{3}{2} $$ |
Нужно подробное решение своей задачи?
ЗАКАЗАТЬ РЕШЕНИЕ
Источник: https://xn--24-6kcaa2awqnc8dd.xn--p1ai/predely-s-faktorialami.html
Факторизация факториала
Название темы, для несведующих людей, может быть немного запутанным, и даже похже на тафтологическое выражение «масло масленное». На самом деле, под название темы подразумевается разложение факториала на простейшие множители с степенями.
Зачем это надо?
Кто сталкивался с факториалами, знают что уже при значении 20, факториал достигает огромных значений 2432902008176640000
При факториале 100 значение получается еще больше, и возникает резонный вопрос а как можно представить факториал такого числа в более удобной и наглядной форме? Во первых это красиво, а во вторых полезно, так как отвечает еще и на попутно возникающий вопрос, например , сколько двоек/пятерок/семерок в факториале числа 2015?
Что бы решить такую задачу, не надо вычислять факториал от числа 2015, а потом искать число целочисленных делений на тройку например , достаточно знать формулу по который рассчитывается число вхождений.
Итак если число p простое, то количество вхождений в факториал числа m, вычисляется как
- где квадратные скобки означают что берётся целая часть от деления.
- Самый простой пример, сколько раз входит число 3 в факториал 50?
- Рассчитываем:
то есть тройка встречается в числе 50! ровно 22 раза.
Теперь несложно, пробежавшись по всем простым числам от 1 до 50, для каждого из них узнать количество вхождений.
Окончательный ответ, в виде факторизации факториала пятидести будет иметь вид.
- Решим еще один пример, часто встречающийся.
- На какое количество нулей оканчивается факториал числа 306?
- Для решения такой задачи надо знать что 10 это произвдение двух простых чисел 2 и 5.
- Таким образом узнав количество вхождений пятерки в факториал ( количество вхождений двойки, естественно будет больше), мы узнаем какое количество нулей будет в факториала 306.
- Ответ: на 75 нулей будет оканчиватся заданный факториал.
- Удачных расчетов!
Источник: https://abakbot.ru/online-16/351-fac-fac
Элементы комбинаторики. Перестановки, размещения, сочетания
Ниже калькулятор, подсчитывающий число перестановок, размещений и сочетаний. Под ним, как водится, ликбез, если кто подзабыл.
Число размещений из n по m
Число размещений из n по m с повторениями
Число сочетаний из n по m
Итак, есть множество из n элементов.
Вариант упорядочивания данного множества называется перестановкой (permutation).
Например, есть множество, состоящее из 3 элементов — А, В, и С. Пример перестановки — СВА. Число всех перестановок из n элементов:
Пример: Для случая А, В, С число всех перестановок 3! = 6. Перестановки: АВС, АСВ, ВАС, ВСА, САВ, СВА
Если из множества n элементов выбирают m в определенном порядке, это называется размещением (arrangement).
Пример размещения из 3 по 2: АВ или ВА — это два разных размещения. Число всех размещений из n по m
Пример: Для случая А, В, С число всех размещений из 3 по 2 равно 3!/1! = 6. Размещения: АВ, ВА, АС, СА, ВС, СВ
Также бывают размещения с повторениями, как ясно из названия, элементы на определенных позициях могут повторяться.
Число всех размещений из n по m с повторениями:
Пример: Для случая А, В, С число всех размещений из 3 по 2 с повторениями равно 3*3 = 9. Размещения: AA, АВ, АС, ВА, BB, ВС, СА, СВ, CC
Если из множества n элементов выбирают m, и порядок не имеет значения, это называется сочетанием (combination).
Пример сочетания из 3 по 2: АВ. Число всех сочетаний из n по m
Пример: Для случая А, В, С число всех сочетаний из 3 по 2 равно 3!/(2!*1!) = 3. Сочетания: АВ, АС, СВ
Приведем до кучи формулу соотношения между перестановками, размещениями и сочетаниями:
Обратите внимание, что внизу
Источник: https://planetcalc.ru/978/