Как найти n-ое число антиФибоначчи?

Question

Eсть задача - найти n-ое число антиФибоначчи:

(F(n) = (F(n-1)-(F(n-2))
В случае если F(0) = вернуть значение a
В случае если F(1) = вернуть значение b

Написал следующий код на c++:

long long antfib(unsigned long long a, unsigned long long b, unsigned long long n) {
    if (n == 0)
        return a;
    if (n == 1)
        return b;
    if (n > 1)
        return antfib(a, b, n - 1) - antfib(a, b, n - 2);
}

int main() {
    unsigned long long a, b, n;
    cin >> a >> b >> n;
    cout << antfib(a, b, n);
}

Проблема: при вводе следующих значении a = 425 b = 9631 c= 9876543215, компилятор выдаёт следующую ошибку:

Необработанное исключение по адресу 0x00772269 в ConsoleApplication9.exe: 0xC00000FD: Stack overflow (параметры: 0x00000001, 0x00A02F64).

Answer 1

0xC00000FD - переполнение стека. В вашем случае - от слишком большой глубины рекурсии.

Перепишите без использования рекурсии: или циклом, или каким-то более умным способом.

Answer 2

Для решения данной задачи Вам нужно использовать нерекурсивный алгоритм. Один способ выше Вам уже предложили - использовать цикл, в котором считаются два члена последовательности, предшествующих указанному. Возможная реализация:

template<typename T>
constexpr auto get_n_af(std::size_t n, T a, T b) -> T
{
    if (n == 0) return a;
    if (n == 1) return b;
    std::array<T, 2> values = { a, b };
    for (std::size_t i = 2; i < n; ++i)
        values = { values[1], values[1] - values[0] };
    return values[1] - values[0];
}

Однако есть и другой способ. В отличие от последовательности, образуемой числами Фибоначчи, данная задается рекуррентным соотношением, у которого вместо суммы используется разность. Это означает, что нам не обязательно знать значения всех предыдущих членов последовательности, так как в итоге значения не аккумулируются - меняются только знаки у коэффициентов a и b (либо же они вообще исчезают). Давайте выразим несколько первых членов последовательности через a и b:

F0 = a
F1 = b
F2 = F1 - F0 = b - a
F3 = F2 - F1 = -a
F4 = F3 - F2 = -b
F5 = F4 - F3 = a - b 
и так далее

Таким образом, чтобы найти n-ый член последовательности, Вам нужно посчитать два коэффициента coef_a и coef_b такие что: Fn = coef_a * a + coef_b * b. Для этого Вам требуется восстановить два ряда - один образован коэффициентами для a, второй - коэффициентами для b.

Я сделал это следующим образом (но мне, признаться, самому не очень нравится): сначала я взял функцию, которая дает нам на [0;3] "трапецию" (0 1 1 0) - 3 * x - n ^ 2, а затем нашел функцию которая бы меняла нам попеременно знак - это sign(sin(pi / 3 * n)). Это ряд для b. Несложно заметить, что соответствующий ряд для a смещен на две позиции влево, поэтому мы просто добавим двойку к аргументу.

Реализация:

template<typename T>
constexpr auto get_n_af_o1(std::size_t n, T a, T b) -> T
{
    if (n == 0) return a;
    if (n == 1) return b;

    auto sign =
        [](std::size_t theta) -> int
            {
                theta %= 360;
                if (theta == 0 or theta == 180) return 0;
                else if (theta < 180) return 1;
                else return -1;
            };

    auto coef =
        [](std::size_t n) -> int
            {
                return static_cast<int>((3 * n - n * n) / 2);
            };

    const auto coef_a = sign((n + 2) * 60) * coef((n + 2) % 3);
    const auto coef_b = sign(n * 60) * coef((n + 0) % 3);

    return coef_a * a + coef_b * b;
}

БЛОГ НА HUSL

Как найти n-ое число антиФибоначчи?

Ответы (2 шт):