fibonnaci number

[rotenegg]

error in ma program it shows the last digit twice.

#include<conio.h>
#include<stdio.h>
int main()
{
     int fib(int);
      int n,c,a=0,b=1;
     printf("enter a number: ");
     scanf("%d",&n);
     printf("%d %d ",a,b);
    c=fib(n);
    printf("%d ",c);
    getch();
}
int fib(int n)

{
int a=0,i,b=1,sum;

    for(i=0;i<n-2;i++)
    {
                      sum=a+b;
                      a=b;
                      b=sum;
                      printf("%d ",sum);
                      }

                      return(sum);
                      }

[Gonbe]

The printf statement in main does the second?

Somewhat related, I found another (iterative) fibonacci function lately that is interesting:

long int fib(unsigned long int n) {
   return lround((pow(0.5 + 0.5 * sqrt(5.0), n) - 
                  pow(0.5 - 0.5 * sqrt(5.0), n)) / 
                 sqrt(5.0));
}

[rubberman]

Given how fast Fibonacci numbers hit system limits, don't bother using an iterative approach. Use a recursive one instead. You will never overrun your stack, and it is a LOT easier to code correctly! :-)

[rotenegg]

for example @rubberman

[NP-complete]

Example:

int fib (int n) 
{
   if (n <= 1)
     return n;
   else
     return fib(n - 1) + fib(n - 2);
 }

But the iterative approach is much better in terms of complexity! That is, for large n's the iterative version will be much faster than the recursive one.

Well, you can improve the naive recursive approach^^ with memoization but if you have never heard of Dynamic Programming, may be you can skip this for now.
But keep it at the back of your head and you may find this handy when you learn DP (if you're into a CS program, you will someday!)

[rubberman]

Thanks NP! FWIW, I once wrote a Fibonacci program using exceptions, in order to test early standard C++ compiler exception handling. It was interesting how many failed the test! :-) I wish I could dig up the code (it sits on a floppy somewhere in my home office - written in the mid-1990's) as it really was quite neat. All my systems that still have floppy drives have been mothballed - I'm not sure they will even boot up! :-)

[NP-complete]

My pleasure, rubberman! Add a rep, maybe? :-)

And hey, good luck finding that old floppy! I'm sure people can learn a thing or two about exception handling and how to inmplement them with your code...