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

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

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 $n\in \mathbb{N},n>0$ eine eindeutige Darstellung der Form

$n=\sum _{i=2}^k{c}_i{f}_i{c}_i\in \{0,1\};\mathrm{\forall }i:c_i{c}_{i+1}=0$

Die entstehende Folge $(c)$ 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.

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

(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

Lösungen sind in folgenden Sprachen verfügbar:

• Haskell
• Java

Weitere Aufgaben dazu

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