Числа Фібоначчі: циклом і рекурсією

Числа Фібоначчі — лінійна послідовність натуральних чисел, де перше і друге дорівнюють нулю та одиниці, а кожне наступне — сумі двох попередніх: 0, 1, 1, 2, 3, 5, 8, 13, 21, 43, 55, ... Зазначимо, що ці числа були відомі в Індії ще у столітті. В Європі ж вони в такому вигляді вперше з'явилися в книзі Liber Abaci 1202 року (в перекладі з латинської — «Книга обчислень») за авторством Леонардо Пізанського, згодом прозваного Фібонначі. Значення цієї праці для європейської цивілізації переоцінити неможливо: він вперше знайомив західного читача з індо-арабськими цифрами і ставшими вже звичними для нас арифметичними методами. Одна з найвідоміших включених в неї задач — задача про розмноження кроликів.

Послідовність чисел Фібоначчі

Крім опису зростання приплоду тварин, числа Фібоначчі зустрічаються навіть в самій природі, і на подив доволі часто: це і пелюстки квітки, і спіралі соняшнику, ананаса або соснової шишки.

Також хочеться зазначити, що ця послідовність має безліч цікавих з точки зору математики властивостей. Ось приклад: Ви можете розділити лінію на два сегменти, так що співвідношення між більшим і меншим сегментами буде пропорційно співвідношенню між всією лінією і великим сегментом. Цей коефіцієнт пропорційності, приблизно рівний 1.618, відомий як «золотий перетин». В епоху Відродження вважалося, що саме ця пропорція, дотримана в архітектурних спорудах, найбільше радує око. Якщо взяти послідовні пари з ряду Фібоначчі і ділити більше число з кожної пари на менше, то результат буде поступово наближатися до «золотого перетину».

Про числа Фібоначчі можна ще багато цікавого написати, проте перейдемо до практики, а саме, напишемо код програми на Java, який реалізує отримання як завгодно великої послідовності цих чисел. Зазначимо, що рішення посталеної задачі, зазвичай, здійснюється за допомогою красивого рекурсивного алгоритму, що базується на рекурентному визначенні самих чисел. У найпростішому вигляді його реалізація виглядатиме наступним чином.

Програма для знаходження чисел Фібоначчі за допомогою рекурсії

import java.util.Scanner;
import java.math.BigInteger;
import java.util.*;
class Fibonacci_numbers_recursion {
    public static void main (String args[]) {
        Scanner scann = new Scanner(System.in);
        // Введення номера кінцевого елемента ряду Фібоначчі
        System.out.print("Enter a number: ");
        int num = scann.nextInt();
        if (num < 0)
            throw new IllegalArgumentException("The number you entered must not be less than zero!");
        // Обчислюємо та повертаємо числа Фібоначчі від 0 до num вклічно
        for (int i = 0; i<= num; i++) {
            BigInteger res = Fibonacci(i);
            // Вивід результатів роботи програми
            System.out.println("Fibonacci number " + i + " : " + res);
        }
    }
    // Обчислюємо послідовність чисел Фібоначчі
    public static BigInteger Fibonacci(int number) {
        if (number <= 1)
            return BigInteger.valueOf(number);
        else
            return Fibonacci(number - 1).add(Fibonacci(number - 2));
    }
}

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

числа Фібоначчі java, програмування чисел Фібоначчі

Програмування чисел Фібоначчі з використанням рекурсії

Тобто, в черговий раз ми переконуємося в тому, що, попри свою простоту, рекурсивні алгоритми не завжди швидкі та ефективні. Зумовлено це тим, що кількість разів, які функція Fibonacci() викликає сама себе, зростає експоненціально в залежності від значення яке приймає параметр number. Обчислення Fibonacci(45) з використанням цієї функції включає понад 3.6 мільярда рекурсивних викликів функції Fibonacci() (в ході цього обчислення Fibonacci(1) викликається 1 134 903 170 раз). Проблема тут в тому, що одні й ті ж значення обчислюються знову і знову. Оцінка Fibonacci(45) вимагає оцінки Fibonacci(44)Fibonacci(43),..., Fibonacci(0). Але насправді немає необхідності обчислювати будь-яке з цих значень більше одного разу (не кажучи вже про мільйони разів).

