Alternerande Power Fibonacci Sequence

Dennis 08/19/2017. 12 answers, 2.084 views
code-golf math sequence array-manipulation fibonacci

Definition

Alternerande Power Fibonacci Sequence bildas enligt följande.

  1. Börja med den tomma sekvensen och ställ n till 1 .

  2. Beräkna f n , det n icke-negativa Fibonacci-numret , med repetitioner.
    0 är den första, 1 är den andra och den tredje, 2 är den fjärde. Alla andra erhålls genom att summera de två föregående numren i sekvensen, så 3 = 1 + 2 är den femte, 5 = 2 + 3 är den sjätte etc.

  3. Om n är udda, ändra tecknet på f .

  4. Lägg till 2n-1 kopior av f n till sekvensen.

  5. Ökning n och gå tillbaka till steg 2.

Dessa är de första hundra termerna av APF-sekvensen.

0  1  1 -1 -1 -1 -1  2  2  2  2  2  2  2  2 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3
-3 -3 -3 -3 -3 -3  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
 5  5  5  5  5  5  5  5  5  5  5  5  5 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
-8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 

Uppgift

Skriv ett fullständigt program eller en funktion som tar ett positivt heltal n som ingång och skriver ut eller returnerar nte termen för APF-sekvensen.

Om du föredrar 0-baserad indexering kan du alternativt ta ett icke-negativt heltal n och skriva ut eller returnera APF-numret i index n .

Detta är ; får den kortaste koden i byte vinna!

Testfall (1-baserad)

1 ->    0
    2 ->    1
    3 ->    1
    4 ->   -1
    7 ->   -1
    8 ->    2
  100 ->   -8
  250 ->   13
  500 ->  -21
 1000 ->   34
11111 ->  233
22222 -> -377
33333 ->  610 

Testfall (0-baserade)

0 ->    0
    1 ->    1
    2 ->    1
    3 ->   -1
    6 ->   -1
    7 ->    2
   99 ->   -8
  249 ->   13
  499 ->  -21
  999 ->   34
11110 ->  233
22221 -> -377
33332 ->  610 
4 Comments
Okx 01/31/2017
Finns det några begränsningar för n ?
2 Dennis♦ 01/31/2017
Så länge din algoritm fungerar för godtyckligt stora värden på n , kan du anta att den passar in i din datatyp.
1 Mindwin 02/01/2017
Har detta ett OEIS-nummer?
Dennis♦ 02/01/2017
@Mindwin Det gör det inte.

12 Answers


Jonathan Allan 01/31/2017.

Gelé , 5 byte

BLCÆḞ 

Try it online!

Hur?

Utvidga Fibonacci-serien tillbaka till negativa index så att förhållandet f(i) = f(i-2) + f(i-1) fortfarande innehåller:

i   ...   -8  -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   4   5 ...
f(i)  ...  -21  13  -8   5  -3   2  -1   1   0   1   1   2   3   5   8 ... 

Kommer tillbaka från i=0 siffrorna är de vi behöver repetera 2n-1 gånger, och Jelly's Fibonacci inbyggda, ÆḞ , kommer att beräkna dessa.

Vi kan hitta -i (ett positivt tal) som vi behöver genom att ta bitlängden av n och subtrahera 1 .

Eftersom vi vill ha ett (ett negativt tal) kan vi istället utföra 1-bitLength och Jelly har en atom för 1-x , C , komplementmonaden.

BLCÆḞ - Main link: n               e.g.  500
B     - convert n to a binary list      [1,1,1,1,1,0,1,0,0]
 L    - get the length                   9
  C   - complement                      -8
   ÆḞ - Fibonacci                       -21 
3 comments
miles 01/31/2017
Jag visste att det var en kortare väg men inte så mycket, trodde att det skulle vara 7 byte med ett sätt att ta bort µ och
Jonathan Allan 01/31/2017
Din upprepade negation var smart, men jag tittade på minus mina krafter, som lägger till ett par byte tills jag minns om de negativa Fibonacci-värdena och försökte plugga dem i Jelly's monad.
4 ETHproductions 01/31/2017
Ärligt talat, jag är förvånad. Jelly har inte en byte inbyggd för att få binär längd av ett tal ...

xnor 01/31/2017.

Python 2 , 30 byte

 f=lambda n:n<1or f(n/4)-f(n/2) 

Prova det online!

One-indexeras.

Sekvensen kändes som ett pussel, något som Dennis genererade genom att ha en kort väg att uttrycka det. Power-of-Two-repetitionerna föreslår återhämtning genom bitskiftning (golvuppdelning med 2). Alternativet Fibonacci rekursion f(n)=f(n-2)-f(n-1) kan anpassas till bitskift i stället för minskning. Basfallet fungerar fint eftersom allt tränar till n=0 .


martin 02/01/2017.

Mathematica, 43 36 24 bytes

Fibonacci@-Floor@Log2@#& 

7 byte sparade tack vare @GregMartin, och ytterligare 12 tack till @JungHwanMin.

