Die n-te Motzkin-Zahl ist die Anzahl der Pfade von (0, 0) bis (n, 0), wobei jeder Schritt die Form (1, -1), (1, 0) oder (1, 1) hat, und der Pfad geht nie unter y = 0.
Hier ist eine Illustration dieser Pfade für n = 1, 2, 3, 4 aus dem obigen Link:
Die gewünschte Sequenz ist OEIS A001006 . OEIS hat einige andere Charakterisierungen der Sequenz.
Sie erhalten eine positive ganze Zahl n als Eingabe. Sie sollten die n-te Motzkin-Nummer ausgeben.
Hier sind die Motzkin-Nummern 1 bis 10:
1, 2, 4, 9, 21, 51, 127, 323, 835, 2188
Alle Standardeingabe- und Ausgabemethoden sind zulässig. Es gelten Standardlücken .
Das ist Code Golf. Wenigste Bytes gewinnt.
Antworten:
MATL , 13 bis
14BytesBeispiel:
EDIT (16. Juni 2017): Sie können es online ausprobieren! Beachten Sie auch, dass in modernen Sprachversionen (die diese Herausforderung nachholen) die entfernt werden
i
könnten.Erläuterung
Ziemlich einfach, wenn man die Äquivalenz (siehe Gleichung (10)) mit der hypergeometrischen Funktion verwendet :
Aus der Definition der hypergeometrischen Funktion
Es ist klar, dass die Reihenfolge der ersten beiden Argumente vertauscht werden kann, wodurch ein Byte eingespart wird.
quelle
Retina ,
59-58BytesNimmt unäre Eingaben auf . Eingabe 7 (dh
1111111
) dauert eine Weile, ist aber noch in weniger als einer Minute abgeschlossen. Ich würde nicht viel weiter gehen.Probieren Sie es online aus.
Erläuterung
Eine andere Charakterisierung der Motzkin-Zahlen ist die Anzahl der Saiten aus drei verschiedenen Zeichen, von denen zwei korrekt ausgeglichen sind (daher die enge Beziehung zu den katalanischen Zahlen, die ohne das dritte Zeichen, das unabhängig vom Ausgleich ist, identisch sind).
.NET die Bilanzgruppen sind ziemlich gut an richtig abgestimmt Saiten zu erfassen, so dass wir einfach erzeugen alle Strings der Länge
N
(mit_
,<
und>
als die drei Zeichen) und dann wir zählen , wie viele von denen sind richtig ausgewogen. ZB fürN = 4
die gültigen Zeichenfolgen sind:Gegenüber der Definition in der Challenge
_
entspricht dies einem(1,0)
Schritt<
nach(1,1)
und>
nach(1,-1)
.Der eigentliche Code
:
wird als Trennzeichen zwischen den verschiedenen Zeichenfolgen verwendet. Der zweite reguläre Ausdruck ist nur eine Golfform des standardmäßigen .NET- regulären Ausdrucks für ausgeglichene Saiten .Zu beachten ist, dass
:
in jedem Schritt nur eine einzige Zeichenfolge zwischen Zeichenfolgen eingefügt wird, die zweite Regex jedoch mit einer führenden und einer nachfolgenden Zeichenfolge übereinstimmt:
(und da Übereinstimmungen sich nicht überlappen können, bedeutet dies, dass benachbarte Zeichenfolgen, die aus einer Vorlage im letzten Schritt generiert wurden, nicht beide übereinstimmen können ). Dies ist jedoch kein Problem, da höchstens einer dieser drei Werte jemals übereinstimmen kann:_
übereinstimmt, ist das Präfix ohne ""_
bereits richtig ausgeglichen und /<
oder>
würde das Gleichgewicht aufheben.>
Streichhölzer, wird der String ausgeglichen mit , dass>
, so_
oder<
würde dieses Gleichgewicht abwerfen.<
können niemals ausgeglichen werden.quelle
Python 2, 51 Bytes
Verwendet die Formel von Mathworld
Speichert Zeichen , indem Sie den
M[n-1]
Begriff in die Summierung wiek=n-1
, das gibtM[-1]*M[n-1]
, mitM[-1]=1
als Teil der Anfangsbedingung.Edit: Ein Buchstabe kürzer, der die Summe rekursiv schreibt:
Andere Ansätze, die sich als länger herausstellten:
quelle
Pyth, 15 Bytes
Dies definiert eine Funktion
y
. Probieren Sie es online aus: DemonstrationErläuterung:
Sei
y[n]
dien
-te Motzkin-Zahl. Ich berechney[n]
mit der FormelBeachten Sie, dass der erste Vektor größer als der zweite ist (außer bei der Berechnung
y[0]
). In diesem Fall ignoriert Pyth automatisch die 1 am Ende des ersten Vektors, sodass beide Vektoren gleich lang sind.Diese Formel ist eine Variation einer der in OEIS aufgelisteten Formeln. Es kann ein bisschen dumm sein. Aufgrund der 1 am Ende des ersten Vektors (wodurch die Längen ungleich sind) muss ich der Rekursion eigentlich keinen Basisfall geben. Und ich hatte die Hoffnung, dass die beiden
+...1
irgendwie golfen können. Es stellt sich heraus, dass ich nicht kann.Sie können eine ähnliche Rekursion mit einem Punktprodukt von Vektoren gleicher Länge definieren und den Basisfall
y[0] = 1
mit derselben Byteanzahl definieren.quelle
CJam (20 Bytes)
Online-Demo
Wie Mego in den Kommentaren zu dieser Frage bemerkte, hängt dies sehr eng mit den katalanischen Zahlen zusammen: Ändern Sie den Index
.5
in1
und versetzen Sie ihn um eins (oder entfernen Sie ihn.5
ganz und lassen Sie den Index unverändert), um katalanische Zahlen zu erhalten.Die verwendete Wiederholung ist
von der OEIS-Seite. Die entsprechende Wiederholung für die katalanischen Nummern ist als aufgeführt
quelle
Im Ernst, 21 Bytes
Leiht sich Code aus der Catalan Numbers-Lösung von quintopia aus , insbesondere die Verbesserung, die ich in den Kommentaren vorgenommen habe.
Ich benutze die folgende Formel:
Da
nCk
ist 0 fürk > n
, summiere ich den ganzen Weg zun-1
, da diese Werte alle 0 sein werden und somit die Summe nicht beeinflussen.Probieren Sie es online aus
Erläuterung:
quelle
C(n, 2*k)
macht was jetztC(n,k) = nCk
oder die Anzahl der Elementkombinationenk
aus einem Elementpooln
.R, 64 Bytes
Verwendet auch die Mathworld-Formel von @ xnors Python-Antwort . Dank der Vorrangregeln
2:n-2
ist äquivalent zu0:(n-2)
.Testfälle:
quelle
Mathematica,
31-30BytesZum Spaß gibt es hier eine 37-Byte-Version
und 52-Byte-Version
quelle
Jelly ,
171413 BytesDies verwendet die Wiederholungsrelation aus @ PeterTaylors Antwort . Probieren Sie es online!
Wie es funktioniert
quelle
Mathematica,
444234 BytesEine 35-Byte-Version:
quelle
Pari / GP ,
383626 BytesProbieren Sie es online!
Verwenden Sie Gleichung (11) von MathWorld :
woher( nk)2 ist ein Trinomialkoeffizient . Per Definition,( nk)2 ist der Koeffizient von xn + k in der Expansion von ( 1 + x + x2)n .
quelle
);;7 2D$ⁿ$)╡$÷
. Ich werde es nicht als Antwort posten, da die Sprache neuer ist als die Frage.05AB1E ,
1312 BytesProbieren Sie es online!
Während die meisten Antworten eine Formel oder eine Wiederholungsrelation verwenden, ist dies ein einfacher Zählansatz.
Jeder mögliche Pfad durch das Gitter wird durch die Liste seiner y-Koordinaten dargestellt. Für n Segmente gibt es insgesamt (n + 1) Punkte, aber der erste und der letzte Punkt sind notwendigerweise 0, so dass (n-1) Punkte angegeben werden müssen.
Wir haben jetzt eine Liste von Pfaden (die anfängliche und die letzte 0 sind noch nicht enthalten). Konstruktionsbedingt unterschreitet keiner von ihnen den Wert 0. Einige von ihnen haben jedoch unzulässige Steigungen (z. B. von 0 auf 2 springen), sodass wir sie herausfiltern müssen.
Ÿ
ist der Schwankungsbereich eingebaut. Wenn es ein Paar nicht benachbarter Zahlen gibt, werden die fehlenden Zahlen ausgefüllt (z. B. wird [0, 2] zu [0, 1, 2]). Nur legale Pfade bleiben unverändert.Eine vielleicht intuitivere Möglichkeit, nach illegalen Gefällen zu
üαà
suchen, wäre (setzen Sie das Maximum der paarweisen absoluten Unterschiede auf 1). Hierbei fehlt jedoch der flache Pfad [0, 0, ... 0], dessen Korrektur ein zusätzliches Byte kostet.Beachten Sie schließlich, dass der tatsächliche Code verwendet,
.ø
wo diese Erklärung verwendet0.ø
. Anstatt den Pfad mit 0en zu umgeben, wird die implizite Eingabe mit zwei Kopien des Pfads umgeben. Dies stellt das Koordinatensystem auf den Kopf und verkehrt herum, ist aber ansonsten gleichwertig.quelle
Stax , 12 Bytes
Führen Sie es aus und debuggen Sie es
Ich weiß nicht, wie man ausgefallene mathematische Schriftsätze erstellt, aber dies beruht im Wesentlichen auf einer dynamischen Programmierkonstruktion
quelle
Rubin, 50
einfache Implementierung der Wiederholungsrelation.
quelle
Brain-Flak , 90 Bytes
Probieren Sie es online!
Berechnet( n0)2- ( n2)2 , woher ( nk)2 ist ein Trinomialkoeffizient . Ich konnte diese Formel nirgendwo finden, kann sie also nicht referenzieren, aber sie kann auf dieselbe Weise wie die analoge Formel bewiesen werdenCn= ( 2 nn) - ( 2nn + 1) .
quelle
ES6, 44 Bytes
Einfache Portierung der rekursiven Python-Lösung von @ xnor. Braucht
n<1?1:
dennn<1||
würdef(0)
wiederkommentrue
.quelle
Haskell , 55 Bytes
Einfache Implementierung der Rekursion.
Probieren Sie es online!
quelle