7 replies to this topic

[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]

[HIGHLIGHT="C"]int fib(int x) {
if((x == 0) || (x == 1)) {
return x;
}
return fib(x - 1) + fib(x - 2);
}[/HIGHLIGHT]

[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
[HIGHLIGHT="cpp"]#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;
}
[/highlight]

[John]

My three solutions :)

[HIGHLIGHT="C++"]
#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;
}[/HIGHLIGHT]

[shinta]

thanks guys i apreciate it =D

[gszauer]

This article might be a bit of help:
Fibonacci Numbers

[jbakid]

Here's one (assumes n > 0):
[HIGHLIGHT="C"]
int fibbonacci(int n){
return n<2?1:fibbonacci(n-1)+fibbonacci(n-2);
}[/HIGHLIGHT]