# Fibonacci challenge

• (3 Pages)
• 1
• 2
• 3

## 41 Replies - 42297 Views - Last Post: 13 May 2015 - 03:56 AM

### #16 GWatt

Reputation: 307
• Posts: 3,105
• Joined: 01-December 05

## Re: Fibonacci challenge

Posted 02 August 2012 - 12:53 PM

IngeniousHax, on 02 August 2012 - 02:26 PM, said:

Very nice BetaWar, i dig that solution. I believe my solution takes quadratic time to complete (N^2)...

Try O(2^n)

### #17 Blaylok

Reputation: -2
• Posts: 7
• Joined: 19-August 12

## Re: Fibonacci challenge

Posted 19 August 2012 - 09:07 PM

A better way to do fibonacci sequence using looping technique is:

OUTPUT:
Please enter the number of terms: 8
1 1 2 3 5 8 13 21

Spoiler

Hope that works!

This post has been edited by jimblumberg: 19 August 2012 - 09:19 PM
Reason for edit:: Added spoiler tags

### #18 aresh

• It's a 16-Bit World!

Reputation: 273
• Posts: 4,258
• Joined: 08-January 12

## Re: Fibonacci challenge

Posted 20 August 2012 - 03:28 AM

The most easy ways to do this are by loops, like Blaylok has done and by using recursion, which many people have done.

### #19 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: Fibonacci challenge

Posted 20 August 2012 - 04:14 AM

IngeniousHax, on 02 August 2012 - 09:26 PM, said:

Very nice BetaWar, i dig that solution. I believe my solution takes quadratic time to complete (N^2)...

Exponential time is more like it.

EDIT: Yep, GWatt already said it.

Oh wth this is my entry, I'd probably do it like Baylok, but for the sake of variation here is another one.
Spoiler

This post has been edited by mostyfriedman: 20 August 2012 - 05:01 AM

### #20 lukeme99

Reputation: 0
• Posts: 85
• Joined: 15-March 11

## Re: Fibonacci challenge

Posted 25 September 2012 - 11:32 AM

Hmmm... This may be a little late, but this is pretty damn short!

```#include <iostream>

using namespace std;

int n = 0;
int x = 1;

int main()
{

while(x <  2000000000)
{
if(n < 1000000000)
{
n = x+n; // No DAMN idea how this works,
x = n-x; // But it somehow does!

cout << n << endl;
}
}
}

```

This post has been edited by lukeme99: 25 September 2012 - 12:01 PM

### #21 aresh

• It's a 16-Bit World!

Reputation: 273
• Posts: 4,258
• Joined: 08-January 12

## Re: Fibonacci challenge

Posted 25 September 2012 - 11:47 AM

Bah, this can never compile.
```while(x <  2000000000)
{
else if(n < 1000000000)
{

```

You write else if, but an if statement is missing.

This post has been edited by aresh: 25 September 2012 - 11:47 AM

### #22 lukeme99

Reputation: 0
• Posts: 85
• Joined: 15-March 11

## Re: Fibonacci challenge

Posted 25 September 2012 - 11:50 AM

aresh, on 25 September 2012 - 07:47 PM, said:

Bah, this can never compile.
```while(x <  2000000000)
{
else if(n < 1000000000)
{

```

You write else if, but an if statement is missing.

Oops, that was left in from a bulkyer code, I edited it to if.

### #23 aresh

• It's a 16-Bit World!

Reputation: 273
• Posts: 4,258
• Joined: 08-January 12

## Re: Fibonacci challenge

Posted 25 September 2012 - 11:52 AM

Well, also, you will get another error. You use Sleep() function, but you don't have windows.h included. So, another error

### #24 Skydiver

• Code herder

Reputation: 6164
• Posts: 21,263
• Joined: 05-May 12

## Re: Fibonacci challenge

Posted 25 September 2012 - 12:22 PM

The challenge was to write a Fibonacci function, not just print out the series. The point is that if I pass in a value i to the function, the function will return to me, as an integer, the i-th Fibonacci number.

### #25 mojo666

Reputation: 408
• Posts: 882
• Joined: 27-June 09

## Re: Fibonacci challenge

Posted 25 September 2012 - 12:46 PM

Quote

n = x+n; // No DAMN idea how this works,
x = n-x; // But it somehow does!

Spoiler

### #26 lukeme99

Reputation: 0
• Posts: 85
• Joined: 15-March 11

## Re: Fibonacci challenge

Posted 26 September 2012 - 10:07 AM

mojo666, on 25 September 2012 - 08:46 PM, said:

Quote

n = x+n; // No DAMN idea how this works,
x = n-x; // But it somehow does!

Spoiler

Thank you so much, it makes more sense now!

### #27 jjl

• Engineer

Reputation: 1270
• Posts: 4,998
• Joined: 09-June 09

## Re: Fibonacci challenge

Posted 27 September 2012 - 03:39 PM

uses template meta programming to calculate the fibonacci sequence, and then adds it to a look up table at run time.

```#include <iostream>
#include <vector>

template<int N> struct meta_fib {
enum { val = meta_fib<N-1>::val + meta_fib<N-2>::val };
vec.push_back(val);
}
};

template<> struct meta_fib<0> {
enum { val = 0 };
vec.push_back(val);
}
};

template<> struct meta_fib<1> {
enum { val = 1 };
vec.push_back(val);
}
};

int fib(int n, std::vector<int> &fib_table) {
return fib_table[n];
}

int main() {
static std::vector<int> ft;

for(int i=0; i<=45; i++)
std::cout<<"F("<<i<<") = "<<fib(i, ft)<<std::endl;

std::cin.ignore();
std::cin.get();
return 0;
}

```

This post has been edited by jjl: 27 September 2012 - 03:43 PM

### #28 CY5

• D.I.C Regular

Reputation: 17
• Posts: 413
• Joined: 28-September 12

## Re: Fibonacci challenge

Posted 28 September 2012 - 08:32 AM

Code for Fibonacci series.

Code for Fibonacci series.

```#include<iostream.h>
#include<conio.h>
int main()
{
clrscr();
long j=1,l=0;
for(int k=1;k<45;k++)
{
j=j+l;
l=j-l;
cout<<j<<" ";
}
getch();
return 0;
}

```

### #29 aresh

• It's a 16-Bit World!

Reputation: 273
• Posts: 4,258
• Joined: 08-January 12

## Re: Fibonacci challenge

Posted 28 September 2012 - 08:32 AM

Oh wow, a TC++ code, which is non-indented. Awesome!

This post has been edited by aresh: 28 September 2012 - 08:33 AM

### #30 rfs02

Reputation: 26
• Posts: 70
• Joined: 30-September 12

## Re: Fibonacci challenge

Posted 01 October 2012 - 09:37 PM

Keep track of all fib numbers that we calculated over time. In the case of this example, where you calculate the fib numbers in reverse, the performance works out great.

Spoiler