Binarne Fibonacciego

31

Wyzwanie

Musisz wygenerować program lub funkcję, która przyjmuje dodatnią liczbę całkowitą N, oblicza pierwsze N ​​składników sekwencji Fibonacciego w systemie binarnym, konkatenuje ją w pojedynczą liczbę binarną, konwertuje tę liczbę z powrotem na dziesiętną, a następnie wypisuje dziesiętny jako liczba całkowita.

Na przykład

1 -> [0] -> 0 to decimal outputs 0
3 -> [0, 1, 1] -> 011 to decimal outputs 3
4 -> [0, 1, 1, 10] -> 01110 to decimal outputs 14

Nie musisz wyprowadzać ->, tylko numer (np. Jeśli typ użytkownika 4, po prostu wyjdź 14). Strzałki mają jedynie pomóc wyjaśnić, co musi zrobić program.

Przypadki testowe

1 -> 0
2 -> 1
3 -> 3
4 -> 14
5 -> 59
6 -> 477
7 -> 7640
8 -> 122253
9 -> 3912117
10 -> 250375522
11 -> 16024033463
12 -> 2051076283353
13 -> 525075528538512
14 -> 134419335305859305
15 -> 68822699676599964537
16 -> 70474444468838363686498
17 -> 72165831136090484414974939
18 -> 147795622166713312081868676669
19 -> 605370868394857726287334099638808
20 -> 4959198153890674493745840944241119317

Program musi być w stanie wyświetlać dane wyjściowe do limitu używanego języka. Niedozwolone są tabele odnośników i typowe obejścia .

To jest , więc wygrywa odpowiedź z najmniejszą liczbą bajtów!

Nathan Wood
źródło
1
Dodano przypadki testowe od 0 do 20 z tio.run/##DYxBCoQwDAC/… . Podziękowania dla @alephalpha za program.
Nathan Wood
6
Jak nie zostało jeszcze powiedziane: Witamy w PPCG! Ładne pierwsze wyzwanie.
Laikoni
@Laikoni Thanks!
Nathan Wood
Gdzie dokładnie obowiązuje limit dla danego języka? Czy dozwolona byłaby funkcja C zwracająca 32-bitową liczbę całkowitą? Podobnie int32_t binary_concat_Fib(int n), co ograniczyłoby wynikową wartość wyjściową do 2 ^ 31-1. tzn. możesz założyć, że wszystkie połączone bity pasują do liczby całkowitej. A może funkcja powinna działać do tego stopnia, że ​​największa liczba Fibonacciego nie pasuje sama do liczby całkowitej, więc łączenie bitów wymaga większej precyzji?
Peter Cordes
1
I czy „konwersja na dziesiętne” musi być jawne, wywołując funkcję typu integer-> string lub pisząc ją samodzielnie? Łączenie bitów w jedną liczbę całkowitą daje reprezentację ostatecznej wartości. Jeśli dobrze rozumiem, odpowiedź Dennisa w Pythonie zwraca liczbę całkowitą, pozostawiając dzwoniącemu przekształcenie tej wartości w ciąg dziesiętny lub cokolwiek z tym zrobić. Wartości całkowite w językach komputerowych, które obsługują operatory przesunięcia bitów, są naturalnie binarne, a nie dziesiętne, chyba że są przechowywane w ciągach. W językach bez zmian / operatorów bitowych nic nie sugeruje żadnej podstawy.
Peter Cordes

Odpowiedzi:

11

Python , 64 bajty

f=lambda n,a=0,b=1,r=0:n and f(n-1,b,a+b,r<<len(bin(a))-2|a)or r

Wypróbuj online!

Dennis
źródło
1
Fajnie, właśnie starałem się osiągnąć ten styl.
Jonathan Allan
10

Galaretka ,  7  6 bajtów

ḶÆḞBẎḄ

Wypróbuj online!

W jaki sposób?

ḶÆḞBẎḄ - Link: integer, n
Ḷ      - lowered range -> [0,1,2,3,4,5,...,n]
 ÆḞ    - Fibonacci (vectorises) -> [0,1,1,2,3,5...,F(n)]
   B   - to binary (vectorises) -> [[0],[1],[1],[1,0],[1,1],[1,0,1],...,B(F(n))]
    Ẏ  - tighten -> [0,1,1,1,0,1,1,1,0,1,...,B(F(n))[0],B(F(n))[1],...]
     Ḅ - from binary -> answer
