Проблема с задачей Фибоначчи

160

17 июля 2021, 02:50

В задаче нужно посчитать число фибоначчи наоборот (не со сложением, а с вычитанием).

F (0) = а,

F (1) = b,

F (n) = F (n-1) -F (n-2).

Пример Ввода/Вывода:

+---------------------+----------------------+
| стандартный ввод    | стандартный вывод    |
+---------------------+----------------------+
| 4 9 2               | 5                    |
+---------------------+----------------------+
| 10 8 3              | -10                  |
+---------------------+----------------------+

И все неплохо работает до определенного момента, но с большими числами типо таких:

Пример Ввода/Вывода:

+---------------------+----------------------+
| 425 9631 9876543215 | -9206                |
+---------------------+----------------------+

вместо ответа получаю ошибку:

terminate called after throwing an instance of 'std::length_error'
what(): vector::reserve

В коде ошибку не могу найти как не стараюсь. Подскажите в каком направлении плыть.

#include <iostream>
#include <vector>
using namespace std;
long long int a, b;
std::vector<int> fibo(int n)
{
    std::vector<int> w_fibo;
    w_fibo.reserve(n);
    w_fibo[0] = a;
    w_fibo[1] = b;
    for (int i = 1; i < n; i++)
        w_fibo[i + 1] = w_fibo[i] - w_fibo[i - 1];
    return w_fibo;
}
int main()
{
    long long int n;
    int nn;
    cin >> a >> b >> n;
    nn = n%10;
    std::vector<int> fibonacci = fibo(n);
    cout << fibonacci[n];
}

Answer 1

Вы резервируете память для вектора,однако вектор пока остается пустым. Для того, чтобы исправить, нужно поменять

w_fibo.reserve(n);

на

w_fibo.resize(n);

или, еще лучше, сразу обьявите вектор с таким размером:

std::vector<int> w_fibo(n);

Но это еще не решит проблему с выходом за пределы вектора, так как в цикле вы тоже выходите за пределы вектора:

for (int i = 1; i < n; i++)
    w_fibo[i + 1] = w_fibo[i] - w_fibo[i - 1];

тут, когда i == n - 1, условие выполняется, но будет попытка инициализировать w_fibo[n - 1 + 1], т.е. w_fibo[n] что и есть за конец вектора.

Та же ошибка наблюдается в программе:

std::vector<int> fibonacci = fibo(n);
cout << fibonacci[n]; // нужно fibonacci[n - 1]

Но для решения задачи не нужно хранить все вычисления(памяти может не хватать при больших n), а просто вычислить n _ ный член, и лучше передавать в функцию первые два члена, а не обьявлять их как глобальные:

long long 
fibo(long long a, long long  b, const unsigned n)
{
    if (n == 0)
        return a;
    if (n == 1)
        return b;
    long long c;
    for (int i = 1; i < n; i++) {
        c = b - a;
        a = b;
        b = c;
    }
    return c;
}
int main() {    
    cout << fibo(425, 9631, 9876543215);
    return 0;
}

P.S. вас устроил мой ответ, но это еще не все. Чтобы не выполнить каждый раз те же вычисления... Если немного подумать, то результат разности членов повторяется, принимая обратное по знаку значения, так как мы рассматриваем разность тех же чисел. Этот код можно оптимизировать до, например(для наглядности я напишу так, но можно лучше):

long long 
fibo(long long a, long long  b, const unsigned n)
{
    long long c = b - a;
    switch (n % 6)
    {
    case 0:
        return a;
    case 1:
        return b;
    case 2:
        return c;
    case 3:
        return -a;
    case 4:
        return -b;
    case 5:
        return -c;
    }
}

Answer 2

Во-первых, ваш вектор w_fibo имеет размер 0. Вы же пытаетесь осуществлять доступ к элементам этого вектора через оператор [] и даже что-то в них что-то записывать. Поведение не определено.

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