Monday Mini-Golf: Seria krótkich golfowych wyzwań, opublikowanych (miejmy nadzieję!) W każdy poniedziałek.

Fibonacciego jak sekwencji otrzymano z użyciem takiego samego sposobu jak znanego ciągu Fibonacciego ; to znaczy, każdą liczbę F (n) można znaleźć, dodając dwie poprzednie liczby w sekwencji ( F (n) = F (n-1) + F (n-2) ) lub odejmując kolejne dwie liczby ( F (n) = F (n + 2) - F (n + 1) ). Główną różnicą jest to, że sekwencje te mogą zaczynać się dowolnymi dwiema liczbami. Zerowe indeksowanie tych sekwencji jest dyskusyjne, ale na razie użyjemy tej reguły:

• Liczba 0 w sekwencji podobnej do Fibonacciego jest ostatnią liczbą, która jest mniejsza niż liczba poprzednia.

Jako przykład, sekwencję Fibonacciego można zapisać jako 1, 0, 1, 1, 2, 3, 5..., więc 0-ta liczba w sekwencji jest samotna 0.

Wyzwanie

Celem wyzwania jest napisanie programu lub funkcji, która przyjmuje trzy liczby całkowite, w dowolnym formacie:

• A i B , dwie liczby, z którymi rozpoczyna się generowanie sekwencji.
• N , długość wynikowej sekwencji do wyjścia.

I wyprowadza pierwsze N liczb sekwencji, zaczynając od 0.

Detale

• A , B i N można przyjmować w dowolnej kolejności i formacie, o ile są one wyraźnie rozdzielone. Jeśli używasz innego zamówienia / formatu, określ, co to jest.
• Możesz założyć, że A , B i N są zawsze dodatnimi liczbami całkowitymi.
• Możesz założyć, że N wynosi nie więcej niż 100, a wynikowa sekwencja nie będzie zawierać x >= 2^31.
• Jeśli A jest większy niż B , to B jest numerem 0 w sekwencji.
• Dane wyjściowe muszą być oddzielone spacjami, przecinkami i / lub znakami nowej linii.
• Końcowe spacje lub znaki nowej linii są dozwolone, ale nie przecinki końcowe.

Przypadki testowe

Przykład 1:

8 13 10

Pracujemy wstecz, 8 13dopóki nie znajdziemy liczby większej niż poprzednia, otrzymujemy 13 8 5 3 2 1 1 0 1. Zatem 0jest numerem 0 w tej sekwencji. Pracując dalej, drukujemy 0i kolejnych 9 członków:

0 1 1 2 3 5 8 13 21 34

Przykład 2:

23 37 5

Znów pracujemy wstecz, aby znaleźć cyfrę 0 37 23 14 9 5 4 1 3. Tym razem jest to numer 0 1, więc drukujemy go wraz z następnymi 4 członkami:

1 4 5 9 14

Przykład 3:

4 3 8

Dzięki temu nie musimy pracować wstecz, aby znaleźć cyfrę 0, ponieważ 3jest mniejsza niż 4:

3 7 10 17 27 44 71 115

Przykład 4:

29 47 11

Wynik:

1 3 4 7 11 18 29 47 76 123 199

Punktacja

To jest golf golfowy , więc wygrywa najkrótszy prawidłowy kod w bajtach. Tiebreaker przechodzi do wcześniej opublikowanego zgłoszenia. Zwycięzca zostanie wybrany w następny poniedziałek, 28 września. Powodzenia!

Edycja: Gratulacje dla twojego zwycięzcy, @Jakube, używając Pytha dla niesamowitych 23 bajtów!

Pyth, 23 bajty

AQWgHGA,-HGG)VvwHA,H+GH

Wypróbuj online: pakiet demonstracyjny lub testowy

Całkiem nietypowy styl programowania w języku Pyth. Czasami programowanie funkcjonalne ma swoje wady.

Wyjaśnienie:

AQWgHGA,-HGG)VvwHA,H+GH  Q = input list of the two starting numbers
AQ                       G, H = Q (unpacking Q)
  WgHG                   while H >= G:
      A,-HGG                G, H = [H - G, G]
            )            end while
              vw         read a number from input
             V           for N in range(^):
                H           print H
                 A,H+GH     G, H = [H, G + H]

Siatkówka , 65 54 bajtów