Jonathan Allan
źródło
1
Bałąc się nowymi skrótami, odkryłem, że można również znaleźć pierwsze n liczb Fibonacciego, Ṛc’SƲƤktóre mogą być przydatne w podobnych sekwencjach.
mile
7

pieprzenie mózgu , 397 bajtów

>,[<++++++[->--------<]>>[->++++++++++<]>[-<+>]<<[->+<],]>+[-<<+>>[-[->+<]<<[->+>+<<]<[->+>+<<]>[-<+>]>>[-<<+>>]>]]<<[->+>>>>>+<<<<<<]>[-<+>]>+>>+>>>+<[[->-[<<]>]>[[-]<<<<<<<[->>[-<+>>+<]>[-<+>]<<<]<[->+>>>>>+<<<<<<]>[-<+>]>[-<+>]>[->>[-<+<<+>>>]<[->+<]<]>+>[-]>>+>]<<<<<[[->++>+>++<<<]>[-<+>]<<]>>>]>[-]<<<[-]<<[-]<<->[>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>>]<+[->++++++[-<++++++++>]<.<<<+]

To była zabawa!

Pobiera dane wejściowe ASCII (np. 11), Wyniki dają wynik ASCII.

Uwaga: aby wypróbować to online, upewnij się, że ustawiłeś rozmiar komórki na 32 bity (po prawej stronie strony). Jeśli nie wprowadzisz danych wejściowych, przeglądarka może ulec awarii.

Tłumacz nie może obsłużyć danych wejściowych 11i wyższych, ponieważ obsługuje tylko do 32 bitów.

Wypróbuj na copy.sh

Wyjaśnienie

>,[<++++++[->--------<]>>[->++++++++++<]>[-<+>]<<[->+<],]>+

Uzyskaj dane dziesiętne i dodaj jedno (aby złagodzić efekt jeden po drugim)

[-<<+>>[-[->+<]<<[->+>+<<]<[->+>+<<]>[-<+>]>>[-<<+>>]>]]

Wygeneruj liczby Fibonacciego na taśmie.

<<[->+>>>>>+<<<<<<]>[-<+>]>+>>+>>>+<

Skonfigurowany dla przychodzącej pętli binarnej konkatenacji


Więc komórki zawierają wartość, zaczynając od pierwszej pozycji,

1 | 0 | 1 | 1 | 2 | 3 | 5 | ... | f_n | 0 | 1 | 0 | 1 | 0 | f_n | 1 | 0 | 0 | 0...

Spójrz na te komórki:

f_n | 0 | 1 | 0 | 1 | 0 | f_n | 1

Oznaczę to:

num | sum | cat | 0 | pow | 0 | num | pow

powjest tam, aby znaleźć maksymalną moc 2, która jest ściśle większa niż num. sumjest jak dotąd łączeniem liczb. catto potęga 2, którą musiałbym pomnożyć num, aby połączyć numprzed sum(więc mógłbym po prostu dodać).


[[->-[<<]>]>

Pętla: sprawdź, czy f_njest ściśle mniejsza niż pow.

Prawda:

[[-]<<<<<<<[->>[-<+>>+<]>[-<+>]<<<]<[->+>>>>>+<<<<<<]>[-<+>]>[-<+>]>[->>[-<+<<+>>>]<[->+<]<]>+>[-]>>+>]

Zero śmieci. Następnie dodaj num* catdo sum. Następnie załaduj następny numer Fibonacciego (= f_(n-1); jeśli nie istnieje, wyjdź z pętli) i ustaw catna cat* pow. Przygotuj się do następnej pętli (wyzeruj więcej śmieci, przesuń zakres o jeden).

Falsey:

<<<<<[[->++>+>++<<<]>[-<+>]<<]

Ustaw powna 2 * pow, przywróć num.

]

Powtarzaj, aż nie pozostanie liczba Fibonacciego.


>[-]<<<[-]<<[-]<<->[>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>>>]<+[->++++++[-<++++++++>]<.<<<+]

