Wisselstroom Fibonacci-reeks

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

Definitie

De volgorde van de alternerende vermogens-fibonacci wordt als volgt gevormd.

  1. Begin met de lege reeks en stel n op 1 .

  2. Bereken f n , het n de niet-negatieve Fibonacci-nummer , met herhalingen.
    0 is de eerste, 1 is de tweede en de derde, 2 is de vierde. Alle andere worden verkregen door de twee vorige getallen in de reeks te sommeren, dus 3 = 1 + 2 is de vijfde, 5 = 2 + 3 is de zesde, etc.

  3. Als n oneven is, verander dan het teken van f n .

  4. Voeg 2n-1 kopieën van f n toe aan de reeks.

  5. Verhoging n en ga terug naar stap 2.

Dit zijn de eerste honderd termen van de APF-reeks.

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 

Taak

Schrijf een volledig programma of een functie die een positief geheel getal n als invoer neemt en afdrukt of de nde term van de APF-reeks retourneert.

Als u de voorkeur geeft aan indexering op basis van 0, kunt u ook een niet-negatief geheel getal n en het APF-nummer bij index n afdrukken of retourneren.

Dit is ; mag de kortste code in bytes winnen!

Testgevallen (op basis van 1)

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 

Testgevallen (op basis van 0)

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
Zijn er beperkingen voor n ?
2 Dennis♦ 01/31/2017
Zolang uw algoritme voor willekeurig grote waarden van n , kunt u ervan uitgaan dat het in uw gegevenstype past.
1 Mindwin 02/01/2017
Heeft dit een OEIS-nummer?
Dennis♦ 02/01/2017
@Mindwin Dat doet het niet.

12 Answers


Jonathan Allan 01/31/2017.

Jelly , 5 bytes

BLCÆḞ 

Try it online!

Hoe?

De Fibonacci-reeks terugbrengen in negatieve indexen zodat de relatie f(i) = f(i-2) + f(i-1) nog steeds geldt:

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 ... 

Teruggaand van i=0 de getallen die we 2n-1 keer moeten herhalen, en Jelly's Fibonacci ingebouwd, ÆḞ , zal deze berekenen.

We kunnen het -i (een positief getal) vinden dat we nodig hebben door de bitlengte van n en 1 trekken.

Omdat we i (een negatief getal) willen, kunnen we in plaats daarvan 1-bitLength en Jelly heeft een atoom voor 1-x , C , de complementmonad.

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
Ik wist dat er een kortere weg was maar niet zoveel, dacht dat het 7 bytes zou zijn om µ en te verwijderen
Jonathan Allan 01/31/2017
Je herhaalde ontkenning was echter slim, ik keek naar minus één, wat een paar bytes toevoegt, totdat ik me herinnerde over de negatieve Fibonacci-waarden en probeerde ze in Jelly's monade te stoppen.
4 ETHproductions 01/31/2017
Eerlijk gezegd ben ik verrast dat Jelly geen ingebouwde byte heeft om de binaire lengte van een getal te krijgen ...

xnor 01/31/2017.

Python 2 , 30 bytes

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

Probeer het online!

One-geïndexeerd.

De reeks voelde als een puzzel, iets dat Dennis had gegenereerd door een korte manier om het uit te drukken. De power-of-two herhalingen duiden op recursie door bit-shifting (floor-dividing by 2). De Fibonacci-recursie van alternerend teken f(n)=f(n-2)-f(n-1) kan worden aangepast aan bitverschuiving in plaats van decrementering. Het basisscenario werkt goed omdat alles naar n=0 leidt.


martin 02/01/2017.

Mathematica, 43 36 24 bytes

Fibonacci@-Floor@Log2@#& 

7 bytes opgeslagen dankzij @GregMartin en nog eens 12 dankzij @JungHwanMin.

2 comments
1 Greg Martin 01/31/2017
U kunt een paar bytes opslaan met Floor@Log2@# en door Fibonacci[t=...] (en door de spaties in de laatste exponent te verwijderen).
1 JungHwan Min 02/01/2017
-12 bytes: Fibonacci@-Floor@Log2@#& - Fibonacci kan ook negatieve argumenten aannemen (zorgt voor het teken voor u).

Luis Mendo 02/01/2017.

MATL , 19 17 16 11 bytes

lOiB"yy-]x& 

Invoer is op 1 gebaseerd.

Probeer het online! Of verifieer alle testgevallen .

