Erstellen Sie das kürzeste Programm oder die kürzeste Funktion, die die Fakultät einer nicht negativen Ganzzahl findet.

Die Fakultät, dargestellt mit, !ist als solche definiert

Im Klartext ist die Fakultät von 0 1 und die Fakultät von n, wobei n größer als 0 ist, das n-fache der Fakultät von eins weniger als n.

Ihr Code sollte die Eingabe und Ausgabe mit Standardmethoden durchführen.

Bedarf:

• Verwendet keine eingebauten Bibliotheken, die die Fakultät berechnen können (dies schließt jede Form von ein eval)
• Kann Fakultäten für Zahlen bis zu 125 berechnen
• Kann die Fakultät für die Zahl 0 (gleich 1) berechnen
• Wird in weniger als einer Minute für Nummern bis zu 125 ausgeführt

Die kürzeste Einsendung gewinnt, bei Stimmengleichheit gewinnt die Antwort mit den meisten Stimmen.

Golfscript - 12 Zeichen

{,1\{)*}/}:f

Erste Schritte mit Golfscript - Factorial Schritt für Schritt

Ist hier etwas für die Leute, die versuchen, golfscript zu erlernen. Voraussetzung ist ein grundlegendes Verständnis von Golfscript und die Fähigkeit, die Golfscript-Dokumentation zu lesen.

Also wollen wir unser neues Tool Golfscript ausprobieren . Es ist immer gut, mit etwas Einfachem zu beginnen, also fangen wir mit Fakultät an. Hier ist ein erster Versuch, der auf einem einfachen imperativen Pseudocode basiert:

# pseudocode: f(n){c=1;while(n>1){c*=n;n--};return c}
{:n;1:c;{n 1>}{n c*:c;n 1-:n;}while c}:f

Leerzeichen werden im Golfscript sehr selten verwendet. Der einfachste Trick, um Whitespace zu entfernen, ist die Verwendung verschiedener Variablennamen. Jedes Token kann als Variable verwendet werden (siehe Syntaxseite ). Nützliche Token zu verwenden , als Variablen sind Sonderzeichen wie |, &, ?- in der Regel alles , was nicht an anderer Stelle im Code verwendet. Diese werden immer als einzelne Zeichen-Token analysiert. Im Gegensatz ndazu benötigen Variablen wie ein Leerzeichen, um eine Zahl auf den Stapel zu verschieben. Zahlen sind im Wesentlichen vorinitialisierte Variablen.

Wie immer wird es Aussagen geben, die wir ändern können, ohne das Endergebnis zu beeinflussen. In golfscript wertet alles wahr , außer 0, [], ""und {}(siehe diese ). Hier können wir die Schleifenausgangsbedingung in einfach ändern {n}(wir schleifen eine zusätzliche Zeit und beenden, wenn n = 0 ist).