Wyczyść śmieci. Weź każdą cyfrę wynikowej liczby i wypisz każdą (w ascii).

JungHwan Min
źródło
7

Łuska , 7 bajtów

ḋṁḋ↑Θİf

Wypróbuj online!

Wyjaśnienie

ḋṁḋ↑Θİf                              4
     İf    The Fibonacci numbers     [1,1,2,3,5,8..]
    Θ      Prepends 0                [0,1,1,2,3,5..]
   ↑     Take n elements from list   [0,1,1,2]
  ḋ        Convert to binary digits  [[0],[1],[1],[1,0]]
 ṁ       Map function then concat    [0,1,1,1,0]
ḋ        Convert from base 2         14
Fyr
źródło
Witamy w PPCG! :)
DJMcMayhem
5

Japt , 9 bajtów

ÆMgX ¤Ã¬Í

Uruchom

Wyjaśnienie:

ÆMgX ¤Ã¬Í
Æ     Ã     | Iterate X through the range [0...Input]
 MgX        |   Xth Fibonacci number
     ¤      |   Binary
       ¬    | Join into a string
        Í   | Convert into a base-2 number
Oliver
źródło
1
Bah! Pokonaj mnie do tego!
Shaggy
1
@Shaggy Wiedziałem, że to będzie wyścig przeciwko tobie: P
Oliver,
4

Pyth, 22 bajty

JU2VQ=+Js>2J)is.BM<JQ2

Wypróbuj tutaj

Wyjaśnienie

JU2VQ=+Js>2J)is.BM<JQ2
JU2                       Set J = [0, 1].
   VQ       )             <Input> times...
     =+Js>2J              ... add the last 2 elements of J and put that in J.
                  <JQ     Take the first <input> elements...
               .BM        ... convert each to binary...
              s           ... concatenate them...
             i       2    ... and convert back to decimal.

źródło
3

Perl 6 , 38 bajtów

{:2([~] (0,1,*+*...*)[^$_]>>.base(2))}

Wypróbuj online!

nwellnhof
źródło
1
Zauważ, że zaczyna się zauważalnie wolniej przy wejściach powyżej 200.
Wytworzenie
3

JavaScript (Node.js) , 70 65 58 57 55 bajtów

  • dzięki Shaggy za zmniejszenie 2 bajtów („0b + C-0 do„ 0b ”+ C)
f=(n,a=C=0,b=1)=>--n?f(n,b,a+b,C+=b.toString(2)):'0b'+C

Wypróbuj online!

DanielIndie
źródło
Możesz porzucić -0na końcu, aby zapisać kolejne 2 bajty.
Shaggy
2

J, 36 bajtów

3 :'#.;<@#:"0]2}.(,{:+_2&{)^:y _1 1'

Wyjaśnienie:

