Aufgabensammlung Programmierung/ Fibonacci-Zahlen/ Lösung (Haskell)

module Fibonacci where

--------------------------------------------------------------------------------
-- Aufgabe 1: Berechnung von Fibonacci-Zahlen ----------------------------------
--------------------------------------------------------------------------------

-- Möglichkeit 1:
--- rekursive Berechnung der Fibonacci—Zahlen über geralisierte Formel

--- gen -> generisch 

genFib1 :: Num a => a -> a -> Int -> a

genFib1 a _ 0 = a
genFib1 a b c = genFib1 b (a+b) (c-1)

fib1 :: Int -> Integer

fib1 n = genFib1 0 1 n

--- alternative Darstellung

fib2 n = fib2' 0 1 n where
  fib2' a _ 0 = a
  fib2' a b c = fib2' b (a+b) (c-1)

-- Möglichkeit 2:
--- als Element einer Liste, siehe unten

fib3 :: Int -> Integer
fib3 n = fibs2 !! n

--------------------------------------------------------------------------------
-- Aufgabe 2: Liste von Fibonacci-Zahlen berechnen -----------------------------
--------------------------------------------------------------------------------

-- Möglichkeit 1: einfach zusammenfügen

fibs1 :: Int -> [Integer]

fibs1 n = fibs1' n [] where
	fibs1' (-1) k = k
	fibs1' n k = fibs1' (n - 1) (fib1 n : k)

-- Möglichkeit 2: Fixpunktgleichung (fortgeschritten)
--- Funktioniert aufgrund Haskell's lazy evaluation
--- Liste unendlich lang
--- am besten

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

--- daraus endliche Liste

fibs3 :: Int -> [Integer]
fibs3 n = take (n+1) fibs2

-- Möglichkeit 3: Wie 1, nur besser
--- (Besseres Laufzeitverhalten)

fibs4 :: Int -> [Integer]
fibs4 n = fibs4' n 0 1 [] where
  fibs4' (-1) _ _ k = k
  fibs4' n a b k = fibs4' (n - 1) b (a + b) (k ++ [a])

--------------------------------------------------------------------------------
-- Aufgabe 3: Berechnung des goldenen Schnittes --------------------------------
--------------------------------------------------------------------------------

-- Variante 1: Auf Basis des Indexes
--- Division durch 0 wird nicht abgefangen

goldenerSchnitt1 :: (Fractional t) => Int -> t
goldenerSchnitt1 n = fromInteger (fib3 (n+1)) / fromInteger(fib3 n)

-- Variante 2: Auf Basis der Genauigkeit
--- Benutzt Variante 1

goldenerSchnitt2 :: (Fractional t, Ord t) => t -> t
goldenerSchnitt2 n = gS2' 1 where
  gS2' k = if abs (goldenerSchnitt1 k - goldenerSchnitt1 (k+1)) > n
    then gS2' (k+1)
    else goldenerSchnitt1 k