Question

The n th Triangle Problem Write a code for finding the n th triangle number of triangle sequences: 1, 3, 6, 10, ..., n. That is, your code should accept an integer number, which indicates the triangle levels, and returns how many dots we need to form a triangle with respect to the given level. For example, consider the Fig 1. For n = 3 (can be also written as T3), your code should returns 6.

Provide a single program consists of the following:

• Write a function called TriangularRecursive for the recursive version that takes number of level as an int argument.

Hints:

1) Identify the base case for the TriangularRecursive function.

2) Let the TriangularRecursive function call itself, with proper arguments.

• Write a function called TriangularIterative for the non-recursive (iterative) version that takes number of level as an int argument.

• Write a main function that calls the two functions inside. You should have at least a couple of test cases included in the main function that shows the output for both functions.

After implementing the recursive and non-recursive functions, you are supposed to perform two additional tasks. The first task is to analyze both approaches as follows:

• Establish the recurrence relations for the recursive approach.

• Solve the recurrence and provide the order growth.

• Establish the sum expression for the non-recursive approach.

• Solve the sum and provide the order growth.

The second task is to plot the running time of both approaches for different input sizes (n). To do that, consider ten input size (n) values: 10, 50, 100, 200, 400, 800, 2000, 4000, 8000, 10000. For better precision, run each value ten times and take the average of all ten runs for each case.

Answer 1

#include <bits/stdc++.h>

using namespace std;

int TriangularRecursive(int n)

{

    if (n > 1)

        return n + TriangularRecursive(n - 1);

    else

        return 1;

}

int TriangularIterative(int n)

{

    int i, sum = 0;

    for (i = 1; i <= n; i++)

        sum = sum + i;

    return sum;

}

void checkCase(void)

{

    int vals[] = {10, 50, 100, 200, 400, 800, 2000, 4000, 8000, 10000};

    int i, j;

    time_t start, end;

    double cpu_time_used;

    for (i = 0; i < 10; i++)

    {

        cpu_time_used = 0.0;

        for (j = 0; j < 10; j++)

        {

            start = clock();

            ios_base::sync_with_stdio(false);

            TriangularIterative(vals[i]);

            end = clock();

            cpu_time_used = (double(end - start)) / double(CLOCKS_PER_SEC) + cpu_time_used;

        }

        cout << "\nCPU time taken with " << vals[i] << " levels using Recursion : " << fixed << cpu_time_used / 10.0 << setprecision(9) << " sec";

    }

    for (i = 0; i < 10; i++)

    {

        cpu_time_used = 0.0;

        for (j = 0; j < 10; j++)

        {

            start = clock();

            ios_base::sync_with_stdio(false);

            TriangularIterative(vals[i]);

            end = clock();

            cpu_time_used = (double(end - start)) / double(CLOCKS_PER_SEC) + cpu_time_used;

        }

        cout << "\nCPU time taken with " << vals[i] << " levels using Iteration : " << fixed << cpu_time_used / 10.0 << setprecision(9) << " sec";

    }

}

int main()

{

    int n ,m , recr, iter;

    cout<<"Enter value of n: ";

    cin>>n;

    cout<<"Enter value of n: ";

    cin>>m;

    recr = TriangularRecursive(m);

    iter = TriangularIterative(m);

    cout << "\nnth triangular number With " << m << " levels using Recursion : " << recr;

    cout << "\nnth triangular number With " << m << " levels using Iteration : " << iter;

    recr = TriangularRecursive(n);

    iter = TriangularIterative(n);

    cout << "\nnth triangular number With " << n << " levels using Recursion : " << recr;

    cout << "\nnth triangular number With " << n << " levels using Iteration : " << iter;

    checkCase();

    return 0;

}

//SAMPLE OUTPUT