3 :'#.;<@#:"0]2}.(,{:+_2&{)^:y _1 1' | Explicit function
                 (,{:+_2&{)^:y _1 1  | Make n fibonacci numbers, with _1 1 leading
              2}.                    | Drop the _1 1
       <@#:"0]                       | Convert each item to binary and box
      ;                              | Unbox and join
    #.                               | Convert back from binary
Bolce Bussiere
źródło
2

x 86, 37 22 21 bajtów

Dziennik zmian

Wejście edi, wyjście edx.

.section .text
.globl main
main:
        mov     $5, %edi            # n = 5

start:
        dec     %edi                # Adjust loop count
        xor     %ebx, %ebx          # b = 0
        mul     %ebx                # a = result = 0
        inc     %ebx                # b = 1

fib:
        add     %ebx, %eax          # a += b
        xchg    %eax, %ebx          # swap a,b
        bsr     %eax, %ecx          # c = (bits of a) - 1
        inc     %ecx                # c += 1
        sal     %cl, %edx           # result >>= c
        add     %eax, %edx          # result += a

        dec     %edi                # n--; do while(n)
        jnz     fib 

        ret

Objdump:

00000005 <start>:
   5:   4f                      dec    %edi
   6:   31 db                   xor    %ebx,%ebx
   8:   f7 e3                   mul    %ebx
   a:   43                      inc    %ebx

0000000b <fib>:
   b:   01 d8                   add    %ebx,%eax
   d:   93                      xchg   %eax,%ebx
   e:   0f bd c8                bsr    %eax,%ecx
  11:   41                      inc    %ecx
  12:   d3 e2                   shl    %cl,%edx
  14:   01 c2                   add    %eax,%edx
  16:   4f                      dec    %edi
  17:   75 f2                   jne    b <fib>
  19:   c3                      ret    
qwr
źródło
1
Służy leado przesuwania i dodawania w Fib2. Ponadto wyodrębnianie każdego z bitów pojedynczo nie jest konieczne. Użyj, bsr %eax, %ecxaby znaleźć liczbę bitów w reprezentacji binarnej, i użyj przesunięcia CL / lub, aby scalić, tak jak robi to odpowiedź Dennisa w Pythonie.
Peter Cordes
1
Potrzebujesz clliczników przesunięć, więc weź licznik pętli w inny rejestr (jak %edi) i użyj dec %edi / jnz(3 bajty w 32-bitowym kodzie, 4 bajty w 64-bitowym). W kodzie 32-bitowym oszczędza to 1 bajt łącznie przed upuszczeniem ecx push / pop. Nie wpadnij w pułapkę używania, loopgdy problem staje się trudniejszy, a nie łatwiejszy. (Twoja konwencja wywoływania jest już niestandardowa, klobberowanie %ebx, więc nie wywoływaj swojej funkcji main) Możesz być w stanie wrócić w EAX, wciąż korzystając z 1-bajtowego xchg, nie musisz być niestandardowy, jeśli nie musisz.
Peter Cordes
1
Możesz zamienić dodatkową inc %ecxliczbę przesunięć na dodatkowe przesunięcie w lewo podczas dodawania, używając lea (%eax, %edx, 2), %edx. Neutralny w bajtach dla 32-bitów, zapisuje jeden dla x86-64. Ale zapisuje instrukcję.
Peter Cordes
1
Za każdym razem, gdy używam loopgolfa kodowego, czuję się brudny. Cóż, niezupełnie, ale rozczarowany, że nie mogłem znaleźć równie małej implementacji, która unikałaby tak powolnych instrukcji; poza golfowym kodem, loopjest jednym z moich ulubieńców . Chciałbym, żeby był szybki na współczesnych procesorach, ponieważ byłoby to bardzo miłe dla pętli o rozszerzonej precyzji bez przeciągnięć z częściową flagą, ale nie jest to i powinno być traktowane jedynie jako niejasna instrukcja optymalizacji wielkości, która spowalnia kod.
Peter Cordes
1
W każdym razie niezła robota. Poza push / pop / loop -> dec / jnz, nie widzę żadnych oszczędności, tylko przyspieszenie LEA, które jest neutralne pod względem wielkości kodu. Zawsze zastanawiałem się, czy kiedykolwiek istniał prawdziwy przypadek użycia xor/ mullewy do wyzerowania trzech rejestrów (czy potrzebujesz tak wielu zer?), Ale użycie tego jako elementu tworzenia 1czyni bardziej sensownym.
Peter Cordes
2

Haskell , 89 76 75 bajtów

f=0:scanl(+)1f
foldr1(\x y->y+x*2*2^floor(logBase 2.read.show$y)).(`take`f)

Wersja bez golfa:

import Data.Bits

fib = 0:scanl (+) 1 fib

catInt :: Integer -> Integer -> Integer
catInt x y = x' + y where
    position = floor $ succ $ logBase 2 $ realToFrac y
    x' = shift x position

answer :: Integer -> Integer
answer n = foldr1 catInt fib' where
    fib' = take n fib
użytkownik9549915
źródło
1
Witamy w szczególności w PPCG i Haskell! Krótszy sposób na wygenerowanie nieskończonej listy liczb Fibonacciego f=0:scanl(+)1f(wzięty stąd ). Funkcje mogą być anonimowe, więc możesz porzucić wiodące g=, zobacz nasz Przewodnik po zasadach gry w golfa w Haskell .
Laikoni
Dzięki! To kompensuje niektóre z dłuższych używanych funkcji. Spędziłem trochę czasu, starając się znaleźć sposób na zastosowanie bit-shift w bardziej zwięzły sposób, ale nie udało mi się.
user9549915
Można wymienić $realToFrac yz .read.show$yjednej bajt
H.PWiz
1

APL + WIN, 55 bajtów

Monity o wprowadzenie liczby całkowitej.

v←b←0 1⋄⍎∊(⎕-2)⍴⊂'v←v,c←+/¯2↑v⋄b←b,((1+⌊2⍟c)⍴2)⊤c⋄'⋄2⊥b

Maksymalna dokładność liczb całkowitych APL + WIN wynosi 17, a limit liczb całkowitych jest rzędu 10E300, dlatego maksymalna liczba wejściowa wynosi 55, a wynik to: 1.2492739026634838E300

Graham
źródło
1

Galaretka , 6 bajtów

ḶÆḞBFḄ

Wypróbuj online!

owered Zakres -> n p ÆḞliczba ibonacci -> z dec do Binary -> FLatten -> z inary DEC

chromat
źródło
Nie rozumiałem tego języka, ale myślałem, że wynik nie zawsze jest poprawny. np. Wpisz 10i dostaniesz 16024033463, to jest niepoprawne (poprawna odpowiedź to 250375522).
Guoyang Qin
@AbrahamChin Dane wejściowe 10zwraca250375522
Dennis
Równoważna, zduplikowana odpowiedź , po prostu heads-up
caird coinheringaahing
1

MATL , 21 bajtów

0li:"yy+]xx&h"@B]&hXB

