[GWatt]

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)

[Blaylok]

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

#include <iostream.h>

void main()
{ 
  int n; double a=1, b=1, c;
  
  cout << "Please enter the number of terms: ";
  cin >> n;
  
  if (n==1)
  {
     cout << "1";
  }
  else if(n==2)
  { 
     cout << "1\t1";
  }
  else
  {
     cout << "1\t1\t";

  for (int i=3; i<=n; i++)
  {  
     
     c=a+b;
     cout << c << "\t";
     a=b;
     b=c;  
  }
  }
}

---

Hope that works!

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

[aresh]

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

[mostyfriedman]

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

#include<iostream>
#include<vector>

using namespace std;

vector<unsigned> memo;

unsigned fib(int);

int main()
{
	for(int i  = 0; i < 20; i++)
		memo.push_back(0);
	for(int i  = 0; i < 20; i++)
		cout << fib(i) << " ";
	cout << endl;
	return 0;
}

unsigned fib(int n)
{
	if(n == 0 || n == 1)
		return n;
	return memo[n] ? memo[n] : (memo[n] = fib(n-1)+fib(n-2));
}

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

[lukeme99]

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

[aresh]

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

[lukeme99]

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.

[aresh]

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

[Skydiver]

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.

[mojo666]

Quote

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

Spoiler

If f(n+1)=f(n)+f(n-1) then we can say that f(n)=f(n+1)-f(n-1)

int x=0; //f(n), currently f(0)
int y=1; //f(n-1), currently f(-1)?
.
.
//Loops
.
.
//right now, x has f(n) and y has f(n-1)
x = y+x; // calculates f(n+1) from f(n-1)+f(n) and stores result in x.  We no longer have f(n)
//x currently has f(n+1), y has f(n-1)
y = x-y; // calculates f(n) from f(n+1) and f(n-1)
//ready for the next iteration of finding f(x+2) since x has f(n+1) and y has f(n)

It might be clearer if you print out both variables at the end of each iteration

x y
0 1
1 0
1 1
2 1
3 2
5 3
8 5

[lukeme99]

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

If f(n+1)=f(n)+f(n-1) then we can say that f(n)=f(n+1)-f(n-1)

int x=0; //f(n), currently f(0)
int y=1; //f(n-1), currently f(-1)?
.
.
//Loops
.
.
//right now, x has f(n) and y has f(n-1)
x = y+x; // calculates f(n+1) from f(n-1)+f(n) and stores result in x.  We no longer have f(n)
//x currently has f(n+1), y has f(n-1)
y = x-y; // calculates f(n) from f(n+1) and f(n-1)
//ready for the next iteration of finding f(x+2) since x has f(n+1) and y has f(n)

It might be clearer if you print out both variables at the end of each iteration

x y
0 1
1 0
1 1
2 1
3 2
5 3
8 5

Thank you so much, it makes more sense now!

[jjl]

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 };
   static void add(std::vector<int> &vec) {
      meta_fib<N-1>::add(vec);
      vec.push_back(val);
   }
};

template<> struct meta_fib<0> {
   enum { val = 0 };
   static void add(std::vector<int> &vec) {
      vec.push_back(val);
   }
};

template<> struct meta_fib<1> {
   enum { val = 1 };
   static void add(std::vector<int> &vec) {
      meta_fib<0>::add(vec);
      vec.push_back(val);
   }
};



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

int main() {
   static std::vector<int> ft;
   meta_fib<45>::add(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

[CY5]

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;
}

Attached File(s)

•  FIBONNAC.txt (164bytes)
  Number of downloads: 21

[aresh]

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

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

[rfs02]

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

#include "stdafx.h"
#include <map>

using namespace std;

map<int, long> fibonacci;

long Fib(int i)
{
	if (i < 1) return 0;
	if (i == 1) return 1;

	if (fibonacci.find(i) == fibonacci.end())
	{
		fibonacci[i] = Fib(i - 1) + Fib(i - 2);
	}
	
	return fibonacci[i];
}

int main(int argc, char* argv[])
{
	for (int i=0; i <= 45; i++)
		printf("%4i => %i\n", i, Fib(i));
	return 0;
}