Der Satz von Zeckendorf zeigt, dass jede positive ganze Zahl eindeutig als Summe nicht benachbarter Fibonacci-Zahlen dargestellt werden kann. Bei dieser Herausforderung müssen Sie die Summe zweier Zahlen in der Zeckendorfer Darstellung berechnen.

Sei F _n die n- te Fibonacci-Zahl, wobei

F ₁ = 1,
F ₂ = 2 und
für alle k > 2 ist F _k = F _{k - 1} + F _{k - 2} .

Die Zeckendorf-Darstellung Z ( n ) einer nicht negativen ganzen Zahl n ist eine Menge positiver ganzer Zahlen, so dass

n = Σ _{i ∈ Z ( n )} F _i   und
∀ _{i ∈ Z ( n )} i + 1 ∉ Z ( n ).

(in prosa: Die Zeckendorf-Darstellung einer Zahl n ist eine Menge positiver Ganzzahlen, so dass sich die Fibonacci-Zahlen für diese Indizes zu n summieren und keine zwei benachbarten Ganzzahlen Teil dieser Menge sind)

Insbesondere die Darstellung von Zeckendorf ist einzigartig. Hier einige Beispiele für Zeckendorf-Darstellungen:

Z (0) = ∅ (die leere Menge)
Z (1) = {1}
Z (2) = {2}
Z (3) = {3} ({1, 2} ist nicht die Zeckendorf-Darstellung von 3)
Z. (10) = {5, 2}
Z (100) = {3, 5, 10}

Bei dieser Herausforderung werden Zeckendorf-Darstellungen als Bitmengen codiert, wobei das niedrigstwertige Bit darstellt, ob 1es Teil der Menge usw. ist. Sie können davon ausgehen, dass die Zeckendorf-Darstellungen von Eingabe und Ausgabe in 31 Bit passen.

Ihre Aufgabe ist es, Z ( n + m ) mit Z ( n ) und Z ( m ) zu berechnen . Die Lösung mit der kürzesten Länge in Oktetten gewinnt.

Eine in ANSI C geschriebene Referenzimplementierung finden Sie hier . Es kann auch verwendet werden, um Zeckendorf-Darstellungen zu generieren oder eine Zahl aus seiner Zeckendorf-Darstellung zu berechnen.

Hier sind einige Paare von Beispieleingaben und -ausgaben, wobei die ersten beiden Spalten die Eingabe und die dritte Spalte die Ausgabe enthalten:

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 Bytes

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

Probieren Sie es online aus!

@ Bubblers Algorithmus

{ } Funktion mit Argument x

64( )/0 64-mal mit 0 als Anfangswert:

• 1, 1 voranstellen

• +': füge jeden Prior hinzu (lass das erste Element intakt)

F:zuweisen Ffür "Fibonacci-Sequenz"

| umkehren

(.. ){y!x}\.. beginnend mit dem Wert links, berechnen Sie die kumulativen Reste (von links nach rechts) für die Liste rechts. Der Wert links ist die einfache Summe der Eingaben ohne Zeckendorf-Darstellung:

• 2\xbinär codieren die Eingänge. Dies wird eine nbits-by-2-Matrix sein

• | umkehren

• +/' Summe jeder

• &wo sind die 1s - Liste der Indizes. Wenn es 2s gibt, wird der entsprechende Index zweimal wiederholt.

• F@ Array-Indizierung in F

• +/ Summe

<': weniger als jeder vorherige (der erste des Ergebnisses wird immer falsch sein)

2/ binäre Dekodierung

CJam, 76 74 70 63 59 Bytes

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

Probieren Sie es online im CJam-Interpreter aus oder überprüfen Sie alle Testfälle gleichzeitig .

Idee

Wir beginnen mit der Definition einer geringfügigen Variation der Sequenz in der Frage:

G _-2 = 0
G _-1 = 1
G _K = G _k-1 + G _k-2 , wenn k eine nicht-negative ganze Zahl ist

Auf diese Weise entspricht das Bit 0 (LSB) der eingegebenen oder ausgegebenen Bitarrays der Fibonacci-Zahl G ₀ und im Allgemeinen dem Bit k bis G _k .

Jetzt ersetzen wir jedes gesetzte Bit in Z (n) und Z (m) durch den Index, den es codiert.

Beispielsweise wird der Eingang 532 ₁₀ = 1000010100 ₂ in [2 4 9] umgewandelt .

Dies ergibt zwei Arrays von ganzen Zahlen, die wir zu einer einzigen verketten können.

