Twierdzenie Zeckendorfa pokazuje, że każdą dodatnią liczbę całkowitą można jednoznacznie przedstawić jako sumę niesąsiadujących liczb Fibonacciego. W tym wyzwaniu musisz obliczyć sumę dwóch liczb w reprezentacji Zeckendorfa.
Niech F n będzie n- tą liczbą Fibonacciego gdzie
F 1 = 1,
F 2 = 2 i
dla wszystkich k > 2, F k = F k - 1 + F k - 2 .
Reprezentacja Zeckendorfa Z ( n ) nieujemnej liczby całkowitej n jest zbiorem liczb całkowitych dodatnich, takich jak
n = Σ i ∈ Z ( n ) F i oraz
∀ i ∈ Z ( n ) i + 1 ∉ Z ( n ).
(prosa: reprezentacja Zeckendorfa liczby n jest zbiorem liczb całkowitych dodatnich, tak że liczby Fibonacciego dla tych wskaźników sumują się do n, a żadne dwie sąsiednie liczby całkowite nie są częścią tego zbioru)
W szczególności reprezentacja Zeckendorf jest wyjątkowa. Oto kilka przykładów reprezentacji Zeckendorfa:
Z (0) = ∅ (pusty zbiór)
Z (1) = {1}
Z (2) = {2}
Z (3) = {3} ({1, 2} nie jest reprezentacją Zeckendorfa dla 3)
Z (10) = {5, 2}
Z (100) = {3, 5, 10}
W tym wyzwaniu reprezentacje Zeckendorfa są kodowane jako zestawy bitów, w których najmniej znaczący bit reprezentuje if 1
jest częścią zestawu itp. Można założyć, że reprezentacje Zeckendorfa zarówno wejściowego, jak i wyjściowego pasują do 31 bitów.
Twoim zadaniem jest obliczenie Z ( n + m ) na podstawie Z ( n ) i Z ( m ). Rozwiązanie o najkrótszej długości w oktetach wygrywa.
Można znaleźć implementację referencyjną napisany w ANSI C tutaj . Można go również użyć do wygenerowania reprezentacji Zeckendorfa lub obliczenia liczby z jego reprezentacji Zeckendorfa.
Oto kilka par przykładowych danych wejściowych i wyjściowych, w których dwie pierwsze kolumny zawierają dane wejściowe, a trzecia kolumna zawiera dane wyjściowe:
73865 9077257 9478805
139808 287648018 287965250
34 279004309 279004425
139940 68437025 69241105
272794768 1051152 273846948
16405 78284865 83888256
9576577 4718601 19013770
269128740 591914 270574722
8410276 2768969 11184785
16384 340 16724
Odpowiedzi:
K (ngn / k) ,
45 43 4241 bajtówWypróbuj online!
Algorytm Bubblera
{
}
funkcja z argumentemx
64(
)/0
wykonaj 64 razy, używając 0 jako wartości początkowej:1,
prepend 1+':
dodaj każdy poprzedni (pozostaw pierwszy element nienaruszony)F:
przypisać doF
dla „sekwencji fibonacciego”|
odwrócić(
..){y!x}\
.. zaczynając od wartości po lewej, oblicz skumulowane reszty (od lewej do prawej) dla listy po prawej. wartość po lewej stronie jest zwykłą sumą danych wejściowych bez reprezentacji Zeckendorfa:2\x
binarnie koduje wejścia. będzie to macierz nbits-by-2|
odwrócić+/'
zsumuj każdy&
gdzie są jedynki? - lista wskaźników. jeśli są jakieś 2, odpowiedni indeks jest powtarzany dwukrotnie.F@
indeksowanie tablicy doF
+/
suma<':
mniej niż każdy poprzedni (pierwszy wynik zawsze będzie falsey)2/
dekodowanie binarneźródło
CJam,
7674706359 bajtówWypróbuj online w interpretatorze CJam lub zweryfikuj wszystkie przypadki testowe jednocześnie .
Pomysł
Zaczynamy od zdefiniowania niewielkiej odmiany sekwencji w pytaniu:
W ten sposób bit 0 (LSB) na wejściu bit tablic lub odpowiada wyjściowych do liczby Fibonacciego G 0 i, na ogół, nieco K do G K .
Teraz zamieniamy każdy ustawiony bit w Z (n) i Z (m) na kodowany przez niego indeks.
Na przykład wejście 532 10 = 1000010100 2 zostaje przekształcone na [2 4 9] .
Daje to dwie tablice liczb całkowitych, które możemy połączyć, tworząc jedną.
Na przykład, jeśli n = m = 100 , wynikiem jest A: = [2 4 9 2 4 9] .
Jeśli zastąpimy każdy k w A przez G k i dodać wyniki otrzymujemy n + m = 200 , więc jest sposób rozkładać 200 do liczb Fibonacciego, ale na pewno nie jeden z twierdzenie zeckendorfa.
Pamiętając, że G k + G k + 1 = G k + 2 i G k + G k = G k + G k-1 + G k-2 = G k + 1 + G k-2 , możemy zastąpić kolejne i zduplikowane indeksy przez innych (mianowicie (k, k + 1) przez k + 2 i (k, k) przez (k + 1, k - 2) ), powtarzając te podstawienia w kółko, aż do osiągnięcia reprezentacji Zeckendorfa. 1
Szczególny przypadek należy wziąć pod uwagę w przypadku wynikowych indeksów ujemnych. Ponieważ G -2 = 0 , indeks -2 można po prostu zignorować. Ponadto G -1 = 0 = G 0 , więc każdy wynikowy -1 musi zostać zastąpiony przez 0 .
W naszym przykładzie A otrzymujemy następujące (posortowane) reprezentacje, z których ostatnia to reprezentacja Zeckendorfa.
[2 2 4 4 9 9] → [0 3 4 4 9 9] → [0 5 4 9 9] → [0 6 9 9] → [0 6 7 10] → [0 8 10]
Na koniec konwertujemy z powrotem z tablicy liczb całkowitych na tablicę bitów.
Kod
1 Wdrożenie próbuje zastąpić 32 razy i nie sprawdza, czy rzeczywiście osiągnięto reprezentację Zeckendorf. Nie mam formalnego dowodu, że to wystarcza, ale przetestowałem wszystkie możliwe sumy reprezentacji 15-bitowych (których reprezentacje wymagają do 17 bitów) i dla wszystkich z nich wystarczyło 6 powtórzeń. W każdym razie zwiększenie liczby powtórzeń do 99 jest możliwe bez zwiększania liczby bajtów, ale pogorszyłoby to wydajność.
źródło
APL (Dyalog Extended) , 39 bajtów
Wypróbuj online!
Zmieniono na pełny program z jednym argumentem o długości 2, a także zmieniono generator Fibonacciego. Dzięki @ngn za wiele pomysłów.
Używa
⎕IO←0
tak, że⍳2
ocenia0 1
.Generator Fibonacciego (nowy)
Zauważ, że dwie ostatnie liczby są niedokładne, ale nie zmienia to wyniku działania programu.
Zeckendorf na zwykły (częściowy)
APL (Dyalog Extended) , 47 bajtów
Wypróbuj online!
Zmieniono część 1 poprzedniej odpowiedzi, aby ponownie użyć liczb Fibonacciego. Upuść również duplikat 1, aby zapisać niektóre bajty w innych miejscach.
Część 1 (nowa)
APL (Dyalog Extended) , 52 bajty
Wypróbuj online!
Jak to działa
Brak dodatkowego algorytmu do dodania w Zeckendorf, ponieważ APL nie jest znany z działania na poszczególnych elementach tablicy. Zamiast tego postanowiłem przekonwertować dwa wejścia z Zeckendorfa na zwykłe liczby całkowite, dodać je i przekonwertować z powrotem.
Część 1: Zeckendorf do zwykłej liczby całkowitej
Część 2: Dodaj dwie zwykłe liczby całkowite
Część 3: Przelicz sumę z powrotem na Zeckendorf
„Można założyć, że reprezentacje Zeckendorfa zarówno wejścia, jak i wyjścia pasują do 31 bitów” było całkiem przydatne.
Generator Fibonacciego
Wynika to z właściwości liczb Fibonacciego: jeśli Fibonacciego jest zdefiniowane jako
następnie
Łączna suma1 ,fa0, ⋯ ,fan (Tablica Fibonacciego poprzedzona 1) staje się fa1, ⋯ ,fan + 2 . Następnie przygotowuję 1 ponownie, aby uzyskać zwykłą tablicę Fibonacciego, zaczynając od indeksu 0.
Cyfry Fibonacciego do Zeckendorfa
źródło
Haskell, 325
396bajtyEDYCJA: nowa wersja:
z
wykonuje pracę.źródło
=
jest, więc rodzice nie są potrzebni i tak dalej, i tak dalej, i zauważcie, że:
kojarzy się po prawej i możecie tam wyciąć trochę. Ale w każdym razie gratulacje! Wygląda na bardzo skomplikowane. Nie mogę się doczekać, aby dowiedzieć się, jak to działa!ES6, 130 bajtów
Początkowo próbowałem obliczyć sumę w miejscu (efektywnie zgodnie z implementacją CJam), ale wciąż brakowało mi tymczasowości, więc po prostu przekonwertowałem liczby do iz powrotem z prawdziwych liczb całkowitych.
(Tak, prawdopodobnie mogę zapisać bajt, używając eval.)
źródło
Rubinowy ,
85 7365 bajtówWypróbuj online!
W jaki sposób?
Najpierw uzyskaj górną granicę zakodowanej sumy: (a + b) * 2 jest w porządku.
Teraz odfiltruj wszystkie liczby inne niż Zeckendorf z (0..limit).
Mamy tablicę przeglądową, stąd jest z górki.
źródło
Python 3, 207 bajtów
Wypróbuj online! (Sprawdź wszystkie przypadki testowe)
Wyjaśnienie
Ten program bezpośrednio manipuluje binarnymi tłumaczeniami reprezentacji Zeckendorf. Funkcja
a(n,m)
wykonuje główne obliczenia is(n)
jest funkcją pomocniczą, która pozbywa się sąsiednich liczb zawartych w reprezentacji Zeckendorfa.Zacznijmy od funkcji
s(n)
(rozszerzonej dla przejrzystości):Na przykład liczba 107 (
1101011
binarnie, reprezentująca 1 + 2 + 5 + 13 + 21 = 42), przechodzi następujący proces:Wypróbuj online! (s ze szczegółowymi danymi wyjściowymi)
Oto rozszerzona wersja
a(n,m)
:Ta funkcja przekształca dwie reprezentacje Zeckendorfa w cztery liczby binarne, które można łatwiej łączyć. Linia (A) to bitowa OR dwóch binarnych reprezentacji Zeckendorfa - odpowiadają one jednej kopii każdej liczby Fibonacciego w każdej grupie. (B) i (C) to bitowe ORAZ z dwóch liczb odpowiednio przesuniętych w prawo 1 i 2 razy. Wiemy, że gdy odpowiednie liczby Fibonacciego dla (B) i (C) zostaną dodane razem, będą one równoważne bitowemu AND naszej
n
im
ponieważ F (n) = F (n-1) + F (n-2) .Powiedzmy na przykład, że mamy liczby binarne n = 101001 (odpowiadające 1 + 5 + 13) im = 110110 (2 + 3 + 8 + 13). Wtedy będziemy mieli (A) = 111111 (1 + 2 + 3 + 5 + 8 + 13), który jest konwertowany do 1010100 (3 + 8 + 21) przez naszą funkcję
s
, (B) = 10000 (8) i ( C) = 1000 (5). Możemy sprawdzić, czy (1 + 5 + 13) + (2 + 3 + 8 + 13) = (3 + 8 + 21) + (8) + (5) = 45. Ten proces powtarza się z ((3 + 8 + 21) + (8)) + (5) = ((3 + 8 + 21) + (5) + (3)) + (5) itp.Jedyną trudnością związaną z tym systemem jest to, że nie działa on dla liczb Fibonacciego 1 i 2, ponieważ nie są one zgodne z właściwością
F(n)=F(n-1)+F(n-2)
(są to dwie najniższe liczby)! W związku z tym, gdy 1 lub 2 są zawarte w obun
im
są usuwane z A, B i C, po czym ich suma umieszczone D pod właściwości, 1 + 1 = 2 i 2 + 2 = 1 + 3. Na przykład, jeśli dodamy 1 + 3 (101) + 1 + 3 + 5 (1101), otrzymamy:(A): 3 + 5 (1100) = 8 (10000)
(B): 2 (10)
(C): 1 (1)
(D): 2 (10)
Zauważ, że 3 i 5 zostały umieszczone w A, duplikat 3 został podzielony na 2 + 1 w B i C, a duplikaty 1 zostały usunięte z A, B i C, dodane razem i umieszczone w D. Podobnie, jeśli dodajmy 2 + 3 (110) + 2 + 3 + 5 (1110), otrzymujemy:
(A): 3 + 5 (1100) = 8 (10000)
(B): 2 (10)
(C): 1 (1)
(D): 1 + 3 (101)
Wypróbuj online! (ze szczegółowym wyjściem)
źródło
Wolfram Language (Mathematica) , 218 bajtów
Wypróbuj online!
Po prostu dopasowanie wzoru.
Nie golfowany:
źródło