Geekly articles weekly

Fibonacci gerade Zahlen

Inspiriert von einem Kommentar unter einem Fibonacci- Beitrag für ein Interview . Benutzer pavellyzhin erwähnte die folgende Interviewaufgabe ( Kommentar ):
Vor mehr als einem Jahr antwortete „PHP-Programmierer“ auf die freie Stelle, sie schickten TK und es gab eine Aufgabe von Fibonacci: Wählen Sie alle geraden Fibonacci-Zahlen im Bereich von 1 bis 10000 aus . Beschlossen mit einer (for) Schleife. Dort war es auch notwendig, eine SQL-Abfrage durchzuführen, um die nächsten Geburtstage der Benutzer auszuwählen, um etwas zu erfinden. Ich erinnere mich einfach nicht und schreibe eine Funktion. Ich habe alles getan, es geschickt. Sie schickten eine Antwort: „Nach den Ergebnissen der Testaufgabe werden Sie nicht akzeptiert. Was genau sie nicht mochten, wurde nicht geschrieben. Jetzt sitze ich und denke nach, wahrscheinlich bin ich wegen Fibonacci geflogen ... :)
In diesem Beitrag werde ich zeigen, wie es möglich war, dieses Problem effektiv und vielleicht sogar effizient zu lösen, aber das ist nicht korrekt. Gleichzeitig werde ich einige Tausend Fakten über Fibonacci-Zahlen demonstrieren.


Theoretisieren



Der beste Weg, um zu beginnen, besteht darin, durch die Augen der ersten N Fibonacci-Zahlen zu schauen und zu versuchen, ein Muster in der Anordnung gerader Zahlen zu finden.

1.1, bf2,3.5, bf8,13.21, bf34,55.89, bf144, ldots


Gerade Zahlen sind in der Sequenz markiert, da Sie sehen können, dass jede 3. Fibonacci-Zahl gerade ist und wahrscheinlich alle geraden Zahlen in Vielfachen von 3 stehen. Dies wird unsere Vermutung sein, jetzt müssen wir sie bestätigen und einen Berechnungsalgorithmus ausarbeiten.

Der beste Beweis ist einfach, also danke an AllexIn für die einfache Idee, die ich anfangs vermisst habe. Jede nachfolgende Fibonacci-Zahl ist die Summe der beiden vorherigen. Wenn die beiden vorherigen Zahlen ungerade sind, ist die nächste gerade. Wenn in den beiden vorherigen Zahlen eine ungerade und die andere gerade ist, ist die nächste ungerade. Im Prinzip reicht diese Idee bereits aus, um die nachgewiesene Tatsache „intuitiv zu tappen“. Der Beweis durch Induktion ist offensichtlich, aber ich kann nicht widerstehen, um ihn nicht zu bringen

Wir beweisen, dass "jede dritte Fibonacci-Zahl gerade ist und die beiden vor jeder solchen Zahl ungerade sind".
  • Basisinduktion . Die ersten beiden Fibonacci-Zahlen 1.1 - ungerade, dritte Zahl 2 - sogar
  • Hypothese . Angenommen, bis zu einem Fibonacci-Vielfachen von 3 ist es wahr, dass jedes Drittel gerade ist und die beiden davor ungerade sind.
  • Induktionsschritt . Die Zahl nach der letzten geraden aus der Hypothese ist ungerade, weil es ergibt sich aus der Summe der ungeraden mit der geraden, nach dieser Zahl bereits ist auch ungerade, weil es ergibt sich aus der Summe der Geraden mit der Ungeraden und der nächsten nach der Geraden, weil Die beiden vorherigen, die gerade für ihn erhalten wurden, sind ungerade. Konstruktionsbedingt ist seine Zahl ein Vielfaches von 3, sie ist gerade und die beiden vorherigen sind ungerade.


Auf diese Weise können wir unsere Vermutung beweisen, ohne auf mathematische Berechnungen zurückgreifen zu müssen. Sie können diese Idee formalisieren und gleichzeitig eine Formel zur Berechnung jeder dritten Fibonacci-Zahl erhalten Fn+3 von Fn und Fn+1 . Verwenden der rekursiven Beziehung Fn+2=Fn+1+Fn wir bekommen:

Fn+3=Fn+2+Fn+1=2Fn+1+Fn


Also wenn Fn - Auch dann Fn+3 auch aufgrund dieser Formel. Angesichts dessen F3=2 dann ist jede dritte Fibonacci-Zahl wirklich gerade, was einen Teil unserer Vermutung bestätigt. Hier müssen Sie sicherstellen, dass wir keine anderen geraden Zahlen verpassen, d. H. dass sie alle ein Vielfaches von 3 haben. Danke an Janatem für seine einfache Idee, denn aus der obigen Formel für Fn+3 Daraus folgt auch, dass wenn Fn - Dann ungerade Fn+3 auch ungerade, also bekommen wir diese Zahlen mit Zahlen 3k−2,3k−1,k in mathbbN - ungerade (durch Induktion beginnen mit F1=F2=1 - ungerade) und 3k,k in mathbbN - gerade, die alle Fibonacci-Zahlen abdeckt, was bedeutet, dass wir wirklich alle geraden Zahlen abdecken.