Wenn beispielsweise n = m = 100 ist , ist das Ergebnis A: = [2 4 9 2 4 9] .

Wenn wir uns ersetzen k in A durch G _k und die Ergebnisse addieren, so erhalten wir n + m = 200 , so A ist eine Art und Weise zu zersetzen 200 in Fibonacci - Zahlen, aber sicherlich nicht das einer vom Zeckendorf Theorem.

Wenn man bedenkt, dass G _k + G _{k + 1} = G _{k + 2} und G _k + G _k = G _k + G _k-1 + G _k-2 = G _{k + 1} + G _k-2 , können wir aufeinanderfolgende ersetzen und doppelte Indizes von anderen (nämlich (k, k + 1) von k + 2 und (k, k) von (k + 1, k - 2) ), wobei diese Substitutionen immer wieder wiederholt werden, bis die Zeckendorf-Darstellung erreicht ist. ¹

Für die resultierenden negativen Indizes muss ein Sonderfall berücksichtigt werden. Da G _-2 = 0 ist , kann der Index -2 einfach ignoriert werden. Außerdem ist G _-1 = 0 = G ₀ , so dass jedes resultierende -1 durch 0 ersetzt werden muss .

Für unser Beispiel A erhalten wir die folgenden (sortierten) Darstellungen, wobei die letzte die Zeckendorf-Darstellung ist.

[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]

Schließlich konvertieren wir vom Array von Ganzzahlen zurück zum Bit-Array.

Code

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.

¹ _{Die Implementierung versucht 32-mal zu ersetzen und prüft nicht, ob die Zeckendorf-Darstellung tatsächlich erreicht wurde. Ich habe keinen formalen Beweis dafür, dass dies ausreichend ist, aber ich habe alle möglichen Summen von 15-Bit-Darstellungen getestet (deren Summenrepräsentationen bis zu 17 Bit erfordern) und 6 Wiederholungen waren für alle ausreichend. In jedem Fall ist es möglich, die Anzahl der Wiederholungen auf 99 zu erhöhen, ohne die Anzahl der Bytes zu erhöhen, dies würde jedoch die Leistung beeinträchtigen.}

APL (Dyalog Extended) , 39 Bytes

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

Probieren Sie es online aus!

In ein vollständiges Programm mit einem Argument der Länge 2 geändert und auch der Fibonacci-Generator geändert. Vielen Dank an @ngn für viele Ideen.

Verwendet ⎕IO←0so, dass ⍳2ausgewertet wird 0 1.

Fibonacci-Generator (neu)

Beachten Sie, dass die letzten beiden Zahlen ungenau sind, die Ausgabe des Programms jedoch nicht geändert wird.

