import java.text.DecimalFormat;
import java.util.Scanner;

/**
 * Задача 2. Алгебраическая интерполяция в форме Ньютона.
 */
public class SolutionTwo {

    private Scanner in = new Scanner(System.in);
    private int valuesNumber = 0;
    private double leftBound = 0;
    private double rightBound = 0;
    private double[] points;

    /**
     * Функция, которую нужно интерполировать.
     * @param x Аргумент функции.
     * @return e^x + sin x + 1
     */
    private static double goalFunction(double x) {
        return Math.exp(x) + Math.sin(x) + 1;
    }

    private void interpolate() {
        valuesNumber = getInteger(1, "количество значений в таблице");
        points = new double[valuesNumber];
        getBounds();
        int nodesNumber = getInteger(1, "количество узлов");

        if (nodesNumber > valuesNumber) {
            System.out.println("Узлов не может быть больше, чем значений в таблице.");
            return;
        }

        System.out.println("Введите x:");
        double x = in.nextDouble();

        for (int i = 0; i < valuesNumber; i++) {
            points[i] -= x;
        }

        for (int i = valuesNumber - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (Math.abs(points[j+1]) < Math.abs(points[j])) {
                    double temp = points[j];
                    points[j] = points[j+1];
                    points[j+1] = temp;
                }
            }
        }

        for (int i = 0; i < valuesNumber; i++) {
            points[i] += x;
        }

        double[][] table = new double[nodesNumber + 1][];

        for (int i = 0; i < nodesNumber + 1; i++) {
            table[i] = new double[nodesNumber + 2];
        }

        for (int i=0; i < nodesNumber + 1; i++) {
            table[i][0] = points[i];
            table[i][1] = goalFunction(points[i]);
        }

        for (int j = 2; j < nodesNumber + 2; j++) {
            for (int i = 0; i < nodesNumber + 2 - j; i++) {
                table[i][j] = (table[i + 1][j - 1] - table[i][j - 1]) / (table[i + j - 1][0] - table[i][0]);
            }
        }

        DecimalFormat format = new DecimalFormat("###.####");

        System.out.println("Таблица разделённых разностей:");
        for (int i = 0; i < nodesNumber + 1; i++) {
            for (int j = 0; j < nodesNumber + 2 - i ; j++) {
                System.out.print(format.format(table[i][j]) + " ");
            }
            System.out.println();
        }

        double result = 0;
        double temp = 1;

        for (int i = 1; i < nodesNumber + 2; i++) {
            if (i != 1) {
                temp *= (x - table[i - 2][0]);
            }
            result += (table[0][i] * temp);
        }

        System.out.println("Полученное значение: " + format.format(result));
        System.out.println("Точное значение: " + format.format(goalFunction(x)));
        System.out.println("Невязка: " + format.format(Math.abs(goalFunction(x) - result)));

        in.nextLine();
    }

    private int getInteger(int min, String description) {
        int result = min;
        System.out.println("Введите " + description + ":");

        while (result <= min) {
            try {
                result = in.nextInt();

                if (result <= min) {
                    System.out.println("Необходимо число, большее "+ min + ". Введите снова:");
                }
            } catch (Exception e) {
                System.out.println("Неверный формат! Введите снова:");
            }
        }

        return result;
    }

    /**
     * Запрашивает у пользователя границы отрезка и вычисляет узлы интерполяции.
     */
    private void getBounds() {
        System.out.println("Введите границы отрезка:");

        while (rightBound <= leftBound) {
            try {
                leftBound = in.nextDouble();
                rightBound = in.nextDouble();

                if (rightBound <= leftBound) {
                    System.out.println("Необходимо два числа, второе из которых больше. Введите снова:");
                }

            } catch (Exception e) {
                System.out.println("Неверный формат! Введите снова:");
            }
        }

        for (int i = 0; i < valuesNumber; i++) {
            points[i] = leftBound + i * (rightBound - leftBound) / (valuesNumber - 1);
        }
    }

    /**
     * Запрашивает узлы интерполяции, затем вычисляет разделённые разности, выводит в консоль
     * интерполяционный многочлен в форме Ньютона, вычисляет его значения в указанных
     * пользователем точках и абсолютные погрешности в них.
     * @param args Не используется, параметры вводятся уже после запуска.
     */
    public static void main(String[] args) {
        new SolutionTwo().interpolate();
    }
}