Факториал в питоне как пишется

1. Функции

Напомним, что в математике факториал числа n определяется как n! = 1 ⋅ 2 ⋅ … ⋅ n.
Например, 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120.
Ясно, что факториал можно легко посчитать, воспользовавшись циклом for.
Представим, что нам нужно в нашей программе вычислять факториал разных чисел несколько раз (или в разных местах кода).
Конечно, можно написать вычисление факториала один раз, а затем используя Copy-Paste вставить его везде, где это будет нужно.

# вычислим 3!
res = 1
for i in range(1, 4):
    res *= i
print(res)

# вычислим 5!
res = 1
for i in range(1, 6):
    res *= i
print(res)

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

Функции — это такие участки кода, которые изолированы от остальный программы и выполняются только тогда, когда вызываются.
Вы уже встречались с функциями sqrt(), len() и print(). Они все обладают общим свойством: они могут принимать параметры (ноль, один или несколько), и они могут возвращать значение (хотя могут и не возвращать). Например, функция sqrt() принимает один параметр и возвращает значение (корень числа). Функция print() принимает переменное число параметров и ничего не возвращает.

Покажем, как написать функцию factorial(), которая принимает один параметр — число, и возвращает значение — факториал этого числа.

def factorial(n):
    res = 1
    for i in range(1, n + 1):
        res *= i
    return res

print(factorial(3))
print(factorial(5))

Дадим несколько объяснений. Во-первых, код функции должен размещаться в начале программы, вернее, до того места, где мы захотим воспользоваться функцией factorial(). Первая строчка этого примера является описанием нашей функции. factorial — идентификатор, то есть имя нашей функции. После идентификатора в круглых скобках идет список параметров, которые получает наша функция. Список состоит из перечисленных через запятую идентификаторов параметров. В нашем случае список состоит из одной величины n. В конце строки ставится двоеточие.

Далее идет тело функции, оформленное в виде блока, то есть с отступом. Внутри функции вычисляется значение факториала числа n и оно сохраняется в переменной res. Функция завершается инструкцией return res, которая завершает работу функции и возвращает значение переменной res.

Инструкция return может встречаться в произвольном месте функции, ее исполнение завершает работу функции и возвращает указанное значение в место вызова. Если функция не возвращает значения, то инструкция return используется без возвращаемого значения. В функциях, которым не нужно возвращать значения, инструкция return может отсутствовать.

Приведём ещё один пример. Напишем функцию max(), которая принимает два числа и возвращает максимальное из них (на самом деле, такая функция уже встроена в Питон).

def max(a, b):
    if a > b:
        return a
    else:
        return b

print(max(3, 5))
print(max(5, 3))
print(max(int(input()), int(input())))

Теперь можно написать функцию max3(), которая принимает три числа и возвращает максимальное их них.

def max(a, b):
    if a > b:
        return a
    else:
        return b

def max3(a, b, c):
    return max(max(a, b), c)

print(max3(3, 5, 4))

def max(*a):
    res = a[0]
    for val in a[1:]:
        if val > res:
            res = val
    return res

print(max(3, 5, 4))

2. Локальные и глобальные переменные

Внутри функции можно использовать переменные, объявленные вне этой функции

def f():
    print(a)

a = 1
f()

Здесь переменной a присваивается значение 1, и функция f()
печатает это значение, несмотря на то, что до объявления функции f эта переменная
не инициализируется. В момент вызова функции f() переменной a
уже присвоено значение, поэтому функция f() может вывести его на экран.

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

Но если инициализировать какую-то переменную внутри функции,
использовать эту переменную вне функции не удастся. Например:

def f():
    a = 1

f()
print(a)

Получим ошибку NameError: name 'a' is not defined. Такие переменные, объявленные внутри функции,
называются локальными. Эти переменные становятся недоступными после выхода из функции.

Интересным получится результат, если попробовать изменить значение глобальной переменной внутри функции:

def f():
    a = 1
    print(a)

