ลำดับพลังงาน Fibonacci สลับ

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

คำนิยาม

ลำดับพลังงาน Fibonacci สลับเป็นรูปแบบดังนี้

  1. เริ่มต้นด้วยลำดับว่างและตั้ง n เป็น 1

  2. คำนวณ f n n n ไม่ใช่ เลขฟีโบนักชีที่ ไม่ลบด้วยซ้ำ
    0 เป็นครั้งแรก 1 เป็นครั้งที่สองและที่สาม 2 คือสี่ อื่น ๆ ทั้งหมดจะได้รับโดยการรวมสองตัวเลขก่อนหน้านี้ในลำดับดังนั้น 3 = 1 + 2 เป็น 5, 5 = 2 + 3 เป็นที่หกเป็นต้น

  3. ถ้า n เป็นเลขคี่ให้เปลี่ยนเครื่องหมายของ f n

  4. ผนวก 2n-1 สำเนาของ f n เป็นลำดับ

  5. เพิ่มค่า n และกลับไปยังขั้นตอนที่ 2

นี่คือคำศัพท์ APF หนึ่งร้อยคำแรก

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 

งาน

เขียนโปรแกรมเต็มหรือฟังก์ชันที่ใช้จำนวนเต็มบวก n เป็น input และ prints หรือส่งกลับค่า n ของลำดับ APF

หากคุณต้องการใช้การจัดทำดัชนีแบบ 0 คุณสามารถเลือกใช้จำนวนเต็มที่ไม่ใช่ค่าลบ n และพิมพ์หรือคืนค่าหมายเลข APF ที่ดัชนี n

นี่คือ ; รหัสที่สั้นที่สุดในไบต์อาจชนะ!

