CODEWITHSUNDEEP
c++subtraction
transmini
transmini

Reputation: 65

Program not computing subtraction properly

I'm working on a math assignment, not anything that requires programming, but since I enjoy it I try to do it for some of the assignments just to see if I can. This one was writing an integer as a sum of Fibonacci numbers. Here's the code for it:

#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;

int main()
{
  vector<int> fib;
  vector<int> sum;
  int n = 0;
  int total = 0;

  cout << "Enter a number." << endl;
  cin >> n;
  total = n;

  fib.push_back(1);
  fib.push_back(1);

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

  for(int i = n; i >= 0; i--)
  {
    if(total - fib[i] >= 0)
    {
      sum.push_back(fib[i]);
      total -= fib[i];
    }
    if(total == 0)
    {
      break;
    }
    if(total < 0)
    {
      cout << "Program Error. Exiting" << endl;
      exit(1);
    }
  }

  cout << "The sequence of the fewest Fibonacci numbers adding to " << n << " is:" << endl;
  for(int i = 0; i < sum.size(); i++)
  {
    cout << sum[i] << endl;
  }

  return(0);
}

It seems to run fine until I try to put in the number 7.

When it gets to if(total - fib[i] >= 0) it works as its supposed to. total is supposed to get down to 2 and fib[i] also reaches 2 for some i. It calculates this fine and goes into the if statement. but then when it does total -= fib[i] it makes total = -1, thus breaking the code.

Any suggestions as how to fix this?

Edit: It's not just 7. I tried 100, and got extremely large (both positive and negative) numbers that I was too lazy to see if they actually added up to 100 since there were about 30 or so of them. I'm not sure where this would come from.

Edit2: The issue with the #100 is not that it doesn't work, but the value is too large for an int to hold, for anyone having similar situations.

Upvotes: 1

Views: 606

Answers (2)

zydcom
zydcom

Reputation: 518

Change

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

To

for (int i = 2; i <=n; i++) {
    int tmp = fib[i-1] + fib[i-2];
    fib.push_back(tmp);
}

vector<int> fib allocates 8 elements space by default, vector[8+] access will cause memory error, you should use push_back(), vector will auto reallocate space when it's full.

Upvotes: 3

vsz
vsz

Reputation: 4909

Before your line for(int i = 2; i <= n; i++) the size of your fib vector is only 2, because you didn't reserve any space for it, and you called push_back only twice.

This means, if you try to set any element of it after that, you will encounter undefined behavior. You accessed memory which doesn't belong to you.

Upvotes: 3

Related Questions