Aufgabensammlung Programmierung/ Zeckendorf-Sequenz
In dieser Aufgabe soll eine Funktion entworfen werden, die zu einer natürlichen Zahl die zugehörige Zeckendorf-Sequenz berechnet.
Kurzinformation
[Bearbeiten]- Schwierigkeit
- 5 - Schwere Aufgabe
- nötige Zeit
- n/a - bitte ausprobieren und Erfahrungen hier posten
- Vorgeschlagenes Programmierparadigma
- Gleichermaßen mit jedem Paradigma lösbar.
- nötige Vorkenntnisse
-
- Fibonacci-Folge
- nützlich: Rekursion
Aufgabestellung
[Bearbeiten]Der Satz von Zeckendorf (nach Edouard Zeckendorf) besagt, dass jede natürliche Zahl n größer Null eindeutig als Summe voneinander verschiedener, nicht direkt aufeinanderfolgender Fibonacci-Zahlen geschrieben werden kann. Das heißt, es gibt für jedes eine eindeutige Darstellung der Form
Die entstehende Folge von Nullen und Einsen wird Zeckendorf-Sequenz genannt. Da aufeinanderfolgende Fibonacci-Zahlen ausgeschlossen sind, können keine zwei Einsen in einer Zeckendorf-Sequenz unmittelbar hintereinander stehen.[1]
Das Ziel dieser Aufgabe ist es, eine Funktion zu schreiben, die zu einer natürlichen Zahl die Zeckendorf-Sequenz berechnet. Als Repräsentation soll eine Liste oder ein Array von Wahrheitswerten (boolean) verwendet werden. Das erste Element der Liste repräsentiert dabei die Fibonacci-Zahl eins, das zweite die zwei, das dritte die drei, das vierte die fünf usw.
Beispielausgabe
[Bearbeiten](Die Ausgabe ist in Pseudocode verfasst)
- Zeckendorfsequenz(0)
- {}
- Zeckendorfsequenz(1)
- {True}
- Zeckendorfsequenz(2)
- {False, True}
- Zeckendorfsequenz(4)
- {True, False, True}
- Zeckendorfsequenz(10)
- {False, True, False, False, True, False}
Lösung
[Bearbeiten]Lösungen sind in folgenden Sprachen verfügbar:
Weitere Aufgaben dazu
[Bearbeiten]Zur weiteren Vertiefung, oder als Ergänzung könnten man sich mit folgenden Themen beschäftigen:
- Entwerfe eine Funktion, die aus der Zeckendorfsequenz die ursprüngliche Zahl zurückrechnet
- Versuche den Algorithmus hinsichtlich Geschwindigkeit und Speicherverbrauch zu optimieren
Quellen
[Bearbeiten]- ↑ Fibonacci-Folge aus Wikipedia