+`(1*),\1(1*)
$2,$1
+`(1*)(,1*);1\B
$1$2$2$1;
^1*,|;1
<empty>

Tutaj <empty>reprezentuje pustą linię końcową. Uruchom kod jako pojedynczy plik z -sflagą.

Format wejściowy to

A,B;N

gdzie liczby są reprezentowane w jedności . Dane wyjściowe to lista oddzielona przecinkami, również w postaci pojedynczej. Na przykład:

8 13 10

byłoby

11111111,1111111111111;1111111111

i wydajność

,1,1,11,111,11111,11111111,1111111111111,111111111111111111111,1111111111111111111111111111111111

Wyjaśnienie

+`(1*),\1(1*)
$2,$1

Najpierw redukujemy Ai Bdo 0 i 1-szego elementu. +Mówi siatkówki do powtarzać tego podstawienia regex dopóki nie przestanie regex dopasowanie lub substytucja nie zmienia się łańcuch. Wyrażenie regularne przechwytuje Ado grupy 1 za pomocą (1*), a następnie upewnia się, że Bjest co najmniej tak duże, jak Apodczas przechwytywania za B-Apomocą \1(1*)do grupy 2. Zapewnia to, że ta pętla zakończy się raz A>B.

Podstawienie po prostu odwraca A,Bsię B-A,Apoprzez ustawienie zbliżone do $2,$1.

+`(1*)(,1*);1\B
$1$2$2$1;

Teraz mamy już pierwszą liczbę wymaganego wyjścia w ciągu (jak również poprzednią, którą będziemy musieli pozbyć się później). Ta zamiana dodaje teraz inną liczbę jako sumę dwóch ostatnich liczb podczas pobierania 1z N. Ponieważ mamy już jeden numer, chcemy, aby tak się stało N-1. Robimy to, upewniając się \B, że nadal jest co najmniej ;11na końcu łańcucha. Jeśli nazywamy dwie ostatnie wartości sekwencji Ci D, a następnie przechwytuje regex Cw grupie 1 oraz ,Dw grupie drugiej. Odpisujemy je za pomocą $1$2. Następnie piszemy, $2$1co tłumaczy ,D+C. Pamiętaj, że nie odpisujemy singla, do 1którego pasowaliśmyN, zmniejszając go.

^1*,|;1
<empty>

Na koniec musimy pozbyć się -1-szego elementu sekwencji, a także resztek ;1z N, co robimy po prostu dopasowując jeden z nich i zastępując go pustym ciągiem.

Python 2, 93 87 67 61 60 bajtów

i,j,l=input()
while j/i:i,j=j-i,i
exec"i,j=j,i+j;print i;"*l

Pobiera dane wejściowe (jako dosłowną listę python [8,10,13])

Wypracowuje 0 kadencję

Następnie drukuje sekwencję dodawania, aż do osiągnięcia długości

CJam, 26 23 bajtów

Dzięki Dennis za oszczędność 3 bajtów.

q~{_@\-_g)}g\@{_@+_p}*t

Pobiera dane wejściowe w kolejności N B A(oddzielone dowolną białą spacją). Wyświetla wynik jako listę oddzieloną znakiem nowej linii i kończy się z błędem .

Sprawdź to tutaj.

Wyjaśnienie

To idzie o krok dalej, gdy znajduje się 0 element. Oznacza to, że kończy się, gdy jedna z wartości jest ujemna.

q~      e# Read and evaluate input, pushing N, B and A on the stack.
{       e# do while...
  _@\-  e#   B, A = A, B-A
  _W>   e#   Check if A is still non-negative.
}g
\@      e# Reorder N B A into A B N.
{       e# Run the following N times...
  _@+   e#   A, B = B, A+B
  _p    e#   Print B.
}*
t       e# The last A, B are still on the stack. We remove them by trying to
        e# execute a ternary operator: it pops the first two values but then
        e# terminates the program with an error, because there is no third value.

Labirynt , 58 54 49 46 44 bajtów

Podziękowania dla Sp3000 za sugerowanie zastosowania bitowej negacji, co pozwoliło zaoszczędzić dwa bajty.

??#"{=
  ;  -
