0

I am working on this assignment and i trying to figure this out. When i input any other numbers between 1 to 10 except 6. The fibonacci_fast(n) outputs an error main: malloc.c:2401: sysmalloc: Assertion. However, when i use an array to replace the vector or just uncomment the std::cout. It will work fine. Can anyone enlighten me what's the error that i have made.


#include <iostream>
#include <cassert>
#include <vector>
#include <algorithm>



int fibonacci_naive(int n) {
        if (n <= 1)
        return n;

    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2);
    
}

int fibonacci_fast(int n) {

    std::vector<int> numbers{0,n};
    numbers[0] =0;
    numbers[1] =1;
    int ans=0;
    if (n <= 1)
    {
        return n;
    }
    
        //std::cout<<std::endl;
        //int numbers[n];

        for(int i=2;i<=n;i++)
        {
            numbers[i] = numbers[i-1] + numbers[i-2];
            
        }

        ans = numbers[n];

        return ans;
    

    
}

void test_solution() {
    assert(fibonacci_fast(3) == 2);
    assert(fibonacci_fast(10) == 55);
    for (int n = 0; n < 20; ++n)
        assert(fibonacci_fast(n) == fibonacci_naive(n));
}

int main() {
    int n = 0;
    std::cin >> n;

    //std::cout << fibonacci_naive(n) << '\n';
    //test_solution();
    std::cout << fibonacci_fast(n) << std::endl;
    return 0;
}
Fun Sherwin
  • 15
  • 2
  • 4
    `std::vector numbers{0,n};` creates a vector of `size()` 2, with values `0` and `n`. You need to use parantheses to call the fill-n constructor: `std::vector numbers(n,0);`. Also, the length goes first. – Yksisarvinen Feb 07 '22 at 15:15
  • @Yksisarvinen it's not actually a dupe (I can see that now) but they are using a VLA in their "success" case. it's the `int numbers[n];`. They should be aware that's not standard behavior and may work funky. – Mgetz Feb 07 '22 at 15:19
  • 1
    Also, you go out-of-bound in the loop. Max index for vector of size `n` is `n-1`, `numbers[n];` is already out of bounds. – Yksisarvinen Feb 07 '22 at 15:20
  • 1
    Also, you go out-of-bounds if `n <= 1`. Before checking if `n` is that small, you attempt to write to `numbers[1]`. Constructing your vector will also fail spectacularly if `n < 0` – Drew Dormann Feb 07 '22 at 15:23
  • @Mgetz Ah, I didn't notice the comment. Still, StackOverflow decided for me and added both, seems reasonable. – Yksisarvinen Feb 07 '22 at 15:23
  • BTW: a fast Fibonacci solution using no memoization (ie compute each new value regardless of previous operations) only needs an array of 3 numbers. But I cannot show code on a closed question... – Serge Ballesta Feb 07 '22 at 15:39
  • thanks guys, i understand my mistake. Thanks for pointing it out. i changed it to std::vector numbers(n+1,0); i understand that the for loop will increment to 7 when input is 6 but my ans will only return the value at 6. Not the optmized way to do it – Fun Sherwin Feb 07 '22 at 15:40

1 Answers1

1

std::vector<int> numbers{0,n}; creates a vector of size 2, not of size n. You probably want to use std::vector<int> numbers(n, 0).

Yksisarvinen
  • 18,008
  • 2
  • 24
  • 52
Timon van der Berg
  • 506
  • 4
  • 10