Es gibt einen anderen Weg, da gezeigt werden könnte, dass es keine anderen geraden Zahlen gibt. Angenommen, es gibt eine Nummer Fm - gerade und 0 not equivm mod3 dann m=3k−1 oder m=3k+1 wo k - eine Art natürlich.

Wenden wir uns der Matrixdarstellung der Fibonacci-Zahlen aus dem ursprünglichen Beitrag zu

\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_n \\ F_n & F_ {n + 1} \ end {pmatrix}

\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_n \\ F_n & F_ {n + 1} \ end {pmatrix}


Wenn wir die Determinante beider Teile berechnen, erhalten wir

(−1)n=Fn+1Fn−1−F2n


Daraus folgt, dass die Teiler der Zahlen Fn+1,Fn und Fn−1,Fn Spielteiler (−1)n d.h. benachbarte Fibonacci-Zahlen sind gegenseitig einfach. Dies bedeutet auch, dass gegenseitige Einfachheit und Zahlen F3k,F3k−1 und F3k,F3k+1 d.h. F3k und Fm . Aber unter der Annahme Fm - sogar und F3k - auch wie bisher bewiesen. Also andere gerade Zahlen als F3k wo k in mathbbN in der Fibonacci-Sequenz existiert nicht. Und wir haben auch eine interessante Tatsache festgestellt, dass die benachbarten Fibonacci-Zahlen gegenseitig einfach sind.

Schließlich zeigen wir mindestens einen weiteren Weg, um unsere Vermutung zu beweisen: Verwenden Sie Lukes Satz.

Lukes Satz . Ganzzahl teilt Fm und Fn , wenn und nur wenn es ein Teiler ist Fd wo d= gcd(m,n) , insbesondere

 gcd(Fm,Fn)=F gcd(m,n)


Hier  gcd Ist der größte gemeinsame Faktor. Wenn gesetzt m=3 dann  gcd(2,Fn)=F gcd(3,n) . Wenn Fn - gerade dann ist die linke Seite 2, so dass die rechte Seite auch gleich 2 ist, ist es notwendig, dass n geteilt durch 3 und gleichzeitig ist das Gegenteil der Fall. So bekommen wir genau das, was wir beweisen wollten.

Jede dritte Fibonacci-Zahl ist also gerade und jede gerade hat ein Vielfaches von drei. Wir haben dies sorgfältig bewiesen und niemand wagt es, jetzt daran zu zweifeln.

Algorithmus


Und jetzt bleibt noch ein Algorithmus zu entwickeln. Sie können natürlich das tun, was Pavellyzhin ursprünglich getan hat, aber anstatt es zu überprüfen 0 equivFn mod2 wir können überprüfen 0 equivn mod3 , das ist eine Wendung! Dies hat zwar keinen Einfluss auf die Anzahl der Iterationen des Algorithmus, da wir gerade den Sequenzfilter geändert haben. Es ist besser, sofort eine Teilsequenz von Fibonacci-Zahlen mit der von uns benötigten Eigenschaft (Parität) zu generieren. Eine andere naheliegende Möglichkeit ist die Verwendung der Binet-Formel

F_n = \ left \ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \ right \ rceil, \ qquad n \ in \ {3,6, \ ldots, 3k \ ldots \}

F_n = \ left \ lfloor \ frac {\ varphi ^ n} {\ sqrt {5}} \ right \ rceil, \ qquad n \ in \ {3,6, \ ldots, 3k \ ldots \}


Es gibt Schwierigkeiten mit der Effizienz von Berechnungen, mehr dazu im ursprünglichen Beitrag. Daher schlage ich meiner Meinung nach die beste methodisch-iterative Berechnung vor Fn+3 Dies kann, wie wir zuvor gezeigt haben, durch die Formel erfolgen Fn+3=2Fn+1+Fn . Um einen iterativen Übergang im Algorithmus zu konstruieren, müssen wir berechnen Fn+4 Alles ist genauso einfach

Fn+4=Fn+3+Fn+2=2Fn+1+Fn+Fn+1+Fn=3Fn+1+2Fn


Übrigens ist es im Allgemeinen leicht zu beweisen

Fn+m=FmFn+1+Fm−1Fn


Dann wird der Algorithmus formal wie folgt geschrieben (die aktuelle gerade Fibonacci-Zahl Fn gefolgt von der Fibonacci-Nummer Fn+1 , M Ist die Obergrenze für Zahlen im Zustand des Problems angegeben):

  1. Fn leftarrowF3=2, quadFn+1 leftarrowF4=3
  2. Wenn Fn>M , dann beenden, andernfalls zum Ergebnis hinzufügen Fn
  3. (Fn,Fn+1) leftarrow(2Fn+1+Fn,3Fn+1+2Fn) Fahren Sie mit Schritt 2 fort.

