Рубрики

Java-программа для n-го числа Фибоначчи

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

    Fn = Fn-1 + Fn-2

с начальными значениями

   F0 = 0 and F1 = 1.

Метод 1 (Использовать рекурсию)

// Ряд Фибоначчи с использованием рекурсии

class Fibonacci {

    static int fib(int n)

    {

        if (n <= 1)

            return n;

        return fib(n - 1) + fib(n - 2);

    }

  

    public static void main(String args[])

    {

        int n = 9;

        System.out.println(fib(n));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Выход:

34

Способ 2 (использовать динамическое программирование)

// Ряд Фибоначчи с использованием динамического программирования

  

class Fibonacci {

    static int fib(int n)

    {

        / * Объявить массив для хранения чисел Фибоначчи. * /

        int f[] = new int[n + 1];

        int i;

  

        / * 0-й и 1-й номер серии - 0 и 1 * /

        f[0] = 0;

  

        if (n > 0) {

            f[1] = 1;

  

            for (i = 2; i <= n; i++) {

                / * Добавить 2 предыдущих номера в серии

             и сохранить его * /

                f[i] = f[i - 1] + f[i - 2];

            }

        }

  

        return f[n];

    }

  

    public static void main(String args[])

    {

        int n = 9;

        System.out.println(fib(n));

    }

}
/ * Этот код предоставлен Раджатом Мишрой
и улучшено MichaelJoshuaRamos * /

Выход:

34

Метод 3 (Использование динамического программирования с оптимизацией пространства)

// Java-программа для ряда Фибоначчи, использующая Space
// Оптимизированный метод

class Fibonacci {

    static int fib(int n)

    {

        int a = 0, b = 1, c;

        if (n == 0)

            return a;

        for (int i = 2; i <= n; i++) {

            c = a + b;

            a = b;

            b = c;

        }

        return b;

    }

  

    public static void main(String args[])

    {

        int n = 9;

        System.out.println(fib(n));

    }

}

  
// Этот код предоставлен Михиром Джоши

Выход:

34

Метод 4 (Разделяй и властвуй)

class Fibonacci {

    static int fib(int n)

    {

        int F[][] = new int[][] { { 1, 1 }, { 1, 0 } };

        if (n == 0)

            return 0;

        power(F, n - 1);

  

        return F[0][0];

    }

  

    / * Вспомогательная функция, которая умножает 2 матрицы F и M размера 2 * 2, и

     возвращает результат умножения в F [] [] * /

    static void multiply(int F[][], int M[][])

    {

        int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];

        int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];

        int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];

        int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

  

        F[0][0] = x;

        F[0][1] = y;

        F[1][0] = z;

        F[1][1] = w;

    }

  

    / * Вспомогательная функция, которая вычисляет повышение F [] [] до степени n и помещает

    результат в F [] []

    Обратите внимание, что эта функция предназначена только для fib () и не будет работать в целом

    Степенная функция * /

    static void power(int F[][], int n)

    {

        int i;

        int M[][] = new int[][] { { 1, 1 }, { 1, 0 } };

  

        // n - 1 раз умножить матрицу на {{1, 0}, {0, 1}}

        for (i = 2; i <= n; i++)

            multiply(F, M);

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String args[])

    {

        int n = 9;

        System.out.println(fib(n));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Выход:

34

Метод 5 (Разделяй и властвуй)

// Ряд Фибоначчи с использованием оптимизированного метода

class Fibonacci {

    / * функция, которая возвращает n-е число Фибоначчи * /

    static int fib(int n)

    {

        int F[][] = new int[][] { { 1, 1 }, { 1, 0 } };

        if (n == 0)

            return 0;

        power(F, n - 1);

  

        return F[0][0];

    }

  

    static void multiply(int F[][], int M[][])

    {

        int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];

        int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];

        int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];

        int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

  

        F[0][0] = x;

        F[0][1] = y;

        F[1][0] = z;

        F[1][1] = w;

    }

  

    / * Оптимизированная версия power () в методе 4 * /

    static void power(int F[][], int n)

    {

        if (n == 0 || n == 1)

            return;

        int M[][] = new int[][] { { 1, 1 }, { 1, 0 } };

  

        power(F, n / 2);

        multiply(F, F);

  

        if (n % 2 != 0)

            multiply(F, M);

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String args[])

    {

        int n = 9;

        System.out.println(fib(n));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Выход:

34

Пожалуйста, обратитесь к полной статье о программе для чисел Фибоначчи для более подробной информации!

Рекомендуемые посты:

Java-программа для n-го числа Фибоначчи

0.00 (0%) 0 votes