I need a little help, I'm still new to the C++ stuff and this is for my class. Any help anyone could give me would be great.
the code I have is as follows:
____________________________________________________________________________

``````#include <iostream>
using namespace std;

int find_fib(int);

int main(int argc, char* argv[])
{
int n=0, result=0;
cout << "Enter the position in the sequence to find: ";
cin >> n;
result = find_fib( n );
cout << result << " is the " << n << "th Fibonacci sequence number" << endl;
system("pause");
return 0;
}

int find_fib( int n )
{
if(n < 3)
return 1;
else
return( find_fib(n - 2) + find_fib( n - 1 ) );
}``````
5
Contributors
7
Replies
8
Views
9 Years
Discussion Span
Last Post by Salem

1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 2! x 3 = 6
N! = 1 x 2 x 3 x .... (N-2) x (N-1) x N = (N-1)! x N

Could this help?

A guess:

``````int theFact = 1;
for(int i=N; i>0; i--)
{
theFact *= i;
}

return theFact;``````

Did you want to try and do a non-recursive factorial or a non-recursive way to compute the fibonacci ? Please put tags around your code.

And for a non-recursive fibonacci. You could do something like this

``````int fib(int n){

int previous = -1;
int result   = 1;
int sum;

for(int i = 0; i <= n; i++){
sum = previous + result;
previous = result;
result   = sum;
}

return result;
}``````

Hallo
I post u a solution to your problem divided into three parts:

Part A: Includes your solution exactly the way you posted it. However it is an inefficient recursive solution, because it has an exponential performance.
Part B: Includes an optimized recursive solution using the help of a wrapper function which results into a O(n) performance.
Part C: Includes an non-recursive (iterative) solution.

In addition i measure the execution time for all three of them.
U can notice like expected that Part A is a bad solution.....
see here the results for finding the 42th Fibonacci number:

Enter the position in the sequence to find: 42
A: Your function gives: 267914296 is the 42th Fibonacci sequence number
The execution time of the PART A is = 4563 msecs
B: Optimized function gives: 267914296 is the 42th Fibonacci sequence number
The execution time of the PART B is = 0 msecs
C: Iterative function gives: 267914296 is the 42th Fibonacci sequence number
The execution time of the PART C is = 0 msecs

So here is the code (no errors or warnings):

``````#include <iostream>
#include <ctime> //for calculating execution time

double diffclock(time_t ,time_t ); //for calculating execution time
int find_fib(int);
unsigned long double fibWrapper(int);
unsigned long double fibo_find_2 (unsigned long double, unsigned long double, int);
unsigned long double fibo_find_3_NonRecursive(int);

int main(int argc, char* argv[])
{
//Required for measuring execution perfomance
time_t startTime1,endTime1,startTime2;
time_t endTime2,startTime3,endTime3;
double elapsedTime1,elapsedTime2,elapsedTime3;

int n=0;
unsigned long double result=0;
std::cout << "Enter the position in the sequence to find: ";
std::cin >> n;

//PART A:
startTime1 = clock();	//Start measuring execution time
result = find_fib(n);
endTime1 = clock();	//Stop measuring execution time
//Get total execution time in msec
elapsedTime1 = diffclock(endTime1,startTime1);
std::cout <<"A: Your function gives: "<< result << " is the "
<< n << "th Fibonacci sequence number" << std::endl;
std::cout<<"The execution time of the PART A is = "<<elapsedTime1
<<" msecs"<<std::endl;
result = 0;

//PART B:
startTime2 = clock();	//Start measuring execution time
result = fibWrapper(n);
endTime2 = clock();	//Stop measuring execution time
//Get total execution time in msec
elapsedTime2 = diffclock(endTime2,startTime2);
std::cout <<"B: Optimized function gives: " <<result << " is the "
<< n << "th Fibonacci sequence number" << std::endl;
std::cout<<"The execution time of the PART B is = "<<elapsedTime2
<<" msecs"<<std::endl;
result = 0;

//PART C:
startTime3 = clock();	//Start measuring execution time
result = fibo_find_3_NonRecursive(n);
endTime3 = clock();	//Stop measuring execution time
//Get total execution time in msec
elapsedTime3 = diffclock(endTime3,startTime3);
std::cout <<"C: Iterative function gives: " <<result << " is the "
<< n << "th Fibonacci sequence number" << std::endl;
std::cout<<"The execution time of the PART C is = "<<elapsedTime3
<<" msecs"<<std::endl;

return 0;
}
// PART A:
//Your recursive solution: Correct BUT VERY INEFFICIENT exponential performance
unsigned long double find_fib( int n )
{
if(n < 3)
return 1;
else
return( find_fib(n - 2) + find_fib( n - 1 ) );
}

//PART B:
//Optimized recursive solution: Correct and with O(n) performance
unsigned long double fibo_find_2(unsigned long double fibCurr,unsigned long double fibPrev, int n) //is called indirectly throuth the wrapper function
{
//fibCurr: the current fibonacci Number
//fibPrev: the previous fibonacci number
//n: the number of the fibonacci numbers left to calculate
if(n == 1)
return fibCurr;
else
return fibo_find_2(fibCurr+fibPrev,fibCurr, n-1);
}
//The wrapper function for calculating fibonacci numbers
unsigned long double fibWrapper (int n)
{
//returns the value of the nth fibonacci number
return fibo_find_2(1, 0, n);
}

//PART C:
////Non recursive==Iterative solution
unsigned long double fibo_find_3_NonRecursive (int n)
{
unsigned long double localresult = 1;
unsigned long double temp1 = 1;
unsigned long double temp2 = 0;

for (int k=3;k<=n;k++)
{
temp2 = localresult;
localresult +=  temp1;
temp1 = temp2;
}
return localresult;
}
//Nedded for calculating the execution time
double diffclock(time_t clock1,time_t clock2) //Using time_t & difftime
{
double diffticks=difftime(clock1,clock2);
double diffms=(diffticks)/(CLOCKS_PER_SEC/1000);
return diffms;
}``````

NOTE: if sbdy thinks that the way I calculate the execution time is inaccurate please provide an optimized and tested alternative. I tested on my machine with ACE timers but I think its not an solution available for all people.

Which compiler allows the nonsense "unsigned long double" as a declaration?

Votes + Comments
XD

Strangely MSVC++ 2008 does allow it .. although gcc does not.

Come on guys
It was "long Double" just used the "replace all" replacing "long" with "unsigned long" having not noticed the double there... ;) ;)
and like u correctly said in VS 2008 gave me the compiler no clue to notice that...

But what about the rest
Is it also nonsense:@ ????

Rest seems fine.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.