Der Algorithmus ist ziemlich trivial - wir springen einfach auf jede dritte Fibonacci-Zahl und drucken sie aus (wenn es nicht mehr ist M ) Die Komplexität des Algorithmus ist immer noch linear, aber die Anzahl der Wiederholungen von Schritt 2 entspricht genau der Anzahl der geraden Fibonacci-Zahlen im Bereich 1 ldotsM Zum Vergleich: Ein einfacher Algorithmus mit Filterung erfordert dreimal mehr Iterationen (für jeden gefundenen werden 2 verworfen).

Der Algorithmus existiert auf Papier, was war das Interview, PHP? Nun, endlich PHP-Mittel aufdecken

function evenfibs($ubound) { $result = []; [$evenf, $nextf] = [2, 3]; while($evenf <= $ubound) { array_push($result, $evenf); [$nextf, $evenf] = [ 3 * $nextf + 2 * $evenf, 2 * $nextf + $evenf]; } return $result; }


Hinweis : Diese Methode kann jederzeit verbessert werden, wie beispielsweise die Benutzer- Hunroll gezeigt hat. Die Idee ist, dass wir für Berechnungen nichts Überflüssiges benötigen, außer dem teilweise erhaltenen Ergebnis, d.h. Wir können gerade Zahlen nur mit den vorherigen geraden Fibonacci-Zahlen berechnen.

Fn+3=2Fn+1+Fn=3Fn+2Fn−1=3Fn+Fn−1+Fn−1=3Fn+(Fn−1+Fn−2)+Fn−3=4Fn+Fn−3



 function evenfibs($ubound) { if($ubound < 2) return []; $evens = [2]; $next = 8; for($i = 1; $next <= $ubound; $i++) { $evens[$i] = $next; $next = $evens[$i]*4 + $evens[$i-1]; } return $evens; }


Verallgemeinerung


Wir haben hier Lukes Satz erwähnt, der das besagt  gcd(Fm,Fn)=F gcd(m,n) . Infolgedessen können wir die Fibonacci-Zahl erhalten Fn Vielfaches von Fm , genau dann, wenn seine Nummer n mehrfach zu nummerieren m . Das heißt, Jede 4. Fibonacci-Zahl wird durch 3 geteilt, jede 5. durch 5, jede 6. durch 8 usw.

Dann erhalten wir auf einfache Weise einen Algorithmus zur Berechnung der Fibonacci-Teilsequenz, bei dem die Elemente Vielfache einer bestimmten Zahl sind Fm . Mit der Tatsache, dass

Fn+m=FmFn+1+Fm−1FnFn+m+1=Fm+1Fn+1+FmFn


Der vorherige Algorithmus wird zu

  1. Fn linkerPfeilFm, quadFn+1 linkerPfeilFm+1
  2. Wenn Fn>M , dann beenden, andernfalls zum Ergebnis hinzufügen Fn
  3. (Fn,Fn+1) linkerPfeil(FmFn+1+Fm−1Fn,Fm+1Fn+1+FmFn) Fahren Sie mit Schritt 2 fort.

Wo Fm−1,Fm,Fm+1 kann als Konstanten gesetzt werden.

Zusammenfassung der Notizen . Wie die Unwissenheit des Benutzers zu Recht bemerkt hat, ist es im verallgemeinerten Fall auch möglich, einen Algorithmus zu konstruieren, der nur Zahlen aus einem Teilergebnis verwendet.

Fn+1=Fn+Fn−1Fn+2=3Fn−Fn−2Fn+3=4Fn+Fn−3Fn+4=7Fn−Fn−4Fn+5=11Fn+Fn−5 cdotsFn+t=(Ft+2Ft−1)Fn+(−1)t−1Fnt



Beweisen wir dies durch die Methode der mathematischen Induktion, für t = 1 und t = 2 ist die Erfüllung offensichtlich. Angenommen, es hält bis zu einem gewissen Grad

Fn+t+1=Fn+t+Fn+t−1=(Ft+2Ft−1)Fn+(−1)t−1Fnt+(Ft−1+2Ft−2)Fn+(−1)t−2Fn−t+1=(Ft+Ft−1+2(Ft−1+Ft−2))Fn+(−1)t−1(Fnt−Fn−t+1)=(Ft+1+2Ft)Fn+(−1)t−1(Fnt−Fnt−Fnt−1)=(Ft+1+2Ft)Fn+(−1)tFnt−1



So etwas wie eine Summe


Die Aufgabe ist natürlich komplett synthetisch, die Anzahl der Iterationen ist sehr gering (z M=$10.00 die Antwort enthält nur 6 Zahlen, d.h. 6 Iterationen wären abgeschlossen worden, und der ursprüngliche "frontale" Algorithmus hätte 18) erforderlich gemacht, aber auf diese Weise kann ein Benutzer, der hier etwas Neues entdeckt hat, jetzt im Interview ein wenig tieferes mathematisches Wissen in Fibonacci-Zahlen zeigen.

Bearbeiten: Dank der Benutzer von janatem und AllexIn für die einfachen Beweise habe ich sie in „Theoremizing“ aufgenommen und den Algorithmus nur mit den geraden Zahlen verwendet, die bereits in den Berechnungen erhalten wurden, und der Unwissenheit des Benutzers, ihn zu verallgemeinern.

Source: https://habr.com/ru/post/de450594/

More articles:


All Articles