DaniWeb Forum Index > Software Development > C++

C++ RSS

fibonacci

Please support our C++ advertiser: Intel Parallel Studio Home

Thread Solved

•

Join Date: Jun 2006

Posts: 1,169

Reputation: Duki has a spectacular aura about

Solved Threads: 9

Duki

Offline

Veteran Poster

fibonacci

Oct 24th, 2007

Hey guys,

I'm supposed to write a program that will calculate the Nth fibonacci number, without using recursion.

I have the recursion problem written already, but am having a hard time doing the iterative one.

here's my recursion function:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int fib ( int n )
{
    if ( n <= 1 )
        return 1 ;
    else
        return ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;
}
int fib ( int n )
{
    if ( n <= 1 )
        return 1 ;
    else
        return ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;
}

any help with getting me started on the iterative one?

It is practically impossible to teach good programming style to students that have had prior exposure to Basic; as potential programmers they are mentally mutilated beyond hope of regeneration.

-Edsger Dijkstra

•

Join Date: Jun 2006

Posts: 1,169

Reputation: Duki has a spectacular aura about

Solved Threads: 9

Duki

Offline

Veteran Poster

Re: fibonacci

Oct 24th, 2007

Nevermind, I got it working. Didn't think to use an array; well I thought about it, but didn't think it would make the problem easier. Here's my fibonacci sequence, written iteratively.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
using namespace std ;
 
int main ( )
{
    int fibArray[25] ; //max fib number
    fibArray[0] = 1 ;
    fibArray[1] = 1 ;
 
    for ( int i = 2 ; i < 25 ; i ++ )
        fibArray[ i ] = fibArray[ i - 1 ] + fibArray[ i - 2 ] ;
 
    cout << fibArray[4] << "\t" << fibArray[7] << "\t" << fibArray[24] << endl ;
 
    return 0 ;
}
#include <iostream>
using namespace std ;

int main ( )
{
    int fibArray[25] ; //max fib number
    fibArray[0] = 1 ;
    fibArray[1] = 1 ;

    for ( int i = 2 ; i < 25 ; i ++ )
        fibArray[ i ] = fibArray[ i - 1 ] + fibArray[ i - 2 ] ;

    cout << fibArray[4] << "\t" << fibArray[7] << "\t" << fibArray[24] << endl ;

    return 0 ;
}

•

Join Date: Aug 2007

Posts: 1,679

Reputation: vmanes is a splendid one to behold

Solved Threads: 193

vmanes

Offline

Posting Virtuoso

Re: fibonacci

Oct 24th, 2007

Your array based solution is limiting in that you have set the array size to the number of values to display.

What about a purely iterative solution, that does not need the excess memory, and is not logically limited in the number of values to display?

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
using namespace std ;
 
int main ( )
{
    unsigned int fib ; //current fibonnaci value
    unsigned int n1 = 1 ;
    unsigned int n2 = 1 ;
 
    int max_fib;
 
     cout << "Enter number of term for Fibonacci series: " ;
     cin >> max_fib;
 
    cout << n1 << '\t' << n2 << '\t';
 
    for ( int i = 2 ; i < max_fib; i ++ )
	{
		fib = n1 + n2;
		n1 = n2;
		n2 = fib;
	        cout << fib <<  "\t" ;
 
		if( i % 5 == 0 )	//five numbers per line
			cout << endl;
	}
 
    return 0 ;
}
#include <iostream>
using namespace std ;

int main ( )
{
    unsigned int fib ; //current fibonnaci value
    unsigned int n1 = 1 ;
    unsigned int n2 = 1 ;

    int max_fib;

     cout << "Enter number of term for Fibonacci series: " ;
     cin >> max_fib;

    cout << n1 << '\t' << n2 << '\t';

    for ( int i = 2 ; i < max_fib; i ++ )
	{
		fib = n1 + n2;
		n1 = n2;
		n2 = fib;
	        cout << fib <<  "\t" ;

		if( i % 5 == 0 )	//five numbers per line
			cout << endl;
	}

    return 0 ;
}

