Algoritmos fatoriais em diferentes idiomas
https://stackoverflow.com/questions/23930
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Quero ver todas as diferentes maneiras que você pode criar para uma sub-rotina ou programa fatorial.A esperança é que qualquer pessoa possa vir aqui e ver se deseja aprender um novo idioma.
Ideias:
- Processual
- Funcional
- Orientado a Objeto
- Um forro
- Ofuscado
- Excêntrico
- Código ruim
- Poliglota
Basicamente, quero ver um exemplo de diferentes maneiras de escrever um algoritmo e como seriam em diferentes linguagens.
Limite-o a um exemplo por entrada.Permitirei que você tenha mais de um exemplo por resposta, se estiver tentando destacar um estilo, linguagem específico ou apenas uma ideia bem pensada que possa ser colocada em um post.
O único requisito real é encontrar o fatorial de um determinado argumento, em todas as linguagens representadas.
Seja criativo!
Diretriz recomendada:
# Language Name: Optional Style type
- Optional bullet points
Code Goes Here
Other informational text goes here
Ocasionalmente irei editar qualquer resposta que não tenha uma formatação decente.
Solução
Poliglota:5 idiomas, todos usando bignums
Então, escrevi um poliglota que funciona nos três idiomas em que escrevo com frequência, bem como um da minha outra resposta a esta pergunta e um que acabei de aprender hoje.É um programa independente, que lê uma única linha contendo um número inteiro não negativo e imprime uma única linha contendo seu fatorial.Bignums são usados em todas as linguagens, portanto o fatorial computável máximo depende apenas dos recursos do seu computador.
- Perl:usa o pacote bignum integrado.Correr com
perl FILENAME. - Haskell:usa bignums integrados.Correr com
runhugs FILENAMEou o equivalente do seu compilador favorito. - C++:requer GMP para suporte bignum.Para compilar com g++, use
g++ -lgmpxx -lgmp -x c++ FILENAMEpara vincular às bibliotecas certas.Depois de compilar, execute./a.out.Ou use o equivalente do seu compilador favorito. - merda cerebral:Eu escrevi um suporte bignum em esta postagem.Usando Distribuição clássica de Muller, ajuntar com
bf < FILENAME > EXECUTABLE.Torne a saída executável e execute-a.Ou use sua distribuição favorita. - Espaço em branco:usa suporte bignum integrado.Correr com
wspace FILENAME.
Editar: adicionou espaço em branco como quinto idioma.Aliás, faça não envolva o código com <code> Tag;isso quebra o espaço em branco.Além disso, o código parece muito melhor em largura fixa.
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*/;}
Outras dicas
lolcódigo:
desculpe, não pude resistir 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
Este é um dos algoritmos mais rápidos, até 170!.Isto falhar inexplicavelmente além de 170!, e é relativamente lento para fatoriais pequenos, mas para fatoriais entre 80 e 170 é incrivelmente rápido em comparação com muitos algoritmos.
curl http://www.google.com/search?q=170!
Há também uma interface online, experimente agora!
Deixe-me saber se você encontrar um bug ou uma implementação mais rápida para grandes fatoriais.
EDITAR:
Este algoritmo é um pouco mais lento, mas fornece resultados além de 170:
curl http://www58.wolframalpha.com/input/?i=171!
Também os simplifica em várias outras representações.
C++:Metaprogramação de modelos
Usa o hack enum clássico.
template<unsigned int n>
struct factorial {
enum { result = n * factorial<n - 1>::result };
};
template<>
struct factorial<0> {
enum { result = 1 };
};
Uso.
const unsigned int x = factorial<4>::result;
O fatorial é calculado completamente em tempo de compilação com base no parâmetro n do modelo.Portanto, factorial<4>::result é uma constante depois que o compilador termina seu trabalho.
Espaço em branco
. . . . . . . . . . . . . . . . . . . . . . . . . .
Foi difícil exibi-lo corretamente aqui, mas agora tentei copiá-lo da visualização e funcionou.Você precisa inserir o número e pressionar enter.
Acho as seguintes implementações simplesmente hilárias:
A evolução de um programador Haskell
Evolução de um programador Python
Aproveitar!
Pesquisa C#:
Nada para calcular realmente, basta pesquisar.Para estendê-lo, adicione outros 8 números à tabela e os números inteiros de 64 bits estarão no limite.Além disso, é necessária uma classe 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];
}
Preguiçoso K
Seus pesadelos de pura programação funcional se tornam realidade!
A única Linguagem de programação esotérica Turing-completa isso tem:
- Uma base, núcleo e bibliotecas puramente funcionais --- na verdade, aqui está a API completa: S K I
- Não lambdas até!
- Não números ou listas necessárias ou permitidas
- Nenhuma recursão explícita, mas ainda assim, permite recursão
- Um simples fluxo preguiçoso infinitomecanismo de E/S baseado em
Aqui está o código fatorial em toda a sua glória entre parênteses:
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)
Características:
- Sem subtração ou condicionais
- Imprime todos os fatoriais (se você esperar o suficiente)
- Usa uma segunda camada de algarismos da Igreja para converter o N-ésimo fatorial em N!asteriscos seguidos por uma nova linha
- Usa o Combinador Y para recursão
Caso você tenha interesse em tentar entendê-lo, aqui está o código fonte do Scheme para rodar através do compilador Lazier:
(lazy-def '(fac input)
'((Y (lambda (f n a) ((lambda (b) ((cons 10) ((b (cons 42)) (f (1+ n) b))))
(* a n)))) 1 1))
(para definições adequadas de Y, contras, 1, 10, 42, 1+ e *).
EDITAR:
Fatorial K preguiçoso em decimal
(10 KB de jargão ou então eu colaria).Por exemplo, no prompt do Unix:
$ echo "4" | ./lazy facdec.lazy
24
$ echo "5" | ./lazy facdec.lazy
120
Bastante lento para números acima, digamos, 5.
O código está meio inchado porque temos que incluir código de biblioteca para todas as nossas próprias primitivas (código escrito em Nebuloso, um interpretador de cálculo lambda e compilador LC-to-Lazy K escrito em Haskell).
XSLT 1.0
O arquivo de entrada, fatorial.xml:
<?xml version="1.0"?>
<?xml-stylesheet href="factorial.xsl" type="text/xsl" ?>
<n>
20
</n>
O arquivo XSLT, fatorial.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>
Salve os dois arquivos no mesmo diretório e abra fatorial.xml no IE.
Pitão:Funcional, de uma linha
factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)
OBSERVAÇÃO:
- Suporta números inteiros grandes.Exemplo:
print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000
- Não funciona para n < 0.
APL (excêntrico/one-liner):
×/⍳X
- ⍳X expande X em uma matriz de inteiros 1..X
- ×/ multiplica todos os elementos do array
Ou com o operador integrado:
!X
Fonte: http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt
Perl6
sub factorial ($n) { [*] 1..$n }
Eu mal sei sobre Perl6.Mas eu acho que isso [*] operador é igual ao de Haskell product.
Este código é executado em Pugs, e talvez Papagaio (Eu não verifiquei.)
Editar
Este código também funciona.
sub postfix:<!> ($n) { [*] 1..$n }
# This function(?) call like below ... It looks like mathematical notation.
say 10!;
Montagem x86-64:Processual
Você pode chamar isso de C (testado apenas com GCC no Linux AMD64).A montagem foi montada com 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
Recursivamente no Informe 7
(lembra o COBOL porque é para escrever aventuras de texto;fonte proporcional é deliberada):
Para decidir qual número é o fatorial de (n - um número):
se n for zero, escolha um;
caso contrário, decida o fatorial de (n menos um) vezes n.
Se você quiser realmente chamar esta função ("frase") de um jogo, você precisa definir uma ação e uma regra gramatical:
"O jogo fatorial" [esta deve ser a primeira linha da fonte]
Há um quarto.[tem que haver pelo menos um!]
A fatorial é uma ação aplicada a um número.
Entenda "fatorial [um número]" como fatorial.
Faça a fatoração:
Seja n o fatorial do número compreendido;
Diga "É [n]".
C#:LINQ
public static int factorial(int n)
{
return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
}
Erlang:cauda recursiva
fac(0) -> 1;
fac(N) when N > 0 -> fac(N, 1).
fac(1, R) -> R;
fac(N, R) -> fac(N - 1, R * N).
Haskel:
ones = 1 : ones
integers = head ones : zipWith (+) integers (tail ones)
factorials = head integers : zipWith (*) factorials (tail integers)
Brainf * ck
+++++
>+<[[->>>>+<<<<]>>>>[-<<<<+>>+>>]<<<<>[->>+<<]<>>>[-<[->>+<<]>>[-<<+<+>>>]<]<[-]><<<-]
Escrito por Michael Reitzenstein.
BÁSICO:moda antiga
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
Lote (NT):
@echo off
set n=%1
set result=1
for /l %%i in (%n%, -1, 1) do (
set /a result=result * %%i
)
echo %result%
Uso:C:>fatorial.bat 15
F#:Funcional
Direto:
let rec fact x =
if x < 0 then failwith "Invalid value."
elif x = 0 then 1
else x * fact (x - 1)
Ficando sofisticado:
let fact x = [1 .. x] |> List.fold_left ( * ) 1
Prólogo recursivo
fac(0,1).
fac(N,X) :- N1 is N -1, fac(N1, T), X is N * T.
Prólogo recursivo de cauda
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).
rubi recursivo
(factorial=Hash.new{|h,k|k*h[k-1]})[1]=1
uso:
factorial[5]
=> 120
Esquema
Aqui está uma definição recursiva simples:
(define (factorial x)
(if (= x 0) 1
(* x (factorial (- x 1)))))
No esquema, as funções recursivas de cauda usam espaço de pilha constante.Aqui está uma versão do fatorial que é recursiva na cauda:
(define factorial
(letrec ((fact (lambda (x accum)
(if (= x 0) accum
(fact (- x 1) (* accum x))))))
(lambda (x)
(fact x 1))))
Exemplos excêntricos?Que tal usar a função gama!Desde, Gamma n = (n-1)!.
OCaml:Usando Gama
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)))
Programador Haskell calouro
fac n = if n == 0
then 1
else n * fac (n-1)
Sophomore Haskell Programmer, no MIT (Estudado Esquema como calouro)
fac = (\(n) ->
(if ((==) n 0)
then 1
else ((*) n (fac ((-) n 1)))))
Programador Junior Haskell (Player Peano Iniciante)
fac 0 = 1
fac (n+1) = (n+1) * fac n
Outro programador júnior de Haskell (leia que os padrões N+K são "uma parte nojenta de Haskell" [1] e se juntou ao "Ban N+K Patterns"-Movidem [2])
fac 0 = 1
fac n = n * fac (n-1)
Programador sênior de Haskell (votado em Nixon Buchanan Bush - "Suba direita")
fac n = foldr (*) 1 [1..n]
Outro programador sênior de Haskell (votado no McGovern Biafra Nader - "inclina -se à esquerda")
fac n = foldl (*) 1 [1..n]
Outro programador sênior de Haskell (inclinado à direita, ele voltou à esquerda novamente!)
-- using foldr to simulate foldl
fac n = foldr (\x g n -> g (x*n)) id [1..n] 1
Memomando o programador Haskell (leva a Ginkgo Biloba diariamente)
facs = scanl (*) 1 [1..]
fac n = facs !! n
Programador Haskell (AHEM) sem sentido (AHEM) (estudado em Oxford)
fac = foldr (*) 1 . enumFromTo 1
Programador Iterativo Haskell (ex -programador 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
Programador de uma liner itera Haskell (ex-programador APL e C)
fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))
Acumulando o programador Haskell (construindo um clímax rápido)
facAcc a 0 = a
facAcc a n = facAcc (n*a) (n-1)
fac = facAcc 1
Programador de Haskell que passa continuação (coelhos elevados nos primeiros anos, depois mudou-se para Nova Jersey)
facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)
fac = facCps id
Programador Haskell Scout Haskell (gosta de amarrar nós;Sempre "reverente", ele pertence à igreja do ponto menos fixo [8])
y f = f (y f)
fac = y (\f n -> if (n==0) then 1 else n * f (n-1))
Programador combinatório Haskell (evita variáveis, se não ofuscar;todo esse curry é apenas uma fase, embora raramente atrapalhe)
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)))
Programador Haskell de codificação de lista (prefere contar em UNARY)
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
Programador interpretativo Haskell (nunca "conheceu uma linguagem" que ele não gostava)
-- 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)))
Programador estático Haskell (ele faz isso com a classe, ele tem o FUNEPEP JONES!Depois de “Diversão com Dependências Funcionais” de Thomas Hallgren [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
O graduado iniciante Haskell Programmer (o ensino de pós-graduação tende a libertar um das preocupações mesquinhas sobre, por exemplo, a eficiência de números inteiros à base de hardware)
-- 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
Programador de origamista Haskell (sempre começa com a “dobra básica do pássaro”)
-- (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
O programador de Haskell, inclinado cartesiano (prefere comida grega, evita o material indiano picante;inspirado em “Sorting Morphisms” de Lex Augusteijn [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)
Ph.D.Programador Haskell (comeu tantas bananas que seus olhos se incomodaram, agora ele precisa de novas lentes!)
-- 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
Programador pós-doutorado Haskell (de "Esquemas de Recursão de Uustalu, Vene e Pardo das 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
Professor titular (ensinando Haskell para calouros)
fac n = product [1..n]
Modelos D:Funcional
template factorial(int n : 1)
{
const factorial = 1;
}
template factorial(int n)
{
const factorial =
n * factorial!(n-1);
}
ou
template factorial(int n)
{
static if(n == 1)
const factorial = 1;
else
const factorial =
n * factorial!(n-1);
}
Usado assim:
factorial!(5)
Java 1.6:recursivo, memorizado (para chamadas subsequentes)
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
}
Aqui está uma frase:
$n..1 | % {$result = 1}{$result *= $_}{$result}
Bash:Recursivo
Em bash e recursivo, mas com a vantagem adicional de lidar com cada iteração em um novo processo.O máximo que ele pode calcular é !20 antes de transbordar, mas você ainda pode executá-lo para números grandes se não se importar com a resposta e quiser que seu sistema caia;)
#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));
