package by.it.a_khmelev.lesson01;

import java.math.BigInteger;

/*
 * Вам необходимо выполнить рекурсивный способ вычисления чисел Фибоначчи
 */

public class FiboA {


    private long startTime = System.currentTimeMillis();

    public static void main(String[] args) {
        FiboA fibo = new FiboA();
        int n = 33;
        System.out.printf("calc(%d)=%d \n\t time=%d \n\n", n, fibo.calc(n), fibo.time());

        //вычисление чисел фибоначчи медленным методом (рекурсией)
        fibo = new FiboA();
        n = 34;
        System.out.printf("slowA(%d)=%d \n\t time=%d \n\n", n, fibo.slowA(n), fibo.time());
    }

    private long time() {
        long res = System.currentTimeMillis() - startTime;
        startTime = System.currentTimeMillis();
        return res;
    }

    private int calc(int n) {
        if (n < 2) return n;
        return calc (n - 1) + calc(n - 2);
    }


    BigInteger slowA(Integer n) {
        if (n == 0) return BigInteger.ZERO;
        if (n == 1) return BigInteger.ONE;
        return slowA (n - 1).add(slowA (n - 2));
    }


}













package by.it.a_khmelev.lesson01;

import java.math.BigInteger;

/*
 * Вам необходимо выполнить способ вычисления чисел Фибоначчи с вспомогательным массивом
 * без ограничений на размер результата (BigInteger)
 */

public class FiboB {

    private long startTime = System.currentTimeMillis();

    private long time() {
        return System.currentTimeMillis() - startTime;
    }

    public static void main(String[] args) {

        //вычисление чисел простым быстрым методом
        FiboB fibo = new FiboB();
        int n = 55555;
        System.out.printf("fastB(%d)=%d \n\t time=%d \n\n", n, fibo.fastB(n), fibo.time());
    }

    BigInteger fastB(Integer n) {
        BigInteger result = BigInteger.ZERO;
        BigInteger prev = BigInteger.ONE;
        BigInteger prevprev = BigInteger.ZERO;
        int i = 2;
        while (i <= n) {
            result = prev.add(prevprev);
            prevprev = prev;
            prev = result;
            i++;
        }
        return result;
    }
}














package by.it.a_khmelev.lesson01;

/*
 * Даны целые числа 1<=n<=1E18 и 2<=m<=1E5,
 * необходимо найти остаток от деления n-го числа Фибоначчи на m.
 * время расчета должно быть не более 2 секунд
 */

import java.math.BigInteger;

public class FiboC {

    private long startTime = System.currentTimeMillis();

    private long time() {
        return System.currentTimeMillis() - startTime;
    }

    public static void main(String[] args) {
        FiboC fibo = new FiboC();
        int n = 18;
        int m = 4;
        System.out.printf("fasterC(%d)=%d \n\t time=%d \n\n", n, fibo.fasterC(n, m), fibo.time());
    }

    long fasterC(long n, int m) {
        //Решение сложно найти интуитивно
        //возможно потребуется дополнительный поиск информации
        //см. период Пизано
        //int period = m * 6; // каждые m * 6 раз или меньше остатки m чисел будут повторяться
        BigInteger numberFib;
        BigInteger prev = BigInteger.ONE;
        BigInteger prevprev = BigInteger.ZERO;
        BigInteger bigPeriod = BigInteger.valueOf(m); // m в BigInteger
        long worsePeriod = n %  (m * 6L);
        int [] arrOfReminder = new int[(int) worsePeriod + 1];
        int i = 2;
        arrOfReminder[0] = 0;
        arrOfReminder[1] = 1;
        while (i <= worsePeriod) {
            numberFib = prev.add(prevprev);
            prevprev = prev;
            prev = numberFib;
            arrOfReminder[i] = (numberFib.mod(bigPeriod)).intValue(); // массив остатков
            i++;
        }
        int[] finalArray = new int[(int) worsePeriod + 1];
        i = 0;
        for (int j = 1; j < arrOfReminder.length - 2; j++) {
            if (arrOfReminder[0] == arrOfReminder[j]) {
                if (arrOfReminder[1] == arrOfReminder[j + 1]) {
                    if (arrOfReminder[2] == arrOfReminder[j + 2]) {
                        while (i != j) {
                            finalArray[i] = arrOfReminder[i];
                            i++;
                        }
                        break;
                    }
                }
            }
        }
        int reminder = 0;

        if (n == 1)
            return 1;
        if (n ==2)
            return 2;
        if (n < m)
            reminder = (int)n;
        else
            reminder = (int) n % i; // оно должно работать всегда, когда i != 0
        return finalArray[reminder];
    }


}