hi all I'm trying to build a couple of algorithms here for, my advanced data structures course and get the run times however I cant seem to get the clock_t variables to output to the screen at all. check the code
the problem is located in the first loop in the main. Every time I output the variable duration to the screen it shows up as zero. I did a debug on it and according that it shows a value for start and finish. So what is the deal here.Code:#include<iostream> #include<fstream> #include<iomanip> #include <time.h> using namespace std; /************************************************************** PURPOSE: The algorithm works iterativley it takes an input n it then calculates the fibonacci sequence up to that number by adding LastButOne's values and lastValue over and over again until the value of "i" is equal to that of the value of "n". At this point the loop terminates and no longer calculates any more numbers in the fibonacci series. Since the algorithm is being increased by a constant value the growth rate for this algorithm is Big O(N) IteratFib DATA TABLE: n = input for the function to calculate up to the nth fibonacci LastValue = the F(n-1) value to be added lastButone = the F(n-2) value to be added i = The current number to be calculated starting at 2 counter = the number of iterations required to complete answer = the actual calculation of the nth fibonacci number start = a clock t variable to start the timer in each iteration of both algorithms finish = a clock t variable to get the end time of each iteration /***************************************************************/ double IteratFib(double n, double &counter ) { double answer; if( n == 0 || n == 1 ) return n; else { double lastButOne = 0; double lastValue = 1; //for loop to take n and compare it the //variable j. If j is less than that number //the loop then iterates and adds makes the //variable answer equal to LastButOne + lastValue //it then makes LastButone = Last Value or //the Fn-2 it then makes lastValue = Currnent //or Fn-1. These values are saved in each of //these variables to calculate the Fn Fibonacci //number for. It will do this until "n" is //greater than "i". It then exits the loop //and returns the calculated value of the nth //Fibonacci number The loop will do this u //the requested fibonacci number for( int i = 2; i <= n; i++ ) { answer = lastButOne + lastValue; lastButOne = lastValue; lastValue = answer; counter++; } } return answer; } /**************************************************************** PURPOSE: this is the second version of the fibonacci series calculation. This is the recursive version of the program. This function is designed to go up to the nth value which in shis case is 128. The implementation of the program works by solving two previous instances of itself. In this case it is the previous two numbers that are two be added to equal the current fibonacci number. For instance if you would like the fifth fibonacci number it would be obtained by calculating 0,1,1,2,3. So in essence the fifth fibonacci number is obtained by adding the 3rd and the 4th numbers in that series. So the problem doubles each time it is called and you end up with a growth rate that is Big O(2^n) power or an exponential growth rate. fibonacci() DATA TABLE: num = the value that is being used as the base case count = the number of iterations for the function /******************************************************************/ double fibonacci(double num, double &counter) { counter++; //The first if statement is the base case for this program //which checks to see if the number entering the algorithm //is either one or zero. If it is either value it will then //return that number since the Fibonacci of one or zero is //itself. This is the case that will terminate the recusive //calls back to the algorithm. if(num==0 || num ==1) { counter++; return num; } //the other case is if the number is greater than zero or one //it then returns the number minus + the number minus two or //the Fn = Fn-1 + Fn-2. else { return fibonacci(num - 1, counter) + fibonacci(num - 2, counter); } } void main() { /****************************************************************** main DATA TABLE: j = variable being used to determine whether the nth fib counter = the number of iterations that are required for each iteratOut = an ofstream variable to output to text file name "iterout.txt" outfile = an ofstream variable to output to text file named "outfile.txt" m = this variable is to store the calculation of "fibonacci" temp = this variable is to store temporary variables when the user enters a one to start the series of both algorithms *******************************************************************/ ofstream outfile; outfile.open("output.xls", ios::out); ofstream iteratOut; iteratOut.open("iteratData.xls", ios::out); double m; double counter = 0; int temp; clock_t start, finish; double duration; cout<<"This is the iterative version of the Fibonacci Calculation: "<<endl; cout<<endl<<endl; cout<<"Enter '1' to begin: "<<endl; cout<<"From 1-128: "<<endl<<endl; cin>>temp; if(temp!=1) temp=1; //this first for loop is designed to start at 1 and //go up to the 128th fibonacci number using an //iterative fibonacci calculation for (double j=1; j<=128; j++) { //initialize counter to zero cout<< "F(" << j << ") = " <<setw(20)<<setiosflags(ios::left); start=clock(); m=IteratFib(j,counter); finish=clock(); duration = (double)(finish - start)/CLK_TCK; //output the result of the nth fibonacci number cout << fixed<<setprecision(2)<<m; //output that to the screen as well as the counter cout << "\t" << counter <<" Time elapsed : "; cout <<duration<< "\n"; //now output those countents to the file iteratOut << "F("<<j<< ")=" <<setw(20)<<setiosflags(ios::left); iteratOut << fixed<<setprecision(2)<<m; iteratOut << "\t" << counter << "\t"<<duration<<"\n"; counter=0; } //close text file iteratOut.close(); cout <<endl<<endl; //output to screen cout << "This is the Recursive version of fibonacci: "<< endl; //output to file outfile << "RUN TIME AND ANALYSIS OF A RECURSIVE FIBONACCI ALGORITHM" << endl; outfile << "FROM 1 TO 128"<<endl; cout << "Enter '1' to begin: "; //request user to start the sequence of in the recursive version fibonacci() cin >> j; //if else statement user enters something other than 1 if(j!=1) j=1; else { while(j<=128) { //initialize counter to zero for next iteration counter=0; //make "m" the value of the nth fibonacci m=fibonacci(j, counter); //output that value to the screen cout <<"The fibonacci of "<<setprecision(0)<<fixed<<j<<" is "<<m <<endl; //output the number of calls required to do recursive algorithm cout <<"The total number of recursive calls to achieve fibonacci of " << counter <<" is " <<counter<<endl; //output the value and the number of iterations outfile <<"F("<<j<<")= "<<m<<"\t" <<"ITERATIONS"<<"\t"<<counter<<endl; //add one to "j" and get the next version of fibonacci ++j; } } //close output file outfile.close(); //end programs }
Originally Posted by dwks
