Fungsi Ackermann

35

Fungsi Ackermann terkenal karena menjadi salah satu contoh paling sederhana dari total, fungsi yang dapat dihitung yang bukan rekursif primitif.

Kami akan menggunakan definisi A(m,n)mengambil dua bilangan bulat tidak negatif di mana

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

Anda dapat menerapkan

  • fungsi bernama atau anonim mengambil dua bilangan bulat sebagai input, mengembalikan bilangan bulat, atau
  • sebuah program mengambil dua bilangan bulat yang dipisahkan spasi atau baris baru pada STDIN, mencetak hasilnya ke STDOUT.

Anda tidak boleh menggunakan fungsi Ackermann atau fungsi hyperexponentiation dari perpustakaan, jika ada, tetapi Anda dapat menggunakan fungsi lain dari perpustakaan lain. Eksponen reguler diperbolehkan.

Fungsi Anda harus dapat menemukan nilai A(m,n)untuk m ≤ 3 dan n ≤ 10 dalam waktu kurang dari satu menit. Setidaknya harus diakhiri secara teoritis pada input lain: diberi ruang stack tak terbatas, tipe Bigint asli, dan periode waktu yang lama secara sewenang-wenang, itu akan mengembalikan jawabannya. Sunting: Jika bahasa Anda memiliki kedalaman rekursi default yang terlalu ketat, Anda dapat mengonfigurasi ulang tanpa biaya karakter.

Pengajuan dengan jumlah karakter terpendek akan menang.

Berikut ini beberapa nilai, untuk memeriksa jawaban Anda:

  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...
algoritme hiu
sumber
15
Bagaimana ini belum pernah ditanyakan sebelumnya ??
Hobi Calvin
9
Saya pikir akan lebih menyenangkan untuk membuat kode tercepat
Sp3000
22
Menunduk karena tidak ada tantangan di sini. Jawaban yang jelas - hanya secara naif mengimplementasikan fungsi persis sesuai dengan definisinya - selalu akan menjadi jawaban terbaik. Jadi pertanyaannya adalah "Bahasa mana yang memiliki jumlah karakter paling sedikit dalam ekspresi yang jelas dari fungsi Ackermann?" Pemenang sejati adalah bahasa pemrograman, bukan orang yang menulis program yang jelas di dalamnya.
David Richerby
1
Bagaimana jika batas rekursi bahasa saya terlalu rendah untuk dihitung A(3,8)dan di atas sama naifnya dengan yang lain? Apakah saya harus datang dengan solusi non-rekursi, atau bisakah saya juga "mengasumsikan ruang stack tak terbatas" dalam kasus ini? Saya cukup yakin, itu akan berakhir dalam satu menit.
Martin Ender
5
@DavidRicherby "Jawaban yang jelas [...] akan selalu menjadi jawaban terbaik." Ini tidak berlaku untuk semua bahasa. Saya merasa sedikit kotor karena hanya memiliki contoh dalam bahasa rumah saya, tetapi ada beberapa cara untuk mengekspresikan Ackermann dan dalam beberapa bahasa Anda bisa mendapatkan penghematan dengan menggunakan fakta itu. Ini adalah niat saya untuk tantangan ini.
algoritme

Jawaban:

7

Pyth , 19

DaGHR?atG?aGtHH1GhH

Menentukan a, yang berfungsi sebagai fungsi Ackermann. Perhatikan bahwa ini membutuhkan kedalaman rekursi yang lebih tinggi daripada compiler pyth resmi yang diizinkan hingga hari ini untuk menghitung a 3 10, jadi saya meningkatkan kedalaman rekursi. Ini bukan perubahan bahasa, hanya ke kompiler.

Uji:

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

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

Penjelasan:

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)

Pada dasarnya, ini pertama-tama mengkondisikan pada nilai kebenaran Gapakah akan muncul kembali atau mengembalikan H + 1. Jika berulang, argumen pertama selalu G-1, dan itu mengkondisikan pada nilai kebenaran Hapakah akan digunakan a(G,H-1)sebagai argumen kedua, atau untuk digunakan 1sebagai argumen kedua.