Everyone's gotta believe in something. I believe I'll have another drink.
~~~~~~~~~~~~~~~~~~
Looking for an exciting graduate degree? Robotics and Intelligent Autonomous Systems (RIAS) at SDSM&T See the program brochure here.

•

Join Date: Oct 2007

Posts: 62

Reputation: Ptolemy is an unknown quantity at this point

Solved Threads: 8

Ptolemy

Offline

Junior Poster in Training

Re: fibonacci

Oct 24th, 2007

>What about a purely iterative solution, that does not need the excess
>memory, and is not logically limited in the number of values to display?
That's fine for just printing the sequence. The array is more open to extension though. Let's say you want to write fib(x) where x is the number and the function returns $F^N$ . With the array you can do this:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int fib ( int x )
{
  static const int max = 25;
  static int n = 2;
  static int fibArray[max] = {1,1};
 
  while ( n < x ) {
    fibArray[n] = fibArray[n - 1] + fibArray[n - 2];
    ++n;
  }
 
  return fibArray[x];
}
int fib ( int x )
{
  static const int max = 25;
  static int n = 2;
  static int fibArray[max] = {1,1};

  while ( n < x ) {
    fibArray[n] = fibArray[n - 1] + fibArray[n - 2];
    ++n;
  }

  return fibArray[x];
}

At the (minor, in this case) cost of extra storage, you avoid recalculating parts of the sequence that you've already calculated. That's the principle behind the dynamic recursive algorithm.

•

Join Date: Jun 2006

Posts: 1,169

Reputation: Duki has a spectacular aura about

Solved Threads: 9

Duki

Offline

Veteran Poster

Re: fibonacci

Oct 24th, 2007

seeing as this is being discussed still, I would like to pose another question: How do I use an array using recursion? This will be more efficient, no? Here is my current code:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
using namespace std ;
 
int fib ( int ) ;
 
int main ( )
{
int i = fib ( 5 ) ;
cout << i << endl ;
 
return 0 ;
}
 
