Data structure and algorithm

/** * @author Jane Programmer * @cwid 123 45 678 * @class COSC 2336, Spring 2019 * @ide Visual Studio Community 2017 * @date January 12, 2019 * @assg Assignment 04 * * @description Assignment 04 Practice defining recursive functions. We * implement factorial and counting combinations functions using the * binomial coefficient in this assignment. This file containts unit * tests of the required functions for this assignment. */ #include <iostream> #include <cassert> #include <chrono> // measure elapsed time of functions using high resolution clock #include "BinomialFunctions.hpp" using namespace std; /** main * The main entry point for this program. Execution of this program * will begin with this main function. * * @param argc The command line argument count which is the number of * command line arguments provided by user when they started * the program. * @param argv The command line arguments, an array of character * arrays. * * @returns An int value indicating program exit status. Usually 0 * is returned to indicate normal exit and a non-zero value * is returned to indicate an error condition. */ int main(int argc, char** argv) { // test iterative version of factorial cout << "Testing iterative version factorialIterative() " << endl; cout << "-------------------------------------------------------------" << endl; bigint res; //res = factorialIterative(0); //cout << "Test base case: factorialIterative(0) = " << res << endl; //assert(res == 1); //res = factorialIterative(1); //cout << "Test edge case: factorialIterative(1) = " << res << endl; //assert(res == 1); //res = factorialIterative(-1); //cout << "Test error case: factorialIterative(-1) = " << res << endl; //assert(res == 1); //res = factorialIterative(10); //cout << "Test general case: factorialIterative(10) = " << res << endl; //assert(res == 3628800); //res = factorialIterative(12); //cout << "Test general case (largest 32 bit int): factorialIterative(12) = " << res << endl; //assert(res == 479001600); //res = factorialIterative(20); //cout << "Test general case (largest 64 bit int): factorialIterative(20) = " << res << endl; //assert(res == 2432902008176640000); // timing test for factorialIterative, do it 10000 times and see how much time // elapses // https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c-- const int NUM_TIMING_LOOPS = 10000; //auto start = chrono::high_resolution_clock::now(); //for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++) //{ // res = factorialIterative(20); //} //auto finish = chrono::high_resolution_clock::now(); //chrono::duration<double> elapsed = finish - start; //cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of factorialIterative(20) " // << elapsed.count() << endl; // test recursive version of factorial cout << endl; cout << "Testing recursive version factorialRecursive() " << endl; cout << "-------------------------------------------------------------" << endl; //res = factorialRecursive(0); //cout << "Test base case: factorialRecursive(0) = " << res << endl; //assert(res == 1); //res = factorialRecursive(1); //cout << "Test edge case: factorialRecursive(1) = " << res << endl; //assert(res == 1); //res = factorialRecursive(-1); //cout << "Test error case: factorialRecursive(-1) = " << res << endl; //assert(res == 1); //res = factorialRecursive(10); //cout << "Test general case: factorialRecursive(10) = " << res << endl; //assert(res == 3628800); //res = factorialRecursive(12); //cout << "Test general case (largest 32 bit int): factorialRecursive(12) = " << res << endl; //assert(res == 479001600); //res = factorialRecursive(20); //cout << "Test general case (largest 64 bit int): factorialRecursive(20) = " << res << endl; //assert(res == 2432902008176640000); //cout << "Test equivalence of iterative and recursive solutions from n=0 to 20: " << endl; //for (int n = 0; n <= 20; n++) //{ // cout << " Testing n = " << n << "..."; // assert(factorialIterative(n) == factorialRecursive(n)); // cout << " passed" << endl; //} // timing test for factorialRecursive, do it 10000 times and see how much time // elapses // https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c-- //start = chrono::high_resolution_clock::now(); //for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++) //{ // res = factorialRecursive(20); //} //finish = chrono::high_resolution_clock::now(); //elapsed = finish - start; //cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of factorialRecursive(20) " // << elapsed.count() << endl; // test direct calculation version of counting combinations cout << endl; cout << "Testing combinations countCombinationsDirectly() " << endl; cout << "-------------------------------------------------------------" << endl; int i; int n; //n=5; i=0; //res = countCombinationsDirectly(n, i); //cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 1); //n=5; i=5; //res = countCombinationsDirectly(n, i); //cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 1); //n=0; i=0; //res = countCombinationsDirectly(n, i); //cout << "Test edge case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 1); //n=5; i=1; //res = countCombinationsDirectly(n, i); //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 5); //n=4; i=2; //res = countCombinationsDirectly(n, i); //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 6); //n=15; i=6; //res = countCombinationsDirectly(n, i); //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 5005); //n=15; i=14; //res = countCombinationsDirectly(n, i); //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 15); // max factorial using bigint //n=20; i=10; //res = countCombinationsDirectly(n, i); //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 184756); // timing test for countCobminationsDirectory, do it 10000 times and see how much time // elapses // https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c-- //start = chrono::high_resolution_clock::now(); //for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++) //{ // n=20; i=10; // res = countCombinationsDirectly(n, i); //} //finish = chrono::high_resolution_clock::now(); //elapsed = finish - start; //cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of countCombinationsDirectly(" // << "n=" << n << " choose i=" << i << ") :" // << elapsed.count() << endl; // test recursive calculation version of counting combinations cout << endl; cout << "Testing combinations countCombinationsRecursive() " << endl; cout << "-------------------------------------------------------------" << endl; //n=5; i=0; //res = countCombinationsRecursive(n, i); //cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 1); //n=5; i=5; //res = countCombinationsRecursive(n, i); //cout << "Test base case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 1); //n=0; i=0; //res = countCombinationsRecursive(n, i); //cout << "Test edge case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 1); //n=5; i=1; //res = countCombinationsRecursive(n, i); //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 5); //n=4; i=2; //res = countCombinationsRecursive(n, i); //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 6); //n=15; i=6; //res = countCombinationsRecursive(n, i); //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 5005); //n=15; i=14; //res = countCombinationsRecursive(n, i); //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 15); // max factorial using bigint //n=20; i=10; //res = countCombinationsRecursive(n, i); //cout << "Test general case: n=" << n << " choose i=" << i << ": " << res << endl; //assert(res == 184756); //cout << "Test equivalence of iterative and recursive solutions for counting combinations" << endl // << "This is an exhaustive test of all combinations of n and i from 0 to 15" << endl; //for (n = 0; n <= 15; n++) //{ // for (i = 0; i <= n; i++) // { // cout << " Testing (n=" << n << " choose i=" << i << ") equivalence..."; // assert(countCombinationsDirectly(n, i) == countCombinationsRecursive(n, i)); // cout << " passed" << endl; // } //} // timing test for countCobminationsRecursive, do it 10000 times and see how much time // elapses // https://www.pluralsight.com/blog/software-development/how-to-measure-execution-time-intervals-in-c-- //start = chrono::high_resolution_clock::now(); //for (int testnum = 0; testnum < NUM_TIMING_LOOPS; testnum++) //{ // n=20; i=10; // res = countCombinationsRecursive(n, i); //} //finish = chrono::high_resolution_clock::now(); //elapsed = finish - start; //cout << "Elapsed time " << NUM_TIMING_LOOPS << " loops of countCombinationsRecursive(" // << "n=" << n << " choose i=" << i << ") :" // << elapsed.count() << endl; // return 0 to indicate successful completion return 0; }