isaacg
sumber
Dalam Pyth modern (saya menganggap ini ditambahkan setelah tantangan ini) saya pikir Anda dapat lebih atau kurang berubah DaGHRke Mdan ake g. (Apakah urutan argumen untuk ?perubahan?)
Lynn
@Mauris Ya, Anda bisa menggunakan Msebagai gantinya, dan ya, ?urutan argumen berubah. Sekarang kondisinya, benar, salah. Itu benar, kondisi, salah.
isaacg
@Lynn Fun Fakta sejarah Pyth: Pertanyaan ini sebenarnya memengaruhi isaacg untuk mengubah (setidaknya) dua hal tentang Pyth: batas rekursi dan perubahan keM !
FryAmTheEggman
23

Haskell, 35

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

ini menentukan fungsi operator %.

ini bekerja dengan memperhatikan bahwa m%n(di mana aadalah fungsi Ackerman) untuk nol myang (m-1)%diterapkan n+1kali untuk 1. misalnya, 3%2didefinisikan apa 2%(3%1)adanya 2%(2%(3%0)), dan ini2%(2%(2%1))

haskeller bangga
sumber
Sayang sekali saya tidak bisa menggunakan 0%nbukan n+1karena diutamakan
haskeller bangga
wow, ini sudah salah sejak lama, dan tak seorang pun, termasuk saya, memperhatikan? kerja bagus. jadi sepertinya saya salah menyalin versi pertama dari jawaban, yang salah, mungkin karena kesalahan atau karena saya pikir itu berhasil.
haskeller bangga
12

GolfScript (30)

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

Demo online

Tanpa 1>(kasus-kasus khusus A(1, n)) yang dibutuhkan 9 menit untuk menghitung A(3, 10)di komputer saya sudah mengujinya. Dengan case khusus itu cukup cepat sehingga demo online membutuhkan waktu kurang dari 10 detik.

Perhatikan bahwa ini bukan terjemahan definisi yang naif. Kedalaman rekursi dibatasi oleh m.

Pembedahan

{             # 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
sumber
Di CJam, Anda tidak perlu 1>. Setelah dihapus (dan diubah ifke ?), komputasi 3 10 Amembutuhkan 110 detik dengan juru bahasa online dan enam detik dengan juru bahasa Java.
Dennis
7

Kalkulus biner biner , 54 bit = 6,75 byte

Hexdump:

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

Biner:

000101100000011100101101100010000000011100101111011010

Ini adalah λ m . mg . λ n . g ( n g 1)) (λ n . λ f . λ x . f ( n f x )), di mana semua angka direpresentasikan sebagai angka Gereja .

Anders Kaseorg
sumber
6

JavaScript, ES6, 41 34 byte

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

Jalankan ini di Konsol Firefox terbaru dan itu akan membuat fungsi yang disebut fyang dapat Anda panggil dengan nilai mdan nsuka yang berbeda

f(3,2) // returns 29

ATAU

coba kode di bawah ini dalam Firefox terbaru

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>

Pengoptimal
sumber
Menguji ini dengan 0,1 di Chrome tidak memberikan hasil.
Nzall
3
Tolong baca, ini hanya berfungsi di Firefox terbaru karena ES6
Optimizer
Wow ... kami punya 4 solusi JS yang hampir sama, semuanya 34 byte. Saya belum pernah melihat itu sebelumnya.
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

(Kredit ke xnor!)

Lebih mudah dibaca, tetapi dengan 1 karakter lebih:

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

Bukan berarti saya harus mengatur sys.setrecursionlimit(10000)untuk mendapatkan hasil A(3,10). Golf lebih lanjut menggunakan pengindeksan logis tidak bekerja karena kedalaman rekursi tumbuh secara dramatis.

Falko
sumber
Saya mendapatkan kesalahan sintaks pada 1else. Huruf awal emenyebabkan masalah bagi parser karena angka dapat ditulis seperti 1e3.
xnor
Menyimpan beberapa karakter beralih ke and/or:A=lambda m,n:m and A(m-1,n<1or A(m,n-1))or-~n
xnor
@ xnor: Terima kasih atas tipnya! Lihat diskusi ini untuk masalah parsing. Python 2.7.8 menerima 1else, sebagian besar versi lain tidak.
Falko
Terima kasih atas petunjuk tentang 1else; itu memungkinkan saya memeras char di sini dan mungkin di tempat lain. Tapi sialan itu khusus versi! Python 2.7.4 tidak mengizinkannya. Apakah Anda menggunakan versi online dengan 2.7.8 atau haruskah saya mengunduhnya?
xnor
@ xnor: Ini instalasi offline. ideone.com , misalnya, gagal mengurai 1elsejuga.
Falko
6