Hoe het werkt

Voor 1-gebaseerde invoer n , laat m het aantal cijfers in de binaire uitbreiding van n . De n term in de uitvoerreeks is de m term in de Fibonacci-reeks, mogelijk met het teken veranderd.

Een idee zou zijn om m keer te herhalen om termen uit de Fibonacci-reeks te berekenen. Dit is gemakkelijk met een for each lus met behulp van de reeks binaire cijfers. Als de Fibonacci-reeks met 0 was gepartialiseerd, dan 1 zoals gebruikelijk, zou het herhaaldelijk m malen resulteren in m+2 termen op de stapel, dus de bovenste twee getallen moeten worden verwijderd. In plaats daarvan initialiseren we met 1 en vervolgens met 0 . Op die manier zijn de volgende gegenereerde termen 1 , 1 , 2 , ... en is slechts one verwijdering nodig.

Het teken kan worden afgehandeld door een andere lus te gebruiken om het teken m maal te wijzigen. Maar dat is duur. Het is beter om de twee lussen te integreren, wat eenvoudig wordt gedaan door in plaats daarvan de Fibonacci-iteratie af te trekken.

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 bytes

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

1 geïndexeerd.

Een antwoord van xnor zou 23 zijn:

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) 

Probeer het online!

1 comments
TuukkaX 01/31/2017
Whitespace niet vereist op or -1 .

miles 01/31/2017.

Jelly , 9 bytes

BLµ’ÆḞN⁸¡ 

Gebruikt indexering op basis van één.

Probeer het online!

Uitleg

Deze methode werkt als uw Fibonacci-functie alleen niet-negatieve argumenten ondersteunt.

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 

Test het online!

Hoe het werkt

Zoals vermeld in andere antwoorden, is de nde term in de Fibonacci-reeks met alternerend teken dezelfde als de -n de term in de reguliere reeks. n kan worden gevonden door de bitlengte van de invoer te nemen en er een af ​​te trekken; dit negeert de resultaten in 1 minus de bitlengte.

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 bytes

Maakt gebruik van op 1 gebaseerde indexering

De Fibonacci-functie van 05AB1E retourneert positieve fictienummers minder dan n , wat betekent dat we meer dan nodig zouden moeten genereren, de juiste index moeten krijgen en dan het teken moeten berekenen. Dus ik betwijfel of een methode die daarop is gebaseerd korter is dan het iteratief berekenen van de getallen.

Gebruikt het besef dat we de stack kunnen initialiseren met 1, 0 omgekeerd om de case af te handelen wanneer n=1 zoals beschreven in het MATL-antwoord van Luis Mendo .

XÎbgG‚D«`- 

Probeer het 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 bytes

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

Simpele implementatie van de reeks, zoals beschreven.
Zero-based.


Dennis 04/13/2017.

Julia 0,5 , 19 bytes

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

Probeer het online!

Hoe het werkt

Dit gebruikt dezelfde formule als het Python-antwoord van @ xnor . De relatie herhaling
g(n) = g(n-2) + g(n-1) genereert de negatieve termen van de Fibonacci-reeks, die gelijk zijn aan de positieve termen met afwisselende tekens. Vanaf elke plek in een reeks van 2 k herhalingen van hetzelfde nummer, kunnen we elke herhaling van de vorige reeks van 2 k-1- nummers en de reeks van 2 k-2- nummers vóór die punten kiezen door de index te delen door 2 en 4 .

In plaats van het rechtdoorzee

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

we kunnen een operator herdefiniëren voor onze doeleinden. Ook f werkt net zo goed met drijvers, dus we krijgen

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

Tenslotte, als we n bijwerken met een deling door 4 , kunnen we n/2 als 2n en een paar parens weglaten, leidend tot de 19-byte functiedefinitie in dit antwoord.


miles 02/05/2017.

J , 18 bytes

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

Gebruikt indexering op basis van één. Neemt een invoer-geheel getal n > 0 en berekent floor(log2(n)) door de lengte van de binaire representatie te vinden en verlaagt die waarde vervolgens met één. Vervolgens wordt de floor(log2(n))-1 th coëfficiënt van de genererende functie x / (1 + x - x 2 ) gevonden, die de gf is voor de negatief geïndexeerde Fibonacci-waarden.

Probeer het online!

Uitleg

(%>:-*:)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 

Related questions

Hot questions

Language

Popular Tags