Фибоначчи на языке D

Фибоначчи… Помните, как мы впервые услышали это слово? Может, на уроках математики или читая научную фантастику. Так или иначе, последовательность Фибоначчи пронизывает наш мир, от природы до технологий. Сегодня мы погрузимся в эту тему, исследуя, как можно реализовать последовательность Фибоначчи на языке программирования D.

Что такое последовательность Фибоначчи?

Последовательность Фибоначчи — это ряд чисел, где каждое следующее число является суммой двух предыдущих. Она начинается с 0 и 1, и выглядит так:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Вы можете спросить, зачем это нужно программистам? На первый взгляд, это может показаться просто математическим курьезом. Однако, эта последовательность находит применение в алгоритмах, оптимизации и даже в создании компьютерной графики.

Рекурсивная реализация

Начнем с самого простого метода — рекурсивного. Этот способ интуитивно понятен: функция вызывает сама себя, чтобы вычислить нужное значение.

import std.stdio;

int fib(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

void main() {
    writeln(fib(10)); // 55
}

Смысл рекурсии

Рекурсия, как концепция, привлекает своей элегантностью и простотой. Представьте дерево: каждый узел (число в последовательности) порождает два других узла (предыдущие числа), и так до тех пор, пока не достигнем основы — первых двух чисел.

Недостатки рекурсии

Рекурсивный метод обладает своими минусами:

1. Медлительность: На каждое вычисление порождаются новые вызовы функций, что замедляет процесс.
2. Память: Глубокая рекурсия может привести к переполнению стека.

Итеративная реализация

Чтобы обойти эти проблемы, мы можем использовать итеративный метод.

import std.stdio;

int fib(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    int a = 0;
    int b = 1;
    for (int i = 2; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

void main() {
    writeln(fib(10)); // 55
}

Преимущества итерации

Итерация выполняется быстрее и эффективнее, чем рекурсия. Мы избегаем создания большого количества вызовов функций, что экономит память и ускоряет выполнение.

Мемоизация

Но что если нам нужно часто вычислять числа Фибоначчи? В таком случае может помочь мемоизация — сохранение уже вычисленных результатов для повторного использования.

import std.stdio;
import std.array : Appender;
import std.algorithm : map;

int fibMemo(int n, int[] memo) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

int fib(int n) {
    int[] memo = new int[n + 1];
    foreach (i; 0 .. n + 1) {
        memo[i] = -1;
    }
    return fibMemo(n, memo);
}

void main() {
    writeln(fib(10)); // 55
}

Как это работает?

Мемоизация сводит к минимуму количество вычислений. Мы используем массив, чтобы хранить результаты для каждого значения n. Если значение уже вычислено, мы просто берем его из массива.

Использование матриц

Хотите что-то более сложное? Давайте рассмотрим метод матриц, который позволяет вычислять числа Фибоначчи за логарифмическое время.

import std.stdio;
import std.math : pow;

void multiply(long[][] F, long[][] M) {
    long x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    long y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    long z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    long 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;
}

void power(long[][] F, int n) {
    if (n == 0 || n == 1) return;
    long[][] M = [[1, 1], [1, 0]];

    power(F, n ~/ 2);
    multiply(F, F);

    if (n % 2 != 0) {
        multiply(F, M);
    }
}

long fib(int n) {
    if (n == 0) return 0;
    long[][] F = [[1, 1], [1, 0]];
    power(F, n - 1);
    return F[0][0];
}

void main() {
    writeln(fib(10)); // 55
}

Смысл матриц

Использование матриц позволяет вычислять числа Фибоначчи за O(log n) операций, что намного быстрее для больших значений n. Этот метод основывается на возведении матрицы в степень.

Последовательность Фибоначчи — это мощный инструмент, который находит применение во многих областях, от чистой математики до компьютерной графики. Язык программирования D, обладая высокой производительностью и простотой использования, идеально подходит для таких задач. Мы рассмотрели несколько методов вычисления чисел Фибоначчи, начиная от простой рекурсии и заканчивая сложными методами с использованием матриц. Не бойтесь экспериментировать и применять эти знания на практике. Ведь как говорил Эдсгер Дейкстра: «Программы пишут для того, чтобы с их помощью думать, а не для того, чтобы компьютеры их выполняли».

---

---