J - 26 char

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

Ada definisi Ackermann alternatif yang lebih fungsional:

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

Kebetulan Itersangat mudah untuk menulis dalam J, karena J memiliki cara untuk meneruskan m-1ke Ackdan juga untuk menentukan nilai awal Itermenjadi 1. Dijelaskan oleh ledakan:

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

Ini bergantung pada apa yang disebut J sebagai bentuk gerund - pada ^:dasarnya cara untuk memiliki kontrol lebih besar atas semua batasan dengan cara diam-diam (point-free).

Di 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

Kita perlu mendefinisikan ackdengan nama untuk bisa meletakkannya di meja, karena itu $:adalah binatang yang mengerikan, jelek dan menyerang siapa pun yang mencoba memahaminya. Ini adalah referensi-diri, di mana diri didefinisikan sebagai frase kata kerja terbesar yang mengandungnya. tableadalah kata keterangan dan sangat ingin menjadi bagian dari frasa kata kerja jika Anda memberinya kesempatan, jadi Anda harus menjebak $:dalam definisi yang disebutkan untuk menggunakannya.


Sunting: 24 karakter?

Bertahun-tahun kemudian, saya menemukan solusi yang dua karakter lebih pendek.

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

Ini jauh lebih lambat: 3 ack 8membutuhkan waktu lebih dari satu menit pada mesin saya. Ini karena (1) Saya menggunakan lipatan /alih-alih iterasi, jadi J mungkin harus mengingat lebih banyak hal daripada biasanya, dan (2) saat 0&<~melakukan perhitungan yang sama dengan (0<[), itu sebenarnya dieksekusi n+1kali sebelum mengambil langkah rekursif ketika memohon m ack n- 0&<terjadi menjadi idempoten, sehingga tidak merusak perhitungan, tetapi nmenjadi besar cepat dan acksangat rekursif.

Saya ragu bahwa mesin yang lebih kuat dapat mendorong kode baru di bawah satu menit, karena ini adalah komputer di mana kode lama dapat ditemukan 3 ack 10dalam waktu kurang dari 15 detik.

algoritme hiu
sumber
5

C - 41 byte

Tidak ada artinya - batas kecil berarti bahwa semua nilai yang diperlukan dapat dihitung dalam waktu kurang dari 1 detik dengan secara naif mengikuti definisi fungsi.

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
sumber
5

Javascript ES6 (34)

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

Pelaksanaan:

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
sumber
4

JavaScript (ES6) - 34

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

Dan ujian:

> 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
sumber
3

Coq, 40

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

Ini adalah fungsi tipe nat -> nat -> nat . Karena Coq hanya memungkinkan konstruksi fungsi total, Coq juga berfungsi sebagai bukti resmi bahwa perulangan Ackermann beralasan.

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

Catatan: Coq 8.5, dirilis setelah tantangan ini, diganti namanya nat_itermenjadi Nat.iter.

Anders Kaseorg
sumber
2

Raket 67

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

Mathematica, 46 byte

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

Memakan waktu yang cukup tepat a[3,10]. Perhatikan bahwa batas rekursi default Mathematica terlalu kecil untuk a[3,8]dan di luar (setidaknya di komputer saya), tetapi itu dapat diperbaiki dengan mengkonfigurasi

$RecursionLimit = Infinity
Martin Ender
sumber
1
Wow, jadi maksudmu JS lebih cepat 25 kali dari Mathematica?
Pengoptimal
@Optimizer Setidaknya ketika datang ke rekursi ... Saya kira sebagian jika itu yang harus mencari tahu setiap kali definisi yang digunakan, dan Ifmenjadi fungsi bahkan lebih lambat.
Martin Ender
1
Dengan memoisasi, dibutuhkan 0,07 detik. Yaitu m_~a~n_:=m~a~n=...
Mark Adler
@MarkAdler Itu cara yang sangat bagus untuk melakukan memoisasi di Mathematica!
Martin Ender
2

Javascript dengan lambdas, 34

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

Jawaban tipical, tidak dapat membuat sesuatu lebih pendek.

Qwertiy
sumber
2

Haskell, 48 44 karakter (36 untuk daftar)

Meskipun tidak sependek solusi Haskell lainnya, solusi ini terkenal karena mengekspresikan fungsi Ackermann sebagai daftar tanpa batas, yang menurut saya agak rapi. Hasilnya adalah daftar tak terbatas (dari daftar tak terbatas) sehingga pada posisi [m, n] ia memegang nilai A (m, n) .

Daftar yang tak terbatas itu sendiri:

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

Sebagai fungsi (untuk memenuhi spesifikasi):

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

Formulasi diturunkan dengan mengamati bahwa kasus umum / umum untuk fungsi Ackermann adalah menggunakan nilai di sebelah kiri sebagai indeks pada baris di atas. Kasing dasar untuk rekursi ini (yaitu kolom paling kiri dari suatu baris, yaitu A (m, 0) ) adalah menggunakan nilai paling kiri kedua pada baris di atas. Kasus dasar untuk yang rekursi adalah A (0, n) = n + 1 kasus, yaitu baris pertama adalah [1..].

Jadi, kita dapatkan

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

Kemudian kita cukup menambahkan tingkat iterasi lain berdasarkan pola itu, dan melakukan beberapa juggling sia-sia .

FireFly
sumber
Anda bisa alias iterateke satu nama huruf yaitui=iterate;ack=i ...
bangga haskeller
@ Proudhaskeller oh yeah, tidak memikirkan itu. Terima kasih! Meminjam nama operator Anda juga.
FireFly
2

Tiny Lisp , 70 (keluar dari kompetisi)

Ini kehabisan kompetisi, karena bahasanya lebih baru dari pertanyaan, dan itu juga tidak berhasil menjalankan (A 3 10)seperti yang dipersyaratkan dalam pertanyaan, karena stack overflow.

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

Ini mendefinisikan fungsi Ayang menghitung fungsi Ackermann. Diformat:

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

Kami menggunakan semua makro builtin ( d(define) dan q(quote) dan i(if)) dan satu fungsi builtin ( s- kurangi) di sini.

i mengeksekusi bagian yang sebenarnya ketika kondisinya adalah angka> 0 (dan sebaliknya bagian yang salah), jadi kita tidak perlu melakukan perbandingan eksplisit di sini.

sadalah satu-satunya operasi aritmatika yang tersedia, kami menggunakannya untuk n-1/m-1 , dan juga (s n (s 0 1))untuk n+1.

Lump kecil menggunakan optimasi rekursi ekor, tetapi ini hanya membantu untuk bagian luar A panggilan dalam hasil, bukan untuk A(m, n-1)panggilan yang digunakan untuk parameter.

Dengan implementasi cisp kecil saya di Ceylon pada JVM, ia bekerja hingga(A 3 5) = 253 , tetapi tampaknya rusak ketika mencoba menghitung (A 2 125)secara langsung (yang seharusnya memberikan hasil yang sama). Jika menghitung setelah itu(A 3 4) = 125 , JVM tampaknya harus mengoptimalkan fungsi cukup untuk inline beberapa panggilan fungsi menengah di interpreter saya, memungkinkan kedalaman rekursi lebih. Aneh.

The implementasi referensi bangun untuk (A 3 5) = 253dan juga (A 2 163) = 329, tapi tidak berhasil (A 2 164), dan karena itu bahkan kurang (A 3 6) = (A 2 253).

Paŭlo Ebermann
sumber
ini mungkin kompetitif kecuali untuk spasi putih dan kurung;)
cat
2

