/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 13, Dynamisches Programmieren
 *
 * @author A. Gogol-Döring, Th. Letschert
 */


import Foundation

struct AuD_13_09_Fibonacci {

    static func fibR(_ n: Int) -> UInt64 {
        (n <= 1) ?  UInt64(n) : fibR(n-1) + fibR(n-2)
    }

    static func fibTab(_ n: Int) -> UInt64 {
        if n <= 1 {
            return UInt64(n)
        }
        var Fib: [UInt64] = [UInt64](repeating: 0, count: n+1)
        Fib[0] = 0
        Fib[1] = 1
        for i in 2 ... n {
            Fib[i] = Fib[i - 1] + Fib[i - 2]
        }
        return Fib[n]
    }

    static func fib(_ n: UInt) -> UInt64 {
        if n <= 1 {
            return UInt64(n)
        }
        var f1: UInt64 = 0
        var f2: UInt64 = 1
        for _ in 2 ... n {
            let f = f1 + f2
            f1 = f2
            f2 = f
        }
        return f2
    }

    static func run() {
        print(fibR(40)) // 102334155
        print(fibTab(50)) // 12586269025
        print(fib(60)) // 1548008755920
    }

}