Funkcja Ackermanna wyróżnia się jako jeden z najprostszych przykładów całkowitej, obliczalnej funkcji, która nie jest prymitywną rekurencyjną.

Użyjemy definicji A(m,n)przyjmowania dwóch nieujemnych liczb całkowitych gdzie

A(0,n) = n+1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1,A(m,n-1))

Możesz wdrożyć

• nazwana lub anonimowa funkcja przyjmująca dwie liczby całkowite jako dane wejściowe, zwracająca liczbę całkowitą lub
• program przyjmujący dwie liczby całkowite oddzielone spacją lub znakiem nowej linii na STDIN, drukujący wynik do STDOUT.

Nie możesz używać funkcji Ackermanna ani funkcji hipereponentyzacji z biblioteki, jeśli taka istnieje, ale możesz użyć dowolnej innej funkcji z dowolnej innej biblioteki. Dozwolone jest regularne potęgowanie.

Twoja funkcja musi być w stanie znaleźć wartość A(m,n)dla m ≤ 3 in ≤ 10 w mniej niż minutę. Musi przynajmniej teoretycznie kończyć się na innych wejściach: biorąc pod uwagę nieskończoną przestrzeń stosu, natywny typ Biginta i dowolnie długi okres czasu, zwróci odpowiedź. Edycja: Jeśli Twój język ma domyślną głębokość rekurencji, która jest zbyt restrykcyjna, możesz ją ponownie skonfigurować bez żadnych kosztów znaków.

Zgłoszenie z najmniejszą liczbą znaków wygrywa.

Oto kilka wartości, aby sprawdzić swoją odpowiedź:

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

Pyth , 19 lat

DaGHR?atG?aGtHH1GhH

Definiuje a, który działa jako funkcja Ackermanna. Zauważ, że wymaga to większej głębokości rekurencji niż oficjalny kompilator Pyth, który do tej pory mógł obliczać a 3 10, więc zwiększyłem głębokość rekurencji. To nie jest zmiana języka, tylko kompilatora.

Test:

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

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

Wyjaśnienie:

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)

Zasadniczo, najpierw Gzależy od wartości prawdy, czy powrócić, czy zwrócić H + 1. Jeśli jest rekurencyjny, pierwszym argumentem jest zawsze G-1 i warunkuje on wartość prawdy, Hczy użyć a(G,H-1)jako drugi argument, czy użyć 1jako drugi argument.

Haskell, 35

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

określa to funkcję operatora %.

to działa, zauważając, że m%n(gdzie ajest funkcja Ackerman) dla niezerowego mjest (m-1)%stosowane n+1razy 1. na przykład 3%2jest zdefiniowane jako 2%(3%1)to 2%(2%(3%0)), co jest i to jest2%(2%(2%1))

GolfScript (30)

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

Demo online

Bez 1>(w jakich przypadkach specjalnych A(1, n)) obliczenie zajmuje 9 minut A(3, 10)na komputerze, na którym go przetestowałem. W tym specjalnym przypadku jest wystarczająco szybki, aby demo online zajęło mniej niż 10 sekund.

Zauważ, że nie jest to naiwne tłumaczenie definicji. Głębokość rekurencji jest ograniczona przez m.

Sekcja

{             # 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

Binarny rachunek lambda , 54 bity = 6,75 bajtów

Hexdump:

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

Dwójkowy:

000101100000011100101101100010000000011100101111011010

To jest λ m . m (λ g . λ n . g ( n g 1)) (λ n . λ f . λ x . f ( n f x )), gdzie wszystkie liczby są reprezentowane jako liczby kościelne .

JavaScript, ES6, 41 34 bajtów

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

Uruchom to w najnowszej konsoli Firefox, aby utworzyć funkcję o nazwie, fktórą możesz wywoływać z różnymi wartościami mi npodobnymi

f(3,2) // returns 29

LUB

wypróbuj poniższy kod w najnowszym Firefoksie

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>

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

(Kredyty xnor!)

Bardziej czytelny, ale z 1 dodatkową postacią:

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

Nie żebym musiał ustawić sys.setrecursionlimit(10000), aby uzyskać wynik A(3,10). Dalsza gra w golfa przy użyciu logicznego indeksowania nie działała z powodu dramatycznie rosnącej głębokości rekurencji.

J - 26 char

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

Istnieje alternatywna, bardziej funkcjonalna definicja 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))

