Die Ackermann-Funktion ist eines der einfachsten Beispiele für eine vollständig berechenbare Funktion, die nicht primitiv rekursiv ist.
Wir werden die Definition von A(m,n)
zwei nichtnegativen ganzen Zahlen verwenden, bei denen
A(0,n) = n+1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1,A(m,n-1))
Sie können implementieren
- eine benannte oder anonyme Funktion, die zwei Ganzzahlen als Eingabe verwendet und eine Ganzzahl zurückgibt, oder
- Ein Programm, das zwei durch Leerzeichen oder Zeilenumbrüche getrennte Ganzzahlen in STDIN verwendet und ein Ergebnis in STDOUT ausgibt.
Sie dürfen keine Ackermann-Funktion oder Überkompensationsfunktion aus einer Bibliothek verwenden, sofern eine vorhanden ist, aber Sie dürfen jede andere Funktion aus einer anderen Bibliothek verwenden. Regelmäßige Potenzierung ist zulässig.
Ihre Funktion muss in der Lage sein, den Wert A(m,n)
für m ≤ 3 und n ≤ 10 in weniger als einer Minute zu finden. Es muss zumindest theoretisch bei allen anderen Eingaben enden: Bei einem unendlichen Stapelspeicherplatz, einem systemeigenen Bigint-Typ und einem beliebig langen Zeitraum würde es die Antwort zurückgeben. Bearbeiten: Wenn Ihre Sprache eine zu restriktive Standard-Rekursionstiefe hat, können Sie diese ohne Zeichenkosten neu konfigurieren.
Die Einsendung mit der kürzesten Anzahl von Zeichen gewinnt.
Hier sind einige Werte, um Ihre Antwort zu überprüfen:
A | n=0 1 2 3 4 5 6 7 8 9 10
-----+-----------------------------------------------------------------
m=0 | 1 2 3 4 5 6 7 8 9 10 11
1 | 2 3 4 5 6 7 8 9 10 11 12
2 | 3 5 7 9 11 13 15 17 19 21 23
3 | 5 13 29 61 125 253 509 1021 2045 4093 8189
4 | 13 65533 big really big...
A(3,8)
so naiv wie die anderen zu rechnen ? Muss ich mir eine nicht rekursive Lösung einfallen lassen, oder kann ich in diesen Fällen auch nur "unendlichen Stapelspeicher annehmen"? Ich bin mir ziemlich sicher, es würde innerhalb einer Minute enden.Antworten:
Pyth , 19
Definiert
a
, welche Funktion als Ackermann-Funktion arbeitet. Beachten Sie, dass dies eine höhere Rekursionstiefe erfordert, als es der offizielle Pyth-Compiler bis heute zulässt. Deshalba 3 10
habe ich die Rekursionstiefe erhöht. Dies ist keine Änderung der Sprache, nur für den Compiler.Prüfung:
Erläuterung:
Im Wesentlichen
G
hängt es zunächst vom Wahrheitswert ab, ob H + 1 rekursiv oder zurückgegeben werden soll. Wenn es sich um ein rekursives Argument handelt, ist das erste Argument immer G-1 und hängt vom Wahrheitswert ab,H
ob esa(G,H-1)
als zweites Argument oder1
als zweites Argument verwendet werden soll.quelle
DaGHR
zuM
unda
zu wechselng
. (Hat sich die Reihenfolge der Argumente?
geändert?)M
stattdessen verwenden, und ja, die?
Argumentreihenfolge wurde geändert. Es ist jetzt Bedingung, wahr, falsch. Es war wahr, Bedingung, falsch.M
!Haskell, 35
Dies definiert die Bedienerfunktion
%
.Dies funktioniert , indem das zu bemerken
m%n
(woa
ist die Ackerman - Funktion) für Nicht - Nullm
wird(m-1)%
angewendetn+1
mal1
. Zum Beispiel3%2
ist definiert als2%(3%1)
was ist2%(2%(3%0))
, und das ist2%(2%(2%1))
quelle
0%n
anstelle vonn+1
wegen Vorrang verwenden kannGolfScript (30)
Online-Demo
Ohne die
1>
(welche SonderfälleA(1, n)
) dauert es 9 Minuten, umA(3, 10)
auf dem Computer zu rechnen, auf dem ich es getestet habe. Mit diesem speziellen Fall ist es schnell genug, dass die Online-Demo weniger als 10 Sekunden dauert.Beachten Sie, dass dies keine naive Übersetzung der Definition ist. Die Rekursionstiefe ist begrenzt durch
m
.Präparation
quelle
1>
. Nach dem Entfernen (und Wechselnif
zu?
)3 10 A
dauert das Berechnen mit dem Online-Interpreter 110 Sekunden und mit dem Java-Interpreter sechs Sekunden.Binäre Lambda-Rechnung , 54 Bits = 6,75 Bytes
Hexdump:
Binär:
Das ist λ m . m (& lgr; g . & lgr; n . g ( n g 1)) (& lgr; n . & lgr; f . & lgr; x . f ( n f x )), wobei alle Zahlen als Kirchenzahlen dargestellt sind .
quelle
JavaScript, ES6,
4134 BytesFühren Sie dies in einer aktuellen Firefox-Konsole aus und es wird eine Funktion namens erstellt,
f
die Sie mit unterschiedlichen Werten vonm
undn
wie aufrufen könnenODER
Probieren Sie den folgenden Code in einem aktuellen Firefox aus
quelle
Python 2.7.8 -
80, 54, 48, 4645(Dank an xnor!)
Mehr lesbar, aber mit 1 weiteren Zeichen:
Nicht, dass ich einstellen musste
sys.setrecursionlimit(10000)
, um ein Ergebnis für zu bekommenA(3,10)
. Weiteres Golfen mit logischer Indexierung funktionierte aufgrund der dramatisch wachsenden Rekursionstiefe nicht.quelle
1else
. Der Anfangsbuchstabee
bereitet dem Parser Probleme, da Zahlen wie folgt geschrieben werden können1e3
.and/or
:A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n
1else
, die meisten anderen Versionen nicht.1else
; Dadurch kann ich hier und wahrscheinlich auch an anderen Orten einen Saibling auspressen. Aber verdammt ist es versionsspezifisch! Python 2.7.4 erlaubt es nicht. Verwenden Sie eine Online-Version mit 2.7.8 oder muss ich diese herunterladen?1else
.J - 26 Zeichen
Es gibt eine alternative, funktionalere Definition von Ackermann:
Es kommt also vor, dass
Iter
es sehr einfach ist, in J zu schreiben, weil J die Möglichkeit hat, anm-1
zu übergebenAck
und auch den Anfangswert vonIter
1 zu definieren . Erklärt durch Explosion:Dies
^:
hängt davon ab, was J als die gerundete Form bezeichnet - im Grunde genommen eine Möglichkeit, alle Grenzen stillschweigend (punktfrei) zu kontrollieren.Auf der REPL:
Wir müssen uns
ack
mit Namen definieren , um es auf einen Tisch setzen zu können, denn es$:
ist eine schreckliche, hässliche Bestie, die jeden angreift, der versucht, es zu verstehen. Es ist eine Selbstreferenz, bei der self als die größte Verbalphrase definiert ist, die es enthält.table
ist ein Adverb und würde daher gerne Teil der Verbalphrase werden, wenn Sie ihm die Möglichkeit geben, also müssen Sie$:
eine benannte Definition einfangen, um sie zu verwenden.Bearbeiten: 24 char?
Jahre später fand ich eine Lösung, die zwei Zeichen kürzer ist.
Es ist jedoch viel langsamer: es
3 ack 8
dauert mehr als eine Minute auf meinem Computer. Dies liegt daran, dass (1) ich eine Falte/
anstelle einer Iteration verwende, sodass J sich wahrscheinlich mehr Dinge als gewöhnlich merken muss, und (2) während0&<~
dieselbe Berechnung durchführt(0<[)
, wird sie tatsächlich ausgeführtn+1
, bevor der rekursive Schritt beim Aufrufen ausgeführt wirdm ack n
-0&<
passiert idempotent zu sein, damit es die Berechnung nicht ruiniert, sondernn
schnell groß wird undack
hochrekursiv ist.Ich bin mir nicht sicher, ob ein leistungsfähigerer Computer den neuen Code
3 ack 10
in weniger als einer Minute übertragen kann, da dies ein Computer ist, auf dem der alte Code in weniger als 15 Sekunden gefunden werden kann.quelle
C - 41 Bytes
Nichts dagegen - die kleinen Grenzwerte bedeuten, dass alle erforderlichen Werte in weniger als 1 Sekunde berechnet werden können, indem naiv die Funktionsdefinition befolgt wird.
quelle
Javascript ES6 (34)
Implementierung:
quelle
JavaScript (ES6) - 34
Und ein Test:
quelle
Coq, 40
Dies ist eine Funktion vom Typ
nat -> nat -> nat
. Da Coq nur die Konstruktion von Gesamtfunktionen erlaubt, dient es auch als formaler Beweis dafür, dass die Ackermann-Wiederholung begründet ist.Demo:
Hinweis: Coq 8.5, veröffentlicht nach dieser Herausforderung, umbenannt
nat_iter
inNat.iter
.quelle
Schläger 67
quelle
Mathematica, 46 Bytes
Dauert ziemlich genau eine Minute
a[3,10]
. Beachten Sie, dass das Standard-Rekursionslimit von Mathematica füra[3,8]
und nach (zumindest auf meinem Computer) zu niedrig ist. Dieses Problem kann jedoch durch Konfigurieren behoben werdenquelle
If
eine Funktion noch langsamer ist.m_~a~n_:=m~a~n=
...Javascript mit Lambdas, 34
Eine typische Antwort, kann nichts kürzer machen.
quelle
Haskell,
4844 Zeichen (36 für die Liste)Obwohl nicht so kurz wie die andere Haskell-Lösung, ist diese bemerkenswert, da sie die Ackermann-Funktion als eine unendliche Liste ausdrückt, die ich für ziemlich ordentlich halte. Das Ergebnis ist eine unendliche Liste (von unendlichen Listen), so dass sie an Position [m, n] den Wert A (m, n) enthält .
Die unendliche Liste selbst:
Als eine Funktion (um der Spezifikation zu entsprechen):
Die Formulierung wurde abgeleitet, indem beobachtet wurde, dass der allgemeine / allgemeine Fall für die Ackermann-Funktion darin besteht, den Wert links als Index in der obigen Zeile zu verwenden. Der Grundfall für diese Rekursion (dh die am weitesten links stehende Spalte einer Zeile, dh A (m, 0) ) besteht darin, den am weitesten links liegenden Wert in der obigen Zeile zu verwenden. Der Grundfall für diese Rekursion ist der Fall A (0, n) = n + 1 , dh die erste Zeile ist
[1..]
.So bekommen wir
Dann fügen wir einfach eine weitere Stufe der Iteration hinzu, die auf diesem Muster basiert, und führen ein sinnloses Jonglieren durch.
quelle
iterate
für einen einzelnen Buchstaben haben, z. B.i=iterate;ack=i ...
Tiny Lisp , 70 (außer Konkurrenz)
Dies führt zu keinem Wettbewerb, da die Sprache neuer als die Frage ist und es
(A 3 10)
aufgrund eines Stapelüberlaufs auch nicht gelingt, die in der Frage erforderliche Sprache auszuführen .(d A(q((m n)(i m(i n(A(s m 1)(A m(s n 1)))(A(s m 1)1))(s n(s 0 1))))))
Dies definiert eine Funktion,
A
die die Ackermann-Funktion berechnet. Formatiert:Wir verwenden hier alle eingebauten Makros (
d
(define) undq
(quote) undi
(if)) und eine eingebaute Funktion (s
- subtrahieren).i
führt seinen wahren Teil aus, wenn die Bedingung eine Zahl> 0 ist (und ansonsten den falschen Teil), so dass wir hier keinen expliziten Vergleich durchführen müssen.s
Ist die einzige arithmetische Operation verfügbar, verwenden wir sie sowohl fürn-1
/m-1
als auch(s n (s 0 1))
fürn+1
.Tiny Lisp verwendet die Schwanzrekursionsoptimierung, dies hilft jedoch nur für den äußeren
A
Aufruf im Ergebnis, nicht für denA(m, n-1)
Aufruf, der für die Parameter verwendet wird.Mit meiner winzigen lisp-Implementierung in Ceylon auf der JVM funktioniert es bis zu
(A 3 5) = 253
, aber es scheint zusammenzubrechen, wenn versucht wird,(A 2 125)
direkt zu berechnen (was dasselbe Ergebnis ergeben sollte). Wenn man das danach berechnet,(A 3 4) = 125
muss die JVM anscheinend die Funktionen ausreichend optimieren, um einige Zwischenfunktionsaufrufe in meinem Interpreter zu integrieren, was eine größere Rekursionstiefe ermöglicht. Seltsam.Die Referenzimplementierung wird auf bis
(A 3 5) = 253
und auch(A 2 163) = 329
, aber nicht erfolgreich(A 2 164)
, und daher noch weniger(A 3 6) = (A 2 253)
.quelle
Los,
260243240122 BytesIch habe nicht gesehen, dass die Frage anon funcs erlaubt.
Weit davon entfernt, wettbewerbsfähig zu sein, aber ich lerne diese Sprache und wollte sie ausprobieren.
benutze es wie
go run ack.go
und gib dann zwei Zahlen ein,m
undn
. Wenn m> 4 oder n> 30 ist, kann die Ausführungszeit mehr als eine halbe Minute betragen.für
m=3 n=11
:edit : speichere insgesamt 17 bytes durch umschalten auf
switch
overif/else
und dot-importequelle
switch 0 {case m:r=n+1 case n:r=a(m-1,1) default:r=a(m-1,a(m,n-1))}
Go'sswitch
Aussage ist so schön flexibel!Haskell:
81 bis69 Bytesa 3 10
dauert ca. 45 Sekunden.quelle
(nicht konkurrierender) Pyth, 15 Bytes
Probieren Sie es online! (Beispielnutzung der Funktion
g3T
hinzugefügt, was bedeutetg(3,10)
)quelle
(nicht konkurrierend) UGL ,
3130 BytesEingabe durch Zeilenumbruch getrennt.
Probieren Sie es online!
(Es wurde als Standardbeispiel im Interpreter implementiert.)
quelle
Julia,
343128 BytesDies ist eine benannte anonyme Funktion. Es ist eine einfache Implementierung der rekursiven Definition und missbraucht Julias Fähigkeit dazu Operatoren neu definieren .
Probieren Sie es online!
quelle
R -
5452Ich habe dies als Ausrede benutzt, um zu versuchen, meinen Kopf um R zu drehen, also ist das wahrscheinlich wirklich schlecht gemacht :)
Beispiellauf
Ich bekomme einen Stapelüberlauf für alles darüber hinaus
T-SQL-222
Ich dachte, ich würde versuchen, auch T-SQL dazu zu bringen. Verwendete eine andere Methode, weil die Rekursion in SQL nicht so schön ist. Alles über 4,2 bombardiert es.
quelle
{}
obwohl es keine Hilfe für die Stapelüberlaufgrenze gibt, da R keine Gesamtbetriebskosten hat ...Brainfuck , 90 Bytes
Probieren Sie es online!
Nimmt eine Implementierung mit beliebig großer Zellengröße mit IO als Zahlen an. -6 Bytes, wenn es Ihnen nichts ausmacht, negative Zellen zu verwenden.
Wird im verknüpften Interpreter in ca. 30 Sekunden für 3,8 ausgeführt, sofern Sie die richtigen Einstellungen ankreuzen. Geben Sie eingegebene Zahlen mit vorangestelltem
\
s ein, z . B.3,9
ist\3\9
.quelle
Tcl , 67 Bytes
Probieren Sie es online!
Tcl , 77 Bytes
Probieren Sie es online!
Im Online-Compiler schlägt die Ausführung aufgrund einer Zeitüberschreitung fehl, in einem lokalen Tcl-Interpreter funktioniert sie jedoch einwandfrei. Ich habe von jedem Root-Aufruf ein
A
Funktionsprofil erstellt, um zu sehen, wie lange die Berechnung für jedes{m,n}
zu testende Paar gedauert hat:Das letzte Paar schlägt fehl
{m,n}={3,10}
, da es etwas länger als eine Minute dauert.Für höhere Werte von
m
muss derrecursionlimit
Wert erhöht werden.Ich könnte es auf 65 Bytes kürzen, aber es wird die Anforderung der Frage "Ihre Funktion muss in der Lage sein, den Wert von A (m, n) für m ≤ 3 und n ≤ 10 in weniger als einer Minute zu finden." Nicht erfüllen. Ohne das
{}
es auf TIO ein Timeout geben und nicht die Demo der letzten beiden Einträge machen.Tcl , 65 Bytes
Probieren Sie es online!
quelle
J: 50
Kehrt in Bruchteilen von Sekunden für 0 ... 3 vs 0 ... 10 zurück:
PS: Die "0" bewirkt, dass A an jedem einzelnen Element arbeitet, anstatt das linke und rechte Array zu verschlingen und Längenfehler zu erzeugen. Sie wird jedoch nicht für z. B. 9 = 2 A 3 benötigt.
quelle
APL, 31
Ziemlich einfach. Verwendet das Zeichen ⍨ einmal, um ein Byte durch Umkehren von Argumenten zu speichern. Nimmt m als linkes Argument und n als rechtes Argument.
TryAPL.org
quelle
Rubin, 65
Erläuterung
Dies ist eine ziemlich einfache Übersetzung des in der Problembeschreibung angegebenen Algorithmus.
Integer
s werden erwartet.Hash
h
. Der||=
Operator wird verwendet, um einen Wert zu berechnen, der zuvor nicht berechnet wurde.a[3,10]
wird auf meinem Rechner in ~ 0,1 Sek. berechnet.Ist hier eine ungolfed Version
quelle
a[3,10]
Wirf einen SystemStackError auf meinen Computer ...m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])
umm<1?n+1:a[m-1,n<1?1:a[m,n-1]]
Mouse-2002 ,
9983 Bytesquelle
Java, 274 Bytes
Es berechnet
A(3,10)
in wenigen Sekunden und kann bei unendlich viel Speicher und Stapelspeicher jede Kombination vonb
und berechnen,B
solange das Ergebnis unter 2 2147483647 -1 liegt.quelle
import java.math.*;BigInteger A(BigInteger b,BigInteger B){return b.equals(B.ZERO)?B.add(B.ONE):B.equals(B.ZERO)?A(b.subtract(B.ONE),B.ONE):A(b.subtract(B.ONE),A(b,B.subtract(B.ONE)));}
Ceylon,
888785Dies ist eine einfache Implementierung. Formatiert:
Der Alias speichert nur ein Byte, ohne es (mit Schreiben
Integer
stattI
) würden wir auf 86 Bytes kommen. Weitere zwei Bytes können== 0
durch< 1
zweimaliges Ersetzen gespeichert werden .Mit den Standardeinstellungen von
ceylon run
funktioniert es bis zuA(3,12) = 32765
(undA(4,0) = 13
), aberA(3,13)
(und daher auchA(4,1)
) löst es einen Stapelüberlauffehler aus. (A(3,12)
dauert ungefähr 5 Sekunden,A(3,11)
ungefähr 3 Sekunden auf meinem Computer.)Die Verwendung von
ceylon run-js
(dh das Ausführen des Ergebnisses der Kompilierung in JavaScript auf node.js) ist viel langsamer (benötigt 1 Min. 19 Sek. FürA(3,10)
) und bricht bereitsA(3, 11)
mit einer »Maximalen Call-Stack-Größe überschritten« (unter Verwendung der Standardeinstellungen) ab, nachdem 1 ausgeführt wurde min 30 s.Ceylon ohne Rekursion, 228
Als Bonus gibt es hier eine nicht-rekursive Version (natürlich länger, aber immun gegen Stapelüberläufe - könnte irgendwann ein Fehler aufgrund von Speichermangel auftreten).
Formatiert:
Es ist auf meinem Computer ziemlich langsamer als die rekursive Version:
A(3,11)
dauert 9,5 Sekunden,A(3,12)
dauert 34 Sekunden,A(3,13)
dauert 2:08 Minuten,A(3,14)
dauert 8:25 Minuten. (Ich hatte ursprünglich eine Version mit Lazy Iterables anstelle der Tupel, die ich jetzt habe, die sogar viel langsamer waren, mit der gleichen Größe).Ein bisschen schneller (21 Sekunden für
A(3,12)
) (aber auch ein Byte länger) ist eine Version, dies.push
anstelle von verwendet wirds.addAll
, die jedoch mehrmals aufgerufen werden musste, um mehrere Zahlen hinzuzufügen, da jeweils nur eine einzelne Ganzzahl erforderlich ist. Die Verwendung einer LinkedList anstelle einer ArrayList ist sehr viel langsamer.quelle