Занимательная математика, очаровательный python. Эпизод 1: Факториалы

Safoyeth 7 Дек 2013

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


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

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

Факториал

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

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

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

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

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

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

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

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

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

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

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

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

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

Для эстетов еще могу порекомендовать обработать значения типа 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() пригодится нам для написания своей функции обратного факториала. Итак, первым делом мы должны проверить поступающее значение на валидность. Также как и с факториалом, мы будем работать только с целыми положительными цифрами, следовательно

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

Теперь логика 🙂 Сначала мы проверяем валидность данных, потом начинаем последовательно делить число, причем важно, что мы делим именно преобразованные во 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. К примеру:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.




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

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: