23

Hari ini tujuan Anda adalah untuk menemukan bilangan bulat a dan b diberikan bilangan bulat non-negatif n sehingga:

(3 + sqrt (5)) ^ n = a + b * sqrt (5)

Anda harus menulis program atau fungsi yang mengambil parameter n dan menghasilkan a dan b dalam format pilihan Anda.

Celah standar berlaku. Selain itu, dimaksudkan agar Anda menerapkan sendiri masalah di atas menggunakan aritmatika dasar. Jadi, Anda tidak boleh menggunakan fungsionalitas aljabar, rasional, atau fungsi aljabar bawaan yang dibangun di dalam matematika (misalnya urutan Lucas ).

Kode terpendek dalam byte menang.

Contoh input / output:

0 → 1, 0
1 → 3, 1
2 → 14, 6
3 → 72, 32
4 → 376, 168
5 → 1968, 880
6 → 10.304, 4608
7 → 53.952, 24.128
8 → 282.496, 126.336
9 → 1.479.168, 661.504

code-golf arithmetic orlp
sumber

3

Dyalog APL, 18 byte

((3∘×+5 1×⌽)⍣⎕)1 0

Ini adalah program yang membutuhkan input ⎕.

 (         )         Monadic train:
  3∘×                3 times argument
     +               Plus
      5 1×⌽          (5 1) times the reverse
(           ⍣⎕)      Apply that function (input) times
               1 0   starting with (1 0)

Fitur yang digunakan di sini dilaksanakan dengan baik sebelum April 2015, membuat jawaban ini berlaku.

Coba di sini . Perhatikan bahwa tryapl.org adalah bagian terbatas Dyalog dan tidak mendukung ⎕.

lirtosiast
sumber

16

Oktaf, 26 byte

[3 5;1 3]**input('')*[1;0]

Karena ( a + b * sqrt (5)) * (3 + sqrt (5)) = ( 3a + 5b ) + ( a + 3b ) * sqrt (5),

mengalikan vektor input

| 1 |    /* a = 1 */
| 0 |    /* b = 0 */

yang merupakan singkatan dari 1 = (3 + sqrt (5)) ^ 0 oleh matriks

| 3 5 |
| 1 3 |

tampak alami. Alih-alih mengulang nkali, kita lebih baik menaikkan matriks ke kekuatan ndan kemudian mengalikannya dengan vektor input.

pawel.boczarski
sumber

Anda menjual diri Anda pendek, [3 5;1 3]**input('')*[1;0]adalah 26 byte, bukan 41.

orlp

3

@(n)[3 5;1 3]^n*[1;0](fungsi pegangan) akan menghemat lima karakter, ide bagus mut!

flawr

14

Python 2, 50

a=1;b=0
exec"a,b=3*a+5*b,3*b+a;"*input()
print a,b

Mengalikan dengan 3+sqrt(5)berulang kali dengan aksinya pada pasangan yang (a,b)mewakili a+b*sqrt(5). Setara dengan memulai dengan vektor kolom [1,0]dan nkali mengalikan kiri oleh matriks [[3,5],[1,3]].

Tidak
sumber

12

Julia, 22 20 byte

n->[3 5;1 3]^n*[1;0]

Ini menciptakan fungsi lambda yang mengambil bilangan bulat tunggal sebagai input dan mengembalikan vektor 2 elemen bilangan bulat yang sesuai dengan solusi [a, b]. Untuk menyebutnya, berikan nama, mis f=n->....

Mulailah dengan mengalikan

Ekspansi awal

Kita kemudian dapat menerjemahkan sisi kanan persamaan ini ke dalam matriks 2-kolom, di mana yang pertama sesuai dengan koefisien a dan yang kedua dengan koefisien b :

Matriks

Kalikan matriks ini dengan sendirinya n kali, lalu kalikan dengan vektor kolom (1, 0), dan POOF! Keluar muncul vektor solusi.

Contoh:

julia> println(f(0))
[1,0]

julia> println(f(5))
[1968,880]

Alex A.
sumber

8

J, 20 byte

+/@:*(3 5,.1 3&)&1 0