กรณีทดสอบ (แบบ 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 

กรณีทดสอบ (อิงตาม 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
มีข้อ จำกัด ใด ๆ สำหรับ n ?
2 Dennis♦ 01/31/2017
ตราบเท่าที่อัลกอริทึมของคุณทำงานกับค่าที่มีขนาดใหญ่โดยพละของ n คุณสามารถสันนิษฐานได้ว่าเหมาะสมกับประเภทข้อมูลของคุณ
1 Mindwin 02/01/2017
หมายเลขนี้มีหมายเลข OEIS หรือไม่?
Dennis♦ 02/01/2017
@Mindwin ไม่ได้

12 Answers


Jonathan Allan 01/31/2017.

เยลลี่ 5 ไบต์

BLCÆḞ 

Try it online!

อย่างไร?

การขยายช่วง Fibonacci กลับไปเป็นดัชนีเชิงลบเช่นความสัมพันธ์ f(i) = f(i-2) + f(i-1) ยังคงถือ:

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

จะกลับมาจาก i=0 ตัวเลขคือตัวเลขที่เราต้องการทำซ้ำ 2n-1 ครั้งและ ÆḞ 's Fibonacci built-in, ÆḞ จะคำนวณค่าเหล่านี้

เราสามารถหา -i (จำนวนบวก) ที่เราต้องการโดยการใช้ความยาวบิตของ n และลบ 1

เนื่องจากเราต้องการ i (จำนวนลบ) เราจึงสามารถทำ 1-bitLength และ Jelly มี atom สำหรับ 1-x , C , monad complement

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
ฉันรู้ว่ามีวิธีที่สั้นกว่า แต่ไม่ได้โดยมากที่คิดว่ามันต้องการจะ 7 bytes ด้วยวิธีการลบ µ และ
Jonathan Allan 01/31/2017
ปฏิเสธซ้ำของคุณได้ฉลาดแม้ว่าฉันกำลังมองหาที่อำนาจของลบหนึ่งซึ่งเพิ่มสอง bytes จนฉันเรียกคืนเกี่ยวกับค่า Fibonacci ลบและพยายามเสียบพวกเขาเป็น monad เยลลี่.
4 ETHproductions 01/31/2017
สุจริตฉันประหลาดใจวุ้นไม่มี builtin หนึ่งไบต์ที่จะได้รับความยาวไบนารีของจำนวน ...

xnor 01/31/2017.

Python 2 , 30 bytes

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

ทดลองใช้แบบออนไลน์!

หนึ่งในการจัดทำดัชนี

ลำดับความรู้สึกเหมือนปริศนาสิ่งที่เดนนิสสร้างขึ้นโดยมีวิธีสั้น ๆ ในการแสดงออก การแสดงซ้ำสองครั้งของพลังงานสองครั้งแนะนำให้มีการทำซ้ำโดยการขยับบิต (แบ่งพื้นด้วย 2) เครื่องหมาย Fibonacci f(n)=f(n-2)-f(n-1) สามารถเปลี่ยนให้เป็น bitshift แทน decrementing กรณีพื้นฐานทำงานได้ดีเพราะทุกอย่างเป็นช่องทาง n=0


martin 02/01/2017.

Mathematica, 43 36 24 ไบต์

Fibonacci@-Floor@Log2@#& 

บันทึก 7 ไบต์ได้ด้วย @GregMartin และอีก 12 ครั้งขอบคุณ @JungHwanMin

2 comments
1 Greg Martin 01/31/2017
คุณสามารถบันทึกบางไบต์ได้โดยใช้ Floor@Log2@# และเขียน Fibonacci[t=...] (และลบช่องว่างในเลขชี้กำลังล่าสุด)
1 JungHwan Min 02/01/2017
-12 bytes: Fibonacci@-Floor@Log2@#& - Fibonacci สามารถใช้อาร์กิวเมนต์เชิงลบได้เช่นกัน (ดูแลเครื่องหมายสำหรับคุณ)

Luis Mendo 02/01/2017.

MATL , 19 17 16 11 ไบต์

lOiB"yy-]x& 

ข้อมูลอินพุตเป็น 1

ทดลองใช้แบบออนไลน์! หรือ ตรวจสอบกรณีทดสอบทั้งหมด

มันทำงานอย่างไร

สำหรับ n input 1 ตัวให้ m เป็นจำนวนหลักในการขยายฐานสองของ n คำที่ n th ในลำดับเอาท์พุทคือ m th ในลำดับ Fibonacci ซึ่งอาจมีการเปลี่ยนแปลงเครื่องหมาย

หนึ่งความคิดที่จะไปย้ำ m ครั้งในการคำนวณเงื่อนไขของลำดับ Fibonacci นี้เป็นเรื่องง่ายด้วย for each วงโดยใช้อาร์เรย์ของตัวเลขไบนารี ถ้าลำดับ Fibonacci ถูก initiallized กับ 0 แล้ว 1 ตามปกติ iterating m ครั้งจะส่งผลให้ m+2 เงื่อนไขในสแต็คดังนั้นด้านบนสองตัวเลขจะต้องถูกลบออก แทนเราเริ่มต้นด้วย 1 แล้ว 0 ด้วยวิธีนี้คำที่สร้างต่อไปคือ 1 , 1 , 2 , ... และจำเป็นต้องมีการลบเพียง one

เครื่องหมายสามารถจัดการได้โดยการใช้ลูปอื่นเพื่อเปลี่ยนเครื่องหมาย m ครั้ง แต่ค่าใช้จ่ายสูงมาก จะดีกว่าที่จะรวมลูปทั้งสองซึ่งทำได้โดยการ subtracting แทนการเพิ่มในการย้ำ Fibonacci

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 ไบต์

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

1 การจัดทำดัชนี

พอร์ตของ คำตอบของ xnor จะเป็น 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) 

ทดลองใช้แบบออนไลน์!

1 comments
TuukkaX 01/31/2017
ช่องว่างไม่จำเป็นต้องใช้ or -1

miles 01/31/2017.

เยลลี่ 9 ไบต์

BLµ’ÆḞN⁸¡ 

ใช้การจัดทำดัชนีแบบหนึ่ง ๆ

ทดลองใช้แบบออนไลน์!

คำอธิบาย

วิธีนี้ใช้งานได้ถ้าฟังก์ชัน Fibonacci ของคุณสนับสนุนอาร์กิวเมนต์ที่ไม่ใช่เชิงลบเท่านั้น

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 ไบต์

Mg1-¢l 

ทดสอบแบบออนไลน์!

มันทำงานอย่างไร

ดังที่ได้กล่าวไว้ในคำตอบอื่น ๆ คำที่ n ในชุด Fibonacci Fibonacci แบบสลับกันจะเหมือนกับคำที่ -n ในชุดปกติ n สามารถพบได้โดยการเอาบิตยาวของ input และ subtracting หนึ่ง; negating ผลลัพธ์นี้ใน 1 ลบความยาวบิต

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 ไบต์

ใช้การจัดทำดัชนีแบบ 1 รายการ

ฟังก์ชัน Fibonacci ของ 05AB1E จะให้ค่าตัวเลข fib บวกน้อยกว่า n ซึ่งหมายความว่าเราต้องสร้างมากกว่าที่จำเป็นให้ได้ค่าที่ถูกต้องจากดัชนีแล้วคำนวณเครื่องหมาย ดังนั้นฉันสงสัยวิธีการตามรอบที่จะสั้นกว่าการคำนวณตัวเลข iteratively.

ใช้การสำนึกที่เราสามารถเริ่มต้นกองด้วย 1, 0 กลับเพื่อจัดการกับกรณีเมื่อ n=1 ตามที่อธิบายไว้ใน คำตอบ MATL ของ Luis Mendo

XÎbgG‚D«`- 

ทดลองใช้แบบออนไลน์!

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 ไบต์

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

การดำเนินการตามลำดับอย่างตรงไปตรงมาตามที่อธิบายไว้
Zero-based


Dennis 04/13/2017.

Julia 0.5 , 19 ไบต์

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

ทดลองใช้แบบออนไลน์!

มันทำงานอย่างไร

สูตรนี้ใช้สูตรเดียวกับ คำตอบ Python ของ xox ของ @ xnor ความสัมพันธ์ของการกลับเป็นซ้ำ
g(n) = g(n-2) + g(n-1) สร้างเงื่อนไขเชิงลบของลำดับ Fibonacci ซึ่งเท่ากับเทอมบวกกับสัญญาณสลับ จากที่ใดก็ได้ในการเรียกซ้ำจำนวน 2 k ที่มีหมายเลขเดียวกันเราสามารถเลือกซ้ำซ้อนของการเรียกใช้เลขที่ 2 k-1 และการเรียกใช้เลข 2 k-2 ก่อนหน้านี้ได้โดยการหารดัชนีด้วย 2 และ 4

แทนที่จะตรงไปตรงมา

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

เราสามารถกำหนดผู้ประกอบการใหม่เพื่อวัตถุประสงค์ของเรา นอกจากนี้ f จะทำงานได้ดีเช่นเดียวกับ floats ดังนั้นเราจึงได้รับ

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

ท้ายสุดถ้าเราอัพเดต n พร้อมกับหารด้วย 4 เราสามารถเขียน n/2 เป็น 2n และละเว้น parens ซึ่งนำไปสู่คำจำกัดความของฟังก์ชัน 19-byte


miles 02/05/2017.

J , 18 ไบต์

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

ใช้การจัดทำดัชนีแบบหนึ่ง ๆ ใช้เลขจำนวนเต็ม input n > 0 และคำนวณ floor(log2(n)) โดยค้นหาความยาวของการแทนค่า binary และลดค่าที่หนึ่ง จากนั้นจะพบ floor(log2(n))-1 ค่าสัมประสิทธิ์ที่ floor(log2(n))-1 ของฟังก์ชันการสร้าง x / (1 + x - x 2 ) ซึ่งเป็นค่า gf สำหรับค่า Fibonacci ที่มีการจัดทำดัชนีเป็นลบ

ทดลองใช้แบบออนไลน์!

คำอธิบาย

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

POP/STARS flac

(G)I-DLE. 2018. Writer: Riot Music Team;Harloe.
2 Ariana Grande

​Thank U, Next flac

Ariana Grande. 2018. Writer: Crazy Mike;Scootie;Victoria Monét;Tayla Parx;TBHits;Ariana Grande.
3 Imagine Dragons

Bad Liar flac

Imagine Dragons. 2018. Writer: Jorgen Odegard;Daniel Platzman;Ben McKee;Wayne Sermon;Aja Volkman;Dan Reynolds.
4 Backstreet Boys

Chances flac

Backstreet Boys. 2018.
5 Clean Bandit

Baby flac

Clean Bandit. 2018. Writer: Jack Patterson;Kamille;Jason Evigan;Matthew Knott;Marina;Luis Fonsi.
6 BTS

Waste It On Me flac

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

Kiss And Make Up flac

BlackPink. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
8 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
9 Kelly Clarkson

Never Enough flac

Kelly Clarkson. 2018. Writer: Benj Pasek;Justin Paul.
10 Fitz And The Tantrums

HandClap flac

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

Told You So flac

Little Mix. 2018. Writer: Eyelar;MNEK;Raye.
12 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
13 Cher Lloyd

None Of My Business flac

Cher Lloyd. 2018. Writer: ​iamBADDLUCK;Alexsej Vlasenko;Kate Morgan;Henrik Meinke;Jonas Kalisch;Jeremy Chacon.
14 Bradley Cooper

Always Remember Us This Way flac

Bradley Cooper. 2018. Writer: Lady Gaga;Dave Cobb.
15 Calum Scott

No Matter What flac

Calum Scott. 2018. Writer: Toby Gad;Calum Scott.
16 Ashley Tisdale

Voices In My Head flac

Ashley Tisdale. 2018. Writer: John Feldmann;Ashley Tisdale.
17 Imagine Dragons

Machine flac

Imagine Dragons. 2018. Writer: Wayne Sermon;Daniel Platzman;Dan Reynolds;Ben McKee;Alex Da Kid.
18 Diplo

Close To Me flac

Diplo. 2018. Writer: Ellie Goulding;Savan Kotecha;Peter Svensson;Ilya;Swae Lee;Diplo.
19 Billie Eilish

When The Party's Over flac

Billie Eilish. 2018. Writer: Billie Eilish;FINNEAS.
20 Little Mix

Woman Like Me flac

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

Related questions

Hot questions

Language

Popular Tags