Pergi, 260 243 240 122 byte

Saya tidak melihat bahwa pertanyaan itu memungkinkan beberapa fungsi.

jauh dari kompetitif tetapi saya sedang belajar bahasa ini dan saya ingin mengujinya.

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}

gunakan seperti go run ack.golalu berikan dua angka, mdan n. jika m> 4 atau n> 30, waktu eksekusi mungkin lebih dari setengah menit.

untuk m=3 n=11:

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

edit : menyimpan total 17 byte dengan beralih ke switchover if/elsedan dot-import

kucing
sumber
1
Anda dapat melakukan yang lebih baik lagi! Pernyataan switch 0 {case m:r=n+1 case n:r=a(m-1,1) default:r=a(m-1,a(m,n-1))}Go switchsangat indah dan fleksibel!
EMBLEM
@EMBLEM Terima kasih, sudah begitu lama sejak saya menulis sebaris Go, tapi saya senang melihat ada pegolf Go lainnya tentang: D
cat
1

Haskell: 81 69 byte

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 membutuhkan sekitar 45 detik.

SophR
sumber
1
ini kode golf, jadi Anda harus mencoba kode sesingkat mungkin. misalnya, hapus spasi yang tidak perlu dan tipe eksplisit
haskeller bangga
Anda juga melewatkan orangtua di baris keempat
haskeller bangga
1

