Как стать автором
Обновить

0! = 1? или почему факториал нуля равен единице

Математика *
Давным давно, еще в классе 10-ом (лет 8 назад) я случайно обнаружил довольно нехитрое объяснение того, почему факториал нуля равен единице.

Я рассказывал про это многим учителям, но никого не торкнуло. Поэтому я просто выложу это знание здесь, а то вдруг кому-то пригодится или наведет на определенные мысли. Сразу скажу я не математик, наткнулся на это случайно, когда игрался с числами. Я тогда даже не знал что такое факториал :)
Перейдем к делу!
Всего голосов 157: ↑126 и ↓31 +95
Просмотры 170K
Комментарии 79

Модификация формулы Стирлинга

Математика *
В математике известна формула Стирлинга (Муавра-Стирлинга) — формула для приближённого вычисления факториала и гамма-функции [Формула Стирлинга]:

Читать дальше →
Всего голосов 30: ↑26 и ↓4 +22
Просмотры 8.8K
Комментарии 16

Видеоуроки по Python от Khan Academy

Python *
Некоммерческая организация Khan Academy начала публиковать микролекции по языку программирования Python для начинающих. Первый урок посвящён написанию простой программки вычисления факториала с использованием цикла.



P.S. Khan Academy специализируется на массовом образовании. С 2006 года её основатель Салман Хан записал более 2300 микролекций в области науки и математики. По данным на июнь 2011 года, у канала Khan Academy на YouTube зафиксировано около 64 млн просмотров.

Khan Academy на YouTube
Всего голосов 67: ↑63 и ↓4 +59
Просмотры 14K
Комментарии 28

Однострочники на С++

Программирование *C++ *Алгоритмы *
Из песочницы
image
На хабе появилось несколько топиков об «однострочниках» на разных языках, которые решали простые задачи. Я решил опубликовать несколько алгоритмов на языке C/С++.
Итак, поехали!
Читать дальше →
Всего голосов 148: ↑111 и ↓37 +74
Просмотры 56K
Комментарии 103

Вычисление факториала на числах Чёрча

Ненормальное программирование *JavaScript *Функциональное программирование *
Доброго дня, друзья!

Тема функционального программирования раскрыта на Хабре весьма неплохо, есть целая куча статей посвященных λ-исчислению, числам Чёрча и подобным темам, так что ничего нового я не открою, зато мы напишем одну бесполезную и крайне неэффективную программу.

Для того, чтоб жизнь мёдом не казалась, ограничим себя небольшим подмножеством языка JavaScript, а именно, будем использовать только анонимные функции от одного аргумента. Больше нам ничего не потребуется (ну почти).

Начнем с определения факториала, и посмотрим, что нам понадобится в процессе решения задачи:

var fact = function (n) {
  if (n === 0) return 1;
  return n * fact(n - 1);
};


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

Готовы?
Ну тогда поехали.
Всего голосов 51: ↑51 и ↓0 +51
Просмотры 25K
Комментарии 47

Факториал на числах Чёрча — теперь и в смайликах

Ненормальное программирование *JavaScript *Функциональное программирование *

Всем доброго утра




Это полностью валидный код на JavaScript.
Как же так?
Всего голосов 20: ↑17 и ↓3 +14
Просмотры 14K
Комментарии 1

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

Спортивное программирование *Алгоритмы *Математика *
Из песочницы
Понятие факториала известно всем. Это функция, вычисляющая произведение последовательных натуральных чисел от 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 <= n; ++i)
        r *= i;
    return r;            
}

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

Далее рассмотрим алгоритмы, которые работают намного быстрее наивной реализации.
Читать дальше →
Всего голосов 48: ↑41 и ↓7 +34
Просмотры 194K
Комментарии 41

Как перебрать все перестановки и о факториальном разложении натуральных чисел

Программирование *Алгоритмы *Параллельное программирование *
Задачи о переборе всех возможных перестановок заданного множества сущностей возникают в программировании достаточно часто. Как известно из комбинаторики, число возможных перестановок n предметов равно попросту факториалу числа n

n! = n * (n — 1) * (n – 2) * … * 3 * 2 * 1

Факториал – достаточно быстро растущая функция, об этом говорит ее асимптотика (формула Стирлинга), хотя достаточно посмотреть на факториалы нескольких первых членов натурального ряда:

1! 1
2! 2
3! 6
4! 24
5! 120
6! 720
7! 5 040
8! 40 320
9! 362 880
10! 3 628 800
11! 39 916 800
12! 479 001 600
13! 6 227 020 800
14! 87 178 291 200
15! 1 307 674 368 000

Как видно, факториал 13-ти уже не умещается в тип данных long.

Если задаться целью найти однозначное соответствие между номером перестановки — числом в диапазоне от 1 до n! – и ее реализацией, можно натолкнуться на один очень интересный математический факт.
Читать дальше →
Всего голосов 31: ↑30 и ↓1 +29
Просмотры 24K
Комментарии 18

Быстрое вычисление факториала — PrimeSwing

Алгоритмы *Математика *
Наткнувшись недавно на эту статью, я понял, что редко упоминаются способы вычисления факториала, отличные от банального перемножения последовательных чисел. Нужно эту ситуацию исправить.
Предлагаю рассмотреть «асимптотически наиболее быстрый» алгоритм вычисления факториала!
Читать дальше →
Всего голосов 21: ↑18 и ↓3 +15
Просмотры 14K
Комментарии 21

Пятничный JS: единственно верный способ вычисления факториала

Ненормальное программирование *JavaScript *

Введение


