So I'm learning C++. I've got my "C++ Programming Language" and "Effective C++" out and I'm running through Project Euler. Problem 1...dunzo. Problem 2...not so much. I'm working in VS2008 on a Win32 Console App.
Whats the Sum of all even terms of the Fibonacci Sequence under 4 million?
It wasn't working so I cut down to a test case of 100...
Here's what I wrote...
// Problem2.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
cout << "Project Euler Problem 2:\n\n";
cout << "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:\n\n";
cout << "1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n\n";
cout << "Find the sum of all the even-valued terms in the sequence which do not exceed four million.\n\n";
cout << "Answer: " << Solve();
}
double Solve() {
int FibIndex = 0;
double result = 0.0;
double currentFib = GenerateNthFibonacciNumber(FibIndex);
while (currentFib < 100.0){
cout << currentFib << " " << (int)currentFib << " " << (int)currentFib % 2 << "\n";
if ((int)currentFib % 2 == 0){
result += currentFib;
cout<<(int)currentFib;
}
currentFib = GenerateNthFibonacciNumber(++FibIndex);
}
return result;
}
double GenerateNthFibonacciNumber(const int n){
//This generates the nth Fibonacci Number using Binet's Formula
const double PHI = (1.0 + sqrt(5.0)) / 2.0;
return ((pow(PHI,n)-pow(-1.0/PHI,n)) / sqrt(5.0));
}
And here's the output...
Project Euler Problem 2:
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, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
0 0 0
1 1 1
1 1 1
2 2 0
3 3 1
5 5 1
8 8 0
13 13 1
21 21 1
34 34 0
55 54 0
89 89 1
Answer: 99
So I have three columns of debug code...the number returned from the generate function, (int)generatedNumber, and (int)generatedNumber % 2
So on the 11th term we have
55,54,0
Why does (int)55 = 54?
Casting to int
truncates the number - same as if you'd called floor(currentFib)
. So even if currentFib
is 54.999999
... (a number so close to 55 that it will be rounded up when printed), (int)currentFib
will produce 54.