Wypróbuj online!

Wyjaśnienie

0l        % Push 0, then 1 (initial terms of the Fibonacci sequence)
i:"       % Do n times, where n is the input
  yy+     %   Duplicate top two numbers and push their sum
  ]       % End
xx        % Delete the last two results. The stack now contains the
          % first n Fibonacci numbers, starting at 0
&h        % Concatenate all numbers into a row vector
"         % For each
  @       %   Push current number
  B       %   Convert to binary. Gives a vector of 0 and 1
]         % End
&h        % Concatenate all vectors into a row vector
XB        % Convert from binary to decimal. Implicitly display
Luis Mendo
źródło
1

J , 25 bajtów

2(#.;)<@#:@(1#.<:!|.)\@i.

Wypróbuj online!

Wyjaśnienie

2(#.;)<@#:@(1#.<:!|.)\@i.  Input: n
                       i.  Range [0, n)
                     \@    For each prefix
                  |.         Reverse
                 !           Binomial coefficient (vectorized)
               <:            Decrement
            1#.              Sum
        #:                   Convert to binary
      <                      Box
    ;                        Link. Join the contents in each box
2 #.                         Convert to decimal from base 2
mile
źródło
1

Dodaj ++ , 113 bajtów

D,f,@@@@*,V$2D+G1+dAppp=0$Qp{f}p
D,k,@,¿1=,1,bM¿
D,g,@,¿1_,1_001${f},1¿{k}
D,w,@,BBbR
D,l,@,ßR€gp€w@0b]@¦+VcG2$Bb

Wypróbuj online!

Cairney Coheringaahing
źródło
1

PHP, 124 bajty

Wypróbuj online!

Szukałem więc sposobu na wyprowadzenie liczb Fibonacciego za pomocą serii, dopóki nie znalazłem tego . Okazuje się, że można obliczyć serię Fibonacciego za pomocą zaokrąglania, więc próbowałem wyzwania z funkcją rekurencyjną.

Uważam, że podejście do „zaokrąglania” jest naprawdę interesujące, również profesor pokazał mi to jakiś czas temu.

Kod

function f($n,$i=0,$b=''){ if($n>$i){$b.=
decbin(round(pow((sqrt(5)+1)/2,$i)/sqrt(5)));f($n,$i+1,$b);}else{echo bindec($b);}}

Wyjaśnienie

function f($n,$i=0,$b=''){           #the function starts with $i=0, our nth-fib number
if($n>$i){                           #it stops once $n (the input) = the nth-fib
    $b.=decbin(                      #decbin returns an integer as bin, concatenates
        round(pow((sqrt(5)+1)/2,$i)/sqrt(5))    
                                       #the formula, basically roundign the expression
        );                           #it returns the (in this case) $i-th fib-number   
    f($n,$i+1,$b);                   #function is called again for the next index
}else{                               #and the current string for fibonacci

    echo bindec($b);                 #"echo" the result, bindec returns the base 10
                                     #value of a base 2 number
}
}

Sprawdź także ten post z przepełnieniem stosu . Najlepsza odpowiedź odnosi się do tego samego artykułu na Wikipedii.

Francisco Hahn
źródło
Ciekawy sposób na zrobienie tego!
Nathan Wood
1

Stax , 9 bajtów

ü1∞╓♪εw≤+

Uruchom i debuguj na staxlang.xyz!

Rozpakowane (10 bajtów) i objaśnienie:

vr{|5|Bm|B
v             Decrement integer from input. Stax's Fibonacci sequence starts with 1 :(
 r            Integer range [0..n).
  {    m      Map a block over each value in an array.
   |5           Push nth Fibonacci number.
     |B         Convert to binary.
        |B    Implicit concatenate. Convert from binary. Implicit print.
Khuldraeseth na'Barya
źródło
1

Pyth, 27 bajtów

JU2V-Q2=aJ+eJ@J_2)is.BM<JQ2

Zestaw testowy

Tłumaczenie Python 3:
Q=eval(input())
J=list(range(2))
for i in range(Q-2):
    J.append(J[-1]+J[-2])
print(int(''.join(map("{0:b}".format,J[:Q])),2))

37 bajtów

J[Z1)W<lJQ=aJ+eJ@J_2)Ig1QZ.?ijkm.BdJ2

Zestaw testowy

Tłumaczenie Python 3:
Q=eval(input())
J=[0,1]
while len(J)<Q:
    J.append(J[-1]+J[-2])
if 1>=Q:
    print(0)
else:
    print(int(''.join(map("{0:b}".format,J)),2))

hakr14
źródło
0

Jotlin , 59 bajtów

g(l(0,1)){l(a.sum(),a[0])}.take(this).j(""){a[0].s(2)}.i(2)

Program testowy

data class Test(val input: Int, val output: Long)

val tests = listOf(
    Test(1, 0),
    Test(2, 1),
    Test(3, 3),
    Test(4, 14),
    Test(5, 59),
    Test(6, 477),
    Test(7, 7640),
    Test(8, 122253),
    Test(9, 3912117),
    Test(10, 250375522)
)
fun Int.r() = g(l(0,1)){l(a.sum(),a[0])}.take(this).j(""){a[0].s(2)}.i(2)

fun main(args: Array<String>) {
    for (r in tests) {
        println("${r.input.r()} vs ${r.output}")
    }
}

Obsługuje do 10, zmiana .i(2)na .toLong(2)obsługuje do 14 w razie potrzeby

jrtapsell
źródło
0

Python 2, 88 bajtów

def f(n):
 a,b,r=0,1,"0"
 for _ in range(n-1):a,b=b,a+b;r+=bin(a)[2:]
 print int(r,2)
sonrad10
źródło
0

R , 244 180 179 bajtów

i=ifelse;g=function(n)i(n<3,1,g(n-1)+g(n-2))
a=scan(,"");i(a==1,0,sum(2^(which(rev(unlist(sapply(g(2:a-1),function(x)(y=rev(as.numeric(intToBits(x))))[which(!!y)[1]:32]))>0))-1)))

Wypróbuj online!

Zapisano niektóre bajty, łącząc wektory numeryczne, a nie łańcuchy. Cholerna specjalna skrzynka na 0!

Andreï Kostyrka
źródło
Funkcje są dopuszczalne. O wiele bardziej efektywne jest również przesunięcie wyniku o liczbę bitów niż zawracanie wektorem numerycznym. Zobacz moją lub Dennisa odpowiedź na python. Ma to dodatkową zaletę obsługi przypadku 0.
qwr
@qwr Odpowiedź nie jest funkcją; Tworzę funkcję pomocnika, ponieważ musi ona być sapplydo wektora ze względu na fakt, że jest rekurencyjna. Nie można wszystkich zawinąć w jedną linię. Jak widać, program pyta użytkownika o dane wejściowe, a następnie zwraca odpowiedź. Jeden bajt można zapisać, tworząc skrót do ifelse. I ... możemy usunąć ,""ze scantak.
Andreï Kostyrka