This is a discussion on Fibonacci Sequence within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by iGuardian I apologize, I'm only 8 weeks into the course so I may come off more dumb ...
Manasij Mukherjee | gcc-4.8.2 @Arch Linux
Slow and Steady wins the race... if and only if :
1.None of the other participants are fast and steady.
2.The fast and unsteady suddenly falls asleep while running !
I assume I made the same mistake as before. Is this in the right direction?
Code:#include <iostream> using namespace std; int fib ( int n ); // Function reference. int main() { int sum_of_all_fibs = 0; // The sum will begin at zero, this will be the final output of all numbers // found to be modded by 5 or 3 and be less then 4,000,000. do { int n = 1; fib (n) == fib (++n); if (fib(n) % 3 == 0 || fib(n) % 5 == 0) { sum_of_all_fibs += fib(n); } } while ( sum_of_all_fibs < 4000000 ); } int fib ( int n ) { int fib = 0; int fib1 = 0; int fib2 = 1; int sum_of_all_fibs; fib = fib1 + fib2; fib1 = fib2; fib2 = sum_of_all_fibs; return sum_of_all_fibs; }
To be honest, I wouldn't use a function for the fibonacci number here. At any given point during your loop you have the two previous fibonacci numbers and the next one is equal to their sum. Then it's a matter of shifting the previous one back into the previous previous variable, and moving the next one into the previous variable, ready for the next time around the loop.
Then get your if statement in the right place, test the right variable, and loop up until the right ending condition.
A recursive fibonacci function isn't just inefficient, it's diabolically inefficient at roughly O(2^(0.694n)). Even a value around 200 would take somewhere on the order of as much time as the age of the universe to calculate, on the worlds fastest PC. It simply cannot be used for this.
The first thing that comes mind which is worse than that is Ackermann's function, which is saying a lot
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"