C++ malloc(): Повреждение памяти

Question

В настоящее время я просматриваю проблему с фибоначчи на хакерранке, и у меня ошибка повреждения памяти malloc. Это ссылка на проблему я делаю:

https://www.hackerrank.com/contests/programming-interview-questions/challenges/fibonacci-returns/

Input 0-10, каждое число разделенных новой строки. Для каждого ввода печатается значение в этой точке последовательности. Он работает для небольших входов, но после 6 он получает ошибку malloc. Кажется, что размер последовательности не является проблемой, сколько всего сделано подряд.

#include <cmath> 
#include <cstdio> 
#include <vector> 
#include <iostream> 
#include <algorithm> 
using namespace std; 

vector<int> bigFib(1); 

int main() { 
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int x; 
    while(cin >> x){ 
     if(bigFib.size()-1 >= x){ 
      cout << bigFib[x] << endl; 
     } 
     else{ 
      vector<int> fib(x); 
      fib[0] = 0; 
      fib[1] = 1; 
      for(int j = 2; j <= x; j++){ 
       fib[j] = fib[j-1] + fib[j-2]; 
      } 
      bigFib = fib; 
      cout << fib[x] << endl; 
     } 
    } 
    return 0; 
} 

Я довольно новичок в C++ и не могу найти проблему. Спасибо за ваше время.

Answer 1

Когда вы создаете std::vector размера N, вы можете получить доступ к элементам с индексом [0, N-1] - который является N элементами. Вы можете создать вектор размера x и в вашем цикле:

for(int j = 2; j <= x; j++){ 
    fib[j] = fib[j-1] + fib[j-2]; 
    } 

и в этом заявлении

cout << fib[x] << endl; 

вы пытаетесь получить доступ к элементу с индексом, равным x, что UB. Если вам необходимо получить доступ к индексировать x создать вектор с, по меньшей мере, x+1 размером

Answer 2

В vector<int> fib(x); вы объявляете vector<int>, который имеет x элементы. Этими элементами являются: fib[0] - до fib[x - 1]. Однако в for(int j = 2; j <= x; j++){ fib[j] = ... вы назначаете элемент за пределы.

Представьте себе, если x является 1, то вы бы ожидать, что ваш fib вектор содержит только один элемент: fib[0] ... пока ваш цикл присваивание fib[1]. Проблема? Ага.

Я считаю for(int j = 2; j <= x; j++){, вероятно, следует for(int j = 2; j < x; j++){ ...

... и cout << fib[x] << endl; должны быть cout << fib[x - 1] << endl;