23

Dziś twoim celem jest znalezienie liczby całkowite a i b daną liczbę całkowitą nieujemną n takie, że:

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

Należy napisać program lub funkcję, która przyjmuje parametr n i wyjść i B w formacie do wyboru.

Obowiązują standardowe luki. Ponadto zamierzone jest samodzielne wdrożenie powyższego problemu za pomocą podstawowej arytmetyki. Dlatego nie możesz używać wbudowanej funkcji algebry dokładnej, wymiernych ani funkcji implementujących nietrywialne konstrukcje matematyczne (na przykład sekwencję Lucas ).

Najkrótszy kod w bajtach wygrywa.

Przykładowe wejście / wyjście:

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

code-golf arithmetic orlp
źródło

3

Dyalog APL, 18 bajtów

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

Jest to program, który pobiera dane wejściowe ⎕.

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

Zastosowane tutaj funkcje zostały wdrożone na długo przed kwietniem 2015 r., Dzięki czemu ta odpowiedź jest ważna.

Wypróbuj tutaj . Pamiętaj, że tryapl.org jest ograniczonym podzbiorem Dyalog i nie obsługuje ⎕.

lirtosiast
źródło

16

Oktawa, 26 bajtów

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

Ponieważ ( a + b * sqrt (5)) * (3 + sqrt (5)) = ( 3a + 5b ) + ( a + 3b ) * sqrt (5),

pomnożenie wektora wejściowego

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

co oznacza 1 = (3 + sqrt (5)) ^ 0 według macierzy

| 3 5 |
| 1 3 |

wydaje się naturalne. Zamiast nczasów zapętlania , raczej podnosimy macierz do potęgi, na następnie mnożymy ją przez wektor wejściowy.

pawel.boczarski
źródło

Sprzedajesz się krótko, [3 5;1 3]**input('')*[1;0]ma 26 bajtów, a nie 41.

lub

3

@(n)[3 5;1 3]^n*[1;0](uchwyt funkcji) pozwoliłby ci zaoszczędzić pięć znaków, mut fajny pomysł!

flawr

14

Python 2, 50

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

Mnoży się 3+sqrt(5)wielokrotnie przez działanie na (a,b)reprezentującą parę a+b*sqrt(5). Równoważne do rozpoczęcia od wektora kolumny [1,0]i nczasów pomnożenia w lewo przez macierz [[3,5],[1,3]].

xnor
źródło

12

Julia, 22 20 bajtów

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

Tworzy to funkcję lambda, która przyjmuje na wejściu pojedynczą liczbę całkowitą i zwraca 2-elementowy wektor liczb całkowitych odpowiadający rozwiązaniu [a, b]. Aby to nazwać, nadaj mu nazwę, np f=n->....

Zacznij od pomnożenia

Początkowe rozwinięcie

Następnie możemy przetłumaczyć prawą stronę tego równania na macierz 2-kolumnową, gdzie pierwsza odpowiada współczynnikowi a, a druga współczynnikowi b :

Matryca

Pomnóż tę macierz sama n razy, a następnie pomnóż w prawo przez wektor kolumny (1, 0) i POOF! Wyskakuje wektor rozwiązania.

Przykłady:

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

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

Alex A.
źródło

8

J, 20 bajtów

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

Pomnóż wektor [1 0]przez [[3 5] [1 3]] nczasy macierzy .

2 bajty zapisane dzięki @al algorytmshark.

