## Quiz 9 :

Recursion and Algorithm Analysis

Answer:

Program plan:

• Include required header files into the program.

• Declare a function template "template " with type parameter. In this template, T is type parameter.

• In the main function, declare "a" and "b" as "integer" and "float" data type respectively.

o Using for loop, get the 5 value. Then appends the copy of index to the end a, increasing its size by 1 using "a.push_back(index)"

o Appends the the copy of index to the end b, increasing its size by 1 using "b.push_back(-index / 3.0)"

o After that check if the ascending order function for integer is satisfied, then display the given integers values is in ascending order.

o check if the ascending order function for float is satisfied, then display the given float values is in ascending order.

• The function "bool ascendingOrder(const vector n)" is used to return true if the given values are in ascending order; otherwise it returns false. In this function, the arguments "n" which is declared in the const vector.

o In the function, check the one by one element is stored in the given data type using for loop.

o After that check if index of each value is greater than or equal to index of each value + 1, then returns false; otherwise it return true.

• The template function "ostream operator (ostream out, const vector n)" means only after a vector holds values must the subscript operator be used to access those values in the output template function.

o In this fucntion, "ostream" is used to stored the output values in a vector.

Program:

/ **********************************************************

* Program to test the ascending-order function *

********************************************************** /

/ / include required header file

#include

/ / vector header file

#include

/ / for cin and cout statement

using namespace std;

/ / type parameter for template

template

/ / function definition of acending order

bool ascendingOrder(const vector n)

{

/ / using for loop check the one by one element

for (int index = 0; index n.size() - 1; index++)

{

/ * check if the index of each value is greater than or equal to index of each value + 1 * /

if (n[index] = n[index+1])

{

/ * if the condition is satisfied, then returns false * /

return false;

}

}

/ / otherwise returns true

return true;

}

/ / template function for output operator

template

/ / Function definition

ostream operator (ostream out, const vector n)

{

/ / print the one by value using for loop

for (int i = 0; i n.size(); i++)

/ * display the values stored in 'n' have been output to out * /

out n[i] " ";

out endl;

/ / return the output statement

return out;

}

/ / main function

int main()

{

/ / declare a as integer data type using vector

vector a;

/ / declare a as float data type using vector

vector b;

/ / push the 10 value using for loop

for (int index = 0; index 5; index++)

{

/ * appends a copy of index to the end of a, increasing its size by 1 * /

a.push_back(index);

/ * appends a copy of index to the end of b, increasing its size by 1 * /

b.push_back(-index / 3.0);

}

/ / print the integer values

cout "The integer values are: " a;

/ / print the float values

cout "The float values are: " b;

/ * if the ascending order function for integer integer is satisfied * /

if (ascendingOrder(a))

/ * display the integers values are in ascending order * /

cout "The given integers values are in ascending order!" endl;

/ / if the ascending order function for flaot values is satisfied, then

if (ascendingOrder(b))

/ * display the integers values are in ascending order * /

cout "The given float values are in ascending order!" endl;

}

Sample Output:

The integer values are: 0 1 2 3 4

The float values are: 0 -0.333333 -0.666667 -1 -1.33333

The given integers values are in ascending order!

Answer:

Template program for find the sum of array elements which is declared as integer data type:

/ / Include required header file

#include

/ / for cin and cout statement

using namespace std;

/ / type parameter for template

template

/ / function definition for find the sum of array elements

ValueType arraySum(ValueType x[], int length)

{

/ / initialize sum is zero using the template identifier

ValueType sum = 0;

/ / for loop for add one by one element

for (int index = 0; index length; index++)

{

/ / display the array elements

cout x[index] " ";

/ / add the sum and element in the array

sum += x[index];

}

/ / returns sum

return sum;

}

/ / main function

int main()

{

/ / set the array elements

int array[] = {20, 35, 10, 25, 12};

/ / print the array elements

cout "The array elements are ";

/ * display sum of array element and call the arraySum() function * /

cout "\n" "Sum of array element is " arraySum(array, 5) endl;

}

Sample Output:

The array elements are 20 35 10 25 12

Sum of array elements is 102

Explanation:

• From the given code, "template " means function template with type parameter. In this template, "ValueType" is the identifier.

• In "main()" function

o Declare the array elements as "integer" data type

o Display the array elements

o Call the "arraySum (a, 5)" function to find sum of five array elements.

• The function "ValueType arraySum(ValueType x[], int length)" is used to find the sum of array element.

o In this function, using template identifier, initializes the sum is 0

o Using for loop, display the array element and add the one by one element using the "sum += x[index]".

o Finally returns the sum of given array elements.

Template program for find the sum of array elements which is declared as float data type:

/ / Include required header file

#include

/ / for cin and cout statement

using namespace std;

/ / type parameter for template

template

/ / function definition for find the sum of array elements

ValueType arraySum(ValueType x[], int length)

