1. Write C++ programs
2. Compile C++ programs
3. Implement programs that use recursion to solve advanced problems

Additional Reading

This lab exercise requires an understanding of some concepts to solve the problems. You are strongly encouraged to read the following tutorials to help you answer the problems.

1. Organizing C++ files: function prototypes, implementations, and drivers.
2. Using objects as parameters and return values in functions
3. Passing arrays as parameters to functions
4. File reading and writing (also includes dealing with arrays)

Instructions

Answer the programming problems sequentially (i.e., answer prob01 before prob02). If you have questions let your instructor or the lab assistant know. You can also consult your classmates.

When you answer two programming problems correctly, let your instructor know and wait for further instruction.

Lab exercise guide

Heres a link to the Lab exercise guide in case you need to review the lab exercise objectives, grading scheme, or evaluation process.

Count Odd

Create a program that counts all the odd numbers from 0 to a number using recursion. Your program should have a function called count_odd that takes in an int value and returns an int value. The user will be asked for a number, and the program will display the following output.

Sample Output:

Enter a number: 5The number of odds from 0 to 5 is 3

Enter a number: 13The number of odds from 0 to 13 is 7

Place the count_odds function prototype in count-odd.hpp and its implementation in count-odd.cpp. The main function already contains some code, but you need to complete the requirements that is described inside the file.

Submission checklist

1. Created function prototype and stored in .hpp file.
2. Created function implementation and stored in .cpp file (see reference).
3. Call function in the driver
4. Compiled and ran the driver (main).
5. Manually checked for compilation and logical errors.
6. Ensured no errors on the unit test (make test).
7. Followed advice from the stylechecker (make stylecheck).
8. Followed advice from the formatchecker to improve code readbility (make formatcheck).

Code evaluation

Open the terminal and navigate to the folder that contains this exercise. Assuming you have pulled the code inside of /home/student/labex02-tuffy and you are currently in /home/student you can issue the following commands

cd labex02-tuffy

You also need to navigate into the problem you want to answer. To access the files needed to answer problem 1, for example, you need to issue the following command.

cd prob01

When you want to answer another problem, you need to go back up to the parent folder and navigate into the next problem. Assuming you are currently in prob01, you can issue the following commands to go to the parent folder then go into another problem you want to answer; prob02 for example.

cd ..cd prob02

Use the clang++ command to compile your code and the ./ command to run it. The sample code below shows how you would compile code save in count-odd.cpp and main.cpp, and into the executable file main. Make sure you use the correct filenames required in this problem. Take note that if you make any changes to your code, you will need to compile it first before you see changes when running it.

clang++ -std=c++17 main.cpp count-odd.cpp -o main./main

You can run one, two, or all the commands below to test your code, stylecheck your codes design, or formatcheck your work. Kindly make sure that you have compiled and executed your code before issuing any of the commands below to avoid errors.

make testmake stylecheckmake formatcheck

A faster way of running all these tests uses the all parameter.

make all

Linear Search Array

Create a recursive linear_search function that receives an integer array (int[]), a number to find in the array, and the size of the array. The function should return the index of the number in the array if it exists, and returns -1 if it isnt in the array.

Place the linear_searchs function prototype in lsa.hpp and its implementation in lsa.cpp. The main function already contains some code, but you need to complete the requirements that is described inside the file.

Sample output:

Array: 3 16 22 8 11 0 55 34 27 31Please enter a number you want to search for: 8The index of 8 in the array is: 3

Array: 3 16 22 8 11 0 55 34 27 31Please enter a number you want to search for: 1515 is not in the array

Submission checklist

1. Created function prototype and stored in .hpp file.
2. Created function implementation and stored in .cpp file (see reference).
3. Call function in the driver
4. Compiled and ran the driver (main).
5. Manually checked for compilation and logical errors.
6. Ensured no errors on the unit test (make test).
7. Followed advice from the stylechecker (make stylecheck).
8. Followed advice from the formatchecker to improve code readbility (make formatcheck).

Code evaluation

Open the terminal and navigate to the folder that contains this exercise. Assuming you have pulled the code inside of /home/student/labex02-tuffy and you are currently in /home/student you can issue the following commands

cd labex02-tuffy

You also need to navigate into the problem you want to answer. To access the files needed to answer problem 1, for example, you need to issue the following command.

cd prob01

When you want to answer another problem, you need to go back up to the parent folder and navigate into the next problem. Assuming you are currently in prob01, you can issue the following commands to go to the parent folder then go into another problem you want to answer; prob02 for example.