a = 0
f()
print(a)

Будут выведены числа 1 и 0. Несмотря на то, что значение переменной a
изменилось внутри функции, вне функции оно осталось прежним! Это сделано в целях
“защиты” глобальных переменных от случайного изменения из функции.
Например, если функция будет вызвана из цикла по переменной i, а в этой функции
будет использована переменная i также для организации цикла, то эти переменные должны
быть различными. Если вы не поняли последнее предложение, то посмотрите на следующий код и подумайте, как бы он работал,
если бы внутри функции изменялась переменная i.

def factorial(n):
    res = 1
    for i in range(1, n + 1):
        res *= i
    return res

for i in range(1, 6):
    print(i, '! = ', factorial(i), sep='')

Если бы глобальная переменная i изменялась внутри функции, то мы бы получили вот что:

5! = 1
5! = 2
5! = 6
5! = 24
5! = 120

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

Более формально: интерпретатор Питон считает переменную локальной для данной функции, если в её коде
есть хотя бы одна инструкция, модифицирующая значение переменной, то эта переменная считается локальной
и не может быть использована до инициализации. Инструкция, модифицирующая значение переменной — это операторы =, +=, а также использование переменной в качестве параметра цикла for.
При этом даже если инструкция,
модицифицирующая переменную никогда не будет выполнена, интерпретатор это проверить
не может, и переменная все равно считается локальной. Пример:

def f():
    print(a)
    if False:
        a = 0

a = 1
f()

Возникает ошибка: UnboundLocalError: local variable 'a' referenced before assignment.
А именно, в функции f() идентификатор a становится локальной переменной,
т.к. в функции есть команда, модифицирующая переменную a, пусть даже никогда и
не выполняющийся (но интерпретатор не может это отследить). Поэтому вывод переменной a
приводит к обращению к неинициализированной локальной переменной.

Чтобы функция могла изменить значение глобальной переменной, необходимо объявить эту переменную
внутри функции, как глобальную, при помощи ключевого слова global:

def f():
    global a
    a = 1
    print(a)

a = 0
f()
print(a)

В этом примере на экран будет выведено 1 1, так как переменная a объявлена, как глобальная,
и ее изменение внутри функции приводит к тому, что и вне функции переменная
будет доступна.

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

Например, пусть ваша программа должна посчитать факториал вводимого числа, который вы потом захотите сохранить в переменной f.
Вот как это не стоит делать:

def factorial(n):
    global f
    res = 1
    for i in range(2, n + 1):
        res *= i
    f = res

n = int(input())
factorial(n)
# дальше всякие действия с переменной f

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

Гораздо лучше переписать этот пример так:

# начало куска кода, который можно копировать из программы в программу
def factorial(n):
    res = 1
    for i in range(2, n + 1):
        res *= i
    return res
# конец куска кода

n = int(input())
f = factorial(n)
# дальше всякие действия с переменной f

Если нужно, чтобы функция вернула не одно значение, а два или более, то
для этого функция может вернуть список из двух или нескольких значений:

Тогда результат вызова функции можно будет использовать во множественном присваивании:

3. Рекурсия

def short_story():
    print("У попа была собака, он ее любил.")
    print("Она съела кусок мяса, он ее убил,")
    print("В землю закопал и надпись написал:")
    short_story()

Как мы видели выше, функция может вызывать другую функцию. Но функция также может вызывать и саму себя!
Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что 0!=1, 1!=1.
А как вычислить величину n! для большого n? Если бы мы могли вычислить величину (n-1)!,
то тогда мы легко вычислим n!, поскольку n!=n⋅(n-1)!. Но как вычислить (n-1)!? Если бы
мы вычислили (n-2)!, то мы сможем вычисли и (n-1)!=(n-1)⋅(n-2)!. А как вычислить (n-2)!?
Если бы… В конце концов, мы дойдем до величины 0!, которая равна 1. Таким образом, для вычисления факториала
мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на Питоне:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

print(factorial(5))

