Failed to get correct answer

[sparki]

I am working on project euler problem 2, as below.


Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Ans is 4613732. Can't figure out why my answer is 2461277582?

#include <iostream>
#include <vector>
int main()
{
	unsigned sum = 0;
	const unsigned n = 4000000;
	std::vector<unsigned>vect;
 
	vect.push_back(1);
	vect.push_back(2);
	vect.resize(n);
	int j = 0;

	for (int i{ 2 };i < n; i++)
	{

		vect[i] = vect[j] + vect[j + 1];
  		j++;
	}
 	for (int i{ 0 }; i < n; i++)
	{
		if (vect[i] % 2 == 0)
		{
 			sum += vect[i];
 
		}
		
	}
	std::cout << sum;
}

[salem c]

> vect[i] = vect[j] + vect[j + 1];
Erm, you're supposed to be summing the previous 2, not the next 2.

[sparki]

But I am summing the previous two though. int j starts from 0 and int i starts from 2. So, first loop would be vect[2] = vect[0]+ vect[1];? Let me know if I'm wrong. Feeling kinda tired.

[highwayman]

By considering the terms in the Fibonacci sequence whose values do not exceed four million

Is not the same thing as

By considering the terms in the first four million values of the Fibonacci sequence

You have implemented the latter, not the former.


To fix this, make the ending condition of your first for loop check whether the current val is less than or equal to 4 million. Then it should work.

[salem c]

> But I am summing the previous two though. int j starts from 0 and int i starts from 2
Bah!
So you are.

Coffee hadn't kicked in, and ij similarity.

[Handy Andy]

Hello sparki,

This is what I came up with before I saw all the comments.

#include <iostream>
#include <vector>

int main()
{
	constexpr unsigned MAXSIZE{ 40 };
	constexpr size_t MAXSUM{ 4000000 };
	
	unsigned sum{};
	std::vector<unsigned>vect{ 1, 2 };
	vect.resize(MAXSIZE);
 
	//vect.push_back(1);
	//vect.push_back(2);
	//int j = 0;

	for (size_t i{ 2 }, j{ 1 }; i < vect.size(); i++, j++)
	{
		vect.at(i) = vect[j - 1] + vect[j];  // <--- Reversed for readability.
  		//j++;
	}
	
 	for (size_t i{}; i < vect.size(); i++)
	{
		if (vect[i] % 2 == 0 && sum <= MAXSUM)
		{
 			sum += vect[i];
 			
 			if(i < MAXSIZE)  // <--- Used for testing. Delete when finished.
 			    std::cout<<vect[i] << ' ';
 		}
	}
	
	std::cout << "\n\n" << sum;
}

this produces the output of:

2 8 34 144 610 2584 10946 46368 196418 832040 3524578 

4613732

I am not saying it is the best approach, but there are concepts that make it easier to write the code. Such as for (int i{ 0 };. The (0) zero is not needed. The empty {}s do the sane thing and set the variable to (0) zero. Also there is for (size_t i{ 2 }, j{ 1 }; i < vect.size(); i++, j++). Here you can work with two variables at the same time.

The ".at()" function does some bounds checking. Although it turned out to not make any difference.

Andy