Katalanische Zahlen

36

Die katalanischen Zahlen ( OEIS ) sind eine Folge natürlicher Zahlen, die häufig in der Kombinatorik vorkommen.

Die n-te katalanische Zahl ist die Anzahl der Dyck-Wörter (ausgeglichene Zeichenfolgen in Klammern oder Klammern wie [[][]]; formal definiert als Zeichenfolge mit zwei Zeichen a und b, sodass jede Teilzeichenfolge, die am Anfang beginnt, die Nummer eines Zeichens hat, das größer oder gleich der Zahl ist von b Zeichen, und die gesamte Zeichenfolge hat die gleiche Anzahl von a und b Zeichen) mit der Länge 2n. Die n-te katalanische Zahl (für n> = 0) ist auch explizit definiert als:

Ab n = 0 lauten die ersten 20 katalanischen Zahlen:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190...

Herausforderung

Schreiben Sie ein vollständiges Programm oder eine Funktion, die eine nicht negative ganze Zahl n über STDIN oder eine akzeptable Alternative annimmt und die n-te katalanische Zahl ausgibt. Ihr Programm muss mindestens für die Eingänge 0-19 funktionieren.

I / O

Eingang

Ihr Programm muss Eingaben von STDIN, Funktionsargumenten oder einer der akzeptablen Alternativen für diesen Meta-Post erhalten. Sie können die eingegebene Zahl als Standard-Dezimalrepräsentation, unäre Repräsentation oder Byte lesen.

  • Wenn (und nur wenn) Ihre Sprache keine Eingabe von STDIN oder einer akzeptablen Alternative annehmen kann, kann sie Eingabe von einer fest codierten Variablen oder einem geeigneten Äquivalent im Programm annehmen.

Ausgabe

Ihr Programm muss die n-te katalanische Nummer für STDOUT, Funktionsergebnis oder eine der zulässigen Alternativen gemäß diesem Metapost ausgeben . Sie können die katalanische Zahl in ihrer Standarddarstellung als Dezimalzahl, als unäre Darstellung oder in Bytes ausgeben.

Die Ausgabe sollte aus der entsprechenden katalanischen Zahl bestehen, optional gefolgt von einer oder mehreren Zeilenumbrüchen. Es kann keine andere Ausgabe generiert werden, mit Ausnahme der konstanten Ausgabe des Interpreters Ihrer Sprache, die nicht unterdrückt werden kann (z. B. eine Begrüßung, ANSI-Farbcodes oder Einrückungen).


Es geht nicht darum, die Sprache zu finden, die am kürzesten ist. Hier geht es darum, das kürzeste Programm in jeder Sprache zu finden. Daher werde ich keine Antwort annehmen.

Bei dieser Herausforderung sind Sprachen, die neuer sind als die Herausforderung, akzeptabel , solange sie implementiert sind. Es ist erlaubt (und sogar empfohlen), diesen Dolmetscher für eine zuvor nicht implementierte Sprache selbst zu schreiben. Ansonsten müssen alle Standardregeln des eingehalten werden. Einsendungen in den meisten Sprachen werden in Bytes in einer geeigneten, bereits vorhandenen Codierung (normalerweise UTF-8) bewertet. Beachten Sie auch, dass integrierte Funktionen zur Berechnung der n-ten katalanischen Nummer zulässig sind.

Katalog

Das Stapel-Snippet am Ende dieses Beitrags generiert den Katalog aus den Antworten a) als Liste der kürzesten Lösungen pro Sprache und b) als Gesamt-Bestenliste.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

## Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:

## Perl, 43 + 2 (-p flag) = 45 bytes

Sie können den Namen der Sprache auch als Link festlegen, der dann im Snippet angezeigt wird:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