@"~~:}
~""
?
"}}:=
(   +
{{\!:

Format wejściowy to B A N. Dane wyjściowe to lista rozdzielona znakiem nowej linii.

Wyjaśnienie

(Nieco przestarzałe. Podstawowa idea jest nadal taka sama, ale układ kodu jest teraz inny).

Wykorzystuje to ten sam pomysł, co moja odpowiedź na CJam (więc kredyty wciąż trafiają do Dennisa): podczas cofania sekwencji nie zatrzymujemy się, dopóki nie otrzymamy wartości ujemnej (która pozostawia nam -1-ty i -2-ty element sekwencji). Następnie zaczynamy je dodawać przed wydrukowaniem pierwszej wartości.

Wykorzystuje kilka fajnych sztuczek golfowych z Labiryntu. Przejrzyjmy kod w sekcjach:

?"
}

Adres IP zaczyna się od ?prawej strony (która czyta A). Na "(no-op) trafia w ślepy zaułek, więc odwraca się, wykonując ?ponownie (czytanie B). Na koniec }przechodzi Bdo stosu pomocniczego. Ślepy zaułek oszczędza bajt naiwnemu

?
?
}

Teraz pętla, która znajduje początek sekwencji:

)(:{
"  -
" "`?...
=}""

Opcja )((inkrement-dekrementacja) nie działa, ale należy upewnić się, że górna część stosu jest dodatnia na skrzyżowaniu (tak, że IP skręca na wschód). :duplikaty A, {przemieszcza się Bz powrotem do głównego stosu, -oblicza A-B. To, czego naprawdę chcemy B-A, to `neguje wartość.

Jest to teraz skrzyżowanie czterokierunkowe. Aby uzyskać negatywne wyniki, adres IP skręca w lewo w kierunku ?, czytając Ni przechodząc do następnej części programu. Jeśli wynik wynosi zero, IP przesuwa się na południe, skręca w rogu i pozostaje w pętli. Jeśli wynik jest pozytywny, IP skręca w prawo (na zachód), skręca w rogu i wykonuje kolejny skręt w prawo (ponownie na zachód), więc również pozostaje w pętli. Myślę, że może to stać się powszechnym wzorcem w celu odróżnienia wartości ujemnych od nieujemnych (lub dodatnich od nie dodatnich):

                v
                "
               """>negative
non-negative <"""

Przynajmniej nie udało mi się znaleźć bardziej kompaktowego / przydatnego układu dla tej skrzynki.

W każdym razie, choć Anie jest ujemna, pętla trwa, }przechodzi Ado stosu pomocniczego i =zamienia Ai B.

Raz Ajest ujemny, ?czyta Ni przechodzimy do drugiej pętli:

 }:=+:
 }   !
?"({{\