2 comments
1 Greg Martin 01/31/2017
Du kan spara några byte med Floor@Log2@# och genom att skriva Fibonacci[t=...] (och genom att ta bort mellanslag i den sista exponenten).
1 JungHwan Min 02/01/2017
-12 bytes: Fibonacci@-Floor@Log2@#& - Fibonacci kan ta negativa argument också (tar hand om tecknet för dig).

Luis Mendo 02/01/2017.

MATL , 19 17 16 11 byte

lOiB"yy-]x& 

Ingången är 1-baserad.

Prova det online! Eller verifiera alla testfall .

Hur det fungerar

För 1-baserad ingång n , låt m vara antalet siffror i binär expansion av n . Den n termen i utmatningssekvensen är m termen i Fibonacci-sekvensen, eventuellt med dess teckenändrade.

En idé skulle vara att iterera m gånger för att beräkna villkor för Fibonacci-sekvensen. Detta är enkelt med en for each slinga med hjälp av en rad binära siffror. Om Fibonacci-sekvensen initierades med 0 , skulle 1 som vanligt resultera i iterering m gånger resultera i m+2 termer på stapeln, så de två översta siffrorna skulle behöva raderas. I stället initierar vi med 1 , sedan 0 . På så sätt är de följande genererade termerna 1 , 1 , 2 , ... och endast one radering behövs.

Tecknet kan hanteras genom att använda en annan slinga för att ändra tecken m gånger. Men det är dyrt. Det är bättre att integrera de två looparna, vilket görs enkelt genom att subtracting istället för att lägga till i Fibonacci-iterationen.

l       % Push 1
O       % Push 0
iB      % Input converted to binary array
"       % For each
  yy    %   Duplicate top two elements
  -     %   Subtract. This computes the new Fibonacci term with the sign changes
]       % End
x       % Delete top number
&       % Specify that implicit display should take only one input
        % Implicitly display the top of the stack 

ETHproductions 04/13/2017.

JavaScript (ES6), 33 byte

f=(n,p=1,c=0)=>n?-f(n>>1,c,p+c):p 

1-indexerade.

En port av xnors svar skulle vara 23:

f=n=>n<1||f(n/4)-f(n/2) 

ovs 02/18/2017.

Python 2 , 83 82 79 bytes

 def f(n,a=0,b=1):
 l=bin(n)[2:]
 for _ in l:a,b=b,a+b
 return a*-(len(l)%2or-1) 

Prova det online!

1 comments
TuukkaX 01/31/2017
Whitespace inte krävs vid or -1 .

miles 01/31/2017.

Gelé , 9 byte

BLµ’ÆḞN⁸¡ 

Använder enbaserad indexering.

Prova det online!

Förklaring

Den här metoden fungerar om din Fibonacci-funktion endast stöder icke-negativa argument.

BLµ’ÆḞN⁸¡  Input: integer n
B          Binary digits of n
 L         Length. len(bin(2)) = floor(log2(n)))
  µ        Start new monadic chain on x = len(bin(2))
   ’       Decrement
    ÆḞ     Get Fibonacci(x-1)
       ⁸¡  Repeat x times on that
      N      Negate.
           Return Fibonacci(x-1) if x is even else -Fibonacci(x-1) 

ETHproductions 01/31/2017.

Japt , 6 bytes

Mg1-¢l 

Testa det på nätet!

Hur det fungerar

Som nämnts i andra svar är nt termen i växeltecken Fibonacci-serien samma som -n termen i den vanliga serien. n kan hittas genom att ta in bitlängden på ingången och subtrahera en; negerera detta resulterar i 1 minus bitlängden.

Mg1-¢l
    ¢l  // Calculate the length of the input in binary.
  1-    // Subtract this from 1.
Mg      // Get the Fibonacci number at this index. 

Emigna 04/13/2017.

05AB1E , 11 10 byte

Använder 1-baserad indexering

05AB1E Fibonacci-funktion returnerar positiva fibtal mindre än n , vilket innebär att vi måste generera mer än nödvändigt, få den rätta efter index och beräkna sedan tecknet. Så jag tvivlar på vilken metod som är baserad kring det som kommer att vara kortare än att beräkna siffrorna iterativt.

Använder insikten att vi kan initiera stapeln med 1, 0 omvänd för att hantera fallet när n=1 som beskrivs i Luis Mendo's MATL-svar .

XÎbgG‚D«`- 

Prova det online!

Explanation

X             # push 1
 Î            # push 0 and input
  b           # convert input to binary
   g          # get length of binary number
    G         # for N in [1...len(bin(input))-1] do:
     ‚        # pair the top 2 elements of the stack in a list
      D       # duplicate the list 
       «      # concatenate the 2 lists together
        `     # split into separate elements on the stack
         -    # subtract the top 2 elements 

smls 01/31/2017.

Perl 6 , 53 byte

 {flat(((0,1,*+*...*)Z*|<-1 1>xx*)Zxx(1,2,4...*))[$_]} 

Enkel implementering av sekvensen, hur den beskrivits.
Zero-baserade.


Dennis 04/13/2017.

