3

Should return the n place of the array. But instead of the value I'm only getting 0.

int fibonacci(int n)
{
    int f[100];
    f[0] = 0;
    f[1] = 1;

    for (int i=2; i<n; i++)
    {
        f[i] = f[i-2] + f[i-1];
    }

    return f[n];
}

int main()
{
    cout << fibonacci(3);
    return 0;
}

New CODE:

New problem its returning one number further then it should. For example if 'n==7' its returning '13' not '8' like it should.

int fibonacci(int n)
{
    int f[100] = { 0, 1 };

    for (int i=2; i<=n; i++)
    {
        f[i] = f[i-2] + f[i-1];
    }

    return f[n-1];
}

int main()
{
    cout << fibonacci(7);
    return 0;
}
Improve this question
4
  • 3
    You could shorten your array initialization to int f[100] = { 0, 1 } and it will initialize all the other elements to 0 automatically. Also, you could make the array static (and add a static counter of the last calculated position) so you don't have to recalculate values you already know every time. Just FYI Commented Dec 3, 2010 at 20:56
  • @ Chris thanks this is helpful i will make sure and do this. Commented Dec 3, 2010 at 21:00
  • NOTE: There is an integer overflow in your code for fibonacci(48). Use uint64_t instead of int to get correct values upto n==94. codepad.org/ApUew5IY Commented Dec 3, 2010 at 23:43
  • you could cache the results in the f array if your measurements show that a program spends too much time in the fibonacci() function codepad.org/Ve7pvSjP Commented Dec 4, 2010 at 0:11

7 Answers 7

Reset to default
4

well, you never set f[n], you only go up to i < n, that is, i == n-1. try returning f[n-1]

EDIT: as Chris Lutz pointed out my answer is no good as it would give an invalid result if you called fibonacci(0)

Like many have answered already, the best solution is to loop until i <= n
Unless, of course, you want fibonacci(3) to return the 3rd element in the fibonacci sequence and not the 4th, in which case fibonacci(0) wouldn't really make sense, and the right return value would be f[n-1]... still the n==0 case should be handled somehow, as should the n<0and the n>100 cases.

you can return f[n-1] as long as you check for the right boundaries:

int fibonacci(int n)
{
    int f[100] = { 0, 1 };

    if ((n <= 0) || (n > 100))
        return -1;//return some invalid number to tell the caller that he used bad input

    for (int i=2; i < n; i++) // you can use i < n here
    {
        f[i] = f[i-2] + f[i-1];
    }

    return f[n-1];
}
Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

-1 right problem, wrong solution. fibonacci(0) should return a valid value.
@filipe - If you @me SO will notify me so I can retract my downvote before the vote-changing time limit expires. (I just happened to check a minute after your edit, so you got lucky this time.)
@filipe this is what i do i <= n but i cant return n-1 for the problems you have said above. So im stuck.
@Chris Lutz like this? huh, I didn't know that. I'll use that from now on, thanks. =)
@filipe the thing is n==0 is a correct input because f[n] when n=0 is f[0] which is = to 0 if that made any scene at all.
|
4

Your loop termination condition is wrong. Since this is homework perhaps you can work out why.

Improve this answer

Comments

3

You forgot to initialize the n-th value of the array. You return f[n] but only initialize up to n-1.

Improve this answer

Comments

2

n is the index that is never reached in your version. You just need to replace the < with <= in your for loop conditional. (You never assigned f[n] because n was never reached by the loop and so you got back a default value.)

int fibonacci(int n)
{
    int f[100];
    f[0] = 0;
    f[1] = 1;

    for (int i=2; i<=n; i++)
    {
        f[i] = f[i-2] + f[i-1];
    }

    return f[n];
}

int main()
{
    cout << fibonacci(3);
    return 0;
}

And you don't need an array to perform the fib sequence by the way. Just use two variables and reassign them in the loop. Something like this:

int a = 0;
int b = 1;

for (int i=2; i<=n; i++)
{
    b = a + b;
    a = b;
}

return b;
Improve this answer

Comments

2

The trouble is that you test for i < n (where n == 3 in your example call), but you return f[3] which has not been set to anything. You are 'lucky' that you're getting zeroes rather than random garbage.

Change the '<' to '<='.

Working Code #1

Retaining the full size array.

#include <iostream>
using namespace std;

static int fibonacci(int n)
{
    int f[100] = { 0, 1 };

    if (n < 0 || n > 100)
        return -1;
    else if (n < 2)
        return f[n];

    for (int i = 2; i <= n; i++)
    {
        f[i] = f[i-2] + f[i-1];
        //cout << "f[" << i << "] = " << f[i] << endl;
    }

    return f[n];
}

int main()
{
    for (int i = 0; i < 8; i++)
        cout << "fib(" << i << ") = " << fibonacci(i) << endl;
    return 0;
}

Sample Output #1

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13

Working Code #2

This uses an array of size 3, at the cost of a lot of modulo operations:

#include <iostream>
using namespace std;

static int fibonacci(int n)
{
    int f[3] = { 0, 1, 0 };

    if (n < 0 || n > 100)
        return -1;
    else if (n < 2)
        return f[n];

    for (int i = 2; i <= n; i++)
    {
        f[i%3] = f[(i-2)%3] + f[(i-1)%3];
        //cout << "f[" << i << "] = " << f[i%3] << endl;
    }

    return f[n%3];
}

int main()
{
    for (int i = 0; i < 8; i++)
        cout << "fib(" << i << ") = " << fibonacci(i) << endl;
    return 0;
}

It produces the same output - so there is no point in repeating it.

Working Code #3

Avoiding arrays and modulo operations:

#include <iostream>
using namespace std;

static int fibonacci(int n)
{
    int f0 = 0;
    int f1 = 1;

    if (n < 0 || n > 46)
        return -1;
    else if (n == 0)
        return f0;
    else if (n == 1)
        return f1;

    int fn;
    for (int i = 2; i <= n; i++)
    {
        int fn = f0 + f1;
        f0 = f1;
        f1 = fn;
        //cout << "f[" << i << "] = " << fn << endl;
    }

    return f1;
}

int main()
{
    for (int i = -2; i < 50; i++)
        cout << "fib(" << i << ") = " << fibonacci(i) << endl;
    return 0;
}

The limit 46 is empirically determined as correct for 32-bit signed integers.

Example Output #3

fib(-2) = -1
fib(-1) = -1
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55
fib(11) = 89
fib(12) = 144
fib(13) = 233
fib(14) = 377
fib(15) = 610
fib(16) = 987
fib(17) = 1597
fib(18) = 2584
fib(19) = 4181
fib(20) = 6765
fib(21) = 10946
fib(22) = 17711
fib(23) = 28657
fib(24) = 46368
fib(25) = 75025
fib(26) = 121393
fib(27) = 196418
fib(28) = 317811
fib(29) = 514229
fib(30) = 832040
fib(31) = 1346269
fib(32) = 2178309
fib(33) = 3524578
fib(34) = 5702887
fib(35) = 9227465
fib(36) = 14930352
fib(37) = 24157817
fib(38) = 39088169
fib(39) = 63245986
fib(40) = 102334155
fib(41) = 165580141
fib(42) = 267914296
fib(43) = 433494437
fib(44) = 701408733
fib(45) = 1134903170
fib(46) = 1836311903
fib(47) = -1
fib(48) = -1
fib(49) = -1
Improve this answer

3 Comments

New problem its returning one number further then it should. For example if 'n==7' its returning '13' not '8' like it should.
what about for case n=0 though?
@Alec: I think that F(7) = 13 when you specify F(0) = 0 and F(1) = 1; see the example outputs above.
1

With the call fibonacci(3), your for loop (inside the fibonacci function) goes until i < 3...

It means that the last assigment is f[2]. Not f[3] as expected (which is the value you return).

Improve this answer

Comments

0

Don't you mean return f[n-1];

I guess your compiler has set the array f[100] to 0?

Looks like the other guy has the right answer....

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.