{

/ / initialize sum is zero using the template identifier

ValueType sum = 0;

/ / for loop for add one by one element

for (int index = 0; index length; index++)

{

/ / display the array elements

cout x[index] " ";

/ / add the sum and element in the array

sum += x[index];

}

/ / returns sum

return sum;

}

/ / main function

int main()

{

/ / set the array elements

float array[] = {20.5, 3.5, 10.23, 25.04, 1.2};

/ / print the array elements

cout "The array elements are ";

/ * display sum of array element and call the arraySum() function * /

cout "\n" "Sum of array element is " arraySum(array, 5) endl;

}

Sample Output:

The array elements are 20.5 3.5 10.23 25.04 1.2

Sum of array elements is 60.47

Explanation:

• From the given code, "template " means function template with type parameter. In this template, ValueType is the identifier.

• In "main()" function

o Declare the array elements as "float" data type

o Display the array elements.

o Call the "arraySum (a, 5)" function to find sum of five array elements.

• The function "ValueType arraySum(ValueType x[], int length)" is used to find the sum of array element.

o In this function, using template identifier, initializes the sum is 0

o Using for loop, display the array element and add the one by one element using the "sum += x[index]".

o Finally returns the sum of given array elements.

Template program for find the sum of array elements which is declared as double data type:

/ / Include required header file

#include

/ / for cin and cout statement

using namespace std;

/ / type parameter for template

template

/ / function definition for find the sum of array elements

ValueType arraySum(ValueType x[], int length)

{

/ / initialize sum is zero using the template identifier

ValueType sum = 0;

/ / for loop for add one by one element

for (int index = 0; index length; index++)

{

/ / display the array elements

cout x[index] " ";

/ / add the sum and element in the array

sum += x[index];

}

/ / returns sum

return sum;

}

/ / main function

int main()

{

/ / set the array elements

double array[] = {1.2345, 3.5056, 10.2341, 25.1204, 1.2420};

/ / print the array elements

cout "The array elements are ";

/ * display sum of array element and call the arraySum() function * /

cout "\n" "Sum of array element is " arraySum(array, 5) endl;

}

Sample Output:

The array elements are 1.2345 3.5056 10.2341 25.1204 1.2420

Sum of array elements is 41.366

Explanation:

• From the given code, "template " means function template with type parameter. In this template, ValueType is the identifier.

• In "main()" function

o Declare the array elements as "double" data type

o Display the array elements

o Call the "arraySum (a, 5)" function to find sum of five array elements.

• The function "ValueType arraySum(ValueType x[], int length)" is used to find the sum of array element.

o In this function, using template identifier, initializes the sum is 0

o Using for loop, display the array element and add the one by one element using the "sum += x[index]".

o Finally returns the sum of given array elements.

Answer:

Template program for find the median of three numbers which is declared as integer data type:

/ / include required header files

#include

/ / for cin and cout statements

using namespace std;

/ / type parameter for template

template

/ / function definition for find median of three values

ValueType median(ValueType p, ValueType q, ValueType r)

{

/ / assign the maximum as p (first number) and minimum as q(second number) using template identifier

ValueType maximum= p, minimum = q;

/ / check if p is less than q

if (p q)

{

/ / assign the maximum as q

maximum = q;

/ / assign the minimum as p

minimum = p;

}

/ / check the r (third number) greater than maximum, then returns maximum is median

if (r maximum)

return maximum;

/ / if r is less than minimum then return the minimum is median

else if (r minimum)

return minimum;

/ / otherwise returns the r is median

else

return r;

}

/ / main function

int main()

{

/ / declare the three numbers p, q, and r as integer data type

int p,q,r;

/ / display the three numbers

cout "Enter the three numbers:\n";

/ / get the three numbers

cin p q r;

/ / display the median of three numbers

cout "The median of three numbers " p "," q "and " r " is: ";

/ / call the function

cout median(p, q, r) endl;

}

Sample Output:

Enter the three numbers:

6 8 5

The median of three numbers 6, 8, and 5 is: 6

Explanation:

• From the given code, template means function template with type parameter. In this template, ValueType is the identifier.

• In main () function

o Declare the three numbers as integer data type

o Get the three numbers

o Call the median (p, q, r) function to find the median of three numbers.

• The function median(ValueType p, ValueType q, ValueType r) is used to return the median of three numbers.

o In this function, using template identifier we can set maximum as p and minimum as q. Here we can consider the first number as p and second number as q.

o Then check whether the p is less than q. if the condition is satisfied, then set the maximum as q and minimum as p.

o

After that check whether r (consider r is the third number) is greater than maximum, then returns the maximum is the median or r is less than minimum, then returns the minimum is median.

o Otherwise return the r is median.

Template program for find the median of three numbers which is declared as float data type:

/ / include required header files

#include

/ / for cin and cout statements

using namespace std;

/ / type parameter for template

template

/ / function definition for find median of three values

ValueType median(ValueType p, ValueType q, ValueType r)