Вычисление факториала — одна из традиционных программистских задач для собеседований. Если вдруг кто забыл, факториал натурального числа N обозначается как N! и равняется произведению всех натуральных чисел от единицы до N включительно. Например, $6! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 = 720$. Казалось бы, что тут сложного? Однако есть свои нюансы.

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

Через цикл
function factorial(n){
    var result = 1;
    while(n){
        result *= n--;
    }
    return result;
}


Через рекурсию
function factorial(n, result){
    result = result || 1;
    if(!n){
        return result;
    }else{
        return factorial(n-1, result*n);
    }
}


Многие скажут, что первый способ лучше, но это не так. Во-первых, циклы уже не в тренде, сейчас модно функциональное программирование. Во-вторых, чем больше людей используют второй способ, тем быстрее в основных джаваскриптовых движках появится оптимизация хвостовой рекурсии.

В любом случае, оба эти способа слишком примитивны, чтобы по ним судить о знаниях кандидата. А вот опытный разработчик на React.js уже может написать что-то в этом роде:
Узнать, что же напишет опытный разработчик на React.js
Всего голосов 21: ↑12 и ↓9 +3
Просмотры 37K
Комментарии 47

Короткое плечо совпадения

Математика *
Перевод
Джеймс Тэнтон разбрасывается задачками по теории чисел с той же щедростью, с которой Джон Д. Рокфеллер раздавал десятицентовики. Я уже писал об одной из задач Тэнтона. Спустя несколько недель моё внимание привлёк этот твит о факториалах и квадратах и уже не давал мне покоя:

Tweet reads: 4!+1 = 25, a square number. 5!+1 = 121, a square number. Another example? Two more examples?

«4!+1 = 25, квадрат числа. 5!+1 = 121, тоже квадрат числа. Можете привести ещё один пример? Ещё два примера?»

С помощью ручки и бумаги легко показать, что $6!$ не подходит. Факториал $6!$ — это $1 \times 2 \times 3 \times 4 \times 5 \times 6 = 720$; прибавив $1$, получим число $721$, которое не является квадратом. (Оно раскладывается на множители как $7 \times 103$.) С другой стороны, $7!$ равно $5040$, а прибавив $1$, мы получим $5041$, что равно $71^2$. Это даёт нам очень милое уравнение:
Читать дальше →
Всего голосов 41: ↑39 и ↓2 +37
Просмотры 16K
Комментарии 26

Сколькими способами можно записать факториал на Scheme?

Ненормальное программирование *Программирование *Lisp *Функциональное программирование *

Злые языки утверждают, что функциональные языки программирования — «языки для написания факториалов». Чаще всего так определяют язык Haskell, мы же начнем с того функционального языка, который сильно повлиял и на Haskell, и на подмножество средств для функционального программирования многих других языков — язык Scheme. По-крайней мере, map и for-each, filter и reduce, а так же apply и eval пришли в наши любимые языки программирования если не именно из Scheme, то в том числе и оттуда.


Рассмотрим некоторые возможные способы записи вычисления факториала. Заодно получится своеобразная ода языку программирования Scheme. Думаю, этот замечательный язык того вполне заслуживает.


У меня получилось 10 вариантов записи определений функций, которые можно свести к 3 основным способам вычисления: традиционному линейно-рекурсивному вычислительному процессу, итерации, генерации последовательности чисел с последующей сверткой умножением. Предлагаю рассмотреть эти варианты подробнее. Попутно мы рассмотрим: оптимизацию хвостовой рекурсии, функции высших порядков и метапрограммирование, отложенные вычисления, бесконечные списки, мемоизацию, способ создать статическую переменную в Scheme и гигиенические макросы.

Читать дальше →
Всего голосов 31: ↑31 и ↓0 +31
Просмотры 6.6K
Комментарии 17

Делимые факториалы

Занимательные задачки Математика *
Перевод
Недавно я был совершенно сбит с толку этим твитом «Библиотеки Ферма»:


«Вот что получится, если в факториале не умножать, а делить.»

Когда я увидел его, мне пришлось бросить свои дела, схватить блокнот и проверить формулу. Результат в черновом виде казался логичным. Так как мультипликативная версия $n!$ при увеличении $n$ стремится к бесконечности, то «делительная» версия должна стремиться к нулю. И $\frac{n^2}{n!}$ ведёт себя именно так; полиномиальная функция $n^2$ растёт медленнее, чем степенная функция $n!$ для достаточно больших $n$:

$\frac{1}{1}, \frac{4}{2}, \frac{9}{6}, \frac{16}{24}, \frac{25}{120}, \frac{36}{720}, \frac{49}{5040}, \frac{64}{40320}, \frac{81}{362880}, \frac{100}{3628800}$


Но почему результат деления принимает именно вид $\frac{n^2}{n!}$? Откуда берётся $n^2$?
Читать дальше →
Всего голосов 39: ↑30 и ↓9 +21
Просмотры 18K
Комментарии 17

Четырёхмерные таблицы в комбинаторике — два странных способа посчитать сочетания

Алгоритмы *Математика *


В комбинаторике сочетанием из $n$ по $k$ называют набор $k$ элементов, выбранных из $n$ элементов. В отличие от размещений, число сочетаний не учитывает последовательность размещения элементов, например: «Сколько групп из 4 человек, можно получить, если всего в классе 20 человек?». Хотя удобные способы подсчёта давно известны, на ещё два стоит взглянуть.
Читать дальше →
Всего голосов 17: ↑17 и ↓0 +17
Просмотры 4.2K
Комментарии 4