Zdarza się, że Iterbardzo łatwo jest napisać w J, ponieważ J ma sposób na przejście m-1do, Acka także zdefiniowanie początkowej wartości Iter1. Wyjaśnione przez wybuch:

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

Zależy to od tego, co J nazywa formą ^:gerunda - zasadniczo sposób na większą kontrolę nad wszystkimi granicami w sposób milczący (bez punktów).

W 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

Musimy zdefiniować ackpo imieniu, aby móc postawić go na stole, ponieważ $:jest okropną, brzydką bestią i rzuca się na każdego, kto próbuje to zrozumieć. Jest to odniesienie do siebie, gdzie ja jest zdefiniowane jako największa fraza czasownika zawierająca je. tablejest przysłówkiem i dlatego chciałbym stać się częścią wyrażenia czasownika, jeśli dasz mu szansę, więc musisz $:użyć nazwanej definicji, aby go użyć.

Edycja: 24 znaki?

Wiele lat później znalazłem rozwiązanie, które jest o dwa znaki krótsze.

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

Jest jednak o wiele wolniejszy: 3 ack 8zajmuje ponad minutę na moim komputerze. Wynika to z tego, że (1) używam fold /zamiast iteracji, więc J prawdopodobnie musi zapamiętać więcej rzeczy niż zwykle, i (2) 0&<~wykonując te same obliczenia (0<[), ponieważ faktycznie wykonuje n+1czasy przed wykonaniem kroku rekurencyjnego podczas wywoływania m ack n- 0&<zdarza się być idempotentnym, więc nie rujnuje obliczeń, ale nszybko się powiększa i ackjest wysoce rekurencyjny.

Wątpię, czy mocniejsza maszyna mogłaby przesunąć nowy kod 3 ack 10w mniej niż minutę, ponieważ jest to komputer, na którym stary kod może znaleźć w mniej niż 15 sekund.

C - 41 bajtów

Nic z tego - małe limity oznaczają, że wszystkie wymagane wartości można obliczyć w czasie krótszym niż 1 sekunda, naiwnie przestrzegając definicji funkcji.

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;
}

JavaScript ES6 (34)

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

Realizacja:

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>

JavaScript (ES6) - 34

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

I 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

Coq, 40

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

Jest to funkcja typu nat -> nat -> nat. Ponieważ Coq pozwala jedynie na konstruowanie funkcji całkowitych, służy również jako formalny dowód, że wznowienie Ackermanna jest uzasadnione.

Próbny:

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

Uwaga: Coq 8.5, wydany po tym wyzwaniu, został przemianowany nat_iterna Nat.iter.

Rakieta 67

(define(a m n)(if(= m 0)(+ n 1)(a(- m 1)(if(= n 0)1(a m(- n 1))))))

Mathematica, 46 bajtów

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

Zajmuje prawie dokładnie minutę a[3,10]. Zauważ, że domyślny limit rekurencji Mathematiki jest za mały na a[3,8]i poza nim (przynajmniej na moim komputerze), ale można to naprawić, konfigurując

$RecursionLimit = Infinity

JavaScript z lambdas, 34

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

Typowa odpowiedź: nic nie może skrócić.

Haskell, 48 44 znaków (36 dla listy)

Chociaż nie jest tak krótkie jak inne rozwiązanie Haskell, to jest godne uwagi, ponieważ wyraża funkcję Ackermanna jako nieskończoną listę, która moim zdaniem jest całkiem fajna. Wynikiem jest lista nieskończona (z list nieskończonych) taka, że ​​w pozycji [m, n] zawiera wartość A (m, n) .

Sama lista nieskończona:

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

W funkcji (zgodnie ze specyfikacją):

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

Sformułowanie wyprowadzono z obserwacji, że ogólnym / powszechnym przypadkiem funkcji Ackermanna jest użycie wartości po lewej stronie jako indeksu w powyższym wierszu. Podstawowym przypadkiem tej rekurencji (tj. Skrajna lewa kolumna wiersza, tj. A (m, 0) ) polega na użyciu drugiej wartości znajdującej się najbardziej na lewo w powyższym wierszu. Podstawowym przypadkiem tej rekurencji jest przypadek A (0, n) = n + 1 , tzn. Pierwszy wiersz to [1..].

Tak otrzymujemy

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

Następnie po prostu dodajemy kolejny poziom iteracji w oparciu o ten wzorzec i przeprowadzamy bezsensowne żonglowanie.

Tiny Lisp , 70 (poza zawodami)