ein Spaghetto
quelle
Können wir einen Gleitkommawert anstatt einer ganzen Zahl ausgeben / zurückgeben?
Alex A.
@AlexA. Das ist akzeptabel.
ein Spaghetto
Soll es ein Tag oeis geben ?
Vi.
1
@Vi. Vor einiger Zeit gab es
eine
@Vi. Hier ist der Meta-Post: meta.codegolf.stackexchange.com/a/5546/8478 . Was einige Überlegungen betrifft, so können Sie Herausforderungen im OEIS-Stil mit einer Sequenz und einer Zahl oder Zahlentheorie recht zuverlässig finden . Ob die gegebene Sequenz tatsächlich ist in OEIS, ist völlig irrelevant für die Herausforderung.
Martin Ender

Antworten:

26

C 78 52 39 34 33 Bytes

Noch mehr C-Magie (danke xsot):

c(n){return!n?:(4+6./~n)*c(n-1);}

?: ist eine GNU-Erweiterung .


Diesmal durch Erweitern der folgenden Wiederholung (danke an xnor und Thomas Kwa):

Noch eine Rekursion

c(n){return n?(4+6./~n)*c(n-1):1;}

-(n+1)wird durch ersetzt ~n, was im Zweierkomplement äquivalent ist und 4 Bytes einspart.


Wieder als Funktion, aber dieses Mal unter Ausnutzung der folgenden Wiederholung:

wiederkehren

c(n){return n?2.*(2*n++-1)/n*c(n-2):1;}

c(n)gibt eine unendliche Rekursion für das Negative ein n, obwohl dies für diese Herausforderung nicht relevant ist.


Da der Aufruf einer Funktion eine akzeptable Alternative zu Konsolen-E / A darstellt:

c(n){double c=1,k=2;while(k<=n)c*=1+n/k++;return c;}

c(n)nimmt ein intund gibt ein zurück int.


Originaleintrag:

main(n){scanf("%d",&n);double c=1,k=2;while(k<=n)c*=1+n/k++;printf("%.0f",c);}

Anstatt die Definition direkt zu berechnen, wird die Formel wie folgt umgeschrieben:

umschreiben

Die Formel geht davon aus n >= 2, aber der Code berücksichtigt n = 0und n = 1auch.

In der C-Mess oben nund khaben die gleiche Rolle wie in der Formel, während cdas Produkt akkumuliert. Alle Berechnungen werden in Gleitkommazahlen ausgeführt double, was fast immer eine schlechte Idee ist, aber in diesem Fall sind die Ergebnisse mindestens bis n = 19 korrekt, also ist es in Ordnung.

float hätte 1 Byte gespart, leider ist es nicht genau genug.

Stefano Sanfilippo
quelle
Ich kann das jetzt nicht testen, aber ich denke, Sie können es weiter verkürzen:c(n){return!n?:(4+6./~n)*c(n-1);}
xsot
Danke @xsot, ich wusste es nicht ?:! Anscheinend ist es eine GNU C-Erweiterung, aber ich denke, dass sie noch qualifiziert ist.
Stefano Sanfilippo
23

Gelee , 4 Bytes

Ḥc÷‘

Probieren Sie es online!

Wie es funktioniert

Ḥc÷‘    Left argument: z

Ḥ       Compute 2z.
 c      Hook; apply combinations to 2z and z.
  ÷‘    Divide the result by z+1.
Dennis
quelle
1
Was bedeutet „Haken‘ Mittelwert Wie? cErhalten 2zund zals Argument?
xnor
@xnor Ein Haken bedeutet Funktionen, die wie folgt bewertet werden: f (x, g (x)). Wenn eine dyadische Funktion gefolgt von einer anderen dyadischen Funktion vorhanden ist, wertet der Parser die erste als Hook aus.
Lirtosiast
5
@ Tennis Ist das wirklich 4 Bytes? Mit diesen Nicht-ASCII-Zeichen sagt mothereff.in/byte-counter 9 Bytes
Luis Mendo
@ LuisMendo es ist wahrscheinlich eine andere Kodierung
undergroundmonorail
3
@LuisMendo Jelly verwendet einen eigenen benutzerdefinierten Kodierungsstandard, bei dem jedes Zeichen ein einzelnes Byte ist. Mit UTF-8 ist der Quellcode in der Tat 9 Bytes lang.
Dennis
11

