Thread: Iteration help please

// Listing 7.15
// Demonstrates solving the nth
// Fibonacci number using iteration

#include <iostream>

int fib(int position);
int main()
{
using namespace std;
int answer, position;
cout << "Which position? ";
cin >> position;
cout << "\n";

answer = fib(position);
cout << answer << " is the ";
cout << position << "th Fibonacci number.\n";
return 0;
}

int fib(int n)
{
int minusTwo=1, minusOne=1, answer=2;

if (n < 3)
return 1;

for (n -= 3; n; n--)
{
minusTwo = minusOne;
minusOne = answer;
answer = minusOne + minusTwo;
}

return answer;
}

/* I need with this problem because I am not really sure why n is being decreased or what the minusTwo=1 and so on mean. I do know that what this problem is trying to accomplish is to find the Fibonacci number, which is 1,1,2,3,5. the nth number being the sum of the two previous number except the first two numbers of the sequence, here being 1 and 1. */

the book says


/* This is exactly how you would solve this problem with pencil and paper. If you were asked for the fifth Fibonacci number, you would write 1,1,2 and think, "two more to do". Youw would then add 2+1 and write, and think, "one more to find" Finally, you would write 3+2 and the answer would be 5. */



// I just don't quite understand it however.



//please help.

That's just plain wierd. I don't know where you got that code, but it's very difficult to follow. This would be a better implementation of the fibonacci series.

Code:

long fib(int n){
    long current, prev, prev_prev;

    current = prev = 1; /*assign 1 to current and prev, first iteration*/
  
    while(n > 2){ /*if n < 2 there's no need, the answer is 1*/
        n -= 1; /*current = 1, so the first iteration is done*/
        prev_prev = prev;
        prev = current;
        current = prev + prev_prev;
    }
    return current;
}

Much easier to follow even without the comments

-Prelude

The recursive version is easier, but I don't recommend using it for anything but describing recursion. The save in complexity isn't worth the horrible decrease in efficiency.