Найпростіший варіант покращення нашої функції — запам'ятовувати вже обчислені значення. Для цього в програмі, введемо додатковий список fibonacci_table реалізований у вигляді масиву, який і буде служити якби кешем для наших обчислень: перед ти як очислювати нове число Фібоначчі будемо виконувати перевірку, чи не обчислювали ми його раніше. Якщо обчислювали — просто повертаємо його без перерахунку. В іншому випадку обчислюємо значення і зберігаємо його в списку перед його поверненням.

Програма для знаходження чисел Фібоначчі за допомогою рекурсії та кешування

import java.util.Scanner;
import java.math.BigInteger;
import java.util.*;
class Fibonacci_numbers_recursion_and_caching {
    public static void main (String args[]) {
        Scanner scann = new Scanner(System.in);
        // Введення номера кінцевого елемента ряду Фібоначчі
        System.out.print("Enter a number: ");
        int num = scann.nextInt();
        if (num < 0)
            throw new IllegalArgumentException("The number you entered must not be less than zero!");
        // Обчислюємо та повертаємо числа Фібоначчі від 0 до num вклічно
        for (int i = 0; i<= num; i++) {
            BigInteger res = Fibonacci(i);
            // Вивід результатів роботи програми
            System.out.println("Fibonacci number " + i + " : " + res);
        }
    }
    // Кеш таблиця
    protected static ArrayList fibonacci_table = new ArrayList();
    // Нульовий та перший елементи кешу ініціалізуються значеннями 0 та 1 відповідно
    static {
        fibonacci_table.add(BigInteger.valueOf(0));
        fibonacci_table.add(BigInteger.valueOf(1));
    }
    // Обчислюємо послідовність чисел Фібоначчі
    public static BigInteger Fibonacci(int number) {
        if (number > fibonacci_table.size() - 1)
            fibonacci_table.add(number, Fibonacci(number - 1).add(Fibonacci(number - 2)));
        return (BigInteger)fibonacci_table.get(number);
    }
}

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

Програмування чисел Фібоначчі з використанням рекурсії та кешування

Ткож хочеться зазначити, що для отримання послідовності Фібоначчі доволі часто використовують і нерекурсивні алгоритми, які обробляють список попередньо обчислених значень «знизу вгору», тобто починаючи з найпростіших випадків переходять до більш складних. Ця ідея призводить до нерекурсивної версії Фібоначчі, яка являється більш ефективною, ніж версія із запам'ятовуванням:

Нерекурсивна версія програми для знаходження чисел Фібоначчі

import java.util.Scanner;
import java.math.BigInteger;
import java.util.*;
public class Fibonacci_numbers {
    public static void main(String[] args) {
        Scanner scann = new Scanner(System.in);
        // Введення номера кінцевого елемента ряду Фібоначчі
        System.out.print("Enter a number: ");
        int num = scann.nextInt();
        if (num <= 0)
            throw new IllegalArgumentException("The number you entered should not be less than one!");
        // Обчислюємо та повертаємо числа Фібоначчі від 0 до num вклічно
        for (int i = 0; i<= num; i++) {
            BigInteger res = Fibonacci(i);
            // Вивід результатів роботи програми
            System.out.println("Fibonacci number " + i + " : " + res);
        }
    }
    // Кеш таблиця
    protected static ArrayList fibonacci_table = new ArrayList();
    // Нульовий та перший елементи кешу ініціалізуються значеннями 0 та 1 відповідно
    static {
        fibonacci_table.add(BigInteger.valueOf(0));
        fibonacci_table.add(BigInteger.valueOf(1));
    }
    // Обчислюємо послідовність чисел Фібоначчі
    public static BigInteger Fibonacci(int number) {
        for (int i = fibonacci_table.size(); i <= number; i++) {
            fibonacci_table.add(fibonacci_table.get(i - 1).add(fibonacci_table.get(i - 2)));
        }
        return (BigInteger)fibonacci_table.get(number);
    }
}
Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар