Fibonacci challenge

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

31 Replies - 25447 Views - Last Post: 09 June 2014 - 03:02 AM

#16 GWatt  Icon User is offline

  • member icon

Reputation: 269
  • View blog
  • Posts: 3,067
  • Joined: 01-December 05

Re: Fibonacci challenge

Posted 02 August 2012 - 12:53 PM

View PostIngeniousHax, 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)
Was This Post Helpful? 0
  • +
  • -

#17 Blaylok  Icon User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#18 aresh  Icon User is offline

  • It's a 16-Bit World!
  • member icon

Reputation: 273
  • View blog
  • Posts: 4,163
  • 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.
Was This Post Helpful? 0
  • +
  • -

#19 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Fibonacci challenge

Posted 20 August 2012 - 04:14 AM

View PostIngeniousHax, 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

Was This Post Helpful? 0
  • +
  • -

#20 lukeme99  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#21 aresh  Icon User is offline

  • It's a 16-Bit World!
  • member icon

Reputation: 273
  • View blog
  • Posts: 4,163
  • 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

Was This Post Helpful? 0
  • +
  • -

#22 lukeme99  Icon User is offline

  • D.I.C Head

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

Re: Fibonacci challenge

Posted 25 September 2012 - 11:50 AM

View Postaresh, 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.
Was This Post Helpful? 0
  • +
  • -

#23 aresh  Icon User is offline

  • It's a 16-Bit World!
  • member icon

Reputation: 273
  • View blog
  • Posts: 4,163
  • 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 :P
Was This Post Helpful? 0
  • +
  • -

#24 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3534
  • View blog
  • Posts: 10,941
  • 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.
Was This Post Helpful? 0
  • +
  • -

#25 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • 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

Was This Post Helpful? 2
  • +
  • -

#26 lukeme99  Icon User is offline

  • D.I.C Head

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

Re: Fibonacci challenge

Posted 26 September 2012 - 10:07 AM

View Postmojo666, 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!
Was This Post Helpful? 0
  • +
  • -

#27 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1072
  • View blog
  • Posts: 4,532
  • 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 };
   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

Was This Post Helpful? 1
  • +
  • -

#28 CY5  Icon User is offline

  • D.I.C Regular

Reputation: 12
  • View blog
  • Posts: 348
  • 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;
}


Was This Post Helpful? 0
  • +
  • -

#29 aresh  Icon User is offline

  • It's a 16-Bit World!
  • member icon

Reputation: 273
  • View blog
  • Posts: 4,163
  • 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

Was This Post Helpful? 0
  • +
  • -

#30 rfs02  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 26
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3