Подобный прием (вызов функцией самой себя) называется рекурсией, а сама функция называется рекурсивной.

Рекурсивные функции являются мощным механизмом в программировании. К сожалению, они не всегда эффективны. Также часто использование рекурсии приводит к ошибкам. Наиболее распространенная
из таких ошибок – бесконечная рекурсия, когда цепочка вызовов функций никогда не завершается и продолжается,
пока не кончится свободная память в компьютере. Пример бесконечной рекурсии приведен в эпиграфе к этому разделу.
Две наиболее распространенные причины для бесконечной рекурсии:

1. Неправильное оформление выхода из рекурсии. Например, если мы в программе вычисления факториала
   забудем поставить проверку if n == 0, то factorial(0) вызовет factorial(-1),
   тот вызовет factorial(-2) и т. д.
2. Рекурсивный вызов с неправильными параметрами. Например, если функция factorial(n) будет
   вызывать factorial(n), то также получится бесконечная цепочка.

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

Этот цикл статей я хочу посвятить обзору математических возможностей python 2.7. Вместе с моей любимой змеёй мы окунёмся в тайны математики и напишем такие функции, который просто поразят воображение. Итак, запускайте python, включайте голову, вперёд!

Нам понадобятся:

1. Python (я буду использовать версию 2.7.5 под Windows 64 bit)
2. Мозги (я буду пользовать свои с примесью google и wikipedia)

• Факториал

Факториалы манили меня еще в школе. Красивое слово, необычный (для того времени) синтаксис. Я всегда с некоторой издевкой мог блеснуть талантом, ”вычисляя” факториал простого числа. Став старше, и особенно влюбившись в python, моя страсть к факториалам не просто не уменьшилась, скорее наоборот, именно поэтому эта статья полностью будет посвящена всевозможным факториалам. Но сначала немного математики. Итак,

Факториалом числа n (обозначается n!) называется произведение всех натуральных  чисел от 1 до n.

Иными словами,

6! = 1*2*3*4*5*6 = 720

Физический смысл (если так можно сказать) факториала определяется как число упорядочиваний  множества из n элементов. Переводя с непонятного на русский, давайте представим себе колоду из 36 карт. Каждый раз, когда мы тасуем эту колоду мы создаем уникальное упорядочивание, одно из 36! = 371993326789901217467999448150835200000000. Возможно, именно поэтому карточные игры так популярны! ?

Но ближе к делу! Наверняка каждый, кто изучал python, знает как вычислить факториал, причем не одним способом. Когда изучают lambda-функции, пишут так:

factorial = lambda x: factorial(x-1) * x if x > 0 else 1

… и мало кто что понимает!

Когда изучают рекурсию, пишут так:

def factorial(x):
    if x == 0:
        return 1
    elif x > 0:
        return factorial(x-1) * x

Это уже понятней! А те, кто совсем хорошо знают python, вообще не парятся и делают так:

import math
math.factorial(5)

Но мы пойдём своим путём. Мы не будем использовать math, вместо этого мы напишем свой собственный модуль. Откройте свой любимый редактор (я буду пользоваться стандартным IDLE), создайте файл factorials.py и давайте творить! В качестве простейшей задачи сначала давайте определим функцию для вычисления факториала. Я буду делать это с помощью lambda, как в первом примере:

def factorial(x):
    result = lambda x: result(x-1) * x if x > 0 else 1
    return result(x)

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

import factorials
factorials.factorial(5)
120

Казалось бы супер! И все примеры, которые можно найти в интернете здесь заканчиваются на позитивной ноте, однако как обычно все не так просто. На самом деле наша функция абсолютно некорректна и простейший способ проверить это — передать ей неадекватное значение. И если с совсем бредятинкой типа ”str” python справится сам, то вот значение типа ”float” легко пропустит. Не верите? Попробуйте посчитать факториал 4.125. Не бином Ньютона, что наша новорожденная функция должна работать только с целочисленным типом данных, следовательно нужно переписать её так:

