Серія Фібоначчі на Java

1. Огляд

У цьому підручнику ми розглянемо серію Фібоначчі.

Зокрема, ми реалізуємо три способи обчислення n-го члена ряду Фібоначчі, останній - рішення з постійним часом.

2. Серія Фібоначчі

Ряд Фібоначчі - це ряд чисел, у яких кожен доданок є сумою двох попередніх доданків . Це перші два доданки - 0 і 1 .

Наприклад, перші 11 термінів ряду - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 та 55 .

У математичному відношенні послідовність S n чисел Фібоначчі визначається відношенням рецидиву:

S(n) = S(n-1) + S(n-2), with S(0) = 0 and S(1) = 1

Тепер давайте розглянемо, як обчислити n-й доданок ряду Фібоначчі. Три методи, на яких ми зупинимось, є рекурсивними, ітеративними та використовують формулу Біне.

2.1. Рекурсивний метод

Для нашого першого рішення давайте просто виразимо відношення рецидиву безпосередньо в Java:

public static int nthFibonacciTerm(int n) { if (n == 1 || n == 0) { return n; } return nthFibonacciTerm(n-1) + nthFibonacciTerm(n-2); }

Як ми бачимо, ми перевіряємо, чи n дорівнює 0 або 1. Якщо це істина, тоді ми повертаємо це значення. У будь-якому іншому випадку ми рекурсивно викликаємо функцію для обчислення (n-1) -го члена і (n-2) -го члена і повертаємо їх суму.

Хоча рекурсивний метод простий у реалізації, ми бачимо, що цей метод робить багато повторних обчислень. Наприклад, для того, щоб обчислити 6-й доданок, ми робимо дзвінки для обчислення 5-го і 4-го доданка. Більше того, виклик для обчислення 5-го члена робить виклик для обчислення 4-го члена знову. Через цей факт рекурсивний метод робить багато зайвої роботи.

Як виявляється, це робить його складність часу експоненціальною; O (Φn), якщо бути точним.

2.2. Ітераційний метод

В ітераційному методі ми можемо уникнути повторних обчислень, зроблених рекурсивним методом. Натомість ми обчислюємо умови серії та зберігаємо попередні два умови для обчислення наступних.

Давайте подивимося на його реалізацію:

public static int nthFibonacciTerm(int n) { if(n == 0 || n == 1) { return n; } int n0 = 0, n1 = 1; int tempNthTerm; for (int i = 2; i <= n; i++) { tempNthTerm = n0 + n1; n0 = n1; n1 = tempNthTerm; } return n1; }

По-перше, ми перевіряємо, чи є термін для обчислення 0-м або 1-м членом. Якщо це так, ми повертаємо початкові значення. В іншому випадку ми обчислюємо 2-й доданок за допомогою n0 та n1 . Потім ми модифікуємо значення змінних n0 та n1 для зберігання 1-го і 2-го доданка відповідно. Ми продовжуємо ітерацію, поки не обчислимо необхідний термін.

Ітераційний метод дозволяє уникнути повторюваної роботи, зберігаючи два останні терміни Фібоначчі у змінних. Складність у часі та складність у просторі ітераційного методу становить O (n) та O (1) відповідно.

2.3. Формула Біне

Ми визначили n-те число Фібоначчі лише через два попередні числа. Тепер ми розглянемо формулу Біне для обчислення n-го числа Фібоначчі за постійний час.

Терміни Фібоначчі підтримують співвідношення, яке називається золотим перетином, що позначається Φ , грецький символ вимовляється як "фі" .

Спочатку розглянемо, як обчислюється золотий перетин :

Φ = ( 1 + √5 )/2 = 1.6180339887...

А тепер давайте розглянемо формулу Біне :

Sn = Φⁿ–(– Φ⁻ⁿ)/√5

Насправді це означає, що ми повинні мати змогу отримати n-те число Фібоначчі за допомогою лише деякої арифметики.

Давайте виразимо це на Java:

public static int nthFibonacciTerm(int n) { double squareRootOf5 = Math.sqrt(5); double phi = (1 + squareRootOf5)/2; int nthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n))/squareRootOf5); return nthTerm; }

Спочатку ми обчислюємо squareRootof5 і phi і зберігаємо їх у змінних. Пізніше ми застосовуємо формулу Біне, щоб отримати необхідний термін.

Оскільки ми маємо справу з ірраціональними числами, ми отримаємо лише наближення. Отже, нам доведеться тримати більше десяткових знаків для вищих чисел Фібоначчі, щоб врахувати помилку округлення.

Ми бачимо, що вищеописаний метод обчислює n-й член Фібоначчі за постійний час, або O (1).

3. Висновок

У цій короткій статті ми розглянули серію Фібоначчі. Ми розглянули рекурсивне та ітераційне рішення. Потім ми застосували формулу Біне для створення рішення з постійним часом.

Як завжди, повний вихідний код робочих прикладів доступний на GitHub.