{

/ / assign the maximum as p (first number) and minimum as q(second number) using template identifier

ValueType maximum= p, minimum = q;

/ / check if p is less than q

if (p q)

{

/ / assign the maximum as q

maximum = q;

/ / assign the minimum as p

minimum = p;

}

/ / check the r (third number) greater than maximum, then returns maximum is median

if (r maximum)

return maximum;

/ / if r is less than minimum then return the minimum is median

else if (r minimum)

return minimum;

/ / otherwise returns the r is median

else

return r;

}

/ / main function

int main()

{

/ * declare the three numbers p, q, and r as float data type * /

float p,q,r;

/ / display the three numbers

cout "Enter the three numbers:\n";

/ / get the three numbers

cin p q r;

/ / display the median of three numbers

cout "The median of three numbers " p "," q "and " r " is: ";

/ / call the function

cout median(p, q, r) endl;

}

Sample Output:

Enter the three numbers:

6.5 8.9 5.6

The median of three numbers 6.5, 8.9, and 5.6 is: 6.5

Explanation:

• From the given code, template means function template with type parameter. In this template, ValueType is the identifier.

• In main () function

o Declare the three numbers as float data type

o Get the three numbers

o Call the median (p, q, r) function to find the median of three numbers.

• The function median(ValueType p, ValueType q, ValueType r) is used to return the median of three numbers.

o In this function, using template identifier we can set maximum as p and minimum as q. Here we can consider the first number as p and second number as q.

o

Then check whether the p is less than q. if the condition is satisfied, then set the maximum as q and minimum as p.

o After that check whether r (consider r is the third number) is greater than maximum, then returns the maximum is the median or r is less than minimum, then returns the minimum is median.

o Otherwise return the r is median.

Template program for find the median of three numbers which is declared as double data type:

/ / include required header files

#include

/ / for cin and cout statements

using namespace std;

/ / type parameter for template

template

/ / function definition for find median of three values

ValueType median(ValueType p, ValueType q, ValueType r)

{

/ / assign the maximum as p (first number) and minimum as q(second number) using template identifier

ValueType maximum= p, minimum = q;

/ / check if p is less than q

if (p q)

{

/ / assign the maximum as q

maximum = q;

/ / assign the minimum as p

minimum = p;

}

/ / check the r (third number) greater than maximum, then returns maximum is median

if (r maximum)

return maximum;

/ / if r is less than minimum then return the minimum is median

else if (r minimum)

return minimum;

/ / otherwise returns the r is median

else

return r;

}

/ / main function

int main()

{

/ * declare the three numbers p, q, and r as double data type * /

double p,q,r;

/ / display the three numbers

cout "Enter the three numbers:\n";

/ / get the three numbers

cin p q r;

/ / display the median of three numbers

cout "The median of three numbers " p "," q "and " r " is: ";

/ / call the function

cout median(p, q, r) endl;

}

Sample Output:

Enter the three numbers:

6.1234 8.4556 2.35678

The median of three numbers 6.1234, 8.4556, and 2.35678 is: 6.1234

Explanation:

• From the given code, "template " means function template with type parameter. In this template, "ValueType" is the identifier.

• In "main()" function

o Declare the three numbers as double data type

o Get the three numbers

o Call the "median (p, q, r)" function to find the median of three numbers.

• The function "median(ValueType p, ValueType q, ValueType r)" is used to return the median of three numbers.

o

In this function, using template identifier we can set maximum as p and minimum as q. Here we can consider the first number as p and second number as q.

o Then check whether the p is less than q. if the condition is satisfied, then set the maximum as q and minimum as p.

o After that check whether r (consider r is the third number) is greater than maximum, then returns the maximum is the median or r is less than minimum, then returns the minimum is median.

o Otherwise return the r is median.

Template program for find the median of three numbers which is declared as complex:

/ / include required header files

#include

/ / include complex header files

#include

/ / for cin and cout statements

using namespace std;

/ / type parameter for template

template

/ / function definition for find median of three values

ValueType median(ValueType p, ValueType q, ValueType r)

{

/ / assign the maximum as p (first number) and minimum as q(second number) using template identifier

ValueType maximum= p, minimum = q;

/ / check if p is less than q

if (p q)

{

/ / assign the maximum as q

maximum = q;

/ / assign the minimum as p

minimum = p;

}

/ / check the r (third number) greater than maximum, then returns maximum is median

if (r maximum)

return maximum;

/ / if r is less than minimum then return the minimum is median

else if (r minimum)

return minimum;

/ / otherwise returns the r is median

else

return r;

}

/ / main function

int main()

{

/ * declare the three numbers p, q, and r as float data type * /

complex p,q,r;

/ / display the three numbers

cout "Enter the three numbers:\n";

/ / get the three numbers

cin p q r;

/ / display the median of three numbers

cout "The median of three numbers " p "," q "and " r " is: ";

/ / call the function

cout median(p, q, r) endl;

}

Explanation:

From the above program, the complier cannot produce a "complex " in the "median ()" function. So the error occurs in the given program; because for complex values, the symbol " " is not defined in the program.