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 golf golfowy , więc wygrywa odpowiedź z najmniejszą liczbą bajtów!
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?Odpowiedzi:
Python , 64 bajty
Wypróbuj online!
źródło
Galaretka ,
76 bajtówWypróbuj online!
W jaki sposób?
źródło
Ṛc’SƲƤ
które mogą być przydatne w podobnych sekwencjach.Python 3.6 , 61 bajtów
Wypróbuj online!
źródło
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
11
i 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,
Spójrz na te komórki:
Oznaczę to:
pow
jest tam, aby znaleźć maksymalną moc 2, która jest ściśle większa niżnum
.sum
jest jak dotąd łączeniem liczb.cat
to potęga 2, którą musiałbym pomnożyćnum
, aby połączyćnum
przedsum
(więc mógłbym po prostu dodać).Pętla: sprawdź, czy
f_n
jest ściśle mniejsza niżpow
.Prawda:
Zero śmieci. Następnie dodaj
num
*cat
dosum
. Następnie załaduj następny numer Fibonacciego (=f_(n-1)
; jeśli nie istnieje, wyjdź z pętli) i ustawcat
nacat
*pow
. Przygotuj się do następnej pętli (wyzeruj więcej śmieci, przesuń zakres o jeden).Falsey:
Ustaw
pow
na 2 *pow
, przywróćnum
.Powtarzaj, aż nie pozostanie liczba Fibonacciego.
Wyczyść śmieci. Weź każdą cyfrę wynikowej liczby i wypisz każdą (w ascii).
źródło
Łuska , 7 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Japt , 9 bajtów
Uruchom
Wyjaśnienie:
źródło
Pyth, 22 bajty
Wypróbuj tutaj
Wyjaśnienie
źródło
Perl 6 , 38 bajtów
Wypróbuj online!
źródło
JavaScript (Node.js) ,
7065585755 bajtówWypróbuj online!
źródło
-0
na końcu, aby zapisać kolejne 2 bajty.05AB1E , 6 bajtów
Wypróbuj online!
1-indeksowany.
źródło
J, 36 bajtów
Wyjaśnienie:
źródło
x 86,
372221 bajtówDziennik zmian
bsr
. Dzięki Peter Cordes!-2 przez zerowanie rejestrów za pomocą
mul
.-1 za pomocą pętli while zamiast
loop
ipush
/pop
ecx
(kredyt Peter Cordes).Wejście
edi
, wyjścieedx
.Objdump:
źródło
lea
do przesuwania i dodawania w Fib2. Ponadto wyodrębnianie każdego z bitów pojedynczo nie jest konieczne. Użyj,bsr %eax, %ecx
aby znaleźć liczbę bitów w reprezentacji binarnej, i użyj przesunięcia CL / lub, aby scalić, tak jak robi to odpowiedź Dennisa w Pythonie.cl
liczników przesunięć, więc weź licznik pętli w inny rejestr (jak%edi
) i użyjdec %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,loop
gdy problem staje się trudniejszy, a nie łatwiejszy. (Twoja konwencja wywoływania jest już niestandardowa, klobberowanie%ebx
, więc nie wywoływaj swojej funkcjimain
) Możesz być w stanie wrócić w EAX, wciąż korzystając z 1-bajtowegoxchg
, nie musisz być niestandardowy, jeśli nie musisz.inc %ecx
liczbę przesunięć na dodatkowe przesunięcie w lewo podczas dodawania, używająclea (%eax, %edx, 2), %edx
. Neutralny w bajtach dla 32-bitów, zapisuje jeden dla x86-64. Ale zapisuje instrukcję.loop
golfa 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,loop
jest 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.xor
/mul
lewy do wyzerowania trzech rejestrów (czy potrzebujesz tak wielu zer?), Ale użycie tego jako elementu tworzenia1
czyni bardziej sensownym.APL (Dyalog) ,
2622 bajtów4 bajty zapisane dzięki @ H.PWiz
Wypróbuj online!
źródło
Haskell ,
897675 bajtówWersja bez golfa:
źródło
f=0:scanl(+)1f
(wzięty stąd ). Funkcje mogą być anonimowe, więc możesz porzucić wiodąceg=
, zobacz nasz Przewodnik po zasadach gry w golfa w Haskell .$realToFrac y
z.read.show$y
jednej bajtPari / GP , 59 bajtów
Wypróbuj online!
źródło
APL + WIN, 55 bajtów
Monity o wprowadzenie liczby całkowitej.
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
źródło
Python 3 , 94 bajty
Wypróbuj online!
źródło
Galaretka , 6 bajtów
Wypróbuj online!
Ḷ
owered Zakres -> n pÆḞ
liczba ibonacci -> z dec doB
inary ->F
Latten -> zḄ
inary DECźródło
10
i dostaniesz16024033463
, to jest niepoprawne (poprawna odpowiedź to250375522
).10
zwraca250375522
MATL , 21 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
J , 25 bajtów
Wypróbuj online!
Wyjaśnienie
źródło
Python 3 , 86 bajtów
Wypróbuj online!
źródło
Dodaj ++ , 113 bajtów
Wypróbuj online!
źródło
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
Wyjaśnienie
Sprawdź także ten post z przepełnieniem stosu . Najlepsza odpowiedź odnosi się do tego samego artykułu na Wikipedii.
źródło
Stax , 9 bajtów
Uruchom i debuguj na staxlang.xyz!
Rozpakowane (10 bajtów) i objaśnienie:
źródło
Julia 0.6 , 65 bajtów
Wypróbuj online!
źródło
Pyth, 27 bajtów
Zestaw testowy
Tłumaczenie Python 3:37 bajtówZestaw testowy
Tłumaczenie Python 3:źródło
Rubin , 61 bajtów
Wypróbuj online!
źródło
Jotlin , 59 bajtów
Program testowy
Obsługuje do 10, zmiana
.i(2)
na.toLong(2)
obsługuje do 14 w razie potrzebyźródło
Python 2, 88 bajtów
źródło
R ,
244180179 bajtówWypróbuj online!
Zapisano niektóre bajty, łącząc wektory numeryczne, a nie łańcuchy. Cholerna specjalna skrzynka na 0!
źródło
sapply
do 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 doifelse
. I ... możemy usunąć,""
zescan
tak.