Aufgabensammlung Programmierung/ Zeckendorf-Sequenz/ Lösung (Haskell)

Diese Lösung löst die Programmieraufgabe Zeckendorf-Sequenz mit Mitteln der funktionalen Programmierung. Als Zusatz ist eine Funktion deklariert, die aus einer Zeckendorfsequenz die zugehörige Zahl bestimmt. Ich versuche bei der Lösung möglichst grundlegende Konzepte zu verwenden.

Hilfsbibliotheken

Um die Aufgabe zu lösen, benötigt man die Fibonacci-Zahlen. Dazu schreibt man folgendes in eine Datei Fibonacci.hs:

-- Datei Fibonacci.hs
module Fibonacci where

-- Funktion zur Berechnung der Fibonacci-Zahlen. Diese ist auf leichte Verständlichkeit ausgelegt
fib :: Int -> Integer -- Kann weggelassen werden
fib n = fib' 0 1 n where
        fib' a _ 0 = a
        fib' a b n = fib' b (a+b) (n-1)

{-- alternativ (schneller, aber schlechter Verständlich), bei bedarf auskommentieren.

fibs :: [Integer]
fibs@(_:rest) = 0:1:[ a+b | (a,b) <- zip fibs rest]

fib :: Int -> Integer
fib = (!!) fib

--}

Lösungsweg

Die Lösung besteht aus folgenden Schritten:

Berechnung der nächstgrößeren oder gleichen Fibonaccizahl

Berechne solange rekursiv die nächstgrößere Fibonaccizahl, bis diese nicht mehr kleiner als die Zahl ist. Liefere diese Zahl zurück.

Rekursive Berechnung der Lösung

Startwert n: oben berechneter Fibonacci - 1. Liste zu Anfang: []

gucke, ob n kleiner der Zahl ist.
- Ja: subtrahiere n von der Zahl, füge ein True an den Anfang der Liste an.
- Nein: füge ein False an den Anfang der Liste an.
setzte n auf die nächstkleinere Fibonaccizahl und führe die Funktion rekursiv mit der schon existierenden Liste aus.
Wenn die Zahl n = 1, terminiere.

Quelltext

Speichere folgendes in einer Datei Zeckendorf.hs im selben Verzeichnis wie die Datei Fibonacci.hs:

-- Datei Zeckendorf.hs

module Zeckendorf where

import Fibonacci

--Erläuterungen, siehe oben / unten
zeck :: Int -> [Bool]
zeck n = zeck' n ((nextFib n) - 1) where
  nextFib 0 = -1
  nextFib n = nextFib' 0 n
  nextFib' n k = if zfib n >= k 
    then n 
    else nextFib' (n+1) k
  zeck' _ (-1) = []
  zeck' n k = if n < zfib k
    then (zeck' n (k-1)) ++ [False]
    else (zeck' (n - zfib k) (k-1)) ++ [True]

-- Hilfsfunktion: zfib ist wie fib, nur dass die ersten beiden Einträge (die nicht gebraucht werden) fehlen
zfib :: Int -> Integer
zfib n = fib (n - 2)

Erläuterungen

Der Code spiegelt den oben beschriebenen Lösungsweg bis auf ein paar Kleinigkeiten (aus Gründen der Einfachheit) wieder. Erstmal wird eine Hilfsfunktion zfib definiert die eigentlich nichts weiter macht, als die Fibonaccifolge ohne die ersten beiden Elemente zu definieren. Somit ist es wesentlich einfacher möglich, die Aufgabe zu lösen, weil der Index gleich der Position in der Liste ist.

Als erstes wird die Funktion nextFib definiert, sie berechnet die nächstkleinere Fibonaccizahl. Dazu prüft sie, ob die Bedingung für die aktuelle Fibonaccizahl erfüllt ist. Falls dies nicht zutrifft, wird die Prüfung mit der nächstgrößeren Fibonaccizahl durchgeführt.

Das Ergebnis dieser Funktion wird als zweites Argument in die Funktion zfib' übergeben. Diese Funktion löst rekursiv die eigentliche Aufgabe:

Die zwei Parameter der Funktion sind die zu zerlegende Zahl und die aktuelle Fibonaccizahl. Die Funktion prüft, ob die aktuelle Fibonaccizahl Teil der Zeckendorf-Zerlegung ist und hängt das Ergebnis vorne an einen rekursiven Aufruf an. Der rekursive Aufruf erfolgt mit der nächstkleineren Fibonaccizahl und - falls die Fibonaccizahl kleiner war als die Zahl - die Fibonaccizahl von der Eingabezahl abgezogen. Abbruchbedingung ist, wenn die Fibonaccizahl 1 erreicht wird. Dann liefert die nächste Rekursionsebene eine leere Liste zurück.

Erweiterungsmöglichkeiten

Die folgende Funktion kann in die Datei Zeckendorf.hs eingearbeitet werden und bietet die Möglichkeit, aus der Zeckendorf-Zerlegung wieder eine Zahl zurückzuliefern. Sie kann als Verifikation der Zerlegungsfunktion benutzt werden.

-- Datei Zeckendorf.hs

unzeck :: [Bool] -> Integer
unzeck n = sum [if a then zfib b else 0 | (a,b) <- zip n [0..(length n) - 1]]