Gandakan vektor [1 0]dengan waktu matriks [[3 5] [1 3]] n.

2 byte disimpan berkat @algorithmshark.

Penggunaan dan uji:

   (+/@:*(3 5,.1 3&)&1 0) 5
1968 880

   (+/@:*(3 5,.1 3&)&1 0) every i.6
   1   0
   3   1
  14   6
  72  32
 376 168
1968 880

randomra
sumber

Anda bisa berjalan turun ke 20 dengan memanfaatkan diam-diam adverbia parsing: +/ .*(3 5,:1 3&)&1 0.

algorithmshark

@algorithmshark Terima kasih, meskipun mengapa (+/@:*&(3 5,.1 3)&1 0)bekerja dan (+/@:*&1 0&(3 5,.1 3))tidak? Bukankah seharusnya ikatan kedua benar dan yang pertama bertukar?

randomra

Mengerti, mereka terikat seperti yang saya harapkan tetapi bagian luar &membuat powering / looping sehingga Anda memodifikasi input sisi kiri selama powering (berlawanan dengan modifikasi sisi kanan normal).

randomra

7

Pyth, 20 byte

u,+*3sGyeG+sGyeGQ,1Z

uyang mengurangi secara umum, digunakan di sini sebagai loop berulang-ulang berlaku. Fungsi memperbarui adalah G-> ,+*3sGyeG+sGyeG, di mana G2 tuple. Fungsi itu diterjemahkan menjadi 3*sum(G) + 2*G[1], sum(G) + 2*G[1]. sadalah sum, yadalah *2.

isaacg
sumber

Saya memilih jawaban @ randomra daripada jawaban Anda karena emailnya diposting 16 menit sebelumnya, maaf.

orlp

5

APL (22)

{⍵+.×⍨2 2⍴3 5 1}⍣⎕⍨2↑1

Penjelasan:

{... }⍣⎕⍨2↑1: baca angka, dan jalankan fungsi berikut berkali-kali, gunakan [1,0]sebagai input awal.
- 2 2⍴3 5 1: matriks [[3,5],[1,3]]
- ⍵+.×⍨: kalikan angka pertama dalam ⍵ dengan 3, yang kedua dengan 5, dan jumlah mereka, ini adalah angka pertama yang baru; kemudian gandakan angka pertama menjadi ⍵ dengan 1, yang kedua dengan 3, dan jumlahkan, itu adalah angka kedua yang baru.

marinus
sumber

1

Awww ya, APL.

Nit

5

Jelly , 13 byte

5W×U++Ḥ
2BÇ³¡

Cobalah online!

Bagaimana itu bekerja

5W×U++Ḥ    Helper link. Argument: [a, b]

5W         Yield [5].
  ×U       Multiply it by the reverse of [a, b]. This yields [5b, a].
    +      Hook; add the argument to the result. This yields [a + 5b, a + b].
     +Ḥ    Fork; add the doubled argument ([2a, 2b]) to the result.
           This yields [3a + 5b, a + 3b].

2BÇ³¡      Main link. Argument: n

2B         Convert 2 to binary, yielding [1, 0].
    ¡      Repeat:
  Ç            Apply the helper link...
   ³           n times.

Dennis
sumber

Tidak, saya cukup yakin Jelly ada sejak lama sebelum penciptaan internet: P

Conor O'Brien

1

@ Doᴡɴɢᴏᴀᴛ Untuk jawaban yang tidak bersaing, saya lebih suka menjaga jumlah byte pada baris kedua. Ini menjaga jawaban agar tidak naik ke atas dalam papan peringkat dan skrip pengguna, yang tampaknya tidak adil.

Dennis

3

Mathematica, 31