def factorial(x):
    if type(x) == int:
        result = lambda x: result(x-1) * x if x > 0 else 1
        return result(x)
    else:
        raise TypeError, "The given value must be integer, not %s"%type(x)

Во-о-о-т! Теперь скормить ересь не получится, так как сразу будет подниматься TypeError. Но и это еще не всё. Если мы попробуем посчитать факториал -5 (минус пяти), то получим в ответ единицу, а это тоже неадекватно. Факториал определяется только для целых и положительных цифр, следовательно нужно ещё раз переписать код.

def factorial(x):
    if type(x) == int and x >= 0:
        result = lambda x: result(x-1) * x if x > 0 else 1
        return result(x)
    else:
        raise TypeError, "The given value must be positive integer, not %s"%(type(x) if type(x) != int else "negative")

Для эстетов еще могу порекомендовать обработать значения типа ”float”, которые по сути являются целыми, типа 25.0, 12.0 etc. Я этого делать не буду, так как предпочитаю более жёстко обращаться с типами данных.

• Обратный факториал

Простейшая задача выполнена, но я бы не стал городить всё это только ради простейшей задачи! ? Куда более интересно найти обратный факториал.  Легко догадаться, что

Обратным факториалом числа i называется такое число, факториал которого будет равен i.

То есть если 4! = 24, то обратным факториалом 24 будет 4. Функция для обратного факториала несколько сложнее. Для начала нужно понять механизм её работы. Если считая факториал числа мы последовательно умножаем цифры, то, как не сложно догадаться, здесь мы должны последовательно делить. Для себя я написал такой алгоритм работы функции: последовательно делим число на 1, 2, 3, 4 etc., до тех пор, пока не получим 1 и тогда возвращаем последний делитель. Но перед тем как начать писать код небольшое лирическое отступление. С помощью нашей функции вычислите факториал 4000. И получаем мы RuntimeError: maximum recursion depth exceeded. Печально? На самом деле ничего страшного не произошло, просто python ограничивает глубину рекурсии, что на мой взгляд правильно. Для того, чтобы посмотреть глубину рекурсии необходимо либо в интерпретаторе, либо где кому удобно импортировать модуль sys и выполнить функцию sys.getrecursionlimit(). В ответ вы скорее всего получите 1000, но лично у меня питон падает при вычислении факториала 995, хотя глубина рекурсии стоит 1000. Это на самом деле не важно, так как можно легко увеличить (но будьте разумны!) глубину путем вызова функции sys.setrecursionlimit(5000) например до 5000. Собственно, к чему все это? А к тому, что функция sys.getrecursionlimit() пригодится нам для написания своей функции обратного факториала. Итак, первым делом мы должны проверить поступающее значение на валидность. Также как и с факториалом, мы будем работать только с целыми положительными цифрами, следовательно

def antifactorial(x):
    if type(x) == int and x >= 0:
        # do_something
    else:
        raise TypeError, "The given value must be positive integer, not %s"%(type(x) if type(x) != int else "negative")

Теперь наша задача сводится к тому, чтобы последовательно делить x на числа от 1 и до… догадались? До sys.getrecursionlimit()+1! Решение вполне простое и изящное. Можно было, конечно, задать какое-нибудь произвольное число, например 500. Однако, давайте представим себе, что пользователь вычислил факториал 900, взял это число и подставил его в нашу функцию. Вы поняли что произойдет, я уверен. Наш антифакториал будет делить и делить до тех пор, пока не дойдет до 500, а затем остановится. Но мы должны были делить последовательно до 900! В общем, для того, чтобы не париться с такой фигнёй и было реализовано такое решение. Смысл его прост — посчитать факториал 3000 можно только увеличив глубину рекурсии допустим до 4000, а это в свою очередь одновременно увеличит и нашу последовательность, следовательно, антифакториал также будет найден! А сейчас, волшебным образом я сразу покажу функцию антифакториала!))

