CareerCup

Fibonacci sequence is as follow 0, 1, 1, 2, 3, 5, 8.....
the first two numbers in the Fibonacci sequence are 0 and 1, and each subsequent number is the sum of the previous two. so the code is easy.

int main()
{
    int line = 0;
    long long Fibonacci[20];
    Fibonacci[0] = 0;
    Fibonacci[1] = 1;
    for (int i = 2; i != 20; ++i) {
        Fibonacci[i] = Fibonacci[i - 1] + Fibonacci[i - 2];
    }
    for (int i = 0; i != 20; ++i) {
        ++line;
        cout << Fibonacci[i] << "\t";
        if (line % 4 == 0)
            cout << endl;
    }
    return 0;

}

The most optimal way here would be to use Dynamic Programming because the subproblems overlap.
F(n) = F(n-1) + F(n-2)
and in next set of iteration:
F(n-1) = F(n-2) + F(n-3).
So, as you can see, there are unnecessary recompuation of same subproblem, which can be avoided by using Dynamic Programming and storing intermediate results in a table. THe normal fibonacci program won't be of much interest since it incurs heavy complexity (exponential factor).

Let n be number of terms entered by user. then we simply use the logic:
for(c=0;c<n;c++)
{
if(c<=1)
next=c;
}
else
{
next=first+second;
first=second;
second=next;
}
printf("%d",next);

if n == 1
	print 0
else if n == 2
	print 1
else if n > 2
	first = 0
	second = 1
	n = n - 2
	print first and second
	while (n-- > 0)
		third = first + second
		print third
		first = second
		second = third

Hi guys, I dont know this answer.

Is this a Joke. No one ask this simple question in the interview.

public static int fib(int n) {
                if (n < 2) return n;
		return fib(n-1)+fib(n-2);
}