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,
F ₂ = 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 1jest 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

K (ngn / k) , 45 43 42 41 bajtów

{2/<':(+/F@&+/'|2\x){y!x}\|F:64(+':1,)/0}

Wypróbuj online!

Algorytm Bubblera

{ } funkcja z argumentem x

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ć do Fdla „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\xbinarnie 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 do F

• +/ suma

<': mniej niż każdy poprzedni (pierwszy wynik zawsze będzie falsey)

2/ dekodowanie binarne

CJam, 76 74 70 63 59 bajtów

2q~{32{2\#I&},}fI+32_,*{WUer$Kf-[UU]/[-2X]*2,/2a*Kf+}fKf#1b

Wypróbuj online w interpretatorze CJam lub zweryfikuj wszystkie przypadki testowe jednocześnie .

Pomysł

Zaczynamy od zdefiniowania niewielkiej odmiany sekwencji w pytaniu:

G _-2 = 0
G _-1 = 1
G _k = G _k-1 + G _k-2, gdy k jest liczbą całkowitą nieujemną

W ten sposób bit 0 (LSB) na wejściu bit tablic lub odpowiada wyjściowych do liczby Fibonacciego G ₀ 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 ₁₀ = 1000010100 ₂ 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. ¹

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 ₀ , 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

2             e# Push a 2 we'll need later.
q~            e# Read and evaluate the input.
{             e# For each integer I in the input:
  32{         e#   Filter [0 ... 31]; for each J:
    2\#       e#     Compute 2**J.
    I&        e#     Compute its logical AND with I.
  },          e#   Keep J if the result in truthy (non-zero).
}fI           e#
+             e# Concatenate the resulting arrays.
32_,*         e# Repeat [0 ... 31] 32 times.
{             e# For each K:
  WUer        e#   Replace -1's with 0's.
  $           e#   Sort.
  Kf-         e#   Subtract K from each element.
  [UU]/[-2X]* e#   Replace subarrays [0 0] with [-2 1].
  2,/2a*      e#   Replace subarrays [0 1] with [2].
  Kf+         e#   Add K to each element.
}fK           e#
f#            e# Replace each K with 2**K.
1b            e# Cast all to integer (discards 2**-2) and sum.

¹ _{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ść.}

APL (Dyalog Extended) , 39 bajtów

⊥1↓⍧|/⌽(+/g[⍸⌽+/⊤⎕]),↑,\⌽g←(2+/,)⍣38⍨⍳2

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←0tak, że ⍳2ocenia 0 1.

Generator Fibonacciego (nowy)

Zauważ, że dwie ostatnie liczby są niedokładne, ale nie zmienia to wyniku działania programu.

(2+/,)⍣38⍨⍳2
→ 0 1 ((2+/,)⍣38) 0 1

Step 1
0 1 (2+/,) 0 1
→ 2+/ 0 1 0 1
→ (0+1) (1+0) (0+1) ⍝ 2+/ evaluates sums for moving window of length 2
→ 1 1 1

Step 2
0 1 (2+/,) 1 1 1
→ 2+/ 0 1 1 1 1
→ 1 2 2 2

Step 3
0 1 (2+/,) 1 2 2 2
→ 2+/ 0 1 1 2 2 2
→ 1 2 3 4 4

Zeckendorf na zwykły (częściowy)

⍸⌽+/⊤⎕
     ⎕  ⍝ Take input from stdin, must be an array of 2 numbers
    ⊤   ⍝ Convert each number to base 2; each number is mapped to a column
  +/    ⍝ Sum in row direction; add up the counts at each digit position
 ⌽      ⍝ Reverse
⍸       ⍝ Convert each number n at index i to n copies of i

APL (Dyalog Extended) , 47 bajtów

g←1↓(1,+\⍤,)⍣20⍨1
{⊥1↓⍧|/⌽⍵,↑,\⌽g}+⍥{+/g[⍸⌽⊤⍵]}

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)

{+/g[⍸⌽⊤⍵]}
       ⊤⍵    ⍝ Argument to binary digits
     ⍸⌽      ⍝ Reverse and convert to indices of ones
   g[    ]   ⍝ Index into the Fibonacci array of 1,2,3,5,...
 +/          ⍝ Sum

APL (Dyalog Extended) , 52 bajty

{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣20⍨1}+⍥({+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤)

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

{+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤  ⍝ Zeckendorf to plain integer
                ⊤  ⍝ Convert the input to array of binary digits (X)
{    (  ≢⊤⍵)  }    ⍝ Take the length L of the binary digits and
      ⌽⍳           ⍝   generate 1,2..L backwards, so L..2,1
{+∘÷⍣(     )⍨1}    ⍝ Apply "Inverse and add 1" L..2,1 times to 1
                   ⍝ The result looks like ..8÷5 5÷3 3÷2 2 (Y)
               ⊥   ⍝ Mixed base conversion of X into base Y

Base |             Digit value
-------------------------------
13÷8 | (8÷5)×(5÷3)×(3÷2)×2 = 8
 8÷5 |       (5÷3)×(3÷2)×2 = 5
 5÷3 |             (3÷2)×2 = 3
 3÷2 |                   2 = 2
 2÷1 |                   1 = 1

Część 2: Dodaj dwie zwykłe liczby całkowite

+⍥z2i  ⍝ Given left and right arguments,
       ⍝   apply z2i to each of them and add the two

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.

{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣20⍨1}  ⍝ Convert plain integer N to Zeckendorf
                 (1,+\⍤,)⍣20⍨1   ⍝ First 41 Fibonacci numbers starting with two 1's
                ⌽                ⍝ Reverse
             ↑,\                 ⍝ Matrix of prefixes, filling empty spaces with 0's
          ⌽⍵,                    ⍝ Prepend N to each row and reverse horizontally
        |/                       ⍝ Reduce by | (residue) on each row (see below)
       ⍧                         ⍝ Nub sieve; 1 at first appearance of each number, 0 otherwise
  1↓¯1↓                          ⍝ Remove first and last item
 ⊥                               ⍝ Convert from binary digits to integer

Generator Fibonacciego

(1,+\⍤,)⍣20⍨1
→ 1 ((1,+\⍤,)⍣20) 1  ⍝ Expand ⍨
→ Apply 1 (1,+\⍤,) x 20 times to 1

First iteration
1(1,+\⍤,)1
→ 1,+\1,1  ⍝ Expand the train
→ 1,1 2    ⍝ +\ is cumulative sum
→ 1 1 2    ⍝ First three Fibonacci numbers

Second iteration
1(1,+\⍤,)1 1 2
→ 1,+\1,1 1 2  ⍝ Expand the train
→ 1 1 2 3 5    ⍝ First five Fibonacci numbers

⍣20  ⍝ ... Repeat 20 times

Wynika to z właściwości liczb Fibonacciego: jeśli Fibonacciego jest zdefiniowane jako

następnie

Łączna suma $1,F_0, \cdots, F_n$ (Tablica Fibonacciego poprzedzona 1) staje się $F_1, \cdots, F_{n+2}$. Następnie przygotowuję 1 ponownie, aby uzyskać zwykłą tablicę Fibonacciego, zaczynając od indeksu 0.

Cyfry Fibonacciego do Zeckendorfa

Input: 7, Fibonacci: 1 1 2 3 5 8 13

Matrix
0 0 0 0 0 0 13 7
0 0 0 0 0 8 13 7
0 0 0 0 5 8 13 7
0 0 0 3 5 8 13 7
0 0 2 3 5 8 13 7
0 1 2 3 5 8 13 7
1 1 2 3 5 8 13 7

Reduction by residue (|/)
- Right side always binds first.
- x|y is equivalent to y%x in other languages.
- 0|y is defined as y, so leading zeros are ignored.
- So we're effectively doing cumulative scan from the right.
0 0 0 0 0 0 13 7 → 13|7 = 7
0 0 0 0 0 8 13 7 →  8|7 = 7
0 0 0 0 5 8 13 7 →  5|7 = 2
0 0 0 3 5 8 13 7 →  3|2 = 2
0 0 2 3 5 8 13 7 →  2|2 = 0
0 1 2 3 5 8 13 7 →  1|0 = 0
1 1 2 3 5 8 13 7 →  1|0 = 0
Result: 7 7 2 2 0 0 0

Nub sieve (⍧): 1 0 1 0 1 0 0
1's in the middle are produced when divisor ≤ dividend
(so it contributes to a Zeckendorf digit).
But the first 1 and last 0 are meaningless.

Drop first and last (1↓¯1↓): 0 1 0 1 0
Finally, we apply base 2 to integer (⊥) to match the output format.

Haskell, 325 396 bajty

EDYCJA: nowa wersja:

s f[]=[]
s f l=f l
x((a:b):(c:d):(e:r))=x(b:d:(a:e):r)
x(a:b:((c:d:e):r))=x((c:a):b:e:((d:s head r):s tail r))
x[]=[]
x(a:r)=a:x r
w l|x l/=l=w.x$l|True=l
l=length
t n x=take n$repeat x
j 0=[]
j n=t(mod(n)2)1:j(div(n)2)
i n=[[],[]]++j n++t(32-(l$j n))[]
u[]=0
u(a:r)=2*u r+l a
o(_:a:r)=u r+l a
z a b=o$w$zipWith(++)(i a)(i b)

z wykonuje pracę.

ES6, 130 bajtów

(n,m)=>{for(a={},s=0,i=x=y=1;i<<1;i+=i,z=y,y=x,x+=z)s+=((n&i)+(m&i))/i*(a[i]=x);for(r=0;i;i>>>=1)s>=a[i]?(s-=a[i],r|=i):0;return r}

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

Rubinowy , 85 73 65 bajtów

->*a{r=(0..2*a.sum).select{|r|r^r*2==r*3};r[a.sum{|w|r.index w}]}

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

Python 3, 207 bajtów

def s(n):
 p=1
 while n>=2*p:
  p*=2
 return n if n<=p else s(n+p//2)if n>=3*p/2 else s(m)if (m:=s(n-p)+p)!= n else n
a=lambda n,m:(b:=n&m)>-1 and s(a(a(a(s((n|m)-b%4),b//4*2),b//4),b%4*2+b%4//2))if m else n

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 i s(n)jest funkcją pomocniczą, która pozbywa się sąsiednich liczb zawartych w reprezentacji Zeckendorfa.

Zacznijmy od funkcji s(n)(rozszerzonej dla przejrzystości):

def s(n): 
    p=1                  #This finds the highest digit of the binary form of n.
    while n>=2*p:
        p*=2
    if n<=p:             #If n is a power of two (i.e, our number is already a Fibonnaci number)...
        return n         #Then return it normally.  This also works for zero. (A)
    if n>=3*p/2:         #If n's first digit is followed by a 1 (i.e, it starts with 11X)
        return s(n+p//2) #Then replace that with 100X (B)
    m = s(n-p)+p         #Otherwise, apply s to the rest of the number (C)
    if m==n:             #If this is out final result, we're done! (D)
        return n
    return s(m)          #Otherwise, reapply it. (E)

Na przykład liczba 107 ( 1101011binarnie, reprezentująca 1 + 2 + 5 + 13 + 21 = 42), przechodzi następujący proces:

1+2+5+13+21 [1101011] -> 1+2+5+34 [10001011] (B)
1+2+5+34 [10001011] (C)
 1+2+5 [1011] (C)
  1+2 [11] -> 3 [100] (B)
 ->3+5 [1100] (A/E)
 (E):  3+5 [1100] -> 8 [10000] (B)
->8+34 [10010000] (A/E)
(E): 8+34 [10010000] (C)
->8+34 [10010000] (A/E)

Wypróbuj online! (s ze szczegółowymi danymi wyjściowymi)

Oto rozszerzona wersja a(n,m):

def a(n,m):
    if m==0:
        return n
    b=n&m
    t=s((n|m)-b%4)              #(A)
    t=a(t,b//4*2)               #(B)
    t=a(t,b//4)                 #(C)
    return s(a(t,b%4*2+b%4//2)) #(D)

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 ni mponieważ 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 obu ni msą 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)

Wolfram Language (Mathematica) , 218 bajtów

Fold[#+##&,Total@PadLeft@IntegerDigits[#,2]//.{{p=n_/;n>1,r=y___}:>{0,n,y},{q=x___,i_,p,j_,k_,r}:>{x,i+1,n-2,j,k+1,y},{q,i_,p,j_}:>{x,i+1,n-2,j+1},{q,i_,p}:>{x,i+1,n-2},{1,1,r}:>{1,0,0,y},{q,i_,1,1,r}:>{x,i+1,0,0,y}}]&

Wypróbuj online!

Po prostu dopasowanie wzoru.

Nie golfowany:

FromDigits[Total@PadLeft@IntegerDigits[#, 2] //.
   {{n_ /; n > 1, y___} :> {0, n, y},
    {x___, i_, n_ /; n > 1, j_, k_, y___} :> {x, i + 1, n - 2, j, k + 1, y},
    {x___, i_, n_ /; n > 1, j_} :> {x, i + 1, n - 2, j + 1},
    {x___, i_, n_ /; n > 1} :> {x, i + 1, n - 2},
    {1, 1, y___} :> {1, 0, 0, y},
    {x___, i_, 1, 1, y___} :> {x, i + 1, 0, 0, y}}, 2] &