To kończy się z konkurencją, ponieważ język jest nowszy niż pytanie, a także nie udaje mu się uruchomić (A 3 10)zgodnie z wymaganiami w pytaniu z powodu przepełnienia stosu.

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

Definiuje funkcję, Aktóra oblicza funkcję Ackermanna. Sformatowany:

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

Używamy tutaj wszystkich wbudowanych makr ( d(zdefiniuj) i q(cytat) i i(jeśli)) oraz jednej wbudowanej funkcji ( s- odejmij).

i wykonuje swoją prawdziwą część, gdy warunkiem jest liczba> 0 (a w przeciwnym razie część fałszywa), więc nie musimy tutaj robić wyraźnego porównania.

sjest jedyną dostępną operacją arytmetyczną, używamy jej dla n-1/ m-1, a także (s n (s 0 1))dla n+1.

Tiny lisp korzysta z optymalizacji rekurencji ogona, ale to pomaga tylko w Awywołaniu zewnętrznym w wyniku, a nie w A(m, n-1)wywołaniu, które jest używane dla parametrów.

Dzięki mojej niewielkiej implementacji lisp na Cejlonie na JVM, działa (A 3 5) = 253, ale wydaje się, że się psuje, gdy próbuję obliczyć (A 2 125)bezpośrednio (co powinno dać ten sam wynik). Jeśli obliczam to później (A 3 4) = 125, JVM wydaje się być w stanie zoptymalizować funkcje na tyle, aby wstawić niektóre pośrednie wywołania funkcji w moim interpreterie, pozwalając na większą głębokość rekurencji. Dziwne.

Implementacja referencyjna wstaje (A 3 5) = 253, a także (A 2 163) = 329, ale nie powiedzie się (A 2 164), a więc nawet mniej (A 3 6) = (A 2 253).

Idź, 260 243 240 122 bajtów

Nie widziałem, żeby pytanie pozwalało na anony.

daleki od rywalizacji, ale uczę się tego języka i chciałem go przetestować.

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}

użyj go jak, go run ack.goa następnie podaj dwie liczby, mi n. jeśli m> 4 lub n> 30, czas wykonania może przekraczać pół minuty.

dla m=3 n=11:

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

edycja : zapisano ogółem 17 bajtów, przechodząc do switchover if/else-importu i importowania kropkami

Haskell: 81 69 bajtów

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 zajmuje około 45 sekund.

(niekonkurencyjny) Pyth, 15 bajtów

M?GgtG?HgGtH1hH

Wypróbuj online! (przykładowe użycie g3Tdodanej funkcji , co oznacza g(3,10))

(niekonkurencyjny) UGL , 31 30 bajtów

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

Wejście oddzielone znakami nowej linii.

Wypróbuj online!

(Został zaimplementowany jako standardowy przykład w tłumaczu.)

Julia, 34 31 28 bajtów

m\n=m>0?~-m\(n<1||m\~-n):n+1

Jest to nazwana anonimowa funkcja. Jest to prosta implementacja definicji rekurencyjnej, nadużywająca zdolności Julii do redefiniowania operatorów .

Wypróbuj online!

R - 54 52

Użyłem tego jako pretekstu, aby spróbować ominąć R, więc prawdopodobnie jest to naprawdę źle zrobione :)

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

Przykładowy przebieg

> a(3,8)
[1] 2045

Dostaję przepełnienie stosu dla wszystkiego poza tym

T-SQL-222

Myślałem, że spróbuję również zmusić T-SQL do zrobienia tego. Zastosowano inną metodę, ponieważ rekurencja nie jest tak ładna w SQL. Wszystko powyżej 4,2 bombarduje to.

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

pieprzenie mózgu , 90 bajtów

>>>>+>,>,<<[>[>[-[->>>+<<<]<[->+>>+<<<]>-[-<+>]>+>>>>>]<[->+>>]]<[>>+[-<<<+>>>]<<-]<<<]>>.

Wypróbuj online!

Zakłada implementację o dowolnym rozmiarze komórki, z IO jako liczbami. -6 bajtów, jeśli nie masz nic przeciwko użyciu komórek ujemnych.

Kończy się za około 30 sekund dla 3,8 w połączonym tłumaczu, pod warunkiem, że zaznaczysz prawidłowe ustawienia. Wpisz wprowadzone liczby poprzedzone \s, np . 3,9Jest \3\9.

Tcl , 67 bajtów

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

Wypróbuj online!

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

Wypróbuj online!