Wiemy, że Njest to pozytywne, więc możemy polegać na IP skręcającym w lewo (na północ). Korpus pętli jest teraz po prostu:

}}:=+:!\{{(

Słownie: porusza się zarówno Ni Ana stos pomocniczy. Duplikuj B, zamień kopię za pomocą Ai dodaj Ado drugiej kopii B. Powtórz go ponownie, aby wydrukować bieżącą wartość B. Wydrukuj nowy wiersz. Przesuń Bi Npowrót do głównego stosu i ubytku N.

Chociaż Njest dodatni, adres IP skręca w prawo (na północ), kontynuując pętlę. Gdy Nosiągnie zero, kod kończy się w dość fantazyjny sposób:

IP porusza się prosto (na zachód). W ?próbuje odczytać inną liczbę całkowitą, ale już osiągnął EOF, więc faktycznie popycha 0zamiast. `próbuje to zanegować, ale to wciąż zero. Tak więc adres IP nadal przesuwa się na zachód, skręca w rogu, a następnie przesuwa się w dół w kierunku tego, @który kończy program.

Zastanawiam się, czy mogę umieść @w jeszcze niższej pozycji (obecnie kosztuje 3 białe znaki) obracając trzy "wokół osób `w związku no-ops (jak )(), ale nie byłem w stanie zrobić jeszcze tej pracy.

C, 105 102 100 bajtów

main(a,b,n,t){for(scanf("%d%d%d",&a,&b,&n);t=b-a,t>=0;a=t)b=a;for(;n--;b=t)t=a+b,printf("%d ",a=b);}

Dzięki @ C0deH4cker za grę w golfa przy 2 bajtach!

Wypróbuj online na Ideone .

Matlab / Octave, 115 125 bajtów

function x=f(x,n)
while x(2)>=x(1)
x=[abs(x(1)-x(2)) x];end
x=x([2 1]);for k=1:n-1
x=[x(1)+x(2) x];end
x=x(n:-1:1);

Funkcja powinna zostać wywołana jako f([8 13],10).

Przykład (Matlab):

>> f([8 13],10)
ans =
     0     1     1     2     3     5     8    13    21    34

Lub wypróbuj online (Octave) .

Haskell, 67 65 56 bajtów

a#b|a>b=b:scanl(+)(a+b)(a#b)|1>0=(b-a)#a
n%a=take n.(a#)

Dzięki @nimi za sugestie

Definiuje to potrójną funkcję infix %, która jest wywoływana w formacie (n%a)b, na przykład:

> (10%8)13
[0,1,1,2,3,5,8,13,21,34]

Wyjaśnienie

Binarna funkcja infiks #zdefiniowanym w pierwszym wierszu, odbywa się w dwóch liczb ai bi zwraca nieskończonej Fibonacciego jak sekwencja gdzie ai bwystępuje w kolejnych elementów.

a#b                                       -- Define a#b:
   |a>b=                                  -- if a>b, then a#b is
        b:                                -- the sequence that starts with b and
          scanl(+)     (a#b)              -- continues with the sums of prefixes of a#b
                  (a+b)                   -- plus the additional term a+b;
                            |1>0=(b-a)#a  -- otherwise, it's (b-a)#a.

Funkcja %po prostu bierze pierwsze nelementy a#b.

> <>, 33 31 + 1 dla -v = 32 bajtów

&:{:@(?v:}-$&
-1;!?:&<$+{oan::$&

Dane wejściowe muszą być wypychane na stos za pomocą -v, ponieważ parsowanie liczb dziesiętnych nie jest trywialne w> <>.

Objaśnienie:

Przedstawię stos po każdej (grupie) operacji. Zaczyna się od [F (n), F (n + 1), N]

Pierwsze wiersze przechodzą w dół serii do 0 kadencji:

& removes N from the stack to put it into a register. [F(n), F(n+1)]
:{:@ move the stack and duplicate items to get [F(n+1), F(n), F(n+1), F(n)]
(?v compares the two top items of the stack and branch to the second line if F(n+1) < F(n) [F(n+1), F(n)]
:} move the stack and duplicate its top to get [F(n), F(n+1), F(n)]
- substracts the two top items and put the result on top of the stack [F(n), F(n+1) - F(n)]
$ switchs the top two values of the stack. [F(n+1) - F(n), F(n)]
& retrieve the value from the register. iteration complete, since [F(n+1) - F(n), F(n), N] can also be read as [F(n-1), F(n), N]

Druga linia przechodzi w górę serii, dopóki nie wydrukuje N terminów:

< changes the code pointer direction to the left [F(0), F(-1)]
& retrieves the stored value back from the stack [F(0), F(-1), N]
:?!; copies N to compare it to 0, stops if it is [F(0), F(-1), N]
1- decreases it [F(0), F(-1), N-1]
& stores it back [F(0), F(-1)]
$:: makes the stack [F(-1), F(0), F(0), F(0)]
n{ prints the top of the stack then left shifts it [F(0), F(0), F(-1)]
ao displays a line feed (ascii character 0x0a) [F(0), F(0), F(-1)]
+ adds the two top values [F(0), F(-1) + F(0)]
$ switch the two top values. iteration complete since [F(-1) + F(0), F(0)] which can be read as [F(1), F(0)]

Java, 113 78 76 bajtów

Podziękowania dla ETHproduction za dostarczenie algorytmu, którego używam w tej odpowiedzi.

(a,b,n)->{for(;a<=b;b-=a)a=b-a;for(;n-->0;b+=a,a=b-a)System.out.println(b);}

Spróbuj tutaj .

Wyjaśnienie:

(a,b,n)->{
    for (;a<=b;b=b-a)a=b-a;  //Compute previous terms while a <= b
    for (;n-->0;b=a+b,a=b-a) //Compute and print next terms while n > 0
    System.out.println(b);   //Print term
}

Oryginalne podejście, 113 93 bajty

Wygląda bardziej golfowo;)

String a(int a,int b,int n){return n<0?a+" "+a(b,a+b,n+1):n>0?a>b?a(b,a+b,-n):a(b-a,a,n):"";}

Wypróbuj tutaj .

Wyjaśnienie:

String a(int a, int b, int n){
    return 
    n < 0 ?                           //If n < 0
        a + " " + a(b, a + b, n + 1)  //Return a + next terms and increment n.
    :                                 //Else
        n > 0 ?                       //If n > 0
            a > b ?                   //If a > b
                a(b, a + b, -n)       //Negate n and return terms.
            :                         //If a <= b
                a(b - a, a, n)        //Generate previous term.
        :                             //If n == 0
            ""                        //Return nothing.
    ;
}

JavaScript (ES6), 83 73 63 bajty

To mogło być gra w golfa na maksa. Zobaczymy.

(a,b,n)=>{while(a<=b)b-=a=b-a;for(;n--;console.log(a=b-a))b+=a}

Nie golfowany:

function f(a,b,n) {
  // repeat until we find the 0th item...
  while (a <= b) {  // if a = 5, b = 8:
    a = b - a;      // a = (8 - 5) = 3
    b = b - a;      // b = (8 - 3) = 5
  }
  // repeat n times...
  while (n-- > 0) { // if a = 5, b = 8:
    b += a;         // b = (8 + 5) = 13
    a = b - a;      // a = (13 - 5) = 8
    console.log(a); // print out each item
  }
}

Mathematica 112

W końcu to golf

z[a_, b_, n_] := (
  f[0] := Min[a, b];
  f[1] := Max[a, b];
  f[x_] := f[x - 1] + f[x - 2];
  f /@ Range[n]
  )

CJam, 40 bajtów

l~:A;{_@_@)<}{_@\-\}w\{A(:A0>}{_p_@+}w\;

Dziecięce kroki. To mój pierwszy program CJam, więc jestem dumny, że w ogóle działa.

Pobiera dane wejściowe w takiej samej formie jak w przykładach.

Widziałem teraz, że mogę zredukować go do 33 bajtów za pomocą { ... }*konstruktu.

l~:A;{_@_@)<}{_@-z\}w\A{_p_@+}*;;

Mógłbym nawet zmniejszyć go o jeszcze jeden, używając operatora potrójnego do czyszczenia stosu i generowania błędu.

Rubin, 141 bajtów

def u a,b,n,z=""
n<1 ? z.chop : u(b,a+b,n-1,z+"#{a} ")
end 
def d a,b,z=0
a.abs>b ? z : d(b-a,a,[a,b]) 
end 
def f a,b,n
x,y=d a,b 
u x,y,n
end 

Wykonanie

Funkcja f generuje pożądany wynik, nazwy argumentów pasują do nazw zmiennych z pytania

f(8,13,10) # returns => "0 1 1 2 3 5 8 13 21 34"

Nic sprytnego:

• Funkcja u (w górę ) oblicza n elementów w sekwencji Fibonacciego zaczynając od a, b przy użyciu rekurencji
• Funkcja d (w dół ) wyszukuje 0-ty i 1-ty element przy dwóch elementach końcowych za pomocą rekurencji
• Funkcja f ( Fibonacciego ) łączy je razem

Mathematica, 59 bajtów

If[#>#2,LinearRecurrence[{1,1},#2+{0,#},#3],#0[#2-#,#,#3]]&

Ruby, 81 75 73

a,b,n=23,37,5;while(c=b-a)<a;b,a=a,c;end;p a;[*2..n].map{b=c+a;c,a=a,b;p b}

Skrócono o 6 bajtów przy zamianie pętli for na range.map

a,b,n=23,37,5;while(c=b-a)<a;b,a=a,c;end;p a;[*2..n].map{p b=c+a;c,a=a,b}

Zaoszczędzono kolejne 2 bajty, przenosząc instrukcję print

Pyke, 24 bajty (niekonkurujące)

DA/IDA-],X_r)QVDsRe
R]);

Wypróbuj tutaj!

Galaretka , 14 bajtów

Ḋ;_/Ɗ>/¿+⁹С/Ṗ

Wypróbuj online!

Common Lisp, 91 bajtów

(lambda(a b n)(do((x a(- y x))(y b x))((> x y)(dotimes(k n)(print y)(psetf y(+ y x)x y)))))

Wypróbuj online!