Getting started with C++

1 min read

This post is a rough translation from german to english and is based on this post: Mein Einstieg in C++.

In order to get started with C++ i decided to have a look at problem #2 on projecteuler.net.
A description of the problem can be found here.

Basically, you have to find the sum of all even-valued terms in the fibonacci sequence which do not exceed four million. Sounds easy, doesn’t it?

Here’s how i solved it.

In order to get a specific fibonacci number I used a formula made by Moivre-Binet.

What is amazing about this formula, is that it uses three square roots and still returns integer numbers. Don’t believe me? I couldn’t really believe it either so i simply implemented it in C++:

double getNthFibonacci(double n)
{
	double out;
	out = 1/sqrt(5.0) * (pow(((1+sqrt(5.0))/2), n)
		- pow(((1-sqrt(5.0))/2), n));
	return out;
}

The rest is relativley simple. Just check if the returned number is even-valued and less than four million. If that’s the case, add the number to the sum variable.

int _tmain(int argc, _TCHAR* argv[])
{
	double Fib = 0;
	double sum = 0;
	int i = 1;

	while(true)
	{
		Fib = getNthFibonacci(i);
		if(Fib < = 4000000)
		{
			if((int)Fib % 2 == 0)
			{
				sum += Fib;
			}
			i++;
		}
		else
			break;
	}

	cout << "Sum: " << sum;
	cin.get();

	return 0;
}

While the formula of Moivre-Binet might not be very efficient it’s quite interesting that it returns integer numbers.

11 Dec 2010
blog comments powered by Disqus