W kompilatorze online nie działa z powodu przekroczenia limitu czasu, ale w lokalnym interpretatorze Tcl działa dobrze. Profilowałem każde wywołanie Afunkcji root , aby zobaczyć, ile czasu zajęło obliczenie każdej {m,n}testowanej pary :

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

Nie powiedzie się dla ostatniej pary {m,n}={3,10} , ponieważ zajmuje to niewiele więcej niż minutę.

Dla wyższych wartości m konieczne będzie zwiększenie tej recursionlimitwartości.

Nie mogę go skrócić do 65 bajtów, ale nie spełni on wymagania pytania „Twoja funkcja musi być w stanie znaleźć wartość A (m, n) dla m ≤ 3 i n ≤ 10 w mniej niż minutę.”. Bez{} tego upłynie limit czasu na TIO i nie zrobi demo dwóch ostatnich wpisów.

Tcl , 65 bajtów

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

Wypróbuj online!

J: 50

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

Zwraca w ułamku sekundy dla 0 ... 3 vs 0 ... 10:

   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: „0 służy do tego, aby A działało na każdym elemencie, zamiast pożerać lewą i prawą tablicę i generować błędy długości. Ale nie jest to potrzebne, np. 9 = 2 A 3.

APL, 31

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

Całkiem proste. Używa znaku once jeden raz, aby zapisać jeden bajt poprzez odwrócenie argumentów. Przyjmuje m jako lewy argument, a n jako prawy argument.

TryAPL.org

Ruby, 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]])}

Wyjaśnienie

Jest to dość proste tłumaczenie algorytmu podanego w opisie problemu.

• Dane wejściowe są traktowane jako argumenty do lambda. DwaIntegerSpodziewane są .
• Aby przyspieszyć i uniknąć błędów przepełnienia stosu, odpowiedzi są zapamiętywane w Hash h. The||=Operatora jest stosowane do obliczenia wartości, która nie była poprzednio.

a[3,10] jest obliczany na ~ 0,1 sekundy na moim komputerze.

Oto wersja bez golfa

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

Mouse-2002 , 99 83 bajtów

$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+;;]]]@

Java, 274 bajty

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)));}}

Oblicza się A(3,10)w ciągu kilku sekund, a biorąc pod uwagę nieskończoną pamięć i przestrzeń stosu, może obliczyć dowolną kombinację bi Bdopóki wynik jest poniżej 2 ^2147483647 -1.

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

Jest to prosta implementacja. Sformatowany:

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

Alias ​​zapisuje tylko jeden bajt, bez niego (z zapisem Integerzamiast I) uzyskalibyśmy 86 bajtów. Kolejne dwa bajty można zapisać, zastępując == 0je< 1 dwukrotnie.

Przy domyślnych ustawieniach ceylon runbędzie działał do A(3,12) = 32765(i A(4,0) = 13), ale A(3,13)(i dlatego też A(4,1)) zgłosi błąd przepełnienia stosu. ( A(3,12)zajmuje to około 5 sekund, A(3,11)około 3 na moim komputerze).

Używanie ceylon run-js(tj. Uruchamianie wyniku kompilacji do JavaScript na node.js) jest znacznie wolniejsze (wymaga 1 min 19 s A(3,10)) i już się psujeA(3, 11) z „Przekroczeniem maksymalnego stosu wywołań” (przy użyciu ustawień domyślnych) po uruchomieniu dla 1 min 30 s.

Cejlon bez rekurencji, 228

Jako bonus, tutaj jest wersja nierekurencyjna (oczywiście dłuższa, ale odporna na przepełnienie stosu - w pewnym momencie może pojawić się błąd braku pamięci).

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;}}}}

Sformatowany:

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;
            }
        }
    }
}

Na moim komputerze jest on wolniejszy niż wersja rekurencyjna: A(3,11)zajmuje 9,5 sekundy, A(3,12)zajmuje 34 sekundy, A(3,13)trwa 2:08 minut,A(3,14) zajmuje 8:25 minut. (Pierwotnie miałem wersję z leniwymi iteratorami zamiast krotek, które mam teraz, które były nawet znacznie wolniejsze, o tym samym rozmiarze).

Nieco szybciej (21 sekund na A(3,12)) (ale także o jeden bajt dłużej) jest wersja używająca s.pushzamiast s.addAll, ale trzeba było ją kilkakrotnie wywoływać, aby dodać wiele liczb, ponieważ każda z nich zajmuje tylko jedną liczbę całkowitą. Korzystanie z LinkedList zamiast ArrayList jest znacznie wolniejsze.