(non-bersaing) Pyth, 15 byte

M?GgtG?HgGtH1hH

Cobalah online!(Contoh penggunaan fungsi g3Tditambahkan, yang berarti g(3,10))

Biarawati Bocor
sumber
1

(tidak bersaing) UGL , 31 30 byte

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

Input dipisahkan oleh baris baru.

Cobalah online!

(Ini telah diterapkan sebagai contoh standar dalam penerjemah.)

Biarawati Bocor
sumber
1

R - 54 52

Saya menggunakan ini sebagai alasan untuk mencoba dan mendapatkan kepalaku sekitar R, jadi ini mungkin benar-benar dilakukan dengan buruk :)

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

Contoh dijalankan

> a(3,8)
[1] 2045

Saya mendapatkan stack overflow untuk apa pun selain itu

T-SQL-222

Saya pikir saya akan mencoba untuk mendapatkan T-SQL untuk melakukannya juga. Menggunakan metode yang berbeda karena rekursi tidak begitu baik di SQL. Lebih dari 4,2 bom itu.

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
sumber
untuk submisson R Anda, sepertinya Anda tidak memerlukannya {}meskipun tidak ada yang membantu batas stack overflow, karena R tidak memiliki TCO ...
Giuseppe
@Giuseppe terima kasih ... dalam pembelaan saya, saya baru
mengenalnya
1

brainfuck , 90 byte

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

Cobalah online!

Mengasumsikan implementasi dengan ukuran sel yang berubah-ubah, dengan IO sebagai angka. -6 byte jika Anda tidak keberatan menggunakan sel negatif.

Selesai dalam waktu sekitar 30 detik selama 3,8 dalam penerjemah tertaut, asalkan Anda mencentang pengaturan yang benar. Ketik nomor diinput didahului dengan \s, misalnya 3,9adalah \3\9.

Jo King
sumber
1

Tcl , 67 byte

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

Cobalah online!


Tcl , 77 byte

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

Cobalah online!

Dalam kompiler online, ia gagal dijalankan karena time-out, tetapi dalam interpreter Tcl lokal ia berjalan dengan baik. Saya membuat profil setiap panggilan root keA berfungsi, untuk melihat berapa banyak waktu perhitungan yang diperlukan untuk setiap {m,n}subjek pasangan yang akan diuji:

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

Gagal untuk pasangan terakhir {m,n}={3,10}, karena dibutuhkan sedikit lebih dari satu menit.

Untuk nilai yang lebih tinggi m, akan diperlukan untuk meningkatkanrecursionlimit nilainya.


Saya dapat membuatnya lebih pendek hingga 65 byte, tetapi tidak akan memenuhi persyaratan pertanyaan "Fungsi Anda harus dapat menemukan nilai A (m, n) untuk m ≤ 3 dan n ≤ 10 dalam waktu kurang dari satu menit.". Tanpa{} itu akan habis pada TIO dan tidak melakukan demo dari dua entri terakhir.

Tcl , 65 byte

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

Cobalah online!

sergiol
sumber
0

J: 50

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