def antifactorial(x):
    if type(x) == int and x >= 0:
        for each in range(1, sys.getrecursionlimit()+1):
            x = float(x)/float(each)
            if x != 1.0 and x > 1.0:
                continue
            elif x != 1.0 and x < 1.0:
                raise ValueError,"The given value is not a factorial"
            else:
                return each
                break
    else:
        raise TypeError, "The given value must be positive integer, not %s"%(type(x) if type(x) != int else "negative")

Теперь логика ? Сначала мы проверяем валидность данных, потом начинаем последовательно делить число, причем важно, что мы делим именно преобразованные во ”float” значения. Для того, чтобы понять смысл этого преобразования прямо в интерпретаторе разделить 8 на 3. Почему вы получаете 2 я расскажу как нибудь потом, для нас же важно точное значение. Разделите 8.0 на 3.0 и увидите разницу. На самом деле цикл работает довольно просто. Мы делим значение на 1, проверяем равно ли получившееся 1.0 или больше 1.0. Если значение не равно 1.0 и больше 1.0, то инструкция continue продолжает цикл, мы делим значение на 2 , проверяем etc. Если вдруг значение не равно 1.0, и при этом уже меньше 1.0, значит данное число не было факториалом и нам нужно выйти из цикла, возбудив ValueError. Мы выходим из цикла для того, чтобы попусту не заставлять python тратить ресурсы на прогон по всему циклу, что логично. Если же значение строго рано 1.0, то мы опять же выходим из цикла и возвращаем тот делитель, на котором этот выход произошел. Строго говоря, можно (и нужно!) еще сократить цикл — смысла делить на 1 тоже нет. Теперь можно потестировать наш antifactorial. К примеру:

antifactorial(-2)
TypeError: The given value must be positive integer, not negative

antifactorial(2)
2

antifactorial(12)
ValueError: The given value is not a factorial

antifactorial(720)
6

antifactorial("720")
TypeError: The given value must be positive integer, not <type 'str'>

Таким образом мы написали пару функций — прямую и обратную, которые помогут нам как посчитать факториал числа, так и выяснить факториалом какого числа является (если вообще является) другое число. Дальше будет проще, но интересней!

• Суперфакториал

Суперфакториал придумали в 1995 году Нейл Слоан и Саймон Плоуф (англ.) и определили они его как произведение факториалов. Иными словами,

sf(4) = 1!*2!*3!*4! = 288

Функция для нахождения суперфакториала элементарна до безобразия, я даже не буду особо распинаться:

def superfactorial(x):
    if type(x) == int and x >= 0:
        result = lambda x: result(x-1) * factorial(x) if x > 0 else 1
        return result(x)
    else:
        raise TypeError, "The given value must be integer, not %s"%(type(x) if type(x) != int else "negative")

Знакомо, не правда ли? По сути, это та же самая функция, что и факториал, но только умножение происходит не на x, а на factorial(x)!

• Обратный суперфакториал

Также элементарен и обратный суперфакториал:

def antisuperfactorial(x):
    if type(x) == int and x >= 0:
        for each in range(2, sys.getrecursionlimit()+1):
            x = float(x)/flactorial(each)
            if x != 1.0 and x > 1.0:
                continue
            elif x != 1.0 and x < 1.0:
                raise ValueError,"The given value is not a superfactorial"
            else:
                return each
                break
    else:
        raise TypeError, "The given value must be positive integer, not %s"%(type(x) if type(x) != int else "negative")

Здесь мы делим в свою очередь не на число, а на факториал числа.

• Гиперфакториалы

Энтузиасты не остановились на суперфакториалах и в 2000 году  Генри Боттомли (англ.) создал гиперфакториалы, которые являются произведением суперфакториалов. Я не буду впадать в маразм и функцию мне писать лень, но о произведении гиперфакториалов, произведении произведения гиперфакториалов etc. я умолчу ?

