Urutan Pengulangan Biner

10

Urutan pengulangan biner adalah urutan yang didefinisikan secara rekursif dari bentuk berikut:

definisi urutan perulangan biner

Ini adalah generalisasi dari deret Fibonacci ( x = 1, y = 2, a = [1, 1], alpha = 1, beta = 1) dan deret Lucas ( x = 1, y = 2, a = [2, 1], alpha = 1, beta = 1).

Tantangan

Mengingat n, x, y, a, alpha, dan beta, dalam format yang wajar, output njangka th urutan kekambuhan yang sesuai biner.

Aturan

  • Anda dapat memilih urutan yang akan diindeks 1 atau 0, tetapi pilihan Anda harus konsisten di semua input, dan Anda harus membuat catatan pilihan Anda dalam jawaban Anda.
  • Anda dapat mengasumsikan bahwa tidak ada input yang tidak valid yang akan diberikan (seperti urutan yang berakhir sebelum n, atau urutan yang referensi istilah yang tidak ditentukan, suka F(-1)atau di F(k)mana k > n). Akibatnya, xdan yakan selalu positif.
  • Input dan output akan selalu berupa bilangan bulat, dalam batas tipe bilangan bulat alami bahasa Anda. Jika bahasa Anda memiliki bilangan bulat tanpa batas, input dan output akan berada dalam kisaran [2**31, 2**31-1](yaitu kisaran untuk integer komplemen dua bertanda tangan 32-bit yang ditandatangani).
  • aakan selalu berisi ynilai persis (sesuai definisi).

Uji Kasus

Catatan: semua test case diindeks 0.

x = 1, y = 2, a = [1, 1], alpha = 1, beta = 1, n = 6 => 13
x = 1, y = 2, a = [2, 1], alpha = 1, beta = 1, n = 8 => 47
x = 3, y = 5, a = [2, 3, 5, 7, 11], alpha = 2, beta = 3, n = 8 => 53
x = 1, y = 3, a = [-5, 2, 3], alpha = 1, beta = 2, n = 10 => -67
x = 5, y = 7, a = [-5, 2, 3, -7, -8, 1, -9], alpha = -10, beta = -7, n = 10 => 39
Mego
sumber
Apakah menerima apesanan terbalik dianggap masuk akal?
Dennis
@ Dennis Ya, benar.
Mego
OK, terima kasih sudah menjelaskan.
Dennis

Jawaban:

2

Jelly , 11 byte

⁴Cịæ.⁵ṭµ¡⁶ị

Cobalah online!  1  |  2  |  3  |  4  |  5 

Bagaimana itu bekerja

⁴Cịæ.⁵ṭµ¡⁶ị  Main link. Arguments: a; [x, y]; [α, β]; n (1-based)

       µ     Combine the links to the left into a chain.
        ¡    Execute that chain n times, updating a after each execution.
⁴              Yield [x, y].
 C             Complement; yield [1 - x, 1 - y].
  ị            Retrieve the elements of a at those indices.
               Indexing is 1-based and modular in Jelly, so this retrieves
               [a[-x], a[-y]] (Python syntax).
     ⁵         Yield [α, β].
   æ.          Take the dot product of [a[-x], a[-y]] and [α, β].
         ⁶   Yield n.
          ị  Retrieve the element of a at index n.
Dennis
sumber
2

Python 2, 62 byte

x,y,l,a,b=input();f=lambda n:l[n]if n<y else a*f(n-x)+b*f(n-y)

Solusi rekursif langsung. Semua input diambil dari STDIN kecuali untuk nsebagai argumen fungsi, pemisahan yang diizinkan secara default (meskipun kontroversial).

Sepertinya tidak ada cara untuk menghemat byte dengan and/ordi tempat if/elsekarena l[n]bisa jadi palsu sebagai 0.

Tidak
sumber
2

Python 2, 59 byte

x,y,A,a,b,n=input()
exec'A+=a*A[-x]+b*A[-y],;'*n
print A[n]

Uji di Ideone .

Dennis
sumber
2

JavaScript (ES6), 51 44 byte

(x,y,z,a,b)=>g=n=>n<y?z[n]:a*g(n-x)+b*g(n-y)

Perhatikan bahwa fungsi ini sebagian dikerjakan, misalnya f(1,2,[1,1],1,1)(8)mengembalikan 34. Akan memakan biaya 2 byte untuk membuat fungsi antara tidak saling tergantung satu sama lain (saat ini hanya fungsi yang dihasilkan terakhir yang bekerja dengan benar).

Sunting: Disimpan 7 byte berkat @Mego menunjukkan bahwa saya telah mengabaikan bahwa array yang lewat selalu berisi yelemen pertama dari hasilnya.

Neil
sumber
@Mego Saya tahu saya sering mengabaikan detail pertanyaan tetapi yang satu menurut saya sangat halus.
Neil
2

Haskell, 54 48 byte

l@(x,y,a,p,q)%n|n<y=a!!n|k<-(n-)=p*l%k x+q*l%k y
Damien
sumber
0

J, 43 byte

{:{](],(2>@{[)+/ .*]{~1-@>@{[)^:(3>@{[)>@{.

Dengan urutan awal istilah A , hitung istilah berikutnya n kali menggunakan parameter x , y , α , dan β . Setelah itu, ia memilih istilah ke- n dalam urutan yang diperluas dan hasilnya sebagai hasilnya.

Pemakaian

Karena J hanya mendukung 1 atau 2 argumen, saya mengelompokkan semua parameter sebagai daftar daftar kotak. Nilai benih awal A adalah yang pertama, diikuti oleh parameter x dan y sebagai daftar, diikuti oleh parameter α dan β sebagai daftar, dan diakhiri dengan nilai n .

   f =: {:{](],(2>@{[)+/ .*]{~1-@>@{[)^:(3>@{[)>@{.
   2 3 5 7 11;3 5;2 3;8
┌──────────┬───┬───┬─┐
│2 3 5 7 11│3 5│2 3│8│
└──────────┴───┴───┴─┘
   f 2 3 5 7 11;3 5;2 3;8
53
   f _5 2 3 _7 _8 1 _9;5 7;_10 _7;10
39
mil
sumber