Wie beim Golfspielen jeder Sprache hilft es, die verfügbaren Funktionen zu kennen. Zum Glück ist die Liste für golfscript sehr kurz. Wir können ändern 1-, (um einen anderen Charakter zu speichern. Gegenwärtig sieht der Code so aus: (Wir könnten 1anstelle von |hier verwenden, wenn wir wollten, was die Initialisierung fallen lassen würde.)

{:n;1:|;{n}{n|*:|;n(:n;}while|}:f

Es ist wichtig, den Stapel gut zu verwenden, um die kürzesten Lösungen zu erhalten (üben üben üben). Wenn Werte nur in einem kleinen Codesegment verwendet werden, ist es im Allgemeinen möglicherweise nicht erforderlich, sie in Variablen zu speichern. Durch Entfernen der aktiven Produktvariablen und einfaches Verwenden des Stapels können wir eine ganze Reihe von Zeichen speichern.

{:n;1{n}{n*n(:n;}while}:f

Hier ist noch etwas zum Nachdenken. Wir entfernen die Variable naus dem Stapel am Ende des Schleifenkörpers, verschieben sie jedoch sofort danach. In der Tat, bevor die Schleife beginnt, entfernen wir sie auch vom Stapel. Wir sollten es stattdessen auf dem Stapel belassen, und wir können die Schleifenbedingung leer lassen.

{1\:n{}{n*n(:n}while}:f

Vielleicht können wir die Variable sogar komplett entfernen. Dazu müssen wir die Variable immer auf dem Stapel halten. Dies bedeutet, dass wir am Ende der Bedingungsprüfung zwei Kopien der Variablen auf dem Stapel benötigen, damit wir sie nach der Prüfung nicht verlieren. Das bedeutet, dass wir 0nach dem Ende der Schleife eine Redundanz auf dem Stack haben, die aber leicht zu beheben ist.

Dies führt uns zu unserer optimalen whileSchleifenlösung!

{1\{.}{.@*\(}while;}:f

Jetzt wollen wir das noch kürzer machen. Das offensichtliche Ziel sollte das Wort sein while. In der Dokumentation gibt es zwei praktikable Alternativen - entfalten und tun . Wenn Sie die Wahl zwischen verschiedenen Routen haben, versuchen Sie, die Vorteile von beiden abzuwägen. Unfold ist so gut wie eine while-Schleife. Als Schätzung werden wir also die 5 Zeichen whileum 4 verringern /. Was dowir schneiden whilevon 3 Zeichen, und erhalten die beiden Blöcke zu fusionieren, die einen anderen Charakter oder zwei retten könnte.

Die Verwendung einer doSchleife hat tatsächlich einen großen Nachteil . Da die Bedingungsprüfung nach einmaliger Ausführung des Körpers durchgeführt wird, ist der Wert von 0falsch, sodass möglicherweise eine if-Anweisung erforderlich ist. Ich sage Ihnen jetzt, dass die Entfaltung kürzer ist (einige Lösungen dowerden am Ende bereitgestellt). Probieren Sie es aus, der Code, den wir bereits haben, erfordert nur minimale Änderungen.

{1\{}{.@*\(}/;}:f

Toll! Unsere Lösung ist jetzt superkurz und wir sind hier fertig, oder? Nee. Dies ist 17 Zeichen und J hat 12 Zeichen. Gib niemals eine Niederlage zu!

Jetzt denkst du mit ... Rekursion

Rekursion bedeutet , dass wir müssen eine Verzweigungsstruktur verwenden. Leider, aber da Fakultät so prägnant rekursiv ausgedrückt werden kann, scheint dies eine gangbare Alternative zur Iteration zu sein.

# pseudocode: f(n){return n==0?n*f(n-1):1}
{:n{n.(f*}1if}:f # taking advantage of the tokeniser

Nun, das war einfach - hätten wir früher eine Rekursion versucht, hätten wir uns vielleicht nicht einmal die Verwendung einer whileSchleife angeschaut ! Trotzdem sind wir nur bei 16 Zeichen.

Arrays

Arrays werden in der Regel auf zwei Arten erstellt - die Verwendung [und ]Zeichen oder mit der ,Funktion. Bei Ausführung mit einer Ganzzahl oben im Stapel wird ,ein Array dieser Länge mit arr [i] = i zurückgegeben.

Für die Iteration über Arrays haben wir drei Möglichkeiten:

1. {block}/: schieben, blockieren, schieben, blockieren, ...
2. {block}%: [push, block, push, block, ...] (dies hat einige Nuancen, zB Zwischenwerte werden vor jedem Push vom Stack entfernt)
3. {block}*: drücken, drücken, blockieren, drücken, blockieren, ...

In der Golfscript-Dokumentation wird beispielhaft {+}*der Inhalt eines Arrays summiert. Dies legt nahe, dass wir {*}*das Produkt eines Arrays erhalten können.

{,{*}*}:f

Ganz so einfach ist es leider nicht. Alle Elemente sind um eins ( [0 1 2]anstelle von [1 2 3]) deaktiviert. Wir können {)}%dieses Problem beheben.

{,{)}%{*}*}:f

Nicht ganz. Dies behandelt Null nicht richtig. Wir können (n + 1)! / (N + 1) berechnen, um dies zu korrigieren, obwohl dies viel zu viel kostet.

{).,{)}%{*}*\/}:f

Wir können auch versuchen, n = 0 im selben Bucket wie n = 1 zu behandeln. Dies ist tatsächlich extrem kurz zu tun, versuchen Sie, so schnell wie möglich zu trainieren.

Nicht so gut ist die Sortierung, bei 7 Zeichen: [1\]$1=. Beachten Sie, dass diese Sortiertechnik nützliche Funktionen hat, z. B. das Auferlegen von Grenzen für eine Zahl (z. B. `[0 \ 100] $ 1 =).
Hier ist der Gewinner mit nur 3 Zeichen:.! +

Wenn wir das Inkrement und die Multiplikation im selben Block haben wollen, sollten wir jedes Element im Array durchlaufen. Da wir kein Array erstellen {)*}/, sollten wir es verwenden , was uns zur kürzesten Implementierung von Fakultät bringt! Bei einer Länge von 12 Zeichen ist dies mit J verknüpft!

{,1\{)*}/}:f

Bonuslösungen

Beginnen Sie mit einer einfachen ifLösung für eine doSchleife:

{.{1\{.@*\(.}do;}{)}if}:f

Wir können ein paar mehr herausholen. Ein bisschen kompliziert, also müssen Sie sich selbst davon überzeugen, dass diese Arbeiten funktionieren. Stellen Sie sicher, dass Sie alle diese verstehen.

{1\.!!{{.@*\(.}do}*+}:f
{.!{1\{.@*\(.}do}or+}:f
{.{1\{.@*\(.}do}1if+}:f

Eine bessere Alternative ist die Berechnung von (n + 1)! / (N + 1), wodurch die Notwendigkeit einer ifStruktur entfällt .

{).1\{.@*\(.}do;\/}:f

Die kürzeste doLösung benötigt hier jedoch ein paar Zeichen, um 0 zu 1 und alles andere für sich selbst zuzuordnen - wir brauchen also keine Verzweigung. Diese Art der Optimierung ist sehr leicht zu übersehen.

{.!+1\{.@*\(.}do;}:f

Für alle Interessierten gibt es hier einige alternative rekursive Lösungen mit der gleichen Länge wie oben:

{.!{.)f*0}or+}:f
{.{.)f*0}1if+}:f
{.{.(f*}{)}if}:f

* Hinweis: Ich habe noch nicht viele der Code-Teile in diesem Beitrag getestet. Sie können sich also jederzeit informieren, wenn Fehler auftreten.

Haskell, 17

f n=product[1..n]

Python - 27

Einfach einfach:

f=lambda x:0**x or x*f(x-1)

APL (4)

×/∘⍳

Funktioniert als anonyme Funktion:

    ×/∘⍳ 5
120

Wenn Sie ihm einen Namen geben möchten, 6 Zeichen:

f←×/∘⍳

J (12)

Eine Standarddefinition in J:

f=:*/@:>:@i.

Weniger als 1 Sekunde für 125!

Z.B:

 f 0
 1
 f 5
 120
  f 125x
 1882677176888926099743767702491600857595403
 6487149242588759823150835315633161359886688
 2932889495923133646405445930057740630161919
 3413805978188834575585470555243263755650071
 31770880000000000000000000000000000000

Golfscript - 13 Zeichen (SYM)

definiert die Funktion !

{),()\{*}/}:!             # happy robot version \{*}/ 

alternative 13 char version

{),()+{*}*}:! 

Die gesamte Programmversion besteht aus 10 Zeichen

~),()+{*}*

Testfälle dauern weniger als 1/10 Sekunde:

Eingang:

0!

Ausgabe

1

Eingang

125!

Ausgabe

188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000

Perl 6: 13 Zeichen

$f={[*]1..$_}

[*]ist dasselbe wie Haskell productund 1..$_zählt von 1 bis $_zum Argument hoch .

Matlab, 15

f=@(x)prod(1:x)

Testfälle

>> f(0)
ans =
     1
>> f(4)
ans =
    24
>> tic,f(125),toc
ans =
  1.8827e+209
Elapsed time is 0.000380 seconds.

Python, 28 Bytes

f=lambda x:x/~x+1or x*f(x-1)

(basierend auf Alexandru's Lösung)

MATL , 2 Bytes

:p

Erklärt:

:    % generate list 1,2,3,...,i, where i is an implicit input
p    % calculate the product of of all the list entries (works on an empty list too)

Probieren Sie es online!

Ruby - 21 Zeichen

f=->n{n>1?n*f[n-1]:1}

Prüfung

irb(main):009:0> f=->n{n>1?n*f[n-1]:1}
=> #<Proc:0x25a6d48@(irb):9 (lambda)>
irb(main):010:0> f[125]
=> 18826771768889260997437677024916008575954036487149242588759823150835315633161
35988668829328894959231336464054459300577406301619193413805978188834575585470555
24326375565007131770880000000000000000000000000000000

Java, 85 Zeichen

BigInteger f(int n){return n<2?BigInteger.ONE:new BigInteger(""+n).multiply(f(n-1));}

PostScript, 26 Zeichen

/f{1 exch -1 1{mul}for}def

Beispiel:

GS> 0 f =
1
GS> 1 f =
1
GS> 8 f =
40320

Die Funktion selbst benötigt nur 21 Zeichen. der Rest ist, es an eine Variable zu binden. Um ein Byte zu speichern, kann man es auch wie folgt an eine Ziffer binden:

GS> 0{1 exch -1 1{mul}for}def
GS> 8 0 load exec =
40320

JavaScript, 25

function f(n)!n||n*f(n-1)

CoffeeScript, 19

f=(n)->!n||n*f(n-1)

Gibt trueim Fall von n = 0 zurück, aber JavaScript wird dies sowieso auf 1 setzen.

Ruby - 30 29 Zeichen

def f(n)(1..n).inject 1,:*end

Prüfung

f(0) -> 1
f(5) -> 120

F #: 26 Zeichen

Es gibt keine eingebaute Produktfunktion in F #, aber Sie können eine mit einer Falte erstellen

let f n=Seq.fold(*)1{1..n}

C #, 20 oder 39 Zeichen, abhängig von Ihrer Sichtweise

Als traditionelle Instanzmethode (39 Zeichen; hier getestet ):

double f(int x){return 2>x?1:x*f(x-1);}

Als Lambda-Ausdruck (20 Zeichen, siehe Haftungsausschluss; hier getestet ):

f=x=>2>x?1:x*f(x-1);

Wir müssen doubleda 125 verwenden! == 1,88 * 10 ²⁰⁹ , was viel höher ist als ulong.MaxValue.

Haftungsausschluss zur Anzahl der Zeichen in der Lambda-Version:

Wenn Sie in einem C # -Lambda rekursiv arbeiten, müssen Sie das Lambda offensichtlich in einer benannten Variablen speichern, damit es sich selbst aufrufen kann. Im Gegensatz zu (z. B.) JavaScript muss jedoch ein selbstreferenzierendes Lambda in einer vorherigen Zeile deklariert und initialisiert worden sein. Sie können die Funktion nicht in derselben Anweisung aufrufen, in der Sie die Variable deklarieren und / oder initialisieren.

Mit anderen Worten, das funktioniert nicht :

Func<int,double> f=x=>2>x?1:x*f(x-1); //Error: Use of unassigned local variable 'f'

Aber das macht :

Func<int,double> f=null;            
f=x=>2>x?1:x*f(x-1);  

Es gibt keinen guten Grund für diese Einschränkung, da fdie Zuordnung zum Zeitpunkt der Ausführung nicht aufgehoben werden kann. Die Notwendigkeit der Func<int,double> f=null;Zeile ist eine Eigenheit von C #. Ob dies dazu führt, dass es fair ist, es bei der Anzahl der Zeichen zu ignorieren, liegt beim Leser.

CoffeeScript, 21 19 Zeichen für echt

f=(x)->+!x||x*f x-1

Hier getestet: http://jsfiddle.net/0xjdm971/

Brachylog , 7 6 Bytes

Indem Sie einen Bereich bilden und ihn multiplizieren

-1-Byte-Tanks zu Ovs, die die Idee haben, die Funktion max () zu verwenden

;1⌉⟦₁×

Erläuterung

;1          --  If n<1, use n=1 instead (zero case)
  ⟦₁        --      Construct the range [1,n]
    ×       --      return the product of said range

Probieren Sie es online!

Brachylog , 10 9 Bytes

Rekursion

≤1|-₁↰;?×

Erläuterung

            --f(n):
≤1          --  if n ≤ 1: return 1
|           --  else:
 -₁↰        --      f(n-1)
    ;?×     --            *n

Probieren Sie es online!

C (39 Zeichen)

double f(int n){return n<2?1:n*f(n-1);}

D: 45 Zeichen

T f(T)(T n){return n < 2 ? 1 : n * f(n - 1);}

Besser leserlich:

T f(T)(T n)
{
    return n < 2 ? 1 : n * f(n - 1);
}

Eine coolere (wenn auch längere) Version ist die Vorlage, die beim Kompilieren alles erledigt ( 64 Zeichen ):

template F(int n){static if(n<2)enum F=1;else enum F=n*F!(n-1);}

Besser leserlich:

template F(int n)
{
    static if(n < 2)
        enum F = 1;
    else
        enum F = n * F!(n - 1);
}

Namensgebende Vorlagen sind jedoch ziemlich ausführlich, so dass Sie sie im Codegolf nicht wirklich gut verwenden können. D ist bereits ausführlich genug in Bezug auf die Anzahl der Zeichen, um für Code-Golf ziemlich schlecht zu sein (obwohl es tatsächlich wirklich gut darin ist, die Gesamtprogrammgröße für größere Programme zu reduzieren). Es ist jedoch meine Lieblingssprache, also denke ich, dass ich genauso gut versuchen kann zu sehen, wie gut ich es beim Codegolf machen kann, auch wenn GolfScript-Typen daran gebunden sind, es zu cremen.

PowerShell - 36

Naiv:

filter f{if($_){$_*(--$_|f}else{1}}

Prüfung:

> 0,5,125|f
1
120
1,88267717688893E+209

Scala, 39 Zeichen

def f(x:BigInt)=(BigInt(1)to x).product

Die meisten Zeichen stellen sicher, dass BigInts verwendet werden, damit die Anforderung für Werte bis zu 125 erfüllt wird.

Javascript, ES6 17

f=n=>n?n*f(n-1):1

ES6:

• Pfeil funktion

PowerShell, 42 Byte

(2 Zeichen mit Filter anstelle von Funktion gespeichert )

filter f($x){if(!$x){1}else{$x*(f($x-1))}}

Ausgabe:

PS C:\> f 0
1
PS C:\> f 5
120
PS C:\> f 1
1
PS C:\> f 125
1.88267717688893E+209

Schläger (Schema) 40 35 29 Bytes

Berechnet 0! 1 zu sein und berechnet 125! in 0 Sekunden nach Timer. Regelmäßige rekursive Annäherung

(define(f n)(if(= n 0)1(* n(f(- n 1)))))

Neue Version gegen gängiges Lispeln: Multipliziert alle Elemente einer Liste (wie bei dieser Haskell-Lösung)

(λ(n)(apply *(build-list n add1)))

Neuere Version, um die andere Schemalösung zu übertreffen und die andere Racket-Lösung zu berechnen, indem Sie foldl anstelle von apply und range anstelle von buildlist verwenden

(λ(n)(foldl * n(range 1 n)))

Mornington Crescent , Jahre 1827 Jahre 1698 Zeichen

Ich wollte heute eine neue Sprache lernen, und das ist es, worauf ich gelandet bin ... (Warum mache ich das für mich selbst?) Dieser Beitrag gewinnt keine Preise, übertrifft aber alle 0 anderen Antworten mit der dieselbe Sprache!

Take Northern Line to Bank
Take Central Line to Holborn
Take Piccadilly Line to Heathrow Terminals 1, 2, 3
Take Piccadilly Line to Acton Town
Take District Line to Acton Town
Take District Line to Parsons Green
Take District Line to Bank
Take District Line to Parsons Green
Take District Line to Acton Town
Take District Line to Hammersmith
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Acton Town
Take Piccadilly Line to Bounds Green
Take Piccadilly Line to Acton Town
Take Piccadilly Line to Bounds Green
Take Piccadilly Line to Acton Town
Take District Line to Acton Town
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Parsons Green
Take District Line to Notting Hill Gate
Take Circle Line to Notting Hill Gate
Take Circle Line to Bank
Take Circle Line to Temple
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Bank
Take District Line to Upney
Take District Line to Upminster
Take District Line to Hammersmith
Take District Line to Upminster
Take District Line to Upney
Take District Line to Bank
Take Circle Line to Embankment
Take Circle Line to Embankment
Take Northern Line to Angel
Take Northern Line to Moorgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Moorgate
Take Circle Line to Moorgate
Take Northern Line to Mornington Crescent

Probieren Sie es online!

Jeder, der durch London gereist ist, wird das natürlich sofort verstehen, daher bin ich mir sicher, dass ich keine vollständige Erklärung geben muss.

Die meiste Arbeit zu Beginn besteht in der Behandlung des 0-Falls. Nachdem ich das Produkt auf 1 initialisiert habe, kann ich damit das Maximum (Eingabe, 1) berechnen, um die neue Eingabe zu erhalten. Dabei wird die Tatsache ausgenutzt, dass 0! = 1! Dann kann die Hauptschleife beginnen.

(BEARBEITEN: Eine ganze Reihe von Reisen wurden durch Entfernen der 1 von "Heathrow Terminals 1, 2, 3" gespeichert, anstatt sie durch Teilen der 7 (Schwestern) durch sich selbst zu generieren. Ich benutze auch eine billigere Methode, um die -1 in zu generieren der nächste Schritt.)

Dekrementierung ist in Mornington Crescent teuer (obwohl billiger als die Tube selbst). Um die Effizienz zu steigern, erzeuge ich ein -1, indem ich das NOT einer analysierten 0 nehme und das für einen Großteil der Schleife in Hammersmith speichere.

Befunge - 2x20 = 40 Zeichen

0\:#v_# 1#<\$v *\<
    >:1-:#^_$>\:#^_$

Dies ist eine Funktion, bei der es sich um einen eigenständigen Codeblock handelt, bei dem der Umlauf nicht verwendet wird. Sie müssen das Argument oben auf dem Stapel platzieren und dann von links oben nach rechts eingeben. Die Funktion wird von rechts unten nach rechts mit dem Ergebnis oben auf dem Stapel beendet.

ZB um die Fakultät von 125 zu berechnen

555**   0\:#v_# 1#<\$v *\<
            >:1-:#^_$>\:#^_$    .@

Testen 0

0   0\:#v_# 1#<\$v *\<
        >:1-:#^_$>\:#^_$    .@

J - 6 Zeichen

*/>:i.

Zählt das? Ich weiß, dass es dem früheren J-Beispiel sehr ähnlich ist, aber es ist etwas kürzer :)

Ich bin ein Anfänger mit J, aber es macht bis jetzt viel Spaß!

In C (23 Zeichen)

Dies missbraucht die GCC-"Funktion", die die letzte Zuweisung als Rückgabe zählt, wenn keine Rückgabe angegeben ist.

f(a){a=a>0?f(a-1)*a:1;}

In richtigem C 28 Zeichen

f(a){return a>0?f(a-1)*a:1;}

Kona ( 11 6)

*/1.+!

K arbeitet von rechts nach links (größtenteils), also zählen wir auf x(bilden eine Liste / ein Array von Zahlen von 0bis x-1), addieren 1dazu (listen Bereiche 0bis x) und multiplizieren dann alle Zahlen miteinander. Wenn es nicht erforderlich wäre, zu berechnen 125!, könnte ich 1 weiteres Byte einsparen, indem ich .neben "" entferne 1. Auf jeden Fall 125! wird in Millisekunden berechnet:

  */1.+!125.
1.882677e+209