Algorithmes Factoriels dans différentes langues
https://stackoverflow.com/questions/23930
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je veux voir toutes les différentes manières que vous pouvez trouver pour un sous-programme ou un programme factoriel.L’espoir est que n’importe qui puisse venir ici et voir s’il souhaite apprendre une nouvelle langue.
Idées :
- De procédure
- Fonctionnel
- Orienté objet
- Une doublure
- Obscurci
- Excentrique
- Mauvais code
- Polyglotte
Fondamentalement, je veux voir un exemple de différentes manières d'écrire un algorithme et à quoi elles ressembleraient dans différentes langues.
Veuillez le limiter à un exemple par entrée.Je vous permettrai d'avoir plus d'un exemple par réponse, si vous essayez de mettre en évidence un style, un langage spécifique ou simplement une idée bien pensée qui se prête à être contenue dans un seul article.
La seule véritable exigence est qu'il doit trouver la factorielle d'un argument donné, dans toutes les langues représentées.
Sois créatif!
Ligne directrice recommandée :
# Language Name: Optional Style type
- Optional bullet points
Code Goes Here
Other informational text goes here
J'accompagnerai occasionnellement et modifierai toute réponse qui n'a pas un formatage décent.
La solution
Polyglotte:5 langues, toutes utilisant des bignums
J'ai donc écrit un polyglotte qui fonctionne dans les trois langues dans lesquelles j'écris souvent, ainsi qu'un de mon autre réponse à cette question et un que je viens d'apprendre aujourd'hui.C'est un programme autonome, qui lit une seule ligne contenant un entier non négatif et imprime une seule ligne contenant sa factorielle.Les Bignums sont utilisés dans toutes les langues, donc la factorielle maximale calculable dépend uniquement des ressources de votre ordinateur.
- Perl:utilise le package bignum intégré.Courir avec
perl FILENAME. - Haskell:utilise des bignums intégrés.Courir avec
runhugs FILENAMEou l'équivalent de votre compilateur préféré. - C++:nécessite GMP pour le support bignum.Pour compiler avec g++, utilisez
g++ -lgmpxx -lgmp -x c++ FILENAMEpour établir un lien avec les bonnes bibliothèques.Après la compilation, exécutez./a.out.Ou utilisez l'équivalent de votre compilateur préféré. - connerie:J'ai écrit du support bignum dans ce post.En utilisant Distribution classique de Muller, compiler avec
bf < FILENAME > EXECUTABLE.Rendez la sortie exécutable et exécutez-la.Ou utilisez votre distribution préférée. - Espaces:utilise le support bignum intégré.Courir avec
wspace FILENAME.
Modifier: ajout de Whitespace comme cinquième langue.D'ailleurs, fais pas enveloppez le code avec <code> Mots clés;cela brise les espaces.De plus, le code est beaucoup plus joli en largeur fixe.
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*/;}
Autres conseils
mdrcode :
désolé, je n'ai pas pu résister 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
C'est l'un des algorithmes les plus rapides, jusqu'à 170!.Il échoue inexplicablement au-delà de 170 !, et c'est relativement lent pour les petites factorielles, mais pour les factorielles entre 80 et 170 c'est incroyablement rapide par rapport à de nombreux algorithmes.
curl http://www.google.com/search?q=170!
Il existe également une interface en ligne, essayez-le maintenant !
Faites-moi savoir si vous trouvez un bug ou une implémentation plus rapide pour les grandes factorielles.
MODIFIER:
Cet algorithme est légèrement plus lent, mais donne des résultats au-delà de 170 :
curl http://www58.wolframalpha.com/input/?i=171!
Cela les simplifie également dans diverses autres représentations.
C++ :Métaprogrammation de modèles
Utilise le hack enum classique.
template<unsigned int n>
struct factorial {
enum { result = n * factorial<n - 1>::result };
};
template<>
struct factorial<0> {
enum { result = 1 };
};
Usage.
const unsigned int x = factorial<4>::result;
La factorielle est calculée entièrement au moment de la compilation en fonction du paramètre de modèle n.Par conséquent, factorial<4>::result est une constante une fois que le compilateur a fait son travail.
Espaces
. . . . . . . . . . . . . . . . . . . . . . . . . .
Il était difficile de l'afficher correctement ici, mais maintenant j'ai essayé de le copier à partir de l'aperçu et cela fonctionne.Vous devez saisir le numéro et appuyer sur Entrée.
Je trouve les implémentations suivantes tout simplement hilarantes :
L'évolution d'un programmeur Haskell
Evolution d'un programmeur Python
Apprécier!
Recherche C# :
Rien à calculer vraiment, il suffit de chercher.Pour l'étendre, ajoutez 8 nombres supplémentaires au tableau et les entiers de 64 bits sont à leur limite.Au-delà, une classe BigNum est nécessaire.
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];
}
Paresseux K
Vos cauchemars de programmation purement fonctionnelle deviennent réalité !
Le seul Langage de programmation ésotérique Turing-complet qui a:
- Une base, un noyau et des bibliothèques purement fonctionnels --- en fait, voici l'API complète : SKI
- Non lambda même!
- Non Nombres ou listes nécessaires ou autorisées
- Pas de récursion explicite mais pour l'instant, permet la récursivité
- Un simple flux paresseux infini-mécanisme d'E/S basé sur
Voici le code factoriel dans toute sa splendeur entre parenthèses :
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)
Caractéristiques:
- Pas de soustraction ni de conditions
- Imprime toutes les factorielles (si vous attendez assez longtemps)
- Utilise une deuxième couche de chiffres Church pour convertir la Nième factorielle en N !astérisques suivis d'une nouvelle ligne
- Utilise le Combinateur Y pour la récursion
Si vous souhaitez essayer de le comprendre, voici le code source Scheme à exécuter via le compilateur 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))
(pour les définitions appropriées de Y, cons, 1, 10, 42, 1+ et *).
MODIFIER:
Factorielle K paresseuse en décimal
(10 Ko de charabia sinon je le collerais).Par exemple, à l'invite Unix :
$ echo "4" | ./lazy facdec.lazy
24
$ echo "5" | ./lazy facdec.lazy
120
Plutôt lent pour les nombres supérieurs, disons, à 5.
Le code est en quelque sorte volumineux car nous devons inclure code de bibliothèque pour toutes nos propres primitives (code écrit en Brumeux, un interpréteur de calcul lambda et un compilateur LC-to-Lazy K écrit en Haskell).
XSLT1.0
Le fichier d'entrée, factoriel.xml:
<?xml version="1.0"?>
<?xml-stylesheet href="factorial.xsl" type="text/xsl" ?>
<n>
20
</n>
Le fichier XSLT, factoriel.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>
Enregistrez les deux fichiers dans le même répertoire et ouvrez factoriel.xml dans IE.
Python:Fonctionnel, mono-liner
factorial = lambda n: reduce(lambda x,y: x*y, range(1, n+1), 1)
NOTE:
- Il prend en charge les grands entiers.Exemple:
print factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915\
608941463976156518286253697920827223758251185210916864000000000000000000000000
- Cela ne fonctionne pas pour n < 0.
APL (bizarre/one-liner):
×/⍳X
- ⍳X développe X dans un tableau d'entiers 1..X
- ×/ multiplie chaque élément du tableau
Ou avec l'opérateur intégré :
!X
Source: http://www.webber-labs.com/mpl/lectures/ppt-slides/01.ppt
Perl6
sub factorial ($n) { [*] 1..$n }
Je connais à peine Perl6.Mais je suppose que ça [*] l'opérateur est le même que celui de Haskell product.
Ce code s'exécute sur Carlins, et peut-être Perroquet (Je ne l'ai pas vérifié.)
Modifier
Ce code fonctionne également.
sub postfix:<!> ($n) { [*] 1..$n }
# This function(?) call like below ... It looks like mathematical notation.
say 10!;
Assemblage x86-64 :De procédure
Vous pouvez appeler cela depuis C (testé uniquement avec GCC sur Linux amd64).L'assemblage a été assemblé avec 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
De manière récursive dans Inform 7
(cela vous rappelle COBOL car c'est pour écrire des aventures textuelles ;la police proportionnelle est délibérée) :
Pour décider quel nombre est la factorielle de (n - un nombre) :
si n est zéro, choisissez-en un ;
sinon, décidez de la factorielle de (n moins un) fois n.
Si vous souhaitez réellement appeler cette fonction ("phrase") depuis un jeu, vous devez définir une règle d'action et de grammaire :
"Le jeu factoriel" [cela doit être la première ligne de la source]
Il y a une pièce.[il doit y en avoir au moins un !]
La factorisation est une action s'appliquant à un nombre.
Comprenez « factorielle [un nombre] » comme une factorisation.
Effectuer une factorisation :
Soit n la factorielle du nombre compris ;
Dites « C'est [n] ».
C# :LINQ
public static int factorial(int n)
{
return (Enumerable.Range(1, n).Aggregate(1, (previous, value) => previous * value));
}
Erlang :queue récursive
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
+++++
>+<[[->>>>+<<<<]>>>>[-<<<<+>>+>>]<<<<>[->>+<<]<>>>[-<[->>+<<]>>[-<<+<+>>>]<]<[-]><<<-]
Écrit par Michael Reitzenstein.
BASIQUE:vieille école
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
Lot (NT) :
@echo off
set n=%1
set result=1
for /l %%i in (%n%, -1, 1) do (
set /a result=result * %%i
)
echo %result%
Usage:C:>factorial.bat 15
F#:Fonctionnel
Direct:
let rec fact x =
if x < 0 then failwith "Invalid value."
elif x = 0 then 1
else x * fact (x - 1)
Devenir chic :
let fact x = [1 .. x] |> List.fold_left ( * ) 1
Prologue récursif
fac(0,1).
fac(N,X) :- N1 is N -1, fac(N1, T), X is N * T.
Prologue récursif de queue
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).
rubis récursif
(factorial=Hash.new{|h,k|k*h[k-1]})[1]=1
usage:
factorial[5]
=> 120
Schème
Voici une définition récursive simple :
(define (factorial x)
(if (= x 0) 1
(* x (factorial (- x 1)))))
Dans Scheme, les fonctions récursives de queue utilisent un espace de pile constant.Voici une version de factorielle récursive :
(define factorial
(letrec ((fact (lambda (x accum)
(if (= x 0) accum
(fact (- x 1) (* accum x))))))
(lambda (x)
(fact x 1))))
Des exemples bizarres ?Et si vous utilisiez la fonction gamma !Depuis, Gamma n = (n-1)!.
OCaml :Utiliser Gamma
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)))
Programmeur Haskell de première année
fac n = if n == 0
then 1
else n * fac (n-1)
Sophomore Haskell Programmer, au MIT (schéma étudié en première année)
fac = (\(n) ->
(if ((==) n 0)
then 1
else ((*) n (fac ((-) n 1)))))
Programmeur de Haskell junior (Player Peano de début)
fac 0 = 1
fac (n+1) = (n+1) * fac n
Un autre programmeur de Haskell junior (lire que les modèles N + K sont «une partie dégoûtante de Haskell» [1] et ont rejoint les motifs «Ban N + K» -Molement [2])
fac 0 = 1
fac n = n * fac (n-1)
Programmeur Haskell senior (voté pour Nixon Buchanan Bush - «se penche à droite»)
fac n = foldr (*) 1 [1..n]
Un autre programmeur Haskell senior (voté pour McGovern Biafra Nader - «Lean à gauche»)
fac n = foldl (*) 1 [1..n]
Encore un autre programmeur Haskell senior (penché tellement à droite qu’il est revenu à gauche !)
-- using foldr to simulate foldl
fac n = foldr (\x g n -> g (x*n)) id [1..n] 1
Mémoriser le programmeur Haskell (prend du Ginkgo Biloba tous les jours)
facs = scanl (*) 1 [1..]
fac n = facs !! n
Programmeur Haskell inutile (ahem) « sans points » (a étudié à Oxford)
fac = foldr (*) 1 . enumFromTo 1
Programmeur Haskell itératif (ancien programmeur 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
Programmeur Haskell itératif d’une ligne (ancien programmeur APL et C)
fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))
Accumulation du programmateur Haskell (jusqu’à un point culminant rapide)
facAcc a 0 = a
facAcc a n = facAcc (n*a) (n-1)
fac = facAcc 1
Programmeur Haskell de continuation-passage (a élevé des lapins dans les premières années, puis a déménagé dans le New Jersey)
facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)
fac = facCps id
Programmeur Boy Scout Haskell (aime faire des nœuds ;Toujours « révérencieux », il appartient à l’Église du Petit Point Fixe [8])
y f = f (y f)
fac = y (\f n -> if (n==0) then 1 else n * f (n-1))
Programmeur combinatoire Haskell (évite les variables, voire l’obscurcissement ;tout ce curry n'est qu'une phase, même si cela gêne rarement)
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)))
Programmeur Haskell d’encodage de liste (préfère compter en unaire)
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
Programmateur d’interprétation Haskell (n’a jamais « rencontré une langue » qu’il n’aimait pas)
-- 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)))
Programmeur Haskell statique (il le fait avec classe, il a ce fundep Jones !D’après « S’amuser avec les dépendances fonctionnelles » 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
Programmeur Haskell débutant (L’enseignement supérieur tend à libérer de préoccupations mesquines sur, par exemple, l’efficacité des entiers matériels)
-- 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
Programmeur origamiste Haskell (commence toujours par le « pli de base de l’oiseau »)
-- (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
Programmeur Haskell à tendance cartésienne (préfère la cuisine grecque, évite les trucs indiens épicés ;inspiré du « 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)
doctoratProgrammeur Haskell (Il a mangé tellement de bananes que ses yeux se sont écarquillés, maintenant il a besoin de nouvelles lentilles !)
-- 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
Programmeur post-doc Haskell (d’après les « Schémas de récursivité des Comonades » d’Uustalu, Vene et Pardo [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
Professeur titulaire (enseignement du haskell aux étudiants de première année)
fac n = product [1..n]
Modèles D :Fonctionnel
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);
}
Utilisé comme ceci :
factorial!(5)
Java1.6 :récursif, mémorisé (pour les appels ultérieurs)
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
}
Voici un one-liner :
$n..1 | % {$result = 1}{$result *= $_}{$result}
Frapper:Récursif
En bash et récursif, mais avec l'avantage supplémentaire de traiter chaque itération dans un nouveau processus.Le maximum qu'il peut calculer est de !20 avant de déborder, mais vous pouvez toujours l'exécuter pour de gros nombres si vous ne vous souciez pas de la réponse et souhaitez que votre système tombe ;)
#!/bin/bash
echo $(($1 * `( [[ $1 -gt 1 ]] && ./$0 $(($1 - 1)) ) || echo 1`));