CJam, 12 Bytes

ri_2,*e!,\)/

Probieren Sie es online aus.

Nach Eingabe von 11 müssen Sie Ihrer Java-VM mitteilen, dass sie mehr Arbeitsspeicher verwenden soll. Und ich würde eigentlich nicht empfehlen, über 11 hinauszugehen. Theoretisch funktioniert es jedoch für jedes N, da CJam Ganzzahlen mit beliebiger Genauigkeit verwendet.

Erläuterung

CJam hat keine eingebauten Binomialkoeffizienten, und die Berechnung aus drei Fakultäten erfordert viele Bytes. Wir müssen also etwas Besseres tun. :)

ri  e# Read input and convert it to integer N.
_   e# Duplicate.
2,  e# Push [0 1].
*   e# Repeat this N times, giving [0 1 0 1 ... 0 1] with N zeros and N ones.
e!  e# Compute the _distinct_ permutations of this array.
,   e# Get the number of permutations - the binomial. There happen to be 2n-over-n of
    e# of them. (Since 2n-over-n is the number of ways to choose n elements out of 2n, and
    e# and here we're choosing n positions in a 2n-element array to place the zeros in.)
\   e# Swap with N.
)/  e# Increment and divide the binomial coefficient by N+1.
Martin Ender
quelle
Das ist wirklich cool. +1
ein Spaghetto
Das ist schlau. Ich habe es mit der Berechnung der Fakultäten versucht. Es sind nur zwei der üblichen drei erforderlich, da zwei gleich sind. ri_2*m!1$m!_*/\)/In meiner Implementierung wurden immer noch 17 Byte ( ) verwendet. Das einzig gute ist, dass es viel schneller ist. :)
Reto Koradi
11

Mathematica, 16 13 Bytes

CatalanNumber

Eingebaute Amiriten: /

Nicht eingebaute Version (21 Bytes):

