Naprzemienne Fibonacciego

17

W naprzemiennej sekwencji Fibonacciego zaczynasz od 1i 1jak zwykle.

Jednak zamiast zawsze dodawać dwie ostatnie wartości w celu uzyskania następnej liczby, naprzemiennie zaczynasz od dodawania i za każdym razem odejmujesz.

Sekwencja zaczyna się w następujący sposób:

1
1
2    # 1 + 1
-1   # 1 - 2
1    # 2 + -1
-2   # -1 - 1
-1   # 1 + -2
-1   # -2 - -1
-2   # -1 + -1
1    # -1 - -2
-1   # -2 + 1
2    # 1 - -1
1    # -1 + 2
1    # 2 - 1

itp.

Zauważ, że po uruchomieniu na raz robi się 1i 1znowu.

Biorąc pod uwagę liczbę N , wydrukuj N- ty termin na przemian sekwencji fibonacciego.

Pamiętaj, że to jest , więc wygrywa kod z najmniejszą liczbą bajtów.

Oliver Ni
źródło
Czy sekwencja jest indeksowana 0, czy indeksowana 1 (albo jedną z nich)?
Klamka
@Doorknob Albo jeden. Podaj w swojej odpowiedzi.
Oliver Ni
Możemy wrócić truedo 1?
ETHprodukcje
Czy pierwsze dwie 1wartości liczą się jako wartości początkowe dla wyjścia? Czy możemy zacząć bezpośrednio od 2?
Luis Mendo,
@LuisMendo Pierwsze dwa się liczą.
Oliver Ni

Odpowiedzi:

17

JavaScript (ES6), 25 bajtów

n=>"334130110314"[n%12]-2

0-indeksowane. Możesz skrócić ciąg z nieco rekurencyjną wersją, chociaż dodaje 6 bajtów:

f=n=>"3341301"[n]-2||f(13-n%12)

Jest to wciąż krótsza niż ostateczna rekurencyjna formuła:

f=n=>n<2||f(n-2)+f(n-1)*(-n%2|1)
ETHprodukcje
źródło
8

Python, 31 bajtów

lambda n:2-33107256/5**(n%12)%5

Nie przeszkadza próba obliczenia wartości. Po prostu przegląda listę długości peroidycznej-12 [1, 1, 2, -1, 1, -2, -1, -1, -2, 1, -1, 2], która jest skompresowana w bazie 5.

Porównaj z rozwiązaniem rekurencyjnym (37 bajtów) z True's dla 1:

f=lambda n:n<2or(-1)**n*f(n-1)+f(n-2)

lub do przechowywania ciągów

lambda n:int('334130110314'[n%12])-2

lub próba wyrażenia arytmetycznego.

lambda n:4**n%7%3*(-1)**((n+n%2*4)/6)
xnor
źródło
7

Oaza , 10 bajtów

Przypomina mi o wdrożeniu kolejnych wbudowanych elementów: p. Dane wejściowe mają indeks 0 .

Kod:

n>2%x<*c+V

Wersja przetłumaczona:

a(n) = (2*((n+1)%2)-1) * a(n-1) + a(n-2)
a(1) = 1
a(0) = 1

I oblicza n- ty termin.

Wypróbuj online!

Adnan
źródło
5

05AB1E , 10 bajtów

•É&†º•sèÍ

Wykorzystuje kodowanie CP-1252 . Wypróbuj online!

Adnan
źródło
Myślę, że powinienem zacząć uczyć się 05AB1E zamiast Galaretki.
Erik the Outgolfer,
4

Galaretka, 12 bajtów

“½Ġ⁻S’b5_2⁸ị

TryItOnline!

Oparte na 1, biorąc pod uwagę pierwszą i drugą wartość 1.

Nie jestem pewien, czy jest to jeszcze krótsze, ale w tym celu zauważyłem, że seria ma okres 12:
[1, 1, 2, -1, 1, -2, -1, -1, -2, 1, -1, 2]

Więc wziąłem to i dodałem, 2aby dać,
[3, 3, 4, 1, 3, 0, 1, 1, 0, 3, 1, 4]
a następnie przekonwertowałem to jako 5liczbę podstawową na bazę 250, aby dać:
[11, 197, 140, 84]
(która jest 184222584).