cd ..cd prob02

Use the clang++ command to compile your code and the ./ command to run it. The sample code below shows how you would compile code save in lsa.cpp and main.cpp, and into the executable file main. Make sure you use the correct filenames required in this problem. Take note that if you make any changes to your code, you will need to compile it first before you see changes when running it.

clang++ -std=c++17 main.cpp lsa.cpp -o main./main

You can run one, two, or all the commands below to test your code, stylecheck your codes design, or formatcheck your work. Kindly make sure that you have compiled and executed your code before issuing any of the commands below to avoid errors.

make testmake stylecheckmake formatcheck

A faster way of running all these tests uses the all parameter.

make all

Recursive Power Function

Create a recursive function called power that receives two positive int parameters that represent the base and exponent. The function should return the base raised to the exponent.

Place the powers function prototype in power.hpp and its implementation in power.cpp. The main function already contains some code, but you need to complete the requirements that is described inside the file.

Sample Output:

Enter a base: 5Enter an exponent: 35 ^ 3 = 125

Enter a base: 2Enter an exponent: 102 ^ 10 = 1024

Submission checklist

1. Created function prototype and stored in .hpp file.
2. Created function implementation and stored in .cpp file (see reference).
3. Call function in the driver
4. Compiled and ran the driver (main).
5. Manually checked for compilation and logical errors.
6. Ensured no errors on the unit test (make test).
7. Followed advice from the stylechecker (make stylecheck).
8. Followed advice from the formatchecker to improve code readbility (make formatcheck).

Code evaluation

Open the terminal and navigate to the folder that contains this exercise. Assuming you have pulled the code inside of /home/student/labex02-tuffy and you are currently in /home/student you can issue the following commands

cd labex02-tuffy

You also need to navigate into the problem you want to answer. To access the files needed to answer problem 1, for example, you need to issue the following command.

cd prob01

When you want to answer another problem, you need to go back up to the parent folder and navigate into the next problem. Assuming you are currently in prob01, you can issue the following commands to go to the parent folder then go into another problem you want to answer; prob02 for example.

cd ..cd prob02

Use the clang++ command to compile your code and the ./ command to run it. The sample code below shows how you would compile code save in power.cpp and main.cpp, and into the executable file main. Make sure you use the correct filenames required in this problem. Take note that if you make any changes to your code, you will need to compile it first before you see changes when running it.

clang++ -std=c++17 main.cpp power.cpp -o main./main

You can run one, two, or all the commands below to test your code, stylecheck your codes design, or formatcheck your work. Kindly make sure that you have compiled and executed your code before issuing any of the commands below to avoid errors.

make testmake stylecheckmake formatcheck

A faster way of running all these tests uses the all parameter.

make all

GCD calculator

Create a recursive Greatest Common Divisor (GCD) calculator function called gcd that receives two integer inputs. The function should return the GCD of those two numbers.

There are two methods to compute the GCD of two numbers: Euclidean and Dijkstras algorithm. You can choose either of the two algorithms to implement your recursive gcd function.

Euclidean Algorithm

The Euclidean algorithm mainly uses division and the remainder of the two numbers to find the GCD. It can be represented as a recursive algorithm such that

gcd(num1, num2) = num2                      if num1 == zero // base case                = gcd(num2 % num1, num1)    if num1 > zero  // recursive case

You can learn more about this topic by going through these slides.

Dijkstras GCD algorithm

Dijkstras algorithm mainly uses subtraction to find the GCD. It can be represented as a recursive algorithm such that

 gcd(num1, num2) = num2                     // if num1 and num2 are equal                 = gcd(num1 - num2, num2)   // if num1 is greater than num2                 = gcd(num1, num2 - num1)   // if num2 is greater than num1

As an example, lets say we want to find the GCD of the two numbers 72 and 56

gcd(72 , 56)  72-56 , 56  Take the larger number, 72 and subtract 56 from it  16 , 56     This is our end result, but we need to keep going. Until they are equalgcd(16 , 56)  16 , 56-16  Take the larger number,56 and subtract 16 from it  16 , 40     This is our end result, but this still doesnt give us our gcd, so we keep going until both numbers are equalgcd(16 , 40)  16 , 40-16  Take the larger number 40 and subtract 16 from it.  16 , 24     This is our end result, but this still doesnt give us our gcd, so we keep going until both numbers are equalgcd(16,24)     16 , 24-16  Take the larger number 24 and subtract 16 from it.  16 , 8      This is our end result, but this still doesnt give us our gcd, so we keep going until both numbers are equalgcd(16, 8)     16-8, 8     Take the larger number 16 and subtract 8 from it.  8 ,8        this is our end result, and on the next function call we will validate the equality of those two numbers there.gcd(8,8)  8 , 8       The two numbers are equal. THIS IS OUR GCD.