(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 zu schlicht (teilweise)

⍸⌽+/⊤⎕
     ⎕  ⍝ 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 Bytes

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

Probieren Sie es online aus!

Teil 1 der vorherigen Antwort wurde geändert, um die Fibonacci-Zahlen wiederzuverwenden. Löschen Sie außerdem das Duplikat 1, um einige Bytes an anderen Stellen zu speichern.

Teil 1 (neu)

{+/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 Bytes

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

Probieren Sie es online aus!

Wie es funktioniert

Kein ausgefallener Algorithmus zum Hinzufügen in Zeckendorf, da APL nicht für die Operation einzelner Elemente in einem Array bekannt ist. Stattdessen habe ich die beiden Eingaben von Zeckendorf in einfache Ganzzahlen konvertiert, hinzugefügt und zurückkonvertiert.

Teil 1: Zeckendorf zur einfachen ganzen Zahl

{+∘÷⍣(⌽⍳≢⊤⍵)⍨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

Teil 2: Fügen Sie zwei einfache Ganzzahlen hinzu

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

Teil 3: Wandle die Summe zurück nach Zeckendorf

"Sie können davon ausgehen, dass die Zeckendorf-Darstellungen von Eingabe und Ausgabe in 31 Bit passen" war ziemlich praktisch.

{⊥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

Der Fibonacci-Generator

(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

Dies folgt aus der Eigenschaft von Fibonacci-Zahlen: wenn Fibonacci definiert ist als

dann

$1,F_0, \cdots, F_n$$F_1, \cdots, F_{n+2}$

Fibonacci nach Zeckendorf Ziffern

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 Bytes

EDIT: neue Version:

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 macht den Job.

ES6, 130 Bytes

(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}

Ich habe ursprünglich versucht, die Summe an Ort und Stelle zu berechnen (effektiv im Sinne der CJam-Implementierung), aber mir gingen immer wieder die temporären Werte aus, sodass ich nur die Zahlen in echte Ganzzahlen und zurück konvertierte.

(Ja, ich kann wahrscheinlich ein Byte mit eval speichern.)

Ruby , 85 73 65 Bytes

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

Probieren Sie es online aus!

Wie?

Erhalten Sie zuerst eine Obergrenze für die codierte Summe: (a + b) * 2 ist in Ordnung.

Filtern Sie nun alle Nicht-Zeckendorf-Zahlen aus (0..limit) heraus.

Wir haben eine Nachschlagetabelle, von hier geht es bergab.

Python 3, 207 Bytes

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

Probieren Sie es online aus! (Überprüfen Sie alle Testfälle)

Erläuterung

Dieses Programm bearbeitet direkt die binären Übersetzungen der Zeckendorf-Darstellungen. Die Funktion a(n,m)führt die Hauptberechnungen durch und s(n)ist eine Hilfsfunktion, die benachbarte Zahlen in der Zeckendorf-Darstellung entfernt.

Beginnen wir mit der Funktion s(n)(der Übersichtlichkeit halber erweitert):

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)

Zum Beispiel wird die Zahl 107 ( 1101011binär, die 1 + 2 + 5 + 13 + 21 = 42 darstellt) dem folgenden Prozess unterzogen:

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)

Probieren Sie es online aus! (s mit detaillierter Ausgabe)

Hier ist eine erweiterte Version von 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)

Diese Funktion konvertiert die beiden Zeckendorf-Darstellungen in vier Binärzahlen, die einfacher zu kombinieren sind. Zeile (A) ist das bitweise ODER der beiden binären Zeckendorf-Darstellungen - diese entsprechen einer Kopie jeder Fibonacci-Zahl in jeder Gruppe. (B) und (C) sind das bitweise UND der beiden Zahlen, die 1 bzw. 2 Mal nach rechts verschoben sind. Wir wissen, dass wenn die entsprechenden Fibonacci-Zahlen für (B) und (C) addiert werden, sie dem bitweisen UND von uns entsprechen nund mweil F (n) = F (n-1) + F (n-2) .

Nehmen wir zum Beispiel an, wir haben die Binärzahlen n = 101001 (entsprechend 1 + 5 + 13) und m = 110110 (2 + 3 + 8 + 13). Dann haben wir (A) = 111111 (1 + 2 + 3 + 5 + 8 + 13), das durch unsere Funktion s(B) = 10000 (8) und (10) in 1010100 (3 + 8 + 21) umgewandelt wird C) = 1000 (5). Wir können überprüfen, ob (1 + 5 + 13) + (2 + 3 + 8 + 13) = (3 + 8 + 21) + (8) + (5) = 45. Dieser Vorgang wiederholt sich mit ((3 + 8 + 21) + (8)) + (5) = ((3 + 8 + 21) + (5) + (3)) + (5) usw.

Die einzige Schwierigkeit bei diesem System ist, dass es für die Fibonacci-Zahlen 1 und 2 nicht funktioniert, da sie der Eigenschaft nicht gehorchen F(n)=F(n-1)+F(n-2)(sie sind die niedrigsten zwei Zahlen)! Aus diesem Grund wird immer dann, wenn 1 oder 2 in beiden enthalten sind nund msie aus A, B und C entfernt werden, ihre Summe in D unter der Eigenschaft 1 + 1 = 2 und 2 + 2 = 1 + 3 platziert. Wenn wir zum Beispiel 1 + 3 (101) + 1 + 3 + 5 (1101) addieren, erhalten wir:

(A): 3 + 5 (1100) = 8 (10000)

(B): 2 (10)

(C): 1 (1)

(D): 2 (10)

Beachten Sie, dass die 3 und 5 in A platziert wurden, das Duplikat 3 in B + C in 2 + 1 aufgeteilt wurde und das Duplikat 1 aus A, B und C entfernt, addiert und in D eingefügt wurde Addiere 2 + 3 (110) + 2 + 3 + 5 (1110), wir erhalten:

(A): 3 + 5 (1100) = 8 (10000)

(B): 2 (10)

(C): 1 (1)

(D): 1 + 3 (101)

Probieren Sie es online aus! (a mit detaillierter Ausgabe)

Wolfram Language (Mathematica) , 218 Bytes

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}}]&

Probieren Sie es online aus!

Einfach Mustervergleich.

Ungolfed:

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] &