Zastosowanie i test:

   (+/@:*(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
źródło

Można zejść do 20 wykorzystując milczącą przysłówek parsowania: +/ .*(3 5,:1 3&)&1 0.

algorytmshark

@al algorytmshark Dzięki, chociaż dlaczego (+/@:*&(3 5,.1 3)&1 0)działa, a (+/@:*&1 0&(3 5,.1 3))nie? Czy drugie nie powinno być prawidłowo połączone, a pierwsze zamienione?

randomra

Rozumiem, łączą się tak, jak się spodziewałem, ale zewnętrzne &powoduje zasilanie / zapętlenie, więc modyfikujesz wejście po lewej stronie podczas zasilania (przeciwnie do normalnej modyfikacji po prawej stronie).

randomra

7

Pyth, 20 bajtów

u,+*3sGyeG+sGyeGQ,1Z

uktóry jest ogólnie redukowany, jest tutaj stosowany jako pętla powtarzania zastosowania. Funkcja aktualizacji to G-> ,+*3sGyeG+sGyeG, gdzie Gjest 2 krotki. Ta funkcja przekłada się na 3*sum(G) + 2*G[1], sum(G) + 2*G[1]. sjest sum, yjest *2.

isaacg
źródło

Wybrałem odpowiedź @ randomra ponad twoją, ponieważ jego / jej została opublikowana 16 minut wcześniej, przepraszam.

orlp

5

APL (22)

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

Wyjaśnienie:

{... }⍣⎕⍨2↑1: przeczytaj liczbę i uruchom następującą funkcję wiele razy, używając [1,0]jako danych wejściowych.
- 2 2⍴3 5 1: macierz [[3,5],[1,3]]
- ⍵+.×⍨: pomnóż pierwszą liczbę w ⍵ przez 3, drugą przez 5, i zsumuj je, to jest nowa pierwsza liczba; następnie pomnóż pierwszą liczbę w ⍵ przez 1, drugą przez 3 i zsumuj te, czyli nową drugą liczbę.

marinus
źródło

1

Awww yiss, APL.

Nit

5

Galaretka , 13 bajtów

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

Wypróbuj online!

Jak to działa

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
źródło

Nie, jestem całkiem pewien, że Jelly była na długo przed stworzeniem Internetu: P

Conor O'Brien

1

@ Doᴡɴɢᴏᴀᴛ W przypadku niekonkurencyjnych odpowiedzi wolę utrzymywanie liczby bajtów w drugiej linii. To powstrzymuje odpowiedź od awansowania na szczyt w rankingach i skryptach użytkowników, co wydaje się niesprawiedliwe.

Dennis

3

Mathematica, 31

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

alephalpha
źródło

3

CJam, 21 bajtów

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

Wypróbuj online.

Jak to działa

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
źródło

3

JavaScript, 63 61 bajtów

Korzystam z rekurencyjnej oceny dwumianu: (x + y) ^ n = (x + y) (x + y) ^ {n-1}

Nowość (dzięki @ edc65)

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

Stary

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

wada
źródło

1

Może warto rozważyć edycję formuły. Nie mamy już MathJax.

Alex A.,

Myślałem, że to właśnie zostało wprowadzone kilka dni temu?

flawr

Tak, ale zawiodło fragmenty stosu, więc trzeba było je wyłączyć.

Alex A.,

Liczę 63 jak jest i można je skrócić do 61F=n=>{for(i=y=0,x=1;i++<n;)[x,y]=[3*x+5*y,x+3*y];return[x,y]}

edc65 13.04.15

n=>[...Array(n)].map(_=>[x,y]=[3*x+5*y,x+3*y],y=0,x=1)[n-1]ta sama długość

l4m2

2

C, 114 bajtów

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

To powoduje nudne mnożenie macierzy. Aby uzyskać więcej zabawy (cytat: „niesamowicie przerażający”) 238 bajtów, nie szukaj dalej!

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

Rozpruty:

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

Prawdopodobnie można to nieco skrócić. Wypróbuj program testowy online !

BrainSteel
źródło

1

Wykorzystuje się w tym dość skomplikowany algorytm: P

orlp

@orlp Nie mogłem wymyślić krótszego algorytmu dla tego języka. Myślałem, że to się uda, ale to wymknęło się spod kontroli, haha. Ręczne wdrożenie mnożenia macierzy może być krótsze.

BrainSteel

1

Głosuj, ponieważ jest to niesamowicie przerażające.

kirbyfan64sos

2

k2 - 22 znak

Funkcja przyjmująca jeden argument.

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

_muljest mnożenie macierzy więc curry go z matrycy (3 5;1 3), a następnie uderzył go z funkcjonalnej mocy przysłówek: f/[n;x]stosuje fsię x, nczasy. Ponownie curry, tym razem z wektorem początkowym 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)

To nie zadziała w Kona, ponieważ z jakiegoś powodu f/[n;x]nie jest poprawnie zaimplementowane. n f/xDziała tylko składnia, więc najkrótsza poprawka to {x _mul[(3 5;1 3)]/1 0}23 znaki.

algorytmshark
źródło

Łał. To curry jest tak inteligentne, że wydaje mi się, że moja odpowiedź na K jest głupia. W każdym razie podniosłem problem, który znalazłeś w Kona na ich narzędziu do śledzenia błędów .

kirbyfan64sos

Do Twojej wiadomości zostało to niedawno naprawione w Kona .

kirbyfan64sos

2

ised, 25 bajtów (20 znaków)

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

Miałem nadzieję, że będzie lepiej, ale jest po prostu zbyt wiele aparatów ortodontycznych potrzebnych, aby uczynić go kompetentnym, priorytet operatorów nie jest optymalny do gry w golfa.

Oczekuje, że wejście znajdzie się w gnieździe pamięci o wartości 1 USD, więc działa to:

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

Dla n = 0 zero jest pomijane (wyjścia 1, zamiast 1 0). Jeśli to problem, wymień ostateczna 1z ~[2].

orion
źródło

2

Poważnie, 32 bajty, niekonkurujące

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

Hex Dump:

2cbb34332f313260bd223b2940342af728362a2d229c6e2e58348df130606e7f

Wypróbuj Onlline

Oczywiście nie jest to zawodnik najkrócej, ale przynajmniej metoda jest oryginalna. (Zwracając uwagę, że taki problem niekoniecznie wskazuje sekwencję Lucas, jak wspomniano w opisie, ten program generuje kolejne terminy sekwencji przy użyciu relacji powtarzalności

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

kwintopia
źródło

1

Haskell, 41 bajtów

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

Przykład użycia: (iterate(\(a,b)->(3*a+5*b,a+3*b))(1,0)!!) 8-> (282496,126336).

nimi
źródło

1

C / C ++ 89 bajtów

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

Sformatowany:

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

Ta sama koncepcja:

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

Stanowisko testowe:

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

Wyjście:

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
źródło

Witamy na stronie i fajna pierwsza odpowiedź!

DJMcMayhem

0

K, 37 bajtów

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

lub

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

Oba są tym samym.

kirbyfan64sos
źródło

0

Python 3, 49 bajtów

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

chociaż na mojej maszynie daje to tylko prawidłową odpowiedź dla danych wejściowych w zakresie 0 <= n <= 18.

To implementuje formułę formularza zamkniętego

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

i wykorzystuje fakt, że v ** nczęść jest niewielka i można ją obliczyć raczej zaokrąglając niż bezpośrednio.

źródło

1

To nie jest poprawne rozwiązanie (musisz wesprzeć dowolne n ), ale ponieważ nie jesteś wcale najkrótszy, nie widzę powodu, aby głosować negatywnie. To fajne rozwiązanie.

orlp

0

Schemat, 97 bajtów

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

Pingwin
źródło

0

C 71 bajtów (60 ze wstępnie zainicjalizowanymi zmiennymi)

Możliwości gry w golfa, ale tylko po to, aby udowodnić, że C nie musi być „strasznie przerażający”.

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

Jeśli wartości w a są inicjalizowane na {1,0}, robimy to lepiej.

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

Jest to iteracyjnie użycie odwzorowań a-> 3a + 5b, b-> a + 3b, ale unikanie zmiennej tymczasowej poprzez obliczenie a na podstawie nowej wartości b.

Alchymist
źródło

Twoje rozwiązanie przepełnia liczby całkowite dla dużych danych wejściowych :)

lub

@orlp - To C dla ciebie. Przyznaję, że to rozwiązanie zawodzi wcześniej niż inne z powodu tymczasowego obliczenia w nawiasach, ale i tak wykonałby tylko kilka dodatkowych kroków, chyba że zmienię typ danych. Czy warto wyraźnie zmienić pytanie, aby podać zakres, który ma być obsługiwany? Prawdopodobnie za późno.

Alchymist

Nie ma zakresu obsługiwanego, właściwe rozwiązanie powinno działać dla każdego wejścia. W C oznacza to, że będziesz musiał zaimplementować liczby całkowite o dowolnej szerokości, przepraszam = /

orlp 14.04.15

Sugerować a[*a=1]=0 zamiast*a=1,a[1]=0

ceilingcat

0

(niekonkurujące) galaretka, 10 bajtów

31,53Dæ*³Ḣ

Wypróbuj online!

Wykorzystuje matrycę. Oblicza ([[3,1], [5,3]] ** input ()) [0].

Leaky Nun
źródło

Obliczanie (3 + sqrt (5)) ^ n dokładnie

Odpowiedzi:

Dyalog APL, 18 bajtów

Oktawa, 26 bajtów

Python 2, 50

Julia, 22 20 bajtów

J, 20 bajtów

Pyth, 20 bajtów

APL (22)

Galaretka , 13 bajtów

Jak to działa

Mathematica, 31

CJam, 21 bajtów

Jak to działa

JavaScript, 63 61 bajtów

C, 114 bajtów

k2 - 22 znak

ised, 25 bajtów (20 znaków)

Poważnie, 32 bajty, niekonkurujące

Haskell, 41 bajtów

K, 37 bajtów

Python 3, 49 bajtów

Schemat, 97 bajtów

(niekonkurujące) galaretka, 10 bajtów