You can learn more about this topic by going through these slides

Place the gcds function prototype in gcd.hpp and its implementation in gcd.cpp. The main function already contains some code, but you need to complete the requirements that is described inside the file.

Sample Output

Enter the first number: 24Enter the second number: 18The GCD of the numbers 24 and 18 is 6

Submission checklist

1. Created function prototype and stored in .hpp file.
2. Created function implementation and stored in .cpp file (see reference).
3. Call function in the driver
4. Compiled and ran the driver (main).
5. Manually checked for compilation and logical errors.
6. Ensured no errors on the unit test (make test).
7. Followed advice from the stylechecker (make stylecheck).
8. Followed advice from the formatchecker to improve code readbility (make formatcheck).

Code evaluation

Open the terminal and navigate to the folder that contains this exercise. Assuming you have pulled the code inside of /home/student/labex02-tuffy and you are currently in /home/student you can issue the following commands

cd labex02-tuffy

You also need to navigate into the problem you want to answer. To access the files needed to answer problem 1, for example, you need to issue the following command.

cd prob01

When you want to answer another problem, you need to go back up to the parent folder and navigate into the next problem. Assuming you are currently in prob01, you can issue the following commands to go to the parent folder then go into another problem you want to answer; prob02 for example.

cd ..cd prob02

Use the clang++ command to compile your code and the ./ command to run it. The sample code below shows how you would compile code save in gcd.cpp and main.cpp, and into the executable file main. Make sure you use the correct filenames required in this problem. Take note that if you make any changes to your code, you will need to compile it first before you see changes when running it.

clang++ -std=c++17 main.cpp gcd.cpp -o main./main

You can run one, two, or all the commands below to test your code, stylecheck your codes design, or formatcheck your work. Kindly make sure that you have compiled and executed your code before issuing any of the commands below to avoid errors.

make testmake stylecheckmake formatcheck

A faster way of running all these tests uses the all parameter.

make all

Max Value

Write a program that finds the largest number in an array of positive numbers using recursion. Your program should have a function called array_max that should pass in an int array, and an int for the size of the array, respectively, and should return an int value.

Given an array of size 10 with contents: {10, 9, 6, 1, 2, 4, 16, 8, 7, 5}

The output should be:

The largest number in the array is 16

The function should return -1 if the input is invalid.

Place the array_maxs function prototype in array_max.hpp and its implementation in array_max.cpp. The main function already contains some code, but you need to complete the requirements that is described inside the file.

Submission checklist

1. Created function prototype and stored in .hpp file.
2. Created function implementation and stored in .cpp file (see reference).
3. Call function in the driver
4. Compiled and ran the driver (main).
5. Manually checked for compilation and logical errors.
6. Ensured no errors on the unit test (make test).
7. Followed advice from the stylechecker (make stylecheck).
8. Followed advice from the formatchecker to improve code readbility (make formatcheck).

Code evaluation

Open the terminal and navigate to the folder that contains this exercise. Assuming you have pulled the code inside of /home/student/labex02-tuffy and you are currently in /home/student you can issue the following commands

cd labex02-tuffy

You also need to navigate into the problem you want to answer. To access the files needed to answer problem 1, for example, you need to issue the following command.

cd prob01

When you want to answer another problem, you need to go back up to the parent folder and navigate into the next problem. Assuming you are currently in prob01, you can issue the following commands to go to the parent folder then go into another problem you want to answer; prob02 for example.

cd ..cd prob02

Use the clang++ command to compile your code and the ./ command to run it. The sample code below shows how you would compile code save in array_max.cpp and main.cpp, and into the executable file main. Make sure you use the correct filenames required in this problem. Take note that if you make any changes to your code, you will need to compile it first before you see changes when running it.

clang++ -std=c++17 main.cpp array_max.cpp -o main./main

You can run one, two, or all the commands below to test your code, stylecheck your codes design, or formatcheck your work. Kindly make sure that you have compiled and executed your code before issuing any of the commands below to avoid errors.

make testmake stylecheckmake formatcheck

A faster way of running all these tests uses the all parameter.

make all