Vielen Dank an die freundlichen Teilnehmer von Habr, die eingeladen wurden, Beiträge zu schreiben und Feedback dazu zu erhalten.
Heute möchte ich das Thema der Darstellung von Zahlen mit der Fibonacci-Reihe hervorheben und natürlich eine einfache REST-API mit dem Mongo DB- Algorithmus unter Verwendung der Ruby- Sprache schreiben , die ihre Darstellung für eine bestimmte Zahl N zurückgibt.
Teil 1: Die Zeckendorff-Darstellung
Wie der Wikipedia- Artikel sagt :
Der Satz von Zeckendorff besagt, dass jede natürliche Zahl eindeutig als die Summe einer oder mehrerer verschiedener Fibonacci-Zahlen dargestellt werden kann, so dass diese Darstellung keine zwei benachbarten Zahlen aus der Fibonacci-Sequenz enthält.
100 = 89 + 8 + 3.
Ich denke, wenn man versteht, was Fibonacci-Zahlen sind, wird es nicht schwierig sein zu verstehen, worum es in diesem Theorem geht.
Zu erreichende Ziele:
Arbeitsgeschwindigkeit
maximale Code-Einfachheit
Als Programmiersprache werde ich Ruby verwenden , warum? Weil Ruby es ist
Der beste Freund des Programmierers.
Zunächst müssen Sie theoretisch ein Muster finden, nach dem der Algorithmus geschrieben wird.
, (), , , .
:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
34, (21) , N, , :-).
, : .
- : .
: N , , <= 0.
:
N = 51
F = 1 , 1 , 2 , 3 , 5 , 8 , 13, 21, 34.
ans = [34]
N = 51 - 34 = 17
F = 1 , 1 , 2 , 3 , 5 , 8 , 13.
ans = [34 , 13]
N = 17 - 13 = 4
F = 1 , 1 , 2 , 3.
ans = [34 , 13 , 3]
N = 4 - 3 = 1
F = 1
ans = [34 , 13 , 3, 1]
:
def le_fib(limit, fib)
theoretical = fib[fib.count - 1] + fib[fib.count - 2]
return fib.last if theoretical > limit
fib << theoretical
le_fib(limit, fib)
end
def main(target,result)
temporary = le_fib(target, [1,1])
result << temporary
return result if target - temporary <= 0
main(target - temporary, result)
end
pp main(gets.to_i,[])
le_fib - , , target. , , .
main - c, , .
, , , , , .
20 1000
( )
Wie Sie sehen, ist die Betriebszeit auch bei Zahlen bis 10 ^ 9 sehr positiv.
Die Gesamtmenge an Code in 17 Zeilen zeigt an, dass beide Aufgaben erfolgreich abgeschlossen wurden.
Ein Artikel über Interesse, Sie müssen immer ein paar Probleme mit Fibonache-Nummern im Ärmel haben, sonst was für ein Programmierer sind Sie :-)