package by.it.group351004.naryvonchyk.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 == 1) || (n == 0))
            return n;
        else
            return calc(n - 1) + calc(n - 2);
    }


    BigInteger slowA(Integer n) {
        if (n == 1 || n == 0) {
            return BigInteger.valueOf(n);
        } else {
            return slowA(n - 1).add(slowA(n - 2));
        }
    }
}



















package by.it.group351004.naryvonchyk.lesson01;

import javax.swing.plaf.basic.BasicIconFactory;
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[] arr = new BigInteger[n+1];
        arr[0] = BigInteger.ZERO;
        arr[1] = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            arr[i] = arr[i-1].add(arr[i-2]);
        }
        return arr[n];
    }

}


























package by.it.group351004.naryvonchyk.lesson01;

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

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 = 10;
        int m = 2;
        System.out.printf("fasterC(%d)=%d \n\t time=%d \n\n", n, fibo.fasterC(n, m), fibo.time());
    }

    int findPeriod(int m) {
        int period = 0;
        int prev = 0;
        int curr = 1;
        int next;

        for (int i = 0; i <= m * 6; i++) {
            next = (prev + curr) % m;
            prev = curr;
            curr = next;
            if (prev == 0 && curr == 1)
                period = i + 1;
        }
        return period;
    }
    long fasterC(long n, int m)
    {

        int period = findPeriod(m);
        long res = n % period;
        int prev = 0;
        int curr = 1;
        int next;
        if (n == 0) return 0;
        if (n == 1) return 1;
        else
            for (int i = 0; i < res - 1; i++ ) {
                next = (prev + curr) % m;
                prev = curr;
                curr = next;
            }
        return curr % m;
    }


}