Binomial[2#,#]/(#+1)&

Eine binomiallose Version (25 Bytes):

Product[(#+k)/k,{k,2,#}]&
ein Spaghetto
quelle
10

TI-BASIC, 11 Bytes

(2Ans) nCr Ans/(Ans+1

Seltsamerweise hat nCr eine höhere Priorität als die Multiplikation.

Lirtosiast
quelle
10

Python 3, 33 Bytes

f=lambda n:0**n or(4+6/~n)*f(n-1)

Verwendet die Wiederholung

f(0) = 1
f(n) = (4-6/(n+1)) * f(n-1)

Der Basisfall von 0 wird als behandelt 0**n or, der als 1wann n==0endet und ansonsten den rekursiven Ausdruck auf der rechten Seite auswertet. Der bitweise Operator ~n==-n-1verkürzt den Nenner und spart Parens.

Python 3 wird für die Float-Division verwendet. Python 2 könnte dasselbe mit einem weiteren zu schreibenden Byte tun 6..

xnor
quelle
Warum nicht n<1lieber als 0**n?
Feersum
@feersum Es gibt Truefür n==0statt 1. Natürlich, True == 1aber True is not 1und es druckt anders. Ich würde erwarten, dass dies nicht erlaubt ist. Wissen Sie, ob wir diesbezüglich eine Entscheidung treffen?
Xnor
Ich glaube, dass es in Ordnung ist. isinstance(True, int) is TrueNach alldem.
Feersum
2
Ich denke, es ist immer noch zweifelhaft im allgemeinen Fall und auch hier, wo die Herausforderung die Ausgabe als Zahl oder deren Darstellung spezifiziert. Aber bis @quartata
xnor
7

J, 8 Bytes

>:%~]!+:

Dies ist ein monadischer Zug; es wird die Formel (2x nCr x) / (x + 1) verwendet. Probieren Sie es hier aus .

Lirtosiast
quelle
7

pl, 4 Bytes

☼ç▲÷

Probieren Sie es online aus.

Erläuterung

In pl nehmen Funktionen ihre Argumente vom Stapel und verschieben das Ergebnis zurück auf den Stapel. Normalerweise schlägt die Funktion im Hintergrund fehl, wenn nicht genügend Argumente auf dem Stapel vorhanden sind. Etwas Besonderes passiert jedoch, wenn die Anzahl der Argumente auf dem Stapel nicht der Arität der Funktion entspricht - die Eingabevariable _wird der Argumentliste hinzugefügt:

☼ç▲÷

☼      double: takes _ as the argument since there is nothing on the stack
 ç     combinations: since there is only one item on the stack (and arity is 2), it adds _ to the argument list (combinations(2_,_))
  ▲    increment last used var (_)
   ÷   divide: adds _ to the argument list again

In der Tat ist dies der Pseudocode:

divide(combinations(double(_),_),_+1);
ein Spaghetto
quelle
6

Sesos , 94 86 68 Bytes

8 Bytes durch Ändern des Faktors er von Version 1 auf Version 2.

18 Bytes durch Rechnen n!(n+1)!in einem Schritt. Weitgehend inspiriert von Dennis 'Primalitätstest-Algorithmus .

Hexdump:

0000000: 16f8de a59f17 a0ebba 7f4cd3 e05f3f cf0fd0 a0ebde  ..........L.._?......
0000015: b1c1bb 76fe18 8cc1bb 76fe1c e0fbda 390fda bde3d8  ...v.....v.....9.....
000002a: 000fbe af9d1b b47bc7 cfc11c b47bc7 cff1fa e07bda  .......{.....{.....{.
000003f: 39e83e cf07                                       9.>..

Probieren Sie es online!

Verwendet die Formel a(n) = (2n)! / (n!(n+1)!) .

  • The factorial-er: Version 1 (in-place, konstanter Speicher), Version 2 (In-Place, linearer Speicher)
  • Der Multiplikator: hier (an Ort und Stelle, konstantes Gedächtnis)
  • Der Teiler: hier (bleibt nicht stehen, wenn nicht teilbar)

Assembler

set numin
set numout
get
jmp,sub 1,fwd 1,add 1,fwd 2,add 2,rwd 3,jnz
fwd 1,add 1
jmp
  jmp,sub 1,rwd 1,add 1,rwd 1,add 1,rwd 1,add 1,fwd 3,jnz
  rwd 1,sub 1,rwd 1,sub 1,rwd 1
  jmp,sub 1,fwd 3,add 1,rwd 3,jnz
  fwd 1
jnz
fwd 3
jmp
  jmp
    sub 1,rwd 1
    jmp,sub 1,rwd 1,add 1,rwd 1,add 1,fwd 2,jnz
    rwd 2
    jmp,sub 1,fwd 2,add 1,rwd 2,jnz
    fwd 3
  jnz
  rwd 1
  jmp,sub 1,jnz
  rwd 1
  jmp,sub 1,fwd 2,add 1,rwd 2,jnz
  fwd 3
jnz 
fwd 1
jmp
  jmp,sub 1,fwd 1,add 1,fwd 1,add 1,rwd 2,jnz
  fwd 1,sub 1,fwd 1
  jmp,sub 1,rwd 2,add 1,fwd 2,jnz
  rwd 1
jnz
rwd 2
jmp
  jmp
    sub 1,fwd 1
    jmp,sub 1,fwd 1,add 1,fwd 1,add 1,rwd 2,jnz
    fwd 2
    jmp,sub 1,rwd 2,add 1,fwd 2,jnz
    rwd 3
  jnz
  fwd 1
  jmp,sub 1,jnz
  fwd 1
  jmp,sub 1,rwd 2,add 1,fwd 2,jnz
  rwd 3
jnz 
fwd 1
jmp
  fwd 1,add 1,rwd 3
  jmp,sub 1,fwd 1,add 1,fwd 1,sub 1,rwd 2,jnz
  fwd 1
  jmp,sub 1,rwd 1,add 1,fwd 1,jnz
  fwd 1
jnz
fwd 1
put

Brainfuck-Äquivalent

Dieses Retina-Skript wird verwendet, um das Brainfuck-Äquivalent zu generieren. Beachten Sie, dass es nur eine Ziffer als Befehlsargument akzeptiert und nicht prüft, ob ein Befehl in den Kommentaren enthalten ist.

[->+>>++<<<]>+
[[-<+<+<+>>>]<-<-<[->>>+<<<]>]>>>
[[-<[-<+<+>>]<<[->>+<<]>>>]<[-]<[->>+<<]>>>]>
[[->+>+<<]>->[-<<+>>]<]<<
[[->[->+>+<<]>>[-<<+>>]<<<]>[-]>[-<<+>>]<<<]>
[>+<<<[->+>-<<]>[-<+>]>]>
Undichte Nonne
quelle
5

Pyth, 8

/.cyQQhQ

Probieren Sie es online aus oder führen Sie die Test Suite aus

Erläuterung

/.cyQQhQ   ## implicit: Q = eval(input())
/     hQ   ## integer division by (Q + 1)
 .c        ## nCr
   yQ      ## use Q * 2 as n
     Q     ## use Q as r
FryAmTheEggman
quelle
5

Im Ernst, 9 Bytes

,;;u)τ╣E\

Hex Dump:

2c3b3b7529e7b9455c

Probieren Sie es online aus

Erläuterung:

,                   Read in evaluated input n
 ;;                 Duplicate it twice
   u)               Increment n and rotate it to bottom of stack
     τ╣             Double n, then push 2n-th row of Pascal's triangle
       E            Look-up nth element of the row, and so push 2nCn
        \           Divide it by the n+1 below it.
Quintopie
quelle
Sie können ein Byte speichern, indem Sie die Tatsache ausnutzen, dass die Zeilen des Pascalschen Dreiecks symmetrisch sind, also der Median der 2ndritten Zeile ist C(2n,n). Also: ,;u@τ╣║/für 8 Bytes.
Mego
Was? Ist 2nCn nicht das Maximum der 2. Reihe?
Quintopia
Ja, und es ist auch der Median. Also beide und Mwürde funktionieren.
Mego
@Mego Ich mache mir Sorgen um Ihre Implementierung des Medians, wenn etwas sowohl der Median als auch der Maximalwert sein kann, falls die Liste nicht alle dieselbe Nummer hat. Wenn Sie "in der Mitte der Liste" meinen, dann könnten Sie einen anderen Namen dafür wählen ...
quintopia
Ja, es ist die Mitte der Liste. Für sortierte Listen ist dies der typische statistische Median, für unsortierte Listen jedoch nur der mittlere (oder Durchschnitt von 2 mittleren Elementen)
Mego
4

JavaScript (ES6), 24 Byte

Basierend auf der Python-Antwort .

c=x=>x?(4+6/~x)*c(x-1):1

Wie es funktioniert

c=x=>x?(4+6/~x)*c(x-1):1
c=x=>                     // Define a function c that takes a parameter x and returns:
     x?               :1  //  If x == 0, 1.
       (4+6/~x)           //  Otherwise, (4 + (6 / (-x - 1)))
               *c(x-1)    //  times the previous item in the sequence.

Ich denke, das ist die kürzeste, die es geben kann, aber Vorschläge sind willkommen!

ETHproductions
quelle
4

Julia, 23 Bytes

n->binomial(2n,n)/(n+1)

Dies ist eine anonyme Funktion, die eine Ganzzahl akzeptiert und einen Gleitkommawert zurückgibt. Es wird die grundlegende Binomialformel verwendet. Um es zu nennen, geben Sie ihm einen Namen, z f=n->....

Alex A.
quelle
4

Matlab, 35 25 Bytes

@(n)nchoosek(2*n,n)/(n+1)

Oktave, 23 Bytes

@(n)nchoosek(2*n,n++)/n
costrom
quelle
2
Sie können @(n)anstelle von Funktion auch anonyme Funktionen verwenden.
FryAmTheEggman
Ich habe hier zuvor mehrere Antworten gesehen, auf die Arbeitsbereichsvariablen zugegriffen wurden (was impliziert, dass sie bereits vom Benutzer an einer anderen Stelle festgelegt wurden). Skripte in MATLAB / Octave können auch als einfache Schnipsel angezeigt werden. Ich habe es
vorerst
1
Sie können 2 weitere Bytes durch nachträgliches Inkrementieren abschneiden n:@(n)nchoosek(2*n,n++)/n
Becher
@beaker danke für den tipp! Es funktioniert jedoch nur in Octave und nicht in Matlab. Ich habe es also aufgeteilt
9.
@ costrom Das ist interessant. Ich denke .../++nauch nicht. : /
Becher
4

𝔼𝕊𝕄𝕚𝕟 3 Zeichen / 6 Bytes

Мƅï

Try it here (Firefox only).

Builtins ftw! Ich bin froh, dass ich math.js früh implementiert habe.

Bonuslösung, 12 Zeichen / 19 Bytes

Мơ 2*ï,ï)/⧺ï

Try it here (Firefox only).

Ja! 19. Byte!

Bewertet zu Pseudo-ES6 als:

nchoosek(2*input,input)/(input+1)
Mama Fun Roll
quelle
3

Haskell, 27 Bytes

g 0=1
g n=(4-6/(n+1))*g(n-1)

Eine rekursive Formel. Es muss einen Weg geben, um bei den Eltern zu sparen ...

Direkt unter dem Produkt war 2 Bytes länger:

g n=product[4-6/i|i<-[2..n+1]]
xnor
quelle
Wo liest dein Code von stdin oder schreibt er nach stdout?
User2845840
2
@ user2845840 Funktionen sind eine der akzeptablen Alternativen, auf die in der Spezifikation verwiesen wird .
Xnor
g(n-1)=> g$n-1spart ein Byte. Bearbeiten: eigentlich funktioniert das nicht, da dann die Formel als interpretiert wird (...*g) (n-1).
Solomonoffs Geheimnis
3

Dyalog APL, 9 Bytes

+∘1÷⍨⊢!+⍨

Dies ist ein monadischer Zug; es wird die Formel (2x nCr x) / (x + 1) verwendet. Probieren Sie es hier online aus .

Lirtosiast
quelle
3

C, 122 121 119 108 Bytes

main(j,v)char**v;{long long p=1,i,n=atoi(v[1]);for(j=0,i=n+1;i<2*n;p=(p*++i)/++j);p=n?p/n:p;printf("%d",p);}

Ich habe gcc (GCC) 3.4.4 (cygming special, gdc 0.12, mit dmd 0.125) verwendet, um in einer Windows-Cygwin-Umgebung zu kompilieren. Die Eingabe erfolgt über die Befehlszeile. Es ähnelt der Python-Lösung von Sherlock9, aber die Schleifen sind zu einer zusammengefasst, um einen Überlauf zu vermeiden und eine Ausgabe bis zur 20. katalanischen Zahl (n = 19) zu erhalten.

Cleblanc
quelle
1
Sie können das Leerzeichen nach dem Komma in der mainDefinition entfernen , um ein Byte zu speichern.
Alex A.
Schön, ich werde den Beitrag jetzt bearbeiten
Cleblanc
Sie können mit char**vanstatt 2 weitere Bytes speichern char *v[]. (Der Platz vorher *wird nicht benötigt, und die Typen sind gleichwertig.)
Mat
Klar, das funktioniert super. Dank Mat
Cleblanc
Hierfür werden einige Informationen von der Tippseite verwendet , um sie zu verkürzen. Beachten Sie jedoch, dass ich für Ideone einen Wert für hardcodiert habe n.
FryAmTheEggman
3

Javagony , 223 Bytes

public class C{public static int f(int a,int b){try{int z=1/(b-a);}catch(Exception e){return 1;}return a*f(a+1,b);}public static void main(String[]s){int m=Integer.parseInt(s[0])+1;System.out.println(f(m,2*m-1)/f(1,m)/m);}}

Voll ausgebaut:

public class C {
    public static int f(int a,int b){
        try {
            int z=1/(b-a);
        } catch (Exception e){
            return 1;
        }
        return a*f(a+1,b);
    }
    public static void main(String[] s){
        int m=Integer.parseInt(s[0])+1;
        System.out.println(f(m,2*m-1)/f(1,m)/m);
    }
}
Fehler
quelle
Esolangs Eintrag spielt keine Rolle - solange Sie einen Dolmetscher verwenden, der vor dem Wettbewerb erstellt wurde, ist alles gut und gültig.
Addison Crump
Wird sowieso nicht gewinnen ^^
Fehler
Es ist Java, also ja.
28.
1
@ Riker Nun, es ist schlimmer als Java.
Jakob
2

Japt, 16 Bytes

Sogar Mathematica ist kürzer. :-/

U*2ª1 o àU l /°U

Probieren Sie es online!

Ungolfed und Erklärung

U*2ª 1 o àU l /° U
U*2||1 o àU l /++U

         // Implicit: U = input number
U*2||1   // Take U*2. If it is zero, take 1.
o àU     // Generate a range of this length, and calculate all combinations of length U.
l /++U   // Take the length of the result and divide by (U+1).
         // Implicit: output result

Alternative Version, basierend auf der rekursiven Formel:

C=_?(4+6/~Z *C$(Z-1):1};$C(U
ETHproductions
quelle
2

Vitsy , 13 Bytes

VV2*FVF/V1+F/
V              Capture the input as a final global variable.
 V             Push it back.
  2*           Multiply it by 2
    F          Factorial.
     VF        Factorial of the input.
       /       Divide the second to top by the first.
        V1+    1+input
           F   Factorial.
            /  Divide.

Dies ist eine Funktion in Vitsy . Wie macht man ein Programm, das das macht? Verketten N. c:

Probieren Sie es online!

Addison Crump
quelle
2

Milchstraße 1.5.14 , 14 Bytes

':2K;*Ny;1+/A!

Erläuterung

'               # read input from the command line
 :              # duplicate the TOS
  2      1      # push integer to the stack
   K            # push a Pythonic range(0, TOS) as a list
    ;   ;       # swap the TOS and the STOS
     *          # multiply the TOS and STOS
      N         # push a list of the permutations of the TOS (for lists)
       y        # push the length of the TOS
          +     # add the STOS to the TOS
           /    # divide the TOS by the STOS
            A   # push the integer representation of the TOS
             !  # output the TOS

oder alternativ die wesentlich effizientere Version:


Milchstraße 1.5.14 , 22 Bytes

'1%{;K£1+k1-6;/4+*}A!

Erläuterung

'                      # read input from the command line
 1     1  1 6  4       # push integer to the stack
  %{  £           }    # for loop
    ;        ;         # swap the TOS and the STOS
     K                 # push a Pythonic range(0, TOS) as a list
        +       +      # add the TOS and STOS
         k             # push the negative absolute value of the TOS
           -           # subtract the STOS from the TOS
              /        # divide the TOS by the STOS
                 *     # multiply the TOS and the STOS
                   A   # push the integer representation of the TOS
                    !  # output the TOS

Verwendung

python3 milkyway.py <path-to-code> -i <input-integer>
Zach Gates
quelle
2

Clojure / ClojureScript, 53 Byte

(defn c[x](if(= 0 x)1(*(c(dec x))(- 4(/ 6(inc x))))))

Clojure kann beim Golfen ziemlich frustrierend sein. Es ist zwar sehr prägnant, aber immer noch gut lesbar, aber einige der raffinierteren Funktionen sind sehr ausführlich. (inc x)ist idiomatischer als (+ x 1)und "fühlt" sich prägnanter an, speichert jedoch keine Zeichen. Und Ketten von Operationen zu schreiben ist schöner als (->> x inc (/ 6) (- 4)), aber es ist tatsächlich länger, als es nur auf hässliche Weise zu tun.

MattPutnam
quelle
2

Prolog, 42 Bytes

Die Verwendung von Rekursion ist bei Prolog fast immer der richtige Weg.

Code:

0*1.
N*X:-M is N-1,M*Y,X is(4-6/(N+1))*Y.

Beispiel:

19*X.
X = 1767263190.0

Probieren Sie es hier online aus

Emigna
quelle
Definieren Sie das *Symbol hier neu?
Paŭlo Ebermann
@PaŭloEbermann nicht genau. Ich definiere ein neues dyadisches Prädikat mit dem Namen *. Ich kann immer noch das reguläre Rechnen verwenden. Im obigen Programm ist M * Y mein definiertes Prädikat, während (4-6 / (N + 1)) * Y reguläre Multiplikation ist.
Emigna
Es ist etwas kürzer als es als p (X, Y) zu schreiben: - das ist schön für Code-Golf.
Emigna
2

Oktave, 22 Bytes

@(n)prod(4-6./(2:n+1))
Alephalpha
quelle
2

Ceylon, 60 Bytes

Integer c(Integer n)=>(1:n).fold(1)((p,i)=>p*(n+i)/i)/(n+1);

Dies funktioniert bis C 30 , da Ceylons Ganzzahlen mit 64-Bit-Zahlen signiert sind (C 31 hat einen Überlauf und wird als -4050872099593203 berechnet).

Ich weiß nicht, ob Ceylon über integrierte höhere mathematische Funktionen verfügt, aber der Import des richtigen Pakets würde wahrscheinlich länger dauern, als dies nur zu Fuß zu berechnen.

// Catalan number C_n
//
// Question:  http://codegolf.stackexchange.com/q/66127/2338
// My answer: http://codegolf.stackexchange.com/a/66425/2338

Integer c(Integer n) =>
        // sequence of length n, starting at 1.
        (1:n)
        // starting with 1, for each element i, multiply the result
        // of the previous step by (n+i) and then divide it by i.
    .fold(1)((p, i) => p * (n + i) / i)
        // divide the result by n+1.
        / (n + 1);
Paŭlo Ebermann
quelle
2

R 35 28 16 Bytes

numbers::catalan

Bearbeiten: Verwenden Sie das integrierte Zahlenpaket.

mnel
quelle
2

MATL , 8 Bytes

2*GXnGQ/

Probieren Sie es online!

Erläuterung

2*     % take number n as input and multiply by 2
G      % push input again
Xn     % compute "2*n choose n"
G      % push input again
Q      % add 1
/      % divide
Luis Mendo
quelle
2

05AB1E , 6 Bytes

Dxcr>/

Erläuterung:

Code:     Stack:               Explanation:

Dxcr>/

D         [n, n]               # Duplicate of the stack. Since it's empty, input is used.
 x        [n, n, 2n]           # Pops a, pushes a, a * 2
  c       [n, n nCr 2n]        # Pops a,b pushes a nCr b
   r      [n nCr 2n, n]        # Reverses the stack
    >     [n nCr 2n, n + 1]    # Increment on the last item
     /    [(n nCr 2n)/(n + 1)] # Divides the last two items
                               # Implicit, nothing has printed, so we print the last item
Adnan
quelle
2

R, 28 Bytes

Kein Paket verwenden, also etwas länger als eine vorherige Antwort

choose(2*(n=scan()),n)/(n+1)
Frédéric
quelle