Kembali dalam sepersekian detik untuk 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: the "0 berfungsi untuk membuat A bekerja pada setiap elemen tunggal, alih-alih melahap array kiri dan kanan, dan menghasilkan kesalahan panjang. Tapi itu tidak diperlukan untuk misalnya. 9 = 2 A 3.

jpjacobs
sumber
codegolf.stackexchange.com/a/40174/48934 Anda telah dikalahkan!
Leaky Nun
0

APL, 31

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

Cukup mudah. Menggunakan karakter ⍨ satu kali untuk menyimpan satu byte dengan membalik argumen. Membawa m sebagai argumen kiri dan n sebagai argumen kanan.

TryAPL.org

Shujal
sumber
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]])}

Penjelasan

Ini adalah terjemahan yang cukup mudah dari algoritma yang diberikan dalam deskripsi masalah.

  • Masukan diambil sebagai argumen untuk lambda. Dua Integers diharapkan.
  • Untuk kecepatan dan menghindari kesalahan stack-overflow, jawaban disimpan di dalam Hash h. The ||=operator yang digunakan untuk menghitung nilai yang sebelumnya tidak dihitung.

a[3,10] dihitung dalam ~ 0,1 detik di mesin saya.

Berikut ini adalah versi yang tidak dipisahkan

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
sumber
a[3,10]melempar SystemStackError pada mesin saya ...
TuxCrafting
Nitpicks Golf: Anda bisa berubah m<1?(n+1):(n<1?a[m-1,1]:a[m-1,a[m,n-1]])menjadim<1?n+1:a[m-1,n<1?1:a[m,n-1]]
Simply Beautiful Art
0

Mouse-2002 , 99 83 byte

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

Java, 274 byte

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

Ini menghitung A(3,10)dalam beberapa detik, dan diberi ruang memori dan stack yang tak terbatas, ia dapat menghitung kombinasi apa pun bdan Bselama hasilnya di bawah 2 2147483647 -1.

dorukayhan ingin Monica kembali
sumber
Saya tahu ini sudah lama, tetapi Anda bisa bermain golf ini hingga 185 byte :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)));

Ini adalah implementasi yang mudah. Diformat:

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 ​​menyimpan hanya satu byte, tanpa itu (dengan tulisan Integeralih-alihI ) kita akan mendapatkan 86 byte. Dua byte dapat disimpan dengan mengganti == 0dengan < 1dua kali.

Dengan pengaturan default ceylon run, ini akan berfungsi hingga A(3,12) = 32765(dan A(4,0) = 13), tetapi A(3,13)(dan karenanya jugaA(4,1) ) akan melempar kesalahan stack overflow. ( A(3,12)membutuhkan sekitar 5 detik, A(3,11)sekitar 3 pada komputer saya.)

Menggunakan ceylon run-js(yaitu menjalankan hasil kompilasi ke JavaScript pada node.js) jauh lebih lambat (perlu 1 menit 19 detik untuk A(3,10)), dan sudah terputus untuk A(3, 11)dengan »Ukuran tumpukan panggilan maksimum melebihi« (menggunakan pengaturan default) setelah berjalan selama 1 min 30 dtk.


Ceylon tanpa rekursi, 228

Sebagai bonus, ini adalah versi non-rekursif (lebih lama, tentu saja, tetapi kebal terhadap stack overflow - mungkin mendapatkan kesalahan kehabisan memori di beberapa titik).

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

Diformat:

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

Ini lebih lambat di komputer saya daripada versi rekursif: A(3,11)membutuhkan 9,5 detik, A(3,12)membutuhkan 34 detik, A(3,13)membutuhkan waktu 2:08 menit,A(3,14) membutuhkan waktu 8:25 menit. (Saya awalnya memiliki versi menggunakan iterables malas, bukan tuple yang saya miliki sekarang, yang bahkan lebih lambat, dengan ukuran yang sama).

Sedikit lebih cepat (21 detik untuk A(3,12)) (tetapi juga satu byte lebih lama) adalah versi yang menggunakan s.pushalih-alih s.addAll, tetapi itu perlu dipanggil beberapa kali untuk menambahkan beberapa angka, karena masing-masing hanya membutuhkan satu bilangan bulat. Menggunakan LinkedList daripada ArrayList jauh lebih lambat.

Paŭlo Ebermann
sumber