Факториальные алгоритмы на разных языках
https://stackoverflow.com/questions/23930
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я хочу увидеть все различные способы, которые вы можете придумать для факториальной подпрограммы или программы.Мы надеемся, что любой желающий может прийти сюда и посмотреть, не захочет ли он выучить новый язык.
Идеи:
- Процедурный
- Функциональный
- Объектно-ориентированный
- Однострочники
- Запутанный
- Чудак
- Плохой код
- Полиглот
По сути, я хочу увидеть пример различных способов написания алгоритма и того, как они выглядели бы на разных языках.
Пожалуйста, ограничьте это одним примером для каждой записи.Я позволю вам привести более одного примера для каждого ответа, если вы пытаетесь выделить определенный стиль, язык или просто хорошо продуманную идею, которая уместна в одном сообщении.
Единственное реальное требование заключается в том, что он должен найти факториал данного аргумента на всех представленных языках.
Будьте изобретательны!
Рекомендуемое Руководство:
# Language Name: Optional Style type
- Optional bullet points
Code Goes Here
Other informational text goes here
Иногда я соглашусь и отредактирую любой ответ, который не имеет приличного форматирования.
Решение
Полиглот:5 языков, все используют bignums
Итак, я написал полиглот, который работает на трех языках, на которых я часто пишу, а также один из моих других ответов на этот вопрос и тот, который я только сегодня выучил.Это автономная программа, которая считывает одну строку, содержащую неотрицательное целое число, и печатает одну строку, содержащую его факториал.Значения используются во всех языках, поэтому максимальный вычислимый факториал зависит только от ресурсов вашего компьютера.
- Perl:использует встроенный пакет bignum.Бегите с
perl FILENAME. - Хаскелл:использует встроенные значения.Бегите с
runhugs FILENAMEили эквивалент вашего любимого компилятора. - C++:требуется GMP для поддержки bignum.Для компиляции с помощью g ++ используйте
g++ -lgmpxx -lgmp -x c++ FILENAMEчтобы связать с нужными библиотеками.После компиляции запустите./a.out.Или используйте эквивалент вашего любимого компилятора. - брейнфокс:Я написал некоторую поддержку bignum в этот пост.Используя Классическая раздача Мюллера, скомпилировать с помощью
bf < FILENAME > EXECUTABLE.Сделайте выходной файл исполняемым и запустите его.Или используйте свой любимый дистрибутив. - Пробел:использует встроенную поддержку bignum.Бегите с
wspace FILENAME.
Редактировать: добавлены пробелы в качестве пятого языка.Кстати, делайте нет оберните код с помощью <code> Теги;это нарушает пробел.Кроме того, код выглядит намного приятнее в формате фиксированной ширины.
char //# b=0+0{- |0*/; #>>>>,----------[>>>>,--------
#define a/*#--]>>>>++<<<<<<<<[>++++++[<------>-]<-<<<
#Perl ><><><> <> <> <<]>>>>[[>>+<<-]>>[<<+>+>-]<->
#C++ --><><> <><><>< > < > < +<[>>>>+<<<-<[-]]>[-]
#Haskell >>]>[-<<<<<[<<<<]>>>>[[>>+<<-]>>[<<+>+>-]>>]
#Whitespace >>>>[-[>+<-]+>>>>]<<<<[<<<<]<<<<[<<<<
#brainf*ck > < ]>>>>>[>>>[>>>>]>>>>[>>>>]<<<<[[>>>>*/
exp; ;//;#+<<<<-]<<<<]>>>>+<<<<<<<[<<<<][.POLYGLOT^5.
#include <gmpxx.h>//]>>>>-[>>>[>>>>]>>>>[>>>>]<<<<[>>
#define eval int main()//>+<<<-]>>>[<<<+>>+>->
#include <iostream>//<]<-[>>+<<[-]]<<[<<<<]>>>>[>[>>>
#define print std::cout << // > <+<-]>[<<+>+>-]<<[>>>
#define z std::cin>>//<< +<<<-]>>>[<<<+>>+>-]<->+++++
#define c/*++++[-<[-[>>>>+<<<<-]]>>>>[<<<<+>>>>-]<<*/
#define abs int $n //>< <]<[>>+<<<<[-]>>[<<+>>-]]>>]<
#define uc mpz_class fact(int $n){/*<<<[<<<<]<<<[<<
use bignum;sub#<<]>>>>-]>>>>]>>>[>[-]>>>]<<<<[>>+<<-]
z{$_[0+0]=readline(*STDIN);}sub fact{my($n)=shift;#>>
#[<<+>+>-]<->+<[>-<[-]]>[-<<-<<<<[>>+<<-]>>[<<+>+>+*/
uc;if($n==0){return 1;}return $n*fact($n-1); }//;#
eval{abs;z($n);print fact($n);print("\n")/*2;};#-]<->
'+<[>-<[-]]>]<<[<<<<]<<<<-[>>+<<-]>>[<<+>+>-]+<[>-+++
-}-- <[-]]>[-<<++++++++++<<<<-[>>+<<-]>>[<<+>+>-++
fact 0 = 1 -- ><><><>< > <><>< ]+<[>-<[-]]>]<<[<<+ +
fact n=n*fact(n-1){-<<]>>>>[[>>+<<-]>>[<<+>+++>+-}
main=do{n<-readLn;print(fact n)}-- +>-]<->+<[>>>>+<<+
{-x<-<[-]]>[-]>>]>]>>>[>>>>]<<<<[>+++++++[<+++++++>-]
<--.<<<<]+written+by+++A+Rex+++2009+.';#+++x-}--x*/;}
Другие советы
лолкод:
извини, я не смог удержаться xD
HAI
CAN HAS STDIO?
I HAS A VAR
I HAS A INT
I HAS A CHEEZBURGER
I HAS A FACTORIALNUM
IM IN YR LOOP
UP VAR!!1
TIEMZD INT!![CHEEZBURGER]
UP FACTORIALNUM!!1
IZ VAR BIGGER THAN FACTORIALNUM? GTFO
IM OUTTA YR LOOP
U SEEZ INT
KTHXBYE
Это один из самых быстрых алгоритмов, вплоть до 170!.IT терпит неудачу необъяснимым образом превышает 170!, и это относительно медленно для небольших факториалов, но для факториалов между 80 и 170 это невероятно быстро по сравнению со многими алгоритмами.
curl http://www.google.com/search?q=170!
Существует также онлайн-интерфейс, попробуйте это прямо сейчас!
Дайте мне знать, если вы обнаружите ошибку или более быструю реализацию для больших факториалов.
Редактировать:
Этот алгоритм немного медленнее, но дает результаты выше 170:
curl http://www58.wolframalpha.com/input/?i=171!
Это также упрощает их в различных других представлениях.
C++:Метапрограммирование шаблонов
Использует классический метод перечисления.
template<unsigned int n>
struct factorial {
enum { result = n * factorial<n - 1>::result };
};
template<>
struct factorial<0> {
enum { result = 1 };
};
Использование.
const unsigned int x = factorial<4>::result;
Факториал полностью вычисляется во время компиляции на основе параметра шаблона n.Следовательно, факториальный<4>:: результат является константой после того, как компилятор выполнил свою работу.
Пробел
. . . . . . . . . . . . . . . . . . . . . . . . . .
Было трудно заставить его отображаться здесь должным образом, но теперь я попробовал скопировать его из предварительного просмотра, и это сработало.Вам нужно ввести номер и нажать enter.
Я нахожу следующие реализации просто забавными:
Эволюция программиста на Haskell
Эволюция программиста на Python
Наслаждайтесь!
Поиск на C #:
На самом деле ничего не нужно вычислять, просто посмотрите.Чтобы расширить его, добавьте в таблицу еще 8 чисел, и 64-битные целые числа будут на пределе.Помимо этого, требуется класс BigNum.
public static int Factorial(int f)
{
if (f<0 || f>12)
{
throw new ArgumentException("Out of range for integer factorial");
}
int [] fact={1,1,2,6,24,120,720,5040,40320,362880,3628800,
39916800,479001600};
return fact[f];
}
Ленивый K
Ваши кошмары о чистом функциональном программировании становятся явью!
Единственный Эзотерический Тьюринг - полный Язык программирования это имеет:
- Чисто функциональная основа, ядро и библиотеки - фактически, вот полный API: С К И
- НЕТ лямбды квиты!
- НЕТ числа или списки необходимых или разрешенных
- Явной рекурсии нет, но все же, допускает рекурсию
- Простой бесконечный ленивый поток-основанный на механизме ввода-вывода
Вот Факториальный код во всей его красе в скобках:
K(SII(S(K(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(K(S(K(S(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
(S(S(KS)K)(SII(S(S(KS)K)I))))))))K))))))(S(K(S(K(S(SI(K(S(K(S(SI(K(S(K(S(S(KS)K)I))
(S(S(KS)K)(SII(S(S(KS)K)I))(S(S(KS)K))(S(SII)I(S(S(KS)K)I))))))))K)))))))
(S(S(KS)K)(K(S(S(KS)K)))))))))(K(S(K(S(S(KS)K)))K))))(SII))II)
Характеристики:
- Никаких вычитаний или условных обозначений
- Выводит все факториалы (если вы будете ждать достаточно долго)
- Использует второй слой цифр Черча для преобразования N-го факториала в N!звездочки, за которыми следует новая строка
- Использует Y - комбинатор для рекурсии
На случай, если вам интересно попытаться понять это, вот исходный код схемы для запуска через более ленивый компилятор:
(lazy-def '(fac input)
'((Y (lambda (f n a) ((lambda (b) ((cons 10) ((b (cons 42)) (f (1+ n) b))))
(* a n)))) 1 1))
(для подходящих определений Y, cons, 1, 10, 42, 1+, и *).
Редактировать:
Ленивый K -факториал в десятичной форме
(10 КБ тарабарщины или же я бы вставил его).Например, в командной строке Unix:
$ echo "4" | ./lazy facdec.lazy
24
$ echo "5" | ./lazy facdec.lazy
120
Довольно медленно для чисел выше, скажем, 5.
Код немного раздут, потому что мы должны включить библиотечный код для всех наших собственных примитивов (код, написанный на Туманный, интерпретатор лямбда-исчисления и компилятор LC-to-Lazy K, написанный на Haskell).
XSLT 1.0
Входной файл, factorial.xml:
<?xml version="1.0"?>
<?xml-stylesheet href="factorial.xsl" type="text/xsl" ?>
<n>
20
</n>
Файл XSLT, факториал.xsl:
<?xml version="1.0"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:msxsl="urn:schemas-microsoft-com:xslt" >
<xsl:output method="text"/>
<!-- 0! = 1 -->
<xsl:template match="text()[. = 0]">
1
</xsl:template>
<!-- n! = (n-1)! * n-->
<xsl:template match="text()[. > 0]">
<xsl:variable name="x">
<xsl:apply-templates select="msxsl:node-set( . - 1 )/text()"/>
</xsl:variable>
<xsl:value-of select="$x * ."/>
</xsl:template>
<!-- Calculate n! -->
<xsl:template match="/n">
<xsl:apply-templates select="text()"/>
</xsl:template>
</xsl:stylesheet>
Сохраните оба файла в одном каталоге и откройте factorial.xml в IE.
Питон:Функциональный, однострочный
factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)
ПРИМЕЧАНИЕ:
- Он поддерживает большие целые числа.Пример:
print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000
- Это не работает для n < 0.
АПЛ (странный / однострочный):
×/⍳X
- ⍳X расширяет X в массив целых чисел 1..X
- ×/ умножает каждый элемент в массиве
Или со встроенным оператором:
!X
Источник: http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt
Perl6
sub factorial ($n) { [*] 1..$n }
Я почти ничего не знаю о Perl6.Но я предполагаю, что это [*] оператор такой же, как у Хаскелла product.
Этот код выполняется на Мопсы, и , возможно , Попугай (Я этого не проверял.)
Редактировать
Этот код также работает.
sub postfix:<!> ($n) { [*] 1..$n }
# This function(?) call like below ... It looks like mathematical notation.
say 10!;
сборка x86-64:Процедурный
Вы можете вызвать это из C (тестировалось только с GCC в linux amd64).Сборка была собрана с помощью nasm.
section .text
global factorial
; factorial in x86-64 - n is passed in via RDI register
; takes a 64-bit unsigned integer
; returns a 64-bit unsigned integer in RAX register
; C declaration in GCC:
; extern unsigned long long factorial(unsigned long long n);
factorial:
enter 0,0
; n is placed in rdi by caller
mov rax, 1 ; factorial = 1
mov rcx, 2 ; i = 2
loopstart:
cmp rcx, rdi
ja loopend
mul rcx ; factorial *= i
inc rcx
jmp loopstart
loopend:
leave
ret
Рекурсивно в Inform 7
(это напоминает вам COBOL, потому что он предназначен для написания текстовых приключений;пропорциональный шрифт написан намеренно):
Чтобы решить, какое число является факториалом (n - число):
если n равно нулю, выберите единицу;
в противном случае определите факториал (n минус один), умноженный на n.
Если вы хотите на самом деле вызвать эту функцию ("фразу") из игры, вам нужно определить действие и грамматическое правило:
"Факториальная игра" [это должна быть первая строка исходного текста]
Там есть комната.[там должен быть хотя бы один!]
Факторизация - это действие, применяемое к числу.
Понимайте "факториал [число]" как факториализацию.
Провести факторинг:
Пусть n - факториал понимаемого числа;
Скажите "Это [n]".
C#:LINQ
public static int factorial(int n)
{
return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
}
Эрланг:хвост рекурсивный
fac(0) -> 1;
fac(N) when N > 0 -> fac(N, 1).
fac(1, R) -> R;
fac(N, R) -> fac(N - 1, R * N).
Хаскелл:
ones = 1 : ones
integers = head ones : zipWith (+) integers (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)
Брейнфокс
+++++
>+<[[->>>>+<<<<]>>>>[-<<<<+>>+>>]<<<<>[->>+<<]<>>>[-<[->>+<<]>>[-<<+<+>>>]<]<[-]><<<-]
Автор сценария - Майкл Рейценштейн.
Базовые модели:старая школа
10 HOME
20 INPUT N
30 LET ANS = 1
40 FOR I = 1 TO N
50 ANS = ANS * I
60 NEXT I
70 PRINT ANS
Пакет (NT):
@echo off
set n=%1
set result=1
for /l %%i in (%n%, -1, 1) do (
set /a result=result * %%i
)
echo %result%
Использование:C:>факториал.bat 15
F#:Функциональный
Прямолинейный:
let rec fact x =
if x < 0 then failwith "Invalid value."
elif x = 0 then 1
else x * fact (x - 1)
Становлюсь модным:
let fact x = [1 .. x] |> List.fold_left ( * ) 1
Рекурсивный Пролог
fac(0,1).
fac(N,X) :- N1 is N -1, fac(N1, T), X is N * T.
Хвостовой Рекурсивный Пролог
fac(0,N,N).
fac(X,N,T) :- A is N * X, X1 is X - 1, fac(X1,A,T).
fac(N,T) :- fac(N,1,T).
рекурсивный ruby
(factorial=Hash.new{|h,k|k*h[k-1]})[1]=1
использование:
factorial[5]
=> 120
Схема
Вот простое рекурсивное определение:
(define (factorial x)
(if (= x 0) 1
(* x (factorial (- x 1)))))
В схеме хвостово-рекурсивные функции используют постоянное пространство стека.Вот версия factorial, которая является хвостовой рекурсией:
(define factorial
(letrec ((fact (lambda (x accum)
(if (= x 0) accum
(fact (- x 1) (* accum x))))))
(lambda (x)
(fact x 1))))
Странные примеры?Как насчет использования гамма-функции?!С тех пор как, Gamma n = (n-1)!.
OCaml:Использование Гаммы
let rec gamma z =
let pi = 4.0 *. atan 1.0 in
if z < 0.5 then
pi /. ((sin (pi*.z)) *. (gamma (1.0 -. z)))
else
let consts = [| 0.99999999999980993; 676.5203681218851; -1259.1392167224028;
771.32342877765313; -176.61502916214059; 12.507343278686905;
-0.13857109526572012; 9.9843695780195716e-6; 1.5056327351493116e-7;
|]
in
let z = z -. 1.0 in
let results = Array.fold_right
(fun x y -> x +. y)
(Array.mapi
(fun i x -> if i = 0 then x else x /. (z+.(float i)))
consts
)
0.0
in
let x = z +. (float (Array.length consts)) -. 1.5 in
let final = (sqrt (2.0*.pi)) *.
(x ** (z+.0.5)) *.
(exp (-.x)) *. result
in
final
let factorial_gamma n = int_of_float (gamma (float (n+1)))
Программист-первокурсник на Haskell
fac n = if n == 0
then 1
else n * fac (n-1)
Программист-второкурсник на Haskell в Массачусетском технологическом институте (изучал Scheme на первом курсе)
fac = (\(n) ->
(if ((==) n 0)
then 1
else ((*) n (fac ((-) n 1)))))
Младший программист на Haskell (начинающий игрок в Peano)
fac 0 = 1
fac (n+1) = (n+1) * fac n
Другой младший программист на Haskell (прочитал, что n + k шаблонов являются “отвратительной частью Haskell” [1] и присоединился к движению “Запретить n + k шаблонов" [2])
fac 0 = 1
fac n = n * fac (n-1)
Старший программист Haskell (голосовал за Никсона Бьюкенена Буша — “склоняется вправо”)
fac n = foldr (*) 1 [1..n]
Другой старший программист Haskell (проголосовал за Макговерна Биафру Надер — “склоняется влево”)
fac n = foldl (*) 1 [1..n]
Еще один старший программист на Haskell (отклонился так далеко вправо, что снова вернулся влево!)
-- using foldr to simulate foldl
fac n = foldr (\x g n -> g (x*n)) id [1..n] 1
Запоминание программиста на Haskell (ежедневно принимает гинкго билоба)
facs = scanl (*) 1 [1..]
fac n = facs !! n
Бессмысленный (кхм) “Безбилетный” программист на Haskell (учился в Оксфорде)
fac = foldr (*) 1 . enumFromTo 1
Итеративный программист на Haskell (бывший программист на Pascal)
fac n = result (for init next done)
where init = (0,1)
next (i,m) = (i+1, m * (i+1))
done (i,_) = i==n
result (_,m) = m
for i n d = until d n i
Итеративный однострочный программист на Haskell (бывший программист APL и C)
fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))
Набирающий силу программист на Haskell (подготовка к быстрой кульминации)
facAcc a 0 = a
facAcc a n = facAcc (n*a) (n-1)
fac = facAcc 1
Продолжение-начинающий программист на Haskell (в ранние годы разводил КРОЛИКОВ, затем переехал в Нью-Джерси)
facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)
fac = facCps id
Программист Boy Scout на Haskell (любит завязывать узлы;всегда “благоговейный”, он принадлежит к Церкви Наименее фиксированной точки [8])
y f = f (y f)
fac = y (\f n -> if (n==0) then 1 else n * f (n-1))
Комбинаторный программист на Haskell (избегает переменных, если не запутывания;все это приготовление карри - всего лишь этап, хотя оно редко мешает)
s f g x = f x (g x)
k x y = x
b f g x = f (g x)
c f g x = f x g
y f = f (y f)
cond p f g x = if p x then f x else g x
fac = y (b (cond ((==) 0) (k 1)) (b (s (*)) (c b pred)))
Программист на Haskell, кодирующий списки (предпочитает считать в унарном формате)
arb = () -- "undefined" is also a good RHS, as is "arb" :)
listenc n = replicate n arb
listprj f = length . f . listenc
listprod xs ys = [ i (x,y) | x<-xs, y<-ys ]
where i _ = arb
facl [] = listenc 1
facl n@(_:pred) = listprod n (facl pred)
fac = listprj facl
Интерпретирующий программист на Haskell (никогда не "встречал язык”, который ему не нравился)
-- a dynamically-typed term language
data Term = Occ Var
| Use Prim
| Lit Integer
| App Term Term
| Abs Var Term
| Rec Var Term
type Var = String
type Prim = String
-- a domain of values, including functions
data Value = Num Integer
| Bool Bool
| Fun (Value -> Value)
instance Show Value where
show (Num n) = show n
show (Bool b) = show b
show (Fun _) = ""
prjFun (Fun f) = f
prjFun _ = error "bad function value"
prjNum (Num n) = n
prjNum _ = error "bad numeric value"
prjBool (Bool b) = b
prjBool _ = error "bad boolean value"
binOp inj f = Fun (\i -> (Fun (\j -> inj (f (prjNum i) (prjNum j)))))
-- environments mapping variables to values
type Env = [(Var, Value)]
getval x env = case lookup x env of
Just v -> v
Nothing -> error ("no value for " ++ x)
-- an environment-based evaluation function
eval env (Occ x) = getval x env
eval env (Use c) = getval c prims
eval env (Lit k) = Num k
eval env (App m n) = prjFun (eval env m) (eval env n)
eval env (Abs x m) = Fun (\v -> eval ((x,v) : env) m)
eval env (Rec x m) = f where f = eval ((x,f) : env) m
-- a (fixed) "environment" of language primitives
times = binOp Num (*)
minus = binOp Num (-)
equal = binOp Bool (==)
cond = Fun (\b -> Fun (\x -> Fun (\y -> if (prjBool b) then x else y)))
prims = [ ("*", times), ("-", minus), ("==", equal), ("if", cond) ]
-- a term representing factorial and a "wrapper" for evaluation
facTerm = Rec "f" (Abs "n"
(App (App (App (Use "if")
(App (App (Use "==") (Occ "n")) (Lit 0))) (Lit 1))
(App (App (Use "*") (Occ "n"))
(App (Occ "f")
(App (App (Use "-") (Occ "n")) (Lit 1))))))
fac n = prjNum (eval [] (App facTerm (Lit n)))
Статический программист на Haskell (он делает это с помощью class, у него есть этот фундеп Джонс!По мотивам книги Томаса Халлгрена “Забавы с функциональными зависимостями” [7])
-- static Peano constructors and numerals
data Zero
data Succ n
type One = Succ Zero
type Two = Succ One
type Three = Succ Two
type Four = Succ Three
-- dynamic representatives for static Peanos
zero = undefined :: Zero
one = undefined :: One
two = undefined :: Two
three = undefined :: Three
four = undefined :: Four
-- addition, a la Prolog
class Add a b c | a b -> c where
add :: a -> b -> c
instance Add Zero b b
instance Add a b c => Add (Succ a) b (Succ c)
-- multiplication, a la Prolog
class Mul a b c | a b -> c where
mul :: a -> b -> c
instance Mul Zero b Zero
instance (Mul a b c, Add b c d) => Mul (Succ a) b d
-- factorial, a la Prolog
class Fac a b | a -> b where
fac :: a -> b
instance Fac Zero One
instance (Fac n k, Mul (Succ n) k m) => Fac (Succ n) m
-- try, for "instance" (sorry):
--
-- :t fac four
Начинающий программист с высшим образованием на Haskell (высшее образование, как правило, освобождает человека от мелких забот например, об эффективности аппаратных целых чисел)
-- the natural numbers, a la Peano
data Nat = Zero | Succ Nat
-- iteration and some applications
iter z s Zero = z
iter z s (Succ n) = s (iter z s n)
plus n = iter n Succ
mult n = iter Zero (plus n)
-- primitive recursion
primrec z s Zero = z
primrec z s (Succ n) = s n (primrec z s n)
-- two versions of factorial
fac = snd . iter (one, one) (\(a,b) -> (Succ a, mult a b))
fac' = primrec one (mult . Succ)
-- for convenience and testing (try e.g. "fac five")
int = iter 0 (1+)
instance Show Nat where
show = show . int
(zero : one : two : three : four : five : _) = iterate Succ Zero
Программист-оригамист на Haskell (всегда начинает с “базовой складки птицы”)
-- (curried, list) fold and an application
fold c n [] = n
fold c n (x:xs) = c x (fold c n xs)
prod = fold (*) 1
-- (curried, boolean-based, list) unfold and an application
unfold p f g x =
if p x
then []
else f x : unfold p f g (g x)
downfrom = unfold (==0) id pred
-- hylomorphisms, as-is or "unfolded" (ouch! sorry ...)
refold c n p f g = fold c n . unfold p f g
refold' c n p f g x =
if p x
then n
else c (f x) (refold' c n p f g (g x))
-- several versions of factorial, all (extensionally) equivalent
fac = prod . downfrom
fac' = refold (*) 1 (==0) id pred
fac'' = refold' (*) 1 (==0) id pred
Программист на Haskell с картезианскими наклонностями (предпочитает греческую кухню, избегает острых индийских блюд;вдохновленный “Сортировкой морфизмов” Лекса Огастейна [3])
-- (product-based, list) catamorphisms and an application
cata (n,c) [] = n
cata (n,c) (x:xs) = c (x, cata (n,c) xs)
mult = uncurry (*)
prod = cata (1, mult)
-- (co-product-based, list) anamorphisms and an application
ana f = either (const []) (cons . pair (id, ana f)) . f
cons = uncurry (:)
downfrom = ana uncount
uncount 0 = Left ()
uncount n = Right (n, n-1)
-- two variations on list hylomorphisms
hylo f g = cata g . ana f
hylo' f (n,c) = either (const n) (c . pair (id, hylo' f (c,n))) . f
pair (f,g) (x,y) = (f x, g y)
-- several versions of factorial, all (extensionally) equivalent
fac = prod . downfrom
fac' = hylo uncount (1, mult)
fac'' = hylo' uncount (1, mult)
Доктор философии .Программист на Haskell (съел так много бананов, что у него вылезли глаза, теперь ему нужны новые линзы!)
-- explicit type recursion based on functors
newtype Mu f = Mu (f (Mu f)) deriving Show
in x = Mu x
out (Mu x) = x
-- cata- and ana-morphisms, now for *arbitrary* (regular) base functors
cata phi = phi . fmap (cata phi) . out
ana psi = in . fmap (ana psi) . psi
-- base functor and data type for natural numbers,
-- using a curried elimination operator
data N b = Zero | Succ b deriving Show
instance Functor N where
fmap f = nelim Zero (Succ . f)
nelim z s Zero = z
nelim z s (Succ n) = s n
type Nat = Mu N
-- conversion to internal numbers, conveniences and applications
int = cata (nelim 0 (1+))
instance Show Nat where
show = show . int
zero = in Zero
suck = in . Succ -- pardon my "French" (Prelude conflict)
plus n = cata (nelim n suck )
mult n = cata (nelim zero (plus n))
-- base functor and data type for lists
data L a b = Nil | Cons a b deriving Show
instance Functor (L a) where
fmap f = lelim Nil (\a b -> Cons a (f b))
lelim n c Nil = n
lelim n c (Cons a b) = c a b
type List a = Mu (L a)
-- conversion to internal lists, conveniences and applications
list = cata (lelim [] (:))
instance Show a => Show (List a) where
show = show . list
prod = cata (lelim (suck zero) mult)
upto = ana (nelim Nil (diag (Cons . suck)) . out)
diag f x = f x x
fac = prod . upto
Программист Post-doc на Haskell (из книги Уусталу, Вене и Пардо “Схемы рекурсии из Comonads” [4])
-- explicit type recursion with functors and catamorphisms
newtype Mu f = In (f (Mu f))
unIn (In x) = x
cata phi = phi . fmap (cata phi) . unIn
-- base functor and data type for natural numbers,
-- using locally-defined "eliminators"
data N c = Z | S c
instance Functor N where
fmap g Z = Z
fmap g (S x) = S (g x)
type Nat = Mu N
zero = In Z
suck n = In (S n)
add m = cata phi where
phi Z = m
phi (S f) = suck f
mult m = cata phi where
phi Z = zero
phi (S f) = add m f
-- explicit products and their functorial action
data Prod e c = Pair c e
outl (Pair x y) = x
outr (Pair x y) = y
fork f g x = Pair (f x) (g x)
instance Functor (Prod e) where
fmap g = fork (g . outl) outr
-- comonads, the categorical "opposite" of monads
class Functor n => Comonad n where
extr :: n a -> a
dupl :: n a -> n (n a)
instance Comonad (Prod e) where
extr = outl
dupl = fork id outr
-- generalized catamorphisms, zygomorphisms and paramorphisms
gcata :: (Functor f, Comonad n) =>
(forall a. f (n a) -> n (f a))
-> (f (n c) -> c) -> Mu f -> c
gcata dist phi = extr . cata (fmap phi . dist . fmap dupl)
zygo chi = gcata (fork (fmap outl) (chi . fmap outr))
para :: Functor f => (f (Prod (Mu f) c) -> c) -> Mu f -> c
para = zygo In
-- factorial, the *hard* way!
fac = para phi where
phi Z = suck zero
phi (S (Pair f n)) = mult f (suck n)
-- for convenience and testing
int = cata phi where
phi Z = 0
phi (S f) = 1 + f
instance Show (Mu N) where
show = show . int
Штатный профессор (преподает Haskell первокурсникам)
fac n = product [1..n]
Шаблоны D:Функциональный
template factorial(int n : 1)
{
const factorial = 1;
}
template factorial(int n)
{
const factorial =
n * factorial!(n-1);
}
или
template factorial(int n)
{
static if(n == 1)
const factorial = 1;
else
const factorial =
n * factorial!(n-1);
}
Используется вот так:
factorial!(5)
Java 1.6:рекурсивный, запоминающийся (для последующих вызовов)
private static Map<BigInteger, BigInteger> _results = new HashMap()
public static BigInteger factorial(BigInteger n){
if (0 >= n.compareTo(BigInteger.ONE))
return BigInteger.ONE.max(n);
if (_results.containsKey(n))
return _results.get(n);
BigInteger result = factorial(n.subtract(BigInteger.ONE)).multiply(n);
_results.put(n, result);
return result;
}
PowerShell
function factorial( [int] $n )
{
$result = 1;
if ( $n -gt 1 )
{
$result = $n * ( factorial ( $n - 1 ) )
}
$result
}
Вот однострочник:
$n..1 | % {$result = 1}{$result *= $_}{$result}
Удар:Рекурсивный
В bash и рекурсивный, но с дополнительным преимуществом, заключающимся в том, что он обрабатывает каждую итерацию в новом процессе.Максимум, что он может вычислить, равен !20 перед переполнением, но вы все равно можете запустить его для больших чисел, если вам наплевать на ответ и вы хотите, чтобы ваша система зависла ;)
#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));