int fib ( int n )
{
int fibArray [ const n ] ;
 
if ( <= 1 )
return 1 ;
else
{
fibArray[ 0 ] = 1 ;
fibArray[ 1 ] = 1 ;
 
for ( int i = 2 ; i < 25 ; i++ )
fibArray[ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;
}
 
return fibArray[ n ] ;
}
#include <iostream>
using namespace std ;

int fib ( int ) ;

int main ( )
{
int i = fib ( 5 ) ;
cout << i << endl ;

return 0 ;
}

int fib ( int n )
{
int fibArray [ const n ] ;

if ( <= 1 )
return 1 ;
else
{
fibArray[ 0 ] = 1 ;
fibArray[ 1 ] = 1 ;

for ( int i = 2 ; i < 25 ; i++ )
fibArray[ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;
}

return fibArray[ n ] ;
}

Last edited by Duki; Oct 24th, 2007 at 9:31 pm.

•

Join Date: Jun 2006

Posts: 1,169

Reputation: Duki has a spectacular aura about

Solved Threads: 9

Duki

Offline

Veteran Poster

Re: fibonacci

Oct 24th, 2007

•

Originally Posted by Duki

seeing as this is being discussed still, I would like to pose another question: How do I use an array using recursion? This will be more efficient, no? Here is my current code:
Help with Code Tags

C++ Syntax (Toggle Plain Text)
#include <iostream>
using namespace std ;
 
int fib ( int ) ;
 
int main ( )
{
int i = fib ( 5 ) ;
cout << i << endl ;
 
return 0 ;
}
 
int fib ( int n )
{
int fibArray [ const n ] ;
 
if ( <= 1 )
return 1 ;
else
{
fibArray[ 0 ] = 1 ;
fibArray[ 1 ] = 1 ;
 
for ( int i = 2 ; i < 25 ; i++ )
fibArray[ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;
}
 
return fibArray[ n ] ;
}
#include <iostream> using namespace std ; int fib ( int ) ; int main ( ) { int i = fib ( 5 ) ; cout << i << endl ; return 0 ; } int fib ( int n ) { int fibArray [ const n ] ; if ( <= 1 ) return 1 ; else { fibArray[ 0 ] = 1 ; fibArray[ 1 ] = 1 ; for ( int i = 2 ; i < 25 ; i++ ) fibArray[ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ; } return fibArray[ n ] ; }

why can i not do int fibArray [ n ] ? It says "expected constant"

•

Join Date: Aug 2007

Posts: 1,679

Reputation: vmanes is a splendid one to behold

Solved Threads: 193

vmanes

Offline

Posting Virtuoso

Re: fibonacci

Oct 25th, 2007

That's a compiler dependent problem now.

Previously, any declaration of a local array had to be done with a constant expression as the size. The latest C standard (C99) has changed that restriction, but not all compilers have adopted that. And remember, the C++ standard includes the C standard, more or less.

So, legally speaking:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int size = 5;
int arr[size];
int size = 5;
int arr[size];

is now a legitimate construct. Current version of gcc supports this. Visual C++ does not.

Now I have to go change my lesson plans.....
Val

•

Join Date: Jun 2006

Posts: 1,169

Reputation: Duki has a spectacular aura about

Solved Threads: 9

Duki

Offline

Veteran Poster

Re: fibonacci

Oct 25th, 2007

Ok, I got it to work using a pointer. Here's my code.

 Help with Code Tags 
(Toggle Plain Text)
 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
#include <ctime>
#include <iostream>
using namespace std ;
 
int fib ( int ) ;
 
int main ( )
{
    clock_t start ;
    clock_t end ;
 
    cout << "Beginning timer..." << endl ;
    start = clock() ;
 
    cout << endl ;
    for ( int k = 0 ; k < 12 ; k++ )
    {
    int i = fib ( k ) ;
    cout << i << "\t" ;
    }
 
    cout << endl ;
 
    end = clock() ;
    cout << "\nThe calculation took " << ( double ( end ) - start ) / CLOCKS_PER_SEC << " seconds.\n" ;
 
    cout << "\n\n-- Done --\n\n" ;
 
    return 0 ;
}
 
int fib ( int n )
{
    int * fibArray = new int[ n ] ;
 
    if ( n <= 1 )
        return 1 ;
    else
    {
        fibArray[ 0 ] = 1 ;
        fibArray[ 1 ] = 1 ;
 
        for ( int i = 2 ; i <= n ; i++ )
        fibArray [ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;
 
    }
 
    return fibArray[ n ] ;
}
#include <ctime>
#include <iostream>
using namespace std ;

int fib ( int ) ;

int main ( )
{
    clock_t start ;
    clock_t end ;

    cout << "Beginning timer..." << endl ;
    start = clock() ;

    cout << endl ;
    for ( int k = 0 ; k < 12 ; k++ )
    {
    int i = fib ( k ) ;
    cout << i << "\t" ;
    }

    cout << endl ;

    end = clock() ;
    cout << "\nThe calculation took " << ( double ( end ) - start ) / CLOCKS_PER_SEC << " seconds.\n" ;

    cout << "\n\n-- Done --\n\n" ;

    return 0 ;
}

int fib ( int n )
{
    int * fibArray = new int[ n ] ;

    if ( n <= 1 )
        return 1 ;
    else
    {
        fibArray[ 0 ] = 1 ;
        fibArray[ 1 ] = 1 ;

        for ( int i = 2 ; i <= n ; i++ )
        fibArray [ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;

    }

    return fibArray[ n ] ;
}
     Help with Code Tags   c++ Syntax (Toggle Plain Text)    #include <ctime>#include <iostream>using namespace std ; int fib ( int ) ; int main ( ){    clock_t start ;    clock_t end ;     cout << "Beginning timer..." << endl ;    start = clock() ;     cout << endl ;    for ( int k = 0 ; k < 12 ; k++ )    {    int i = fib ( k ) ;    cout << i << "\t" ;    }     cout << endl ;     end = clock() ;    cout << "\nThe calculation took " << ( double ( end ) - start ) / CLOCKS_PER_SEC << " seconds.\n" ;     cout << "\n\n-- Done --\n\n" ;     return 0 ;} int fib ( int n ){    int * fibArray = new int[ n ] ;     if ( n <= 1 )        return 1 ;    else    {        fibArray[ 0 ] = 1 ;        fibArray[ 1 ] = 1 ;         for ( int i = 2 ; i <= n ; i++ )        fibArray [ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;     }     return fibArray[ n ] ;} #include <ctime>
#include <iostream>
using namespace std ;

int fib ( int ) ;

int main ( )
{
    clock_t start ;
    clock_t end ;

    cout << "Beginning timer..." << endl ;
    start = clock() ;

    cout << endl ;
    for ( int k = 0 ; k < 12 ; k++ )
    {
    int i = fib ( k ) ;
    cout << i << "\t" ;
    }

    cout << endl ;

    end = clock() ;
    cout << "\nThe calculation took " << ( double ( end ) - start ) / CLOCKS_PER_SEC << " seconds.\n" ;

    cout << "\n\n-- Done --\n\n" ;

    return 0 ;
}

int fib ( int n )
{
    int * fibArray = new int[ n ] ;

    if ( n <= 1 )
        return 1 ;
    else
    {
        fibArray[ 0 ] = 1 ;
        fibArray[ 1 ] = 1 ;

        for ( int i = 2 ; i <= n ; i++ )
        fibArray [ i ] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) ) ;

    }

    return fibArray[ n ] ;
}  

I can't get it to work with numbers >=12; it gives a system error that it failed unexpectedly. I'm guessing it's a stack issue, but is there a way around it? Is my program the best it can be (using recursion and arrays)?

Last edited by Duki; Oct 25th, 2007 at 1:44 am.

•

Join Date: Oct 2007

Posts: 62

Reputation: Ptolemy is an unknown quantity at this point

Solved Threads: 8

Ptolemy

Offline

Junior Poster in Training

Re: fibonacci

Oct 25th, 2007

>And remember, the C++ standard includes the C standard, more or less.
Standard C++ currently maintains compatibility with C89, not C99. So you can't use VLAs in C++

>Is my program the best it can be (using recursion and arrays)?
No. The entire point of using an array with recursion is to avoid recalculating everything all the time. This is especially true with the Fibonacci sequence, where a lot of the numbers have to be recalculated. You use an array, but you don't take advantage of it, so your function is just a slower, more wasteful version of the original recursive algorithm.

What you need is for the array to persist between function calls and be able to tell if a number has been calculated or not. If it has, you don't need to go through the recursive chain. This is where you'll see performance improvements:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
int fib ( int n )
{
  static int fibArray[25] = {0};
 
  if ( n <= 1 )
    return 1;
  else {
    fibArray[0] = 1;
    fibArray[1] = 1;
 
    for ( int i = 2 ; i <= n ; i++ ) {
      if ( fibArray[i] == 0 )
        fibArray[i] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) );
    }
  }
 
  return fibArray[n];
}
int fib ( int n )
{
  static int fibArray[25] = {0};

  if ( n <= 1 )
    return 1;
  else {
    fibArray[0] = 1;
    fibArray[1] = 1;

    for ( int i = 2 ; i <= n ; i++ ) {
      if ( fibArray[i] == 0 )
        fibArray[i] = ( fib ( n - 1 ) + ( fib ( n - 2 ) ) );
    }
  }

  return fibArray[n];
}

•

Join Date: Dec 2005

Posts: 5,850

Reputation: Salem has a reputation beyond repute

Solved Threads: 749

Salem

Offline

Void main'ers are DOOMed

Re: fibonacci

#10

Oct 25th, 2007

> I can't get it to work with numbers >=12; it gives a system error that it failed unexpectedly.
1. You don't free the memory you allocate. Eventually, you'll run out of memory.

2. You run off the end of the memory allocated.
for ( int i = 2 ; i <= n ; i++ )
If you want <= n, then you need to allocate n+1 items.
It was always wrong, you just got caught with your hand in the cookie jar at n >= 12.

3. Unlike Ptolemy's answer, your array serves no purpose.