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

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ö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
  1. Fibonacci-Folge aus Wikipedia