def hyperfactorial(x):
    if type(x) == int and x >= 0:
        result = lambda x: result(x-1) * superfactorial(x) if x > 0 else 1
        return result(x)
    else:
        raise TypeError, "The given value must be integer, not %s"%(type(x) if type(x) != int else "negative")

 Функция гиперфакториала повторяет суперфакториал, только вместо умножения на factorial(x) мы умножаем на superfactorial(x). Обратный гиперфакториал я предлагаю вам написать самостоятельно, это не составит вообще никакой сложности.

• Двойной факториал

Не намного более сложной задачей является написание функции двойного факториала.  Сначала разберемся, что это собственно такое.

Двойным факториалом числа n (n!!) называется произведение всех натуральных чисел от 1 до n, имеющих ту де чётность, что и n.

Соответственно можно написать такую функцию:

def doublefactorial(x):
    if type(x) == int and x >= 0:
        result = lambda x: result(x-2) * x if x > 0 else 1
        return result(x)
    else:
        raise TypeError, "The given value must be positive integer, not %s"%(type(x) if type(x) != int else "negative")

Смысл такой же как и у обычного факториала, только с одной особенностью — шаг рекурсии не 1, а 2 (так как нам нужно идти строго по чётным или нечётным числам).

• Обратный двойной факториал

Обратный двойной факториал — это ненамного сложнее, чем обычный обратный факториал. Я реализовал её на мой взгляд не самым изящным способом, но пока нет желания как-то сокращать код. Основное отличие от обычных обратных факториалов в том, что мы должны делить не последовательно на 2, 3, 4,5 etc., но последовательно с шагом 2 и начинать деление либо с 2, либо с 3 в зависимости от чётности.  Собственно реализация:

def antiDoubleFactorial(x):
    if type(x) == int and x >= 0:
        if x % 2 == 0:
            for each in [z for z in range(2, sys.getrecursionlimit()) if z % 2 == 0]:
                x = float(x)/float(each)
                if x != 1.0 and x > 1.0:
                    continue
                elif x != 1.0 and x < 1.0:
                    raise ValueError,"The given value is not a factorial"
                else:
                    return each
                    break
        else:
            for each in [z for z in range(1, sys.getrecursionlimit()) if z % 2 != 0]:
                x = float(x)/float(each)
                if x != 1.0 and x > 1.0:
                    continue
                elif x != 1.0 and x < 1.0:
                    raise ValueError,"The given value is not a factorial"
                else:
                    return each
                    break
    else:
        raise TypeError, "The given value must be positive integer, not %s"%(type(x) if type(x) != int else "negative"

Поскольку произведение чётных факториал есть чётное число, мы можем воспользоваться генераторами списков для создания как чётной, так и нечётной последовательностей. Все остальное элементарно.

Тест на внимательность!

Если вы дочитали до сюда, то наверняка уже не раз нашли ошибки в коде.  Нет? Что же, давайте тогда вычислим 0! и 1!. А теперь antifactorial(1)! Именно! Мы совсем забыли об этой единице. Но давайте обратим на неё внимание теперь. Факториал, суперфакториал, гиперфакториал и двойной факториал нуля и единицы равен одному. Разумеется, нам необходимо научить наши функции возвращать значения, причем сразу два. Новичок начнет сразу переписывать все обратные функции, вводить эти конструкции ”если-то”. Мы — не новички!:-) Мы возьмем и напишем декоратор! Я сейчас не буду вдаваться в подробности о декораторах, этим на примере этого же модуля займусь завтра, когда у меня будет время, а сейчас просто напишу этот декоратор. Просто без комментариев:

def constant(function):
    def wrapper(x):
        if x == 1:
            return [0,1]
    return wrapper

 Теперь перед всеми обратными функциями достаточно прописать инструкцию @constant и все будет в порядке!

На этом разрешите пока остановиться. В следующей части мы познакомимся с праймориалами и факторионами, а также научимся (если вдруг кто не умел) генерировать последовательности всех этих кракозябр. После же того, как мы закончим с математикой, мы преобразим наш код в нечто декорированное! ?