import numpy as np
import matplotlib.pyplot as plt

# Für gegenebe Stützstellen xs und Auswertungen fs einer unbekannten Funktion
# gibt die Newtonschen dividierten Differenzen zurürck.
#
# Wären die Stützstellen und Auswertungen durch nummeriert
#   xs = [x_0, x_1, ..., x_n]
#   fs = [f[x_0], f[x_1], ..., f[x_n]]
# so entspricht die Ausgabe den dividierten Differenzen:
#   divDiff(xs, fs) = [f[x_0], f[x_0, x_1],..., f[x_0, x_1,...,x_n]]
# die für die Evaluierung des Interpolationspolynoms nötig sind. Beispielsweise
# wäre:
#   divDiff([3, 1, 5], [1, -3, 2]) # => [1, 2, -3/8]
def divDiff(xs, fs):
    # YOUR IMPLEMENTATION HERE
    return np.zeros_like(xs)

# Gibt eine Funktion zurück, die mittels Horner-Schema das Interpolationspolynom
# zu den gegebenen Daten (xs, fs) auswertet. Zu verwenden als:
#   xs = [-1, 1, 0, -2]
#   fs = [2, 4, 5, -5]
#   pf = interpolPoly(xs, fs)
#
#   pf(-3) # => -16.0
# (N.B. Aufgrund numerischer Fehler mag, bei Ihnen, das Ergebnis nicht exakt
# -16.0 sein.)
def interpolPoly(xs, fs):
    coeff = divDiff(xs, fs)
    def eval(x):
        res = coeff[len(coeff) - 1]
        for i in range(len(coeff) - 2, -1, -1):
            res = res * (x - xs[i]) + coeff[i]
        return res

    return eval

# Vergessen Sie nicht die auf dem Blatt beschriebenen Funktionen mit zugehörigen
# Interpolationspolynomen zu plotten.
if __name__ == "__main__":
    xs = np.linspace(-5, 5)
    plt.plot(xs, np.sin(xs))
    plt.show()