Question

Напишите функцию fibBinet(n), которая будет вычислять Fn по формуле Бине, согласно которой Fn равно ближайшему целому для ϕn/√5, где ϕ=(1+√5)/2 – золотое сечение. Проверьте её для значения F77 (должно получиться fibBinet(77) = 5527939700884757).

Answer 1

Формула Бине:

$Fn = \frac{(\frac{1 + \sqrt{5}}{2})^{n} - (\frac{1 - \sqrt{5}}{2})^{n}}{\sqrt{5}}$

При работе с типом double имеет место быть некоторая погрешность. При больших числах относительная погрешность стремится к 0.

Код:

• #include <iostream>
• #include <cmath>
• #define sqrt5 sqrt(5)
• #define   (1 + sqrt5)/2
• #define n (1 - sqrt5)/2
• long long fibBinet(int n) {
•    return (long long) round((pow(, n) - pow(n, n)) / sqrt5);
• }
• int main() {
•    long long binet77 = fibBinet(77);
•    std::cout << "fibBinet(77) = " << binet77 << " (5527939700884757)" << std::endl;
•    std::cout << "A = " << abs(5527939700884757ll - binet77) << std::endl;
•    std::cout << "B = " << 5527939700884757ll / binet77 << std::endl;
•    return 0;
• }

Answer 2

Для вычисления чисел Фибоначчи по формуле Бине сначала нам понадобится вычислить значение золотого сечения (ϕ), а затем использовать его для расчета Fn. Мы также округлим результат до ближайшего целого числа. Вот функция на Python для этого:

pythonCopy code
import math

def fibBinet(n):
    phi = (1 + math.sqrt(5)) / 2  # Золотое сечение

    Fn = (math.pow(phi, n) - math.pow(1 - phi, n)) / math.sqrt(5)
    return round(Fn)

# Проверим для F77
result = fibBinet(77)
print(result)

Этот код вычислит F77, используя формулу Бине, и вернет округленное ближайшее целое число. Результат будет равен 5527939700884757, как и ожидалось.