Fibonacci's number

[shinta]

hi... well its been plauging me.

i know the formula is this

n = 0 its 0
n = 1 its 1

if n > 1 than

(n-1) + (n-2)


so.. im just having a brain block in making an algorithm out of it. im new to programming so im just trying to challenge my self =D

[G_Morgan]

int fib(int x) {
    if((x == 0) || (x == 1)) {
        return x;
    }
    return fib(x - 1) + fib(x - 2);
} 

[G_Morgan]

You might want to assert(x >= 0) at the start of the function.

This isn't very efficient either but is the direct recursive translation of the function.

You can improve that with either a hash table storing known solutions or by switching to an iterative version. The first isn't easy to pull off nicely in C (lack of closures or objects) but the second can be done.

[mokszyk]

my try

#include <iostream>
using namespace std;
 
int fib(int n) // short version
{
    if (n==1 || n==2)
    {
             return 1;
}
else
{
        return fib(n-2) + fib(n-1);
}       
}
 
int main()
{
  int wej;
  cout << "Ktory wyraz ciagu Fibonacciego podac?\n"; //choose what number
  cin >> wej;
  cout << fib(wej) << "\n";
  system("pause"); //ewentualy if u want see pause
  return 0;
} 

[John]

My three solutions

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;
 
//Non-recrusive: O(1)
unsigned long fib(int n)
{
     return (1/sqrt(5)) * (pow(((1 + sqrt(5)) / 2), n) - pow(((1 - sqrt(5)) / 2), n));
}
 
//Recrusive: O(n)
unsigned long fib2(int n)
{
    if(n <= 2) return 1;
    else return fib2(n - 1) + fib2(n - 2);
}
 
//Iterative: O(n)
unsigned long fib3(int n)
{
    int u = 0;
    int v = 1;
    int i, t;
 
    for(i = 2; i <= n; i++)
    {
        t = u + v;
        u = v;
        v = t;
    }
    return v;        
} 

[shinta]

thanks guys i apreciate it =D

[gszauer]

This article might be a bit of help:
Fibonacci Numbers

[codecall33]

Hello friend !
I will say thanks to all the member for this job
it is really very nice job and i am also try to help to all the member.

[jbakid]

Here's one (assumes n > 0):

[font="Courier New"]
int fibbonacci(int n){
  return n<2?1:fibbonacci(n-1)+fibbonacci(n-2);
}[/font]