Funkcja Ackermanna


35

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

15
Jak o to wcześniej nie pytano?
Calvin's Hobbies

9
Myślę, że
fajniej

22
Oddawanie głosu, ponieważ nie ma tutaj żadnego wyzwania. Oczywista odpowiedź - po prostu naiwne wdrożenie funkcji dokładnie zgodnie z jej definicją - zawsze będzie najlepszą odpowiedzią. Pytanie brzmi: „Który język ma najmniejszą liczbę znaków w oczywistym wyrażeniu funkcji Ackermanna?” Prawdziwym zwycięzcą jest język programowania, a nie osoba, która napisała w nim oczywisty program.
David Richerby

1
Co się stanie, jeśli limit rekurencji mojego języka będzie zbyt niski, aby obliczyć A(3,8)i przewyższyć tak naiwnie jak inne? Czy muszę wymyślić rozwiązanie nierekurencyjne, czy też mogę po prostu „założyć nieskończone miejsce na stosie” w tych przypadkach? Jestem całkiem pewien, że to skończy się w ciągu minuty.
Martin Ender

5
@DavidRicherby „Oczywista odpowiedź [...] zawsze będzie najlepszą odpowiedzią”. Nie dotyczy to wszystkich języków. Czuję się trochę brudny, bo mam tylko przykład w moim języku ojczystym, ale istnieje wiele sposobów wyrażenia Ackermann, aw niektórych językach możesz uzyskać oszczędności, korzystając z tego faktu. To był mój zamiar podjęcia wyzwania.
algorytmshark

Odpowiedzi:


7

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.


We współczesnej Pyth (zakładam tego dodano po to wyzwanie) Myślę, że można bardziej lub mniej zmian DaGHRdo Mi ado g. (Czy kolejność argumentów za ?zmianą?)
Lynn

@ Mauris Tak, możesz Mzamiast tego użyć i tak, ?zmieniono kolejność argumentów. Teraz jest warunek, prawda, fałsz. To była prawda, warunek, fałsz.
isaacg

@Lynn Fun Historia Pyth: To pytanie faktycznie wpłynęło na isaacga, aby zmienić (przynajmniej) dwie rzeczy w Pyth: limit rekurencji i zmianę naM !
FryAmTheEggman

23

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


szkoda, że ​​nie mogę użyć 0%nzamiast z n+1powodu pierwszeństwa
dumny haskeller


wow, to było złe przez tak długi czas i nikt, włączając mnie, nie zauważył? dobra robota. więc wygląda na to, że przez pomyłkę skopiowałem pierwszą wersję odpowiedzi, która była błędna, może przez pomyłkę lub dlatego, że myślałem, że zadziała.
dumny haskeller

12

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

W CJam nie potrzebujesz 1>. Po usunięciu (i zmianie ifna ?) obliczenia 3 10 Azajmują 110 sekund w przypadku interpretera online i sześć sekund w przypadku interpretera Java.
Dennis

7

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

Hexdump:

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

Dwójkowy:

000101100000011100101101100010000000011100101111011010

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


6

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>


Testowanie z 0,1 w Chrome nie daje rezultatu.
Nzall

3
Przeczytaj, działa to tylko w najnowszym Firefoksie z powodu ES6
Optimizer

Wow ... mamy 4 praktycznie identyczne rozwiązania JS, wszystkie o 34 bajtach. Nigdy wcześniej tego nie widziałem.
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

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


Dostaję błąd składniowy na 1else. Litera początkowa epowoduje problemy dla analizatora składni, ponieważ liczby można zapisywać jak 1e3.
xnor

Zapisano kilka znaków przełączając się na and/or:A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n
xnor

@xnor: Dzięki za wskazówkę! Zobacz tę dyskusję dotyczącą problemu z analizowaniem. Python 2.7.8 akceptuje 1else, większość innych wersji nie.
Falko

Dzięki za wskaźnik na temat 1else; pozwala mi wycisnąć char tutaj i prawdopodobnie w innych miejscach. Ale do cholery, to jest specyficzne dla wersji! Python 2.7.4 nie pozwala na to. Czy używasz wersji online z wersją 2.7.8, czy powinienem ją pobrać?
xnor

@xnor: To instalacja offline. np. ideone.com również nie parsuje1else .
Falko

6

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.


5

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

5

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>


4

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

3

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.



2

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

1
Wow, więc mówisz, że JS jest ponad 25 razy szybszy niż Mathematica?
Optymalizator

@Optimizer Przynajmniej jeśli chodzi o rekurencję ... Chyba po części chodzi o to, że musi za każdym razem wymyślać, której definicji użyć, a Ifbycie funkcją jest jeszcze wolniejsze.
Martin Ender

1
Z zapamiętywaniem zajmuje 0,07 sekundy. Czyli m_~a~n_:=m~a~n=...
Mark Adler

@MarkAdler To naprawdę fajny sposób na zapamiętywanie w Mathematica!
Martin Ender

2

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


2

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.


Możesz mieć alias iteratedo pojedynczej litery, tj.i=iterate;ack=i ...
dumny haskeller

@proudhaskeller o tak, nie myślałem o tym. Dzięki! Pożyczanie nazwy operatora również.
FireFly,

2

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


może to być konkurencyjne, z wyjątkiem białych znaków i nawiasów;)
cat

2

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


1
Możesz zrobić jeszcze lepiej! Oświadczenie switch 0 {case m:r=n+1 case n:r=a(m-1,1) default:r=a(m-1,a(m,n-1))}Go switchjest tak pięknie elastyczne!
EMBLEMIA

@EMBLEM Dzięki, minęło tak dużo czasu, odkąd napisałem wiersz Go, ale cieszę się, że są inni golfiści o: D
kot

1

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.


1
to jest kod golfowy, więc powinieneś spróbować mieć możliwie najkrótszy kod. na przykład usuń niepotrzebne spacje i jawny typ
dumny haskeller

brakuje ci również parens na czwartej linii
dumny haskeller


1

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



1

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

dla twojego submissona R wygląda na to, że nie potrzebujesz, {}chociaż nie ma limitu przepełnienia stosu, ponieważ R nie ma TCO ...
Giuseppe

@Giuseppe dzięki ... w mojej obronie byłem wtedy nowy :)
MickyT

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.


1

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!


Tcl , 77 bajtów

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!


0

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.



0

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


0

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

a[3,10]wrzuć SystemStackError na moją maszynę ...
TuxCrafting,

Golfowe nitpicks: Możesz zmienić m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])nam<1?n+1:a[m-1,n<1?1:a[m,n-1]]
Simply Beautiful Art

0

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

0

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.


Wiem, że minęło trochę czasu, ale możesz 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)));}
zagrać w

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

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.