third.py

import math
from operator import mul
from decimal import getcontext, Decimal

getcontext().prec = 100

varianta = 9
accuracy = Decimal(0.00000001)
interval = xrange(1, 6)


def calc_step(value):
    sign = calc_step.sign
    degree = calc_step.degree

    calc_step.sign *= -1
    calc_step.degree += 2
    
    return sign * Decimal((varianta * value) ** degree) / Decimal(math.factorial(degree)) if degree > 0 else 1


def get_row_summary(point):
    calc_step.sign = 1
    calc_step.degree = 0
    
    functional_row = []

    while True:
        functional_row.append(calc_step(point))
        if abs(functional_row[-1]) < accuracy:
            break

    return sum(functional_row)


def get_dense_row():
    x   = [x for x in interval]
    y = [get_row_summary(Decimal(y)) for y in x]

    new_x = [x[0]]
    for index in xrange(1, len(x)):
        new_x += [Decimal(x[index] + x[index - 1]) / 2] + [x[index]]

    new_y = [y[0]]
    for index in xrange(1, len(y)):
        new_y += [Decimal(y[index] + y[index - 1]) / 2] + [y[index]]

    return get_result(new_x, new_y)


def calculate_lagrange(point, x, y):
    result = 0
    for k in xrange(len(x)):        
        resultStep = 1
        
        for i in xrange(len(x)):
            if k != i:
                resultStep *= Decimal(point - x[i]) / Decimal(x[k] - x[i])         
        result += resultStep * Decimal(y[k])
    
    return result;


def calc_interpolant_in_form_Lagrange(X):
    x   = [x for x in X]
    y   = [Decimal(y) ** (len(interval) - 1) for y in x]

    new_x = [Decimal(x[0])]
    for index in xrange(1, len(x)):
        new_x += [Decimal(x[index] + x[index - 1]) / 2] + [Decimal(x[index])]

    new_y = [Decimal(y[0])]
    for index in xrange(1, len(y)):
        new_y += [calculate_lagrange((Decimal(x[index] + x[index - 1]) / 2), x, y)] + [Decimal(y[index])]

    new_z = [x ** (len(interval) - 1) for x in new_x]

    return get_result(new_x, new_y, new_z)



def get_result_callback(x, callback):
    return [str(Decimal(point)) + ':\t {0:.20f}'.format(callback(Decimal(point))) for point in x]

    
def get_result(x, y):
    return [str(Decimal(x[index])) + ':\t {0:.20f}'.format(y[index]) for index in xrange(len(x))]       


def get_result(x, y, z):
    return [str(Decimal(x[index])) + ':\t {0:.15f} = {0:.15f}'.format(y[index], z[index]) for index in xrange(len(x))]



def main():
    try:        
        #first task
        #for answer in get_result_callback(interval, get_row_summary):
        #    print answer

        #print ''

        #second task
        #for answer in get_dense_row():
        #    print answer

        #print ''

        #third task
        
        for answer in calc_interpolant_in_form_Lagrange(interval):
            print answer
        
        print ''
    except Exception, e:
        print e
        exit = raw_input()

    exit = raw_input()


if __name__ == '__main__':
    main()