Die Ackermann-Funktion

35

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...
algorithmshark
quelle
15
Wie wurde das vorher nicht gefragt ??
Calvins Hobbys
9
Ich denke , es ist mehr Spaß machen würde , dies zu machen schnellsten Code
SP3000
22
Downvoting, weil es hier keine Herausforderung gibt. Die naheliegende Antwort - einfach naiv die Funktion genau nach ihrer Definition zu implementieren - wird immer die beste Antwort sein. Die Frage ist also nur "Welche Sprache hat die geringste Anzahl von Zeichen im offensichtlichen Ausdruck von Ackermanns Funktion?" Der wahre Gewinner ist die Programmiersprache, nicht die Person, die das offensichtliche Programm darin geschrieben hat.
David Richerby
1
Was ist, wenn die Rekursionsgrenze meiner Sprache zu niedrig ist, um 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.
Martin Ender
5
@DavidRicherby "Die naheliegende [...] Antwort wird immer die beste sein." Dies gilt nicht für alle Sprachen. Ich fühle mich ein wenig dreckig, weil ich nur ein Beispiel in meiner Muttersprache habe, aber es gibt mehrere Möglichkeiten, Ackermann auszudrücken, und in einigen Sprachen können Sie durch diese Tatsache Einsparungen erzielen. Dies war meine Absicht für die Herausforderung.
Algorithmushai

Antworten:

7

Pyth , 19

DaGHR?atG?aGtHH1GhH

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. Deshalb a 3 10habe ich die Rekursionstiefe erhöht. Dies ist keine Änderung der Sprache, nur für den Compiler.

Prüfung:

$ time pyth -c "DaGHR?atG?aGtHH1GhH           ;a 3 10"
8189

real    0m0.092s
user    0m0.088s
sys     0m0.000s

Erläuterung:

DaGH                     def a(G,H):
    R                    return
    ?          G                (if G:
     atG                              (a(G-1,
        ?    H                               (if H:
         aGtH                                      a(G,H-1)
              1                               else:1)
                hH               else:H+1)

Im Wesentlichen Ghä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, Hob es a(G,H-1)als zweites Argument oder 1als zweites Argument verwendet werden soll.

isaacg
quelle
Im modernen Pyth (ich nehme an, dass dies nach dieser Herausforderung hinzugefügt wurde) kann man meiner Meinung nach mehr oder weniger DaGHRzu Mund azu wechseln g. (Hat sich die Reihenfolge der Argumente ?geändert?)
Lynn
@ Mauris Ja, Sie können Mstattdessen verwenden, und ja, die ?Argumentreihenfolge wurde geändert. Es ist jetzt Bedingung, wahr, falsch. Es war wahr, Bedingung, falsch.
Isaacg
@Lynn Fun Fakten zur Pyth-Geschichte: Diese Frage hat tatsächlich dazu beigetragen, (mindestens) zwei Dinge an Pyth zu ändern: das Rekursionslimit und den Wechsel zuM !
FryAmTheEggman
23

Haskell, 35

0%n=1+n
m%n=iterate((m-1)%)1!!(n+1)

Dies definiert die Bedienerfunktion %.

Dies funktioniert , indem das zu bemerken m%n(wo aist die Ackerman - Funktion) für Nicht - Null mwird (m-1)%angewendet n+1mal 1. Zum Beispiel 3%2ist definiert als 2%(3%1)was ist 2%(2%(3%0)), und das ist2%(2%(2%1))

stolzer haskeller
quelle
schade, dass ich nicht 0%nanstelle von n+1wegen Vorrang verwenden kann
stolzer Haskeller
wow, das ist schon so lange falsch und niemand, auch ich nicht bemerkt? gute Arbeit. so scheint es, als hätte ich versehentlich die erste Version der Antwort kopiert, die fehlerhaft war, vielleicht aus Versehen oder weil ich dachte, dass sie funktioniert.
stolzer Haskeller
12

GolfScript (30)

{1$1>{1\){1$(\A}*\;}{+)}if}:A;

Online-Demo

Ohne die 1>(welche Sonderfälle A(1, n)) dauert es 9 Minuten, um A(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

{             # Function boilerplate
  1$          # Get a copy of m: stack holds m n m
  1>{         # (Optimisation): if m is greater than 1
    1         #   Take this as the value of A(m, -1)
    \){       #   Repeat n+1 times:
              #     Stack: m A(m, i-1)
      1$(\    #     Stack: m m-1 A(m, i-1)
      A       #     Stack: m A(m, i)
    }*
    \;        #   Lose that unwanted copy of m
  }{          # Else
    +)        #   A(m in {0, 1}, n) = m + n + 1
  }if
}:A;          # Function boilerplate
Peter Taylor
quelle
In CJam würden Sie nicht brauchen 1>. Nach dem Entfernen (und Wechseln ifzu ?) 3 10 Adauert das Berechnen mit dem Online-Interpreter 110 Sekunden und mit dem Java-Interpreter sechs Sekunden.
Dennis
7

Binäre Lambda-Rechnung , 54 Bits = 6,75 Bytes

Hexdump:

00000000: 1607 2d88 072f 68                        ..-../h

Binär:

000101100000011100101101100010000000011100101111011010

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 .

Anders Kaseorg
quelle
6

JavaScript, ES6, 41 34 Bytes

f=(m,n)=>m?f(m-1,!n||f(m,n-1)):n+1

Führen Sie dies in einer aktuellen Firefox-Konsole aus und es wird eine Funktion namens erstellt, fdie Sie mit unterschiedlichen Werten von mund nwie aufrufen können

f(3,2) // returns 29

ODER

Probieren Sie den folgenden Code in einem aktuellen Firefox aus

f=(m,n)=>m?f(m-1,!n||f(m,n-1)):n+1

B.onclick=_=>alert(f(+M.value, +N.value))
#M,#N{max-width:15px;border: 1px solid;border-width:0 0 1px 0}
<div>f(<input id=M />,<input id=N />)</div><br><button id=B>Evaluate</button>

Optimierer
quelle
Wenn Sie dies mit 0,1 in Chrome testen, wird kein Ergebnis erzielt.
Nzall
3
Bitte lesen Sie, dies funktioniert nur im neuesten Firefox aufgrund von ES6
Optimizer
Wow ... wir haben 4 praktisch identische JS-Lösungen, alle mit 34 Bytes. Das habe ich noch nie gesehen.
ETHproductions
6

Python 2.7.8 - 80, 54, 48, 46 45

A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n

(Dank an xnor!)

Mehr lesbar, aber mit 1 weiteren Zeichen:

A=lambda m,n:n+(m<1or A(m-1,n<1or A(m,n-1))-n)

Nicht, dass ich einstellen musste sys.setrecursionlimit(10000), um ein Ergebnis für zu bekommen A(3,10). Weiteres Golfen mit logischer Indexierung funktionierte aufgrund der dramatisch wachsenden Rekursionstiefe nicht.

Falko
quelle
Ich bekomme einen Syntaxfehler auf dem 1else. Der Anfangsbuchstabe ebereitet dem Parser Probleme, da Zahlen wie folgt geschrieben werden können 1e3.
Xnor
Ein paar Zeichen beim Umschalten auf and/or:A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n
xnor
@xnor: Danke für den Tipp! In dieser Diskussion finden Sie Informationen zum Parsing-Problem. Python 2.7.8 akzeptiert 1else, die meisten anderen Versionen nicht.
Falko
Danke für den Hinweis über 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?
Xnor
@xnor: Es ist eine Offline-Installation. ideone.com kann z. B. auch nicht analysieren 1else.
Falko
6

J - 26 Zeichen

($:^:(<:@[`]`1:)^:(0<[)>:)

Es gibt eine alternative, funktionalere Definition von Ackermann:

Ack 0 n = n+1
Ack m n = Iter (Ack (m-1)) n
Iter f 0 = f 1
Iter f n = f (Iter f (n-1))

Es kommt also vor, dass Iteres sehr einfach ist, in J zu schreiben, weil J die Möglichkeit hat, an m-1zu übergeben Ackund auch den Anfangswert von Iter1 zu definieren . Erklärt durch Explosion:

(                      >:)  NB. increment n
                ^:(0<[)     NB. if m=0, do nothing to n+1; else:
   ^:                       NB. iterate...
($:                      )  NB.   self ($: is recursion)
     (<:@[     )            NB.   with left arg m-1
          `]                NB.   n+1 times
            `1:             NB.   starting on 1

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:

   3 ($:^:(<:@[`]`1:)^:(0<[)>:) 3
61
   ack =: ($:^:(<:@[`]`1:)^:(0<[)>:)
   (i.4) ack"0 table (i.11)
+-----+------------------------------------------+
|ack"0|0  1  2  3   4   5   6    7    8    9   10|
+-----+------------------------------------------+
|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|
+-----+------------------------------------------+
   6!:2 '3 ($:^:(<:@[`]`1:)^:(0<[)>:) 10'  NB. snugly fits in a minute
58.5831

Wir müssen uns ackmit 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. tableist 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.

(0&<~(<:@#~$:/@,1:^:)>:)

Es ist jedoch viel langsamer: es 3 ack 8dauert 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ährend 0&<~dieselbe Berechnung durchführt (0<[), wird sie tatsächlich ausgeführt n+1, bevor der rekursive Schritt beim Aufrufen ausgeführt wird m ack n- 0&<passiert idempotent zu sein, damit es die Berechnung nicht ruiniert, sondern nschnell groß wird und ackhochrekursiv ist.

Ich bin mir nicht sicher, ob ein leistungsfähigerer Computer den neuen Code 3 ack 10in weniger als einer Minute übertragen kann, da dies ein Computer ist, auf dem der alte Code in weniger als 15 Sekunden gefunden werden kann.

algorithmshark
quelle
5

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.

A(m,n){return!m?n+1:A(m-1,n?A(m,n-1):1);}


int main()
{
    int m,n;
    for(m = 0; m <= 3; m++)
    for(n = 0; n <= 10; n++)
    printf("%d %d %d\n", m,n,A(m,n));
    return 0;
}
Feersum
quelle
5

Javascript ES6 (34)

a=(m,n)=>m?a(m-1,n?a(m,n-1):1):n+1

Implementierung:

a=(m,n)=>m?a(m-1,n?a(m,n-1):1):n+1
td[colspan="2"] input{width: 100%;}
<table><tbody><tr><td>m=</td><td><input id="m" type="number" value="0" /></td></tr><tr><td>n=</td><td><input id="n" type="number" value="0" /></td></tr><tr><td colspan="2"><input type="button" value="Calculate!" onclick="document.getElementById('out').value=a(document.getElementById('m').value, document.getElementById('n').value)" /></td></tr><tr><td colspan="2"><input id="out" disabled="disabled" type="text" /></td></tr></tbody></table>

kitcar2000
quelle
4

JavaScript (ES6) - 34

A=(m,n)=>m?A(m-1,!n||A(m,n-1)):n+1

Und ein Test:

> A=(m,n)=>m?A(m-1,!n||A(m,n-1)):n+1;s=new Date().getTime();console.log(A(3,10),(new Date().getTime() - s)/1000)
8189 16.441
core1024
quelle
3

Coq, 40

nat_rec _ S(fun _ b n=>nat_iter(S n)b 1)

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:

Welcome to Coq 8.4pl6 (November 2015)

Coq < Compute nat_rec _ S(fun _ b n=>nat_iter(S n)b 1) 3 10.
     = 8189
     : nat

Hinweis: Coq 8.5, veröffentlicht nach dieser Herausforderung, umbenannt nat_iterin Nat.iter.

Anders Kaseorg
quelle
2

Schläger 67

(define(a m n)(if(= m 0)(+ n 1)(a(- m 1)(if(= n 0)1(a m(- n 1))))))
Matthew Butterick
quelle
2

Mathematica, 46 Bytes

0~a~n_:=n+1
m_~a~n_:=a[m-1,If[n<1,1,a[m,n-1]]]

Dauert ziemlich genau eine Minute a[3,10]. Beachten Sie, dass das Standard-Rekursionslimit von Mathematica für a[3,8]und nach (zumindest auf meinem Computer) zu niedrig ist. Dieses Problem kann jedoch durch Konfigurieren behoben werden

$RecursionLimit = Infinity
Martin Ender
quelle
1
Wow, sagen Sie also, dass JS mehr als 25-mal schneller ist als Mathematica?
Optimierer
@Optimizer Zumindest wenn es um Rekursion geht ... Ich denke mal, wenn es darum geht, jedes Mal herauszufinden, welche Definition verwendet werden soll, und Ifeine Funktion noch langsamer ist.
Martin Ender
1
Bei der Speicherung dauert es 0,07 Sekunden. Dh m_~a~n_:=m~a~n=...
Mark Adler
@MarkAdler Das ist eine wirklich schöne Art, sich in Mathematica etwas zu merken!
Martin Ender
2

Javascript mit Lambdas, 34

A=(m,n)=>m?A(m-1,n?A(m,n-1):1):n+1

Eine typische Antwort, kann nichts kürzer machen.

Qwertiy
quelle
2

Haskell, 48 44 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:

iterate(tail.(`iterate`1).(!!))[1..]

Als eine Funktion (um der Spezifikation zu entsprechen):

i=iterate;m%n=i(tail.(`i`1).(!!))[1..]!!m!!n

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

let a0 = [1..]
let a1 = tail $ iterate (a0 !!) 1  -- 'tail' because iterate starts by applying
let a2 = tail $ iterate (a1 !!) 1  -- the function 0 times
-- etc

Dann fügen wir einfach eine weitere Stufe der Iteration hinzu, die auf diesem Muster basiert, und führen ein sinnloses Jonglieren durch.

FireFly
quelle
Sie könnten einen Aliasnamen iteratefür einen einzelnen Buchstaben haben, z. B.i=iterate;ack=i ...
stolzer Haskeller
@ proudhaskeller oh yeah, habe nicht darüber nachgedacht. Vielen Dank! Leihen Sie sich auch Ihren Betreibernamen aus.
FireFly
2

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, Adie die Ackermann-Funktion berechnet. Formatiert:

(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)
           )
        )
    ) )
 )

Wir verwenden hier alle eingebauten Makros ( d(define) und q(quote) und i(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.

sIst die einzige arithmetische Operation verfügbar, verwenden wir sie sowohl für n-1/ m-1als auch (s n (s 0 1))für n+1.

Tiny Lisp verwendet die Schwanzrekursionsoptimierung, dies hilft jedoch nur für den äußeren AAufruf im Ergebnis, nicht für den A(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) = 125muss 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) = 253und auch (A 2 163) = 329, aber nicht erfolgreich (A 2 164), und daher noch weniger (A 3 6) = (A 2 253).

Paŭlo Ebermann
quelle
Dies könnte wettbewerbsfähig sein, außer für die Leerzeichen und Klammern;)
Katze
2

Los, 260 243 240 122 Bytes

Ich 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.

func (m,n int)int{r:=0
switch{case m==0&&n!=0:r=n+1
case m!=0&&n==0:r=a(m-1,1)
case m!=0&&n!=0:r=a(m-1,a(m,n-1))}
return r}

benutze es wie go run ack.gound gib dann zwei Zahlen ein, mund n. Wenn m> 4 oder n> 30 ist, kann die Ausführungszeit mehr als eine halbe Minute betragen.

für m=3 n=11:

$ time go run ack
16381
real    0m1.434s
user    0m1.432s
sys     0m0.004s

edit : speichere insgesamt 17 bytes durch umschalten auf switchover if/elseund dot-importe

Katze
quelle
1
Sie können es noch besser machen! switch 0 {case m:r=n+1 case n:r=a(m-1,1) default:r=a(m-1,a(m,n-1))}Go's switchAussage ist so schön flexibel!
EMBLEM
@EMBLEM Danke, es ist schon so lange her, dass ich Go geschrieben habe, aber ich bin froh zu sehen, dass es noch andere Go-Golfer gibt: D
cat
1

Haskell: 81 bis 69 Bytes

a::Int->Int->Int
a 0 n=n+1
a m 0=a (m-1) 1
a m n=a (m-1) a m (n-1)

a 3 10 dauert ca. 45 Sekunden.

SophR
quelle
1
Das ist Codegolf, also sollten Sie versuchen, den kürzestmöglichen Code zu haben. zum Beispiel, entfernen Sie überflüssigen Leerzeichen und den expliziten Typen
stolz haskeller
du vermisst auch die parens in der vierten
zeile
1

(nicht konkurrierender) Pyth, 15 Bytes

M?GgtG?HgGtH1hH

Probieren Sie es online! (Beispielnutzung der Funktion g3Thinzugefügt, was bedeutet g(3,10))

Undichte Nonne
quelle
1

(nicht konkurrierend) UGL , 31 30 Bytes

iiRuldr%l%lR$d%rd:u%d:%+uRu:ro

Eingabe durch Zeilenumbruch getrennt.

Probieren Sie es online!

(Es wurde als Standardbeispiel im Interpreter implementiert.)

Undichte Nonne
quelle
1

R - 54 52

Ich habe dies als Ausrede benutzt, um zu versuchen, meinen Kopf um R zu drehen, also ist das wahrscheinlich wirklich schlecht gemacht :)

a=function(m,n)"if"(m,a(m-1,"if"(n,a(m,n-1),1)),n+1)

Beispiellauf

> a(3,8)
[1] 2045

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.

DECLARE @m INT=4,@n INT=1;WITH R AS(SELECT 2 C, 1 X UNION ALL   SELECT POWER(2,C),X+1FROM R)SELECT IIF(@m=0,@n+1,IIF(@m=1,@n+2,IIF(@m=2,2*@n+3,IIF(@m=3,POWER(2,@n+3)-3,IIF(@m=4,(SELECT TOP(1)C FROM R WHERE x= @n+3)-3,-1)))))
MickyT
quelle
Es sieht so aus, als ob Sie für Ihre R-Submisson die brauchen, {}obwohl es keine Hilfe für die Stapelüberlaufgrenze gibt, da R keine Gesamtbetriebskosten hat ...
Giuseppe
@ Giuseppe danke ... zu meiner Verteidigung, ich war damals neu :)
MickyT
1

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,9ist \3\9.

Scherzen
quelle
1

Tcl , 67 Bytes

proc tcl::mathfunc::A m\ n {expr {$m?A($m-1,$n?A($m,$n-1):1):$n+1}}

Probieren Sie es online!


Tcl , 77 Bytes

proc A m\ n {expr {$m?[A [expr $m-1] [expr {$n?[A $m [expr $n-1]]:1}]]:$n+1}}

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 AFunktionsprofil erstellt, um zu sehen, wie lange die Berechnung für jedes {m,n}zu testende Paar gedauert hat:

m=0, n=0, A=1, time=3.5e-5 seconds
m=0, n=1, A=2, time=2e-6 seconds
m=0, n=2, A=3, time=8e-6 seconds
m=0, n=3, A=4, time=1e-6 seconds
m=0, n=4, A=5, time=2e-6 seconds
m=0, n=5, A=6, time=1e-6 seconds
m=0, n=6, A=7, time=1e-6 seconds
m=0, n=7, A=8, time=1e-6 seconds
m=0, n=8, A=9, time=1e-6 seconds
m=0, n=9, A=10, time=0.0 seconds
m=0, n=10, A=11, time=1e-6 seconds
m=1, n=0, A=2, time=4e-6 seconds
m=1, n=1, A=3, time=6e-6 seconds
m=1, n=2, A=4, time=1e-5 seconds
m=1, n=3, A=5, time=1.2e-5 seconds
m=1, n=4, A=6, time=1.5e-5 seconds
m=1, n=5, A=7, time=2e-5 seconds
m=1, n=6, A=8, time=2e-5 seconds
m=1, n=7, A=9, time=2.6e-5 seconds
m=1, n=8, A=10, time=3e-5 seconds
m=1, n=9, A=11, time=3e-5 seconds
m=1, n=10, A=12, time=3.3e-5 seconds
m=2, n=0, A=3, time=8e-6 seconds
m=2, n=1, A=5, time=2.2e-5 seconds
m=2, n=2, A=7, time=3.9e-5 seconds
m=2, n=3, A=9, time=6.3e-5 seconds
m=2, n=4, A=11, time=9.1e-5 seconds
m=2, n=5, A=13, time=0.000124 seconds
m=2, n=6, A=15, time=0.000163 seconds
m=2, n=7, A=17, time=0.000213 seconds
m=2, n=8, A=19, time=0.000262 seconds
m=2, n=9, A=21, time=0.000316 seconds
m=2, n=10, A=23, time=0.000377 seconds
m=3, n=0, A=5, time=2.2e-5 seconds
m=3, n=1, A=13, time=0.000145 seconds
m=3, n=2, A=29, time=0.000745 seconds
m=3, n=3, A=61, time=0.003345 seconds
m=3, n=4, A=125, time=0.015048 seconds
m=3, n=5, A=253, time=0.059836 seconds
m=3, n=6, A=509, time=0.241431 seconds
m=3, n=7, A=1021, time=0.971836 seconds
m=3, n=8, A=2045, time=3.908884 seconds
m=3, n=9, A=4093, time=15.926341 seconds
m=3, n=10, A=8189, time=63.734713 seconds

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 mmuss der recursionlimitWert 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

proc tcl::mathfunc::A m\ n {expr $m?A($m-1,$n?A($m,$n-1):1):$n+1}

Probieren Sie es online!

Sergiol
quelle
0

J: 50

>:@]`(1$:~<:@[)`(<:@[$:[$:_1+])@.(0>.[:<:@#.,&*)M.

Kehrt in Bruchteilen von Sekunden für 0 ... 3 vs 0 ... 10 zurück:

   A=:>:@]`(1$:~<:@[)`(<:@[$:[$:_1+])@.(0>.[:<:@#.,&*)M.
   timespacex 'res=:(i.4) A"0 table (i.11)'
0.0336829 3.54035e6
   res
┌───┬──────────────────────────────────────────┐
│A"0│0  1  2  3   4   5   6    7    8    9   10│
├───┼──────────────────────────────────────────┤
│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│
└───┴──────────────────────────────────────────┘

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.

jpjacobs
quelle
codegolf.stackexchange.com/a/40174/48934 Sie wurden geschlagen!
Undichte Nonne
0

APL, 31

{⍺=0:⍵+1⋄⍵=0:1∇⍨⍺-1⋄(⍺-1)∇⍺∇⍵-1}

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

Shujal
quelle
0

Rubin, 65

h,a={},->m,n{h[[m,n]]||=m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])}

Erläuterung

Dies ist eine ziemlich einfache Übersetzung des in der Problembeschreibung angegebenen Algorithmus.

  • Die Eingabe wird als Argument für ein Lambda verwendet. Zwei Integers werden erwartet.
  • Um die Geschwindigkeit zu erhöhen und Stapelüberlauffehler zu vermeiden, werden die Antworten in der Liste gespeichert 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

h = {}
a = lambda do |m,n|
  h[[m,n]] ||= if m < 1 
    n + 1
  elsif n < 1
    a[m-1,1]
  else
    a[m-1,a[m,n-1]]
  end
end
britishtea
quelle
a[3,10]Wirf einen SystemStackError auf meinen Computer ...
TuxCrafting
Golf Nitpicks: Sie könnte sich ändern , 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]]
Simply Beautiful Art
0

Mouse-2002 , 99 83 Bytes

$Y1%j:j.0=m:2%k:k.0=n:m.n.>[k.1+!|m.n.<[#Y,j.1-,1;|m.n.*0=[#Y,j.1-,#Y,j.,k.1+;;]]]@
Katze
quelle
0

Java, 274 Bytes

import java.math.*;class a{BigInteger A(BigInteger b,BigInteger B){if(b.equals(BigInteger.ZERO))return B.add(BigInteger.ONE);if(B.equals(BigInteger.ZERO))return A(b.subtract(BigInteger.ONE),BigInteger.ONE);return A(b.subtract(BigInteger.ONE),A(b,B.subtract(BigInteger.ONE)));}}

Es berechnet A(3,10)in wenigen Sekunden und kann bei unendlich viel Speicher und Stapelspeicher jede Kombination von bund berechnen, Bsolange das Ergebnis unter 2 2147483647 -1 liegt.

Dorukayhan will Monica zurück
quelle
Ich weiß, es ist schon eine Weile her, aber Sie können dies auf 185 Bytes Golf spielen :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)));}
Kevin Cruijssen
0

Ceylon, 88 87 85

alias I=>Integer;I a(I m,I n)=>m<1then n+1else(n<1then a(m-1,1)else a(m-1,a(m,n-1)));

Dies ist eine einfache Implementierung. Formatiert:

alias I => Integer;
I a(I m, I n) =>
        m < 1
        then n + 1
        else (n < 1
            then a(m - 1, 1)
            else a(m - 1, a(m, n - 1)));

Der Alias ​​speichert nur ein Byte, ohne es (mit Schreiben Integerstatt I) würden wir auf 86 Bytes kommen. Weitere zwei Bytes können == 0durch < 1zweimaliges Ersetzen gespeichert werden .

Mit den Standardeinstellungen von ceylon runfunktioniert es bis zu A(3,12) = 32765(und A(4,0) = 13), aber A(3,13)(und daher auch A(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ür A(3,10)) und bricht bereits A(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).

import ceylon.collection{A=ArrayList}Integer a(Integer[2]r){value s=A{*r};value p=s.addAll;while(true){if(exists m=s.pop()){if(exists n=s.pop()){if(n<1){p([m+1]);}else if(m<1){p([n-1,1]);}else{p([n-1,n,m-1]);}}else{return m;}}}}

Formatiert:

import ceylon.collection {
    A=ArrayList
}

Integer a(Integer[2] r) {
    value s = A { *r };
    value p = s.addAll;
    while (true) {
        if (exists m = s.pop()) {
            if (exists n = s.pop()) {
                if (n < 1) {
                    p([m + 1]);
                } else if (m < 1) {
                    p([n - 1, 1]);
                } else {
                    p([n - 1, n, m - 1]);
                }
            } else {
                // stack is empty
                return m;
            }
        }
    }
}

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, die s.pushanstelle von verwendet wird s.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.

Paŭlo Ebermann
quelle