Search code examples
c++recursioniterationfibonaccitiming

maxi and min times to calculate the Fibonacci numbers for six seperate runs at n


The wording for this problem has me completely confused. I know how to get "timing" using GetTickCount() but I have to repeat the calculation 6 times for each N and I have to have 6 different N and the results have to be reported in one table as max an min times. It seams to me as though this is not feasible because the run time for one N is not going to be the run time for another N. Any help is greatly appreciated. Ill post the original question below.

EDIT*: My own Frazzled brain was over complicating the problem! I got it figured out now Thanks to everyone who took time to try and help out!

'Your task is to find the maximum and minimum execution times of the Fibonacci number computation routines for six separate, unique runs at each value of n. NOTE: do not use the tail recursion implementation.'

I was thinking of perhaps storing the average run time values in arrays and then sorting those arrays to get the min and max and doing that 6 different times for both the min and max for iterative and recursive but that takes something like 24 arrays which just seems pointless.


Solution

  • For each input N, you need to calculate Fibb(N) six times, and display the minimum and maximum of those times. You display one minimum per N, and one maximum per N. Does it help to imagine that there are 100 N, and each one is calculated 6 times? You'd expect to see 100 minimums and 100 maximums.

    For many simple competitions or homework, it looks vaguely like this:

    while(std::cin >> N) {
       int duration[6] = {};
       int result = 0;
       for(int i=0; i<6; ++i) {
           auto start = GetTickCount();
           int result = Fib(N);
           auto end = GetTickCount();
           duration[i] = end-start;
       }
       int max = std::max_element(std::begin(duration), std::end(duration));
       int min = std::min_element(std::begin(duration), std::end(duration));
       std::cout<<"Fib("<<N<<")="<<result<<" max="<<max<<" min="<<min<<'\n';
    }