“½Ġ⁻S’b5_2⁸ị - Main link: n
“½Ġ⁻S’       - base 250 number      184222584
      b5     - convert to base 5   [3, 3, 4, 1, 3, 0, 1, 1, 0, 3, 1, 4]
        _2   - subtract 2          [1, 1, 2, -1, 1, -2, -1, -1, -2, 1, -1, 2]
          ⁸  - left argument, n
           ị - index into (1-based and modular)
Jonathan Allan
źródło
4

Haskell, 33 26 bajtów

a!b=a:b:(a+b)!(-a)
(1!1!!)

Podejście rekurencyjne. 0-indeksowane. Wypróbuj na Ideone.
Zaoszczędzono 7 bajtów dzięki xnor .

Stosowanie:

Prelude> (1!1!!)11
2
Laikoni
źródło
Wygląda na krótszy do zrobienia a!b=a:b:(a+b)!(-a).
xnor
3

Mathematica, 40 bajtów

Po prostu tworzy tabelę przeglądową i uzyskuje do niej dostęp cyklicznie, jak w odpowiedzi ETHproductions. Funkcja bez nazwy, indeksowana 1.

Join[s={2,1,1,2,-1,1},-s][[#~Mod~12+1]]&
Greg Martin
źródło
3

MATL , 17 16 15 bajtów

'"Bl)e'F5Za2-i)

Dane wejściowe są oparte na 1.

Wypróbuj online!

Wyjaśnienie

Sekwencja ma kropkę [1 1 2 -1 1 -2 -1 -1 -2 1 -1 2].

'"Bl)e     % Compressed array [1 1 2 -1 1 -2 -1 -1 -2 1 -1 2] with source 
           % alphabet [-2 -1 0 1 2]
F5Za       % Decompress with target alphabet [0 1 2 3 4]
2-         % Subtract 2 to transform alphabet into [-2 -1 0 1 2]
i)         % Input N and use as (modular, 1-based) index into the sequence
Luis Mendo
źródło
3

WinDbg, 26 bajtów

?(85824331b>>@$t0%c*3&7)-2

Dane wejściowe są przekazywane przez pseudo-rejestr $t0. 0-indeksowane. +2 każdego terminu w sekwencji jest zapisywane w postaci 3 bitów 85824331b.

Jak to działa:

? (85824331b >> @$t0 % c * 3 & 7) - 2 ;*? Evalutes the expression. Shifts 85824331b to get
                                       *the 3 bits for the @$t0'th term (mod c (12) when
                                       *the sequence repeats). Bitwise AND by 7 to get the
                                       *desired 3 bits, finally subtract 2 since the terms
                                       *where stored as +2.

Przykładowe dane wyjściowe, pętla drukująca pierwsze 14 wartości sekwencji:

0:000> .for(r$t0=0;@$t0<e;r$t0=@$t0+1){?(85824331b>>@$t0%c*3&7)-2}
Evaluate expression: 1 = 00000001
Evaluate expression: 1 = 00000001
Evaluate expression: 2 = 00000002
Evaluate expression: -1 = ffffffff
Evaluate expression: 1 = 00000001
Evaluate expression: -2 = fffffffe
Evaluate expression: -1 = ffffffff
Evaluate expression: -1 = ffffffff
Evaluate expression: -2 = fffffffe
Evaluate expression: 1 = 00000001
Evaluate expression: -1 = ffffffff
Evaluate expression: 2 = 00000002
Evaluate expression: 1 = 00000001
Evaluate expression: 1 = 00000001
mleko
źródło
3

Java, 32 bajty

n->"334130110314".charAt(n%12)-50

Ponieważ jest to Java, odpowiedź jest indeksowana na 0.

Testowanie i niestosowanie:

class Ideone {
  public static void main (String[] args) throws Exception {
    java.util.function.IntFunction f = n->"334130110314".charAt(n%12)-50;
    for (int i = 0; i < 12; i++) {
      System.out.printf("%d -> %d%n", i, f.apply(i));
    }
  }
}

Testuj na Ideone

Olivier Grégoire
źródło
2

Matematyka, 45 41 38 bajtów

Dzięki @MartinEnder za 3 bajty.

±0=±1=1;±n_:=±(n-2)+±(n-1)(1-2n~Mod~2)

0-indeksowane.

Stosowanie

±5

-2

JungHwan Min
źródło
2
Prawdopodobnie można zapisać trzy bajty, definiując jednoargumentowy operator ±zamiast funkcji a.
Martin Ender,
1

Perl 6 ,  39 35  32 bajtów

{(1,1,{|(($/=$^a+$^b),$b-$/)}...*)[$_]}
{(|(334130110314.comb X-2)xx*)[$_]}
{(|334130110314.comb xx*)[$_]-2}
{334130110314.substr($_%12,1)-2}
Brad Gilbert b2gills
źródło
1

C #, 117 bajtów

Gra w golfa:

int A(int n){var f=new List<int>{0,1,1};for(int i=3;i<=n;i++){f.Add(i%2>0?f[i-1]+f[i-2]:f[i-2]-f[i-1]);}return f[n];}

Nie golfowany:

public int A(int n)
{
  var f = new List<int> { 0, 1, 1 };

  for (int i = 3; i <= n; i++)
  {
    f.Add(i % 2 > 0 ? f[i - 1] + f[i - 2] : f[i - 2] - f[i - 1]);
  }

  return f[n];
}

Testowanie:

var alternatingFibonacci = new AlternatingFibonacci();
Console.WriteLine(alternatingFibonacci.B(10));
1
Pete Arden
źródło
Skompiluj do Func <int, int>, więc public int A(int n)teraz n=>możesz usunąć nawiasy klamrowe wokół instrukcji for, oszczędzając 2 bajty, możesz wstępnie zwiększyć ipętlę tj. ++i <= nI ustawić i = 2oszczędzanie 3 bajtów, ponieważ usuwa ona i++na końcu instrukcji
TheLethalCoder
Zobacz także moją odpowiedź, jeśli
śledziłeś
1

R, 38 bajtów

Wykorzystuje rozwiązanie tabeli odnośników inspirowane odpowiedzią JET @ETHproductions.

c(s<-c(2,1,1,2,-1,1),-s)[scan()%%12+1]

Edycja: zapomniałem wspomnieć, że jest to indeks 1.

Billywob
źródło
1

Właściwie 22 bajty

34*@%"334130110314"E≈¬

Wypróbuj online!

Wyjaśnienie:

34*@%"334130110314"E≈¬
34*@%                   input % 12
     "334130110314"E    get that character in the string
                    ≈¬  convert to int, subtract 2
Mego
źródło
1

Java 7, 88 82 79 bajtów

grał w golfa:

int f(int n){int c,i=0,a=1,b=1;for(;i<n;){c=i++%2>0?a-b:a+b;a=b;b=c;}return b;}

bez golfa:

int f(int n)
{
    int c, i = 0, a = 1, b = 1;
    for (; i < n;)
    {
        c = i++ % 2 > 0 ? a - b : a + b;
        a = b;
        b = c;
    }
    return b;
}

Wypróbuj online

brzoskwinia
źródło
1
Ponieważ podążasz „logiczną” drogą, oto kilka wskazówek: 1. zapomniałeś zadeklarować intjako typ zwrotu. 2. można oszczędzić bajty, przenosząc przypisanie 0 do deklaracji i: int c,i=0i for(;i<n;){. 3. Możesz usunąć nawias wokół warunku operatora trójskładnikowego.
Olivier Grégoire,
1
@ OlivierGrégoire dzięki stary :) naprawiono. fajne rozwiązanie btw
peech
1

DC, 55 bajtów

?sd[ln1+snly[[+2Q]sEln2%1=E-]xlyrsylnld>r]sr1sy0sn1lrxp

0-indeksowane.

?sd                                                     takes input and stores
                                                        it in register d

                                            1sy0sn1     stores 1 in register y
                                                        and 0 in register n and
                                                        appends 1 to the stack

   [ln1+snly                                            adds 1 to register n and
                                                        appends the value of
                                                        register y to the stack

            [[+2Q]sEln2%1=E-]                           adds or subtracts the
                                                        the two values on the
                                                        stack depending on
                                                        parity of n

                             xlyrsylnld>r]              does the rest of the
                                                        stuff required to store
                                                        the new values properly
                                                        and quits if it has
                                                        done enough iterations

                                          sr            stores the main macro
                                                        in register r

                                                   lrxp executes the macro and
                                                        prints the stack

Rejestr d przechowuje indeks wartości. Rejestr n liczy liczbę zakończonych iteracji. Zarejestruj się r przechowuje główne makro. Zarejestruj y przechowuje późniejszą wartość w sekwencji, podczas gdy stos zawiera wcześniejszą wartość w sekwencji.

Wizualne wyjaśnienie tego, co dzieje się w dużej pętli (przy założeniu dodania):

register: y=1     y=1   y=1    y=1   y=1    y=2
stack:     1      1 1    2     2 1   1 2     1
               ly     +     ly     r     sy

Sprawdzenie, czy dodać, czy odjąć, bierze licznik modulo dwa i wykorzystuje tę sztuczkę do stworzenia konstrukcji if if else.

Na końcu stos zawiera pojedynczą liczbę, pożądaną wartość, którą drukuje się p.

(Jestem nowy dc, więc spodziewam się, że zostaną tutaj wprowadzone pewne oczywiste ulepszenia).

poi830
źródło
0

ForceLang , 153 bajty

def s set
s a 1
s b 1
s p 1
s k io.readnum()
if k=0
goto b
label a
s c b.mult p
s c a+c
s a b
s b c
s p p.mult -1
s k k+-1
if k
goto a
label b
io.write a
SuperJedi224
źródło
0

Turtlèd , 35 bajtów

#112-1_--_1-2#?:[*l+].(-r'1)(_"-2")

0 zindeksowanych

Wyjaśnienie:

#112-1_--_1-2#                      the 12 values of sequence. - is -1, _ is -2
              ?:                    input a number and move right that many
                [*l+]               move back to the asterisk on start cell, 
                                    increment sting pointer by amount moved
                     .              write pointed char
                      (-r'1)        if it was -, move right, write 1
                            (_"-2") if it was _, write "-2"
      [print grid]

Wypróbuj online!

Zniszczalna cytryna
źródło
0

ABCR, 43 bajty

)AAB)ABB..A))A..A)AA(ABB.)A+A)))AiB5aAb(Bxo

Objaśnienie: pierwsza część ( )AAB)ABB..A))A..A)AA(ABB.)A+A)))A) ustawia kolejkę A, aby zawierała [1, 1, 2, -1, 1, -2, -1, -1, -2, 1, -1, 2], pozostawiając wszystkie pozostałe kolejki puste . iBprzechowuje pożądany termin, a pętla 5aAb(Bxtyle razy przechodzi przez kolejkę. owypisuje przód kolejki jako liczbę, która będzie naszą pożądaną odpowiedzią.

Steven H.
źródło
0

Partia, 49 bajtów

@cmd/cset/a"n=%1%%12,~!(n%%3)*(1|-!(n%%5*(n/4)))"

Pobiera dane wejściowe jako parametr wiersza polecenia. Objaśnienie: Formularz zamknięty korzysta z następujących obserwacji:

  • Sekwencja jest cykliczna z okresem 12
  • Co trzeci termin to ± 2, podczas gdy inne terminy to ± 1
  • Warunki po trzeciej są ujemne, z wyjątkiem wielokrotności 5 (po zmniejszeniu modulo 12)

Dlatego zaczynamy od zmniejszenia modulo 12 (aby zaoszczędzić 2 bajty). Następnie zmniejszamy moduł trzy i odwracamy wynik, który w przeciwnym razie wynosi 1 dla wielokrotności 3 lub 0. Następnie bitowo nie otrzymujemy tej wartości, co daje nam -2 dla wielokrotności 3 lub -1 w przeciwnym razie. Następnie zmniejszamy moduł 5 i dzielimy osobno przez 4, dając zero dla warunków 1, 2, 3, 5, 10 i 12 (0). Odwracanie i negowanie daje nam -1 dla tych wartości i zero dla innych wartości. Następnie bitowo lub to przez 1 i mnożymy przez wcześniejsze obliczenia.

Neil
źródło
0

TI-Basic, 26 bajtów

Niestety bardzo nieciekawe podejście. Nie mogłem znaleźć nic krótszego. Lista jest indeksowana 1.

Input :{1,1,2,-1,1,-2:augment(Ans,-Ans:Ans(X
Timtech
źródło
0

C #, 73 71 bajtów

Wykorzystuje 0 indeksowane wartości n.

n=>{int a=1,b=1,i=0,r;for(;++i<n;){r=i%2>0?a+b:a-b;a=b;b=r;}return b;};

Wersja sformatowana:

Func<int, int> f = n =>
{
    int a = 1, b = 1, i = 0, r;

    for(; ++i < n;)
    {
        r = i % 2 > 0 ? a + b : a - b;
        a = b;
        b = r;
    }

    return b;
};
TheLethalCoder
źródło