Nest[{{3,5},{1,3}}.#&,{1,0},#]&

alephalpha
sumber

3

CJam, 21 byte

0X{_2$3*+@5*@3*+}li*p

Cobalah online.

Bagaimana itu bekerja

0X       " Stack: [ 0 1 ]                                ";
li{      " Do int(input()) times:                        ";
  _2$    " Stack: [ a b ] -> [ a b b a ]                 ";
  3*+    " Stack: [ a b b a ] -> [ a b (b+3a) ]          ";
  @5*@3* " Stack: [ a b (b+3a) ] -> [ (b+3a) 5a 3b ]     ";
  +      " Stack: [ (b+3a) 5a 3b ] -> [ (b+3a) (5a+3b) ] ";
}*       "                                               ";
p        " Print topmost stack item plus linefeed.       ";
         " Print remaining stack item (implicit).        ";

Dennis
sumber

3

Javascript, 63 61 byte

Saya menggunakan evaluasi rekursif binomial: (x + y) ^ n = (x + y) (x + y) ^ {n-1}

Baru (terima kasih kepada @ edc65)

F=n=>{for(i=y=0,x=1;i++<n;)[x,y]=[3*x+5*y,x+3*y];return[x,y]}

Tua

F=n=>{for(i=y=0,x=1;i<n;i++)[x,y]=[3*x+5*y,x+3*y];return [x,y]}

cacat
sumber

1

Mungkin ingin mempertimbangkan untuk mengedit formula Anda. Kami tidak memiliki MathJax lagi.

Alex A.

Saya pikir itu baru saja diperkenalkan beberapa hari yang lalu?

flawr

Ya, tapi itu mengacaukan tumpukan tumpukan, jadi itu harus dinonaktifkan.

Alex A.

Saya menghitung 63 apa adanya, dan dapat disingkat menjadi 61F=n=>{for(i=y=0,x=1;i++<n;)[x,y]=[3*x+5*y,x+3*y];return[x,y]}

edc65

n=>[...Array(n)].map(_=>[x,y]=[3*x+5*y,x+3*y],y=0,x=1)[n-1]panjang yang sama

l4m2

2

C, 114 byte

g(n){int i,a[2]={1,0},b[2];for(i=0;i<n;i++)*b=*a*3+5*a[1],b[1]=*a+3*b[1],*a=*b,a[1]=b[1];printf("%d,%d",*a,a[1]);}

Ini mengimplementasikan perkalian matriks dengan cara yang membosankan. Untuk solusi 238 byte yang lebih menyenangkan (kutipan: "awesomely horrific"), tidak perlu mencari lagi!

f(n){int p[2][n+3],i,j,k=0,a[2]={0};for(j=0;j<n+3;j++)p[0][j]=0;*p[1]=0;(*p)[1]=1;for(j=0;j<n;j++,k=!k)for(i=1;i<n+3;i++)p[!k][i]=p[k][i-1]+p[k][i];for(i=1;i<n+2;i++)a[!(i%2)]+=p[k][i]*pow(3,n+1-i)*pow(5,(i-1)/2);printf("%d,%d",*a,a[1]);}

Terurai:

g(n){
    int i,a[2]={1,0},b[2];
    for(i=0;i<n;i++)
        *b=3**a+5*a[1],b[1]=*a+3*b[1],*a=*b,a[1]=b[1];
    printf("%d,%d",*a,a[1]);
}

Ini mungkin bisa dipersingkat sedikit. Coba program pengujian online !

BrainSteel
sumber

1

Ini menggunakan algoritma yang agak rumit: P

orlp

@ orl Saya tidak bisa memikirkan algoritma yang lebih pendek untuk bahasa ini. Saya pikir yang ini akan berhasil, tapi agak tidak terkendali, haha. Menerapkan perkalian matriks dengan tangan bisa sangat pendek.

BrainSteel

1

Terpilih karena ini sangat mengerikan.

kirbyfan64sos

2

k2 - 22 char

Berfungsi mengambil satu argumen.

_mul[(3 5;1 3)]/[;1 0]

_muladalah penggandaan matriks jadi kami menjilatnya dengan matriks (3 5;1 3)dan kemudian memukulnya dengan keterangan daya fungsional: f/[n;x]berlaku funtuk x, nkali. Sekali lagi kita menjilatnya, kali ini dengan vektor awal 1 0.

  _mul[2 2#3 5 1]/[;1 0] 5
1968 880
  f:_mul[2 2#3 5 1]/[;1 0]
  f'!8  /each result from 0 to 7 inclusive
(1 0
 3 1
 14 6
 72 32
 376 168
 1968 880
 10304 4608
 53952 24128)

Ini tidak akan berfungsi di Kona, karena beberapa alasan f/[n;x]tidak diterapkan dengan benar. Hanya n f/xsintaks yang berfungsi, jadi perbaikan terpendek adalah {x _mul[(3 5;1 3)]/1 0}23 karakter.

algoritme hiu
sumber

Wow. Penggunaan currying ini sangat cerdas sehingga saya merasa jawaban K saya bodoh. Lagi pula, saya mengangkat masalah yang Anda temukan di Kona pada pelacak bug mereka .

kirbyfan64sos

FYI, ini baru saja diperbaiki di Kona .

kirbyfan64sos

2

ised, 25 byte (20 karakter)

({:{2,4}·x±Σx:}$1)∘1

Saya berharap menjadi lebih baik, tetapi ada terlalu banyak kawat gigi yang dibutuhkan untuk membuatnya kompeten, prioritas operator tidak optimal untuk bermain golf.

Ia mengharapkan input berada dalam slot memori $ 1, jadi ini berfungsi:

ised '@1{9};' '({:{2,4}·x±Σx:}$1)∘1'

Untuk n = 0, nol dilewati (output 1, bukan 1 0). Jika itu masalah, ganti final 1dengan ~[2].

orion
sumber

2

Serius, 32 byte, tidak bersaing

,╗43/12`╜";)@4*≈(6*-"£n.X4ì±0`n

Hex Dump:

2cbb34332f313260bd223b2940342af728362a2d229c6e2e58348df130606e7f

Cobalah Onlline

Jelas bukan penantang untuk terpendek, tetapi setidaknya metode ini asli. (Memperhatikan bahwa masalah seperti itu mengindikasikan urutan Lucas, seperti yang disebutkan dalam deskripsi, program ini menghasilkan istilah urutan dari urutan menggunakan relasi perulangan

a_n = 6 * a_ {n-1} - 4 * a_ {n-2}.)

kuintopia
sumber

1

Haskell, 41 byte

(iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!)

Contoh penggunaan: (iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!) 8-> (282496,126336).

nimi
sumber

1

C / C ++ 89 byte

void g(int n,long&a,long&b){if(n){long j,k;g(n-1,j,k);a=3*j+5*k;b=j+3*k;}else{a=1;b=0;}}

Diformat:

    void g(int n, long&a, long&b) {
if (n) {
    long j, k;
    g(n - 1, j, k);
    a = 3 * j + 5 * k;
    b = j + 3 * k;
} else {
    a = 1;
    b = 0;
}}

Konsep yang sama:

void get(int n, long &a, long& b) {
    if (n == 0) {
        a = 1;
        b = 0;
        return;
    }
    long j, k;
    get(n - 1, j, k);
    a = 3 * j + 5 * k;
    b = j + 3 * k;
}

Bangku tes:

#include <iostream>
using namespace std;    
int main() {
    long a, b;
    for (int i = 0; i < 55; i++) {
        g(i, a, b);
        cout << i << "-> " << a << ' ' << b << endl;
    }
    return 0;
}

Hasil:

0-> 1 0
1-> 3 1
2-> 14 6
3-> 72 32
4-> 376 168
5-> 1968 880
6-> 10304 4608
7-> 53952 24128
8-> 282496 126336
9-> 1479168 661504
10-> 7745024 3463680
11-> 40553472 18136064
12-> 212340736 94961664
13-> 1111830528 497225728
14-> 5821620224 2603507712
15-> 30482399232 13632143360
16-> 159607914496 71378829312
17-> 835717890048 373744402432
18-> 4375875682304 1956951097344
19-> 22912382533632 10246728974336
20-> 119970792472576 53652569456640
21-> 628175224700928 280928500842496
22-> 3289168178315264 1470960727228416
23-> 17222308171087872 7702050360000512
24-> 90177176313266176 40328459251089408
25-> 472173825195245568 211162554066534400
26-> 2472334245918408704 1105661487394848768

philn
sumber

Selamat datang di situs ini, dan jawaban pertama yang bagus!

DJMcMayhem

0

K, 37 byte

f:{:[x;*(1;0)*_mul/x#,2 2#3 1 5;1 0]}

atau

f:{:[x;*(1;0)*_mul/x#,(3 1;5 3);1 0]}

Keduanya sama.

kirbyfan64sos
sumber

0

Python 3, 49 byte

w=5**0.5;a=(3+w)**int(input())//2+1;print(a,a//w)

meskipun pada mesin saya, ini hanya memberikan jawaban yang benar untuk input dalam jangkauan 0 <= n <= 18.

Ini mengimplementasikan rumus formulir tertutup

w = 5 ** 0.5
u = 3 + w
v = 3 - w
a = (u ** n + v ** n) / 2
b = (u ** n - v ** n) / (2 * w)

dan mengambil keuntungan dari kenyataan bahwa v ** nbagian itu kecil, dan dapat dihitung dengan pembulatan daripada perhitungan langsung.

sumber

1

Ini bukan solusi yang valid (Anda harus mendukung n ), tetapi karena Anda tidak dekat dengan yang terpendek, saya tidak melihat alasan untuk melakukan downvote. Ini solusi keren.

orlp

0

Skema, 97 byte

(define(r n)(let s([n n][a 1][b 0])(if(= 0 n)(cons a b)(s(- n 1)(+(* a 3)(* b 5))(+ a(* b 3))))))

Penguino
sumber

0

C 71 byte (60 dengan variabel yang diinisialisasi)

Lingkup untuk bermain golf tetapi hanya untuk membuktikan bahwa C tidak harus "sangat mengerikan".

f(int n,int*a){for(*a=1,a[1]=0;n--;a[1]=*a+3*a[1],*a=(5*a[1]+4**a)/3);}

Jika nilai dalam a diinisialisasi ke {1,0}, kami melakukan lebih baik.

f(int n,int*a){for(;n--;a[1]=*a+3*a[1],*a=(5*a[1]+4**a)/3);}

Ini secara iteratif menggunakan pemetaan a-> 3a + 5b, b-> a + 3b tetapi menghindari variabel sementara dengan menghitung a dari nilai baru b sebagai gantinya.

Ahli alkimia
sumber

Solusi Anda

melebihi

@ orlp - Itu C untuk Anda. Memang solusi ini gagal lebih awal daripada yang lain karena perhitungan sementara dalam tanda kurung tetapi hanya akan mengelola beberapa langkah tambahan saja kecuali saya mengubah datatype. Apakah layak secara eksplisit mengubah pertanyaan untuk memberikan rentang yang Anda harapkan untuk didukung? Mungkin sudah terlambat sekarang.

Alchymist

Tidak ada rentang untuk didukung, solusi yang tepat harus bekerja untuk input apa pun. Dalam C itu berarti Anda harus menerapkan bilangan bulat lebar sewenang-wenang, sorry = /

orlp

Sarankan a[*a=1]=0alih-alih*a=1,a[1]=0

ceilingcat

0

(non-bersaing) Jelly, 10 byte

31,53Dæ*³Ḣ

Cobalah online!

Menggunakan matriks. Menghitung ([[3,1], [5,3]] ** input ()) [0].

Biarawati Bocor
sumber

Menghitung (3 + sqrt (5)) ^ n persis

Jawaban:

Dyalog APL, 18 byte

Oktaf, 26 byte

Python 2, 50

Julia, 22 20 byte

J, 20 byte

Pyth, 20 byte

APL (22)

Jelly , 13 byte

Bagaimana itu bekerja

Mathematica, 31

CJam, 21 byte

Bagaimana itu bekerja

Javascript, 63 61 byte

C, 114 byte

k2 - 22 char

ised, 25 byte (20 karakter)

Serius, 32 byte, tidak bersaing

Haskell, 41 byte

K, 37 byte

Python 3, 49 byte

Skema, 97 byte

(non-bersaing) Jelly, 10 byte