tags:

views:

216

answers:

3
#include <iostream>
using namespace std;
void main()
{
  int i = 0;
  while (i < 1000)
  {
      int TEMP = i * 2;
      cout << i << endl;
      TEMP = i;
      i = i +1;
      // ???
  }

  return;
}

I'm so confused?? :(

A: 

If you would like just a hint, Google "recursion".

If you would like the answer, Google "recursion fibonacci C++", but PLEASE try to work it out with the hint above :) It's worth it.

jamesj629
I would avoid suggesting recursion + fibonacci, even with memoization.
Moron
the big hint: the standard fibonacci recursive solution is a pessimal one.
Jimmy
Given the probable experience level of the poster, recursion might be a good way to get the first 50. As dirkgently pointed out above, Fib(1000) is a lot larger than int.
jamesj629
+1  A: 

First you should check that you understand the definition of the Fibonacci numbers.

By definition, the first two Fibonacci numbers are 0 and 1, and each remaining number is the sum of the previous two. Some sources omit the initial 0, instead beginning the sequence with two 1s.

You need two variables to remember the state, not just one as you were trying to do. And you don't multiply by two, you just add the two variables.

#include <iostream>
using namespace std;
int main()
{
    int i = 0;
    int j = 1;
    while (i < 1000)
    {
        /* Print a number. */
        cout << i << endl;

        /* Set j to the sum of i and j, and i to the old value of j. */
        int TEMP = j;
        j += i;
        i = TEMP;
    }
    return 0;
}
Mark Byers
Giving answers is frowned upon. How will anyone learn that way? EDIT: And accepted. Hey Joshua, did you actually learn anything this way? Do you even understand how this works?
GMan
I'll give him the benefit of the doubt this first time... he does appear to have tried himself first and his other questions look like genuine questions.
Mark Byers
YA I DO GMAN FYI
Joshua
@JOSHUA: OK YOU CAN TURN CAPS LOCK OFF NOW. Okay, explain how it works, then. I'll take a no response as a lack of understanding.
GMan
Note that the Fibonacci sequence grows almost as quickly as 2^n, so unless your compiler's `int` type has almost 1000 bits, this is going to overflow.
Laurence Gonsalves
I guess if he wanted just code he could have Googled it. What I have given him is how *his code* can be turned into correct code. That's probably more useful to him than just seeing a completely different solution. I hope he will go 'Ah, that's what I was missing!'. Anyway, hope I didn't offend anyone on here by answering someone's question. If he learned something - great. If he didn't, we can't force him to. :-s
Mark Byers
bitching about giving answers on a Q/A site is fail. +1.
SP
@Laurence: Um, I don't think so. Unless your int type has only 9 bits, this shouldn't overflow.
Sean Nyman
This won't work of course. Because the 45th Fibonacci number is the last one that can be represented as a 32-bit 2's complement integer.
Omnifarious
@Omnifarious: The loop will stop long before then. It isn't outputting the first 1000 in the sequence, it is outputting the integers in the sequence that are less than 1000.
Sean Nyman
@SP: Homework questions: http://meta.stackoverflow.com/questions/10811/homework-on-stackoverflow Look at the first bullet point under *Answering Homework Questions* : Try to give suggestions that will lead the asker in the correct direction **rather than providing a ready-made answer.**
GMan
@Sean: oops! You're right. I misread and thought this was returning the first 1000 Fibonacci numbers, not the first less than 1000.
Laurence Gonsalves
@GMan: How can you be so sure it is homework? It could be something like Euler Project, or just for fun...
Mark Byers
@Mark: I'm pretty sure none of the Euler questions are this trivial, though to be fair I haven't finished them all. (But I don't think the difficulty would dip, so I'm pretty certain there simply aren't any "calculate Fibb. numbers" questions.) That said, I think "homework" is the catch-all term for "learning work." If it's for fun, giving him the answer staight-out still results in the same ability for them to copy-paste and never learn.
GMan
@Sean Nyman: Oops. *sigh* I should read more carefully.
Omnifarious
+11  A: 

The Fibonacci sequence F is F(n) = F(n - 1) + F(n - 2), F(0) = 0, F(1) = 1.

Here's some psuedo-code:

Start Counter1 at 0
Start Counter2 at 1.

For i = 0 to 1000
    New value = Counter1 + Counter2
    Print new value

    Counter2 = Counter1
    Counter1 = New Value
End For

This doesn't print out 0 or 1; it starts at F(2). You can easily fix this by just printing out 0 and 1 first. Also, this code prints the first 1000 numbers. If you change this to: While Counter1 < 1000, you'll stop when you reach or pass 1000.

It's up to you to implement it, and make sure you understand how it works.

GMan
+1 for pseudocode for this question.
p.campbell
Are you sure he wants the first 1000 numbers and not all the numbers less than 1000?
Mark Byers
@Mark: I just edited to include that, though I'm not sure if the comment or edit came first. I only saw it now.
GMan
It looks like your edit came first... by one second. (Hint: hold the mouse over the vague timestamp to get a more exact timestamp as a pop-up).
Mark Byers
@Mark: Wow, I totally forgot about that. Thanks for reminding me.
GMan