Julia 0,5 , 19 byte

 !n=n<1||!(n/=4)-!2n 

Prova det online!

Hur det fungerar

Detta använder samma formel som @ xnors Python-svar . Återkommande relation
g(n) = g(n-2) + g(n-1) genererar de negativa termerna i Fibonacci-sekvensen, vilket motsvarar de positiva termerna med alternerande tecken. Från var som helst i en körning på 2 k- repetitioner med samma tal kan vi välja vilken repetition som helst av den tidigare körningen av 2 k-1- tal och köra 2 k-2- nummer före dem genom att dividera indexet med 2 och 4 .

Snarare än det enkla

 f(n)=n<1||f(n÷4)-f(n÷2) # 25 bytes 

Vi kan omdefiniera en operatör för våra ändamål. f kommer också att fungera lika bra med flottor, så får vi

 !n=n<1||!(n/4)-!(n/2)   # 21 bytes 

Slutligen, om vi uppdaterar n med en division med 4 , kan wwe skriva n/2 som 2n och lämna ett par paren, vilket leder till 19-byte-funktionen definitionen i detta svar.


miles 02/05/2017.

J , 18 byte

(%>:-*:)t.@<:@#@#: 

Använder enbaserad indexering. Tar ett ingångsnumret n > 0 och beräknar floor(log2(n)) genom att hitta längden på sin binära representation och sedan sänker den värdet med en. Den finner sedan floor(log2(n))-1 th koefficienten för genereringsfunktionen x / (1 + x - x 2 ) vilket är gf för de negativa indexerade Fibonacci-värdena.

Prova det online!

Förklaring

(%>:-*:)t.@<:@#@#:  Input: integer n
                #:  Binary
              #@    Length
           <:@      Decrement
(      )            The generating function x/(1+x-x^2)
  >:                  Increment x
     *:               Square x
    -                 Subtract
 %                    Divide x by previous
        t.          Get series coefficient at the index given by previous value 

HighResolutionMusic.com - Download Hi-Res Songs

1 The Chainsmokers

Beach House flac

The Chainsmokers. 2018. Writer: Andrew Taggart.
2 (G)I-DLE

POP/STARS flac

(G)I-DLE. 2018. Writer: Riot Music Team;Harloe.
3 Anne-Marie

Rewrite The Stars flac

Anne-Marie. 2018. Writer: Benj Pasek;Justin Paul.
4 Ariana Grande

​Thank U, Next flac

Ariana Grande. 2018. Writer: Crazy Mike;Scootie;Victoria Monét;Tayla Parx;TBHits;Ariana Grande.
5 Diplo

Close To Me flac

Diplo. 2018. Writer: Ellie Goulding;Savan Kotecha;Peter Svensson;Ilya;Swae Lee;Diplo.
6 BTS

Waste It On Me flac

BTS. 2018. Writer: Steve Aoki;Jeff Halavacs;Ryan Ogren;Michael Gazzo;Nate Cyphert;Sean Foreman;RM.
7 Clean Bandit

Baby flac

Clean Bandit. 2018. Writer: Jack Patterson;Kamille;Jason Evigan;Matthew Knott;Marina;Luis Fonsi.
8 Imagine Dragons

Bad Liar flac

Imagine Dragons. 2018. Writer: Jorgen Odegard;Daniel Platzman;Ben McKee;Wayne Sermon;Aja Volkman;Dan Reynolds.
9 BlackPink

Kiss And Make Up flac

BlackPink. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
10 Nicki Minaj

No Candle No Light flac

Nicki Minaj. 2018. Writer: Denisia “Blu June” Andrews;Kathryn Ostenberg;Brittany "Chi" Coney;Brian Lee;TJ Routon;Tushar Apte;ZAYN;Nicki Minaj.
11 Rita Ora

Cashmere flac

Rita Ora. 2018. Writer: Sean Douglas;Lindy Robbins.
12 Backstreet Boys

Chances flac

Backstreet Boys. 2018.
13 Brooks

Limbo flac

Brooks. 2018.
14 Rita Ora

Velvet Rope flac

Rita Ora. 2018.
15 Fitz And The Tantrums

HandClap flac

Fitz And The Tantrums. 2017. Writer: Fitz And The Tantrums;Eric Frederic;Sam Hollander.
16 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
17 Cher Lloyd

None Of My Business flac

Cher Lloyd. 2018. Writer: ​iamBADDLUCK;Alexsej Vlasenko;Kate Morgan;Henrik Meinke;Jonas Kalisch;Jeremy Chacon.
18 Billie Eilish

When The Party's Over flac

Billie Eilish. 2018. Writer: Billie Eilish;FINNEAS.
19 Kelly Clarkson

Never Enough flac

Kelly Clarkson. 2018. Writer: Benj Pasek;Justin Paul.
20 Lil Pump

Arms Around You flac

Lil Pump. 2018. Writer: Rio Santana;Lil Pump;Edgar Barrera;Mally Mall;Jon Fx;Skrillex;Maluma;Swae Lee;XXXTENTACION.

Related questions

Hot questions

Language

Popular Tags