This is study resource 11 for the 24-week cohort during the summer of 2019. There are six questions in it. Only three questions have answers.
Click here to see all the study resources.
Question #1
Give a recursive implement to the following functions:
a. void printTriangle(int n)
This function is given a positive integer n, and prints a textual image of a right triangle (aligned to the left) made of n lines with asterisks.
b. void printOpositeTriangles(int n)
This function is given a positive integer n, and prints a textual image of a two opposite right triangles (aligned to the left) with asterisks, each containing n lines.
c. void printRuler(int n)
This function is given a positive integer n, and prints a vertical ruler of 2n − 1 lines. Each line contains ‘-‘ marks as follows:
Hints:
1. Take for n=4: when finding print_ruler(4), try to think first what print_ruler(3) does, and how you can use it to print a ruler of size 4. Then, generally identify what print_ruler(n-1) is supposed to print, and use that in order to define how to print the ruler of size n.
2. You may want to have more than one recursive call
3. It looks much scarier than it actually is
#include <iostream>
using namespace std;
void printTriangle(int n);
void printOpositeTriangles(int n);
void printRuler(int n);
int main() {
printTriangle(4);
cout << endl;
printOpositeTriangles(4);
cout << endl;
printRuler(4);
}
void printTriangle(int n){
if(n <= 0){
return;
}
printTriangle(n-1);
for(int i = 0; i < n; i++){
cout << "*";
}
cout << endl;
}
void printOpositeTriangles(int n){
if(n <= 0){
return;
}
for(int i = 0; i < n; i++){
cout << "*";
}
cout << endl;
printOpositeTriangles(n-1);
for(int i = 0; i < n; i++){
cout << "*";
}
cout << endl;
}
void printRuler(int n){
if(n <= 0){
return;
}
printRuler(n-1);
for(int i = 0; i < n; i++){
cout << "-";
}
cout << "\n";
printRuler(n-1);
}
Question #2
Give a recursive implement to the following functions:
a. int sumOfSquares(int arr[], int arrSize)
This function is given arr, an array of integers, and its logical size, arrSize. When called, it returns the sum of the squares of each of the values in arr.
For example, if arr is an array containing [2, -1, 3, 10], calling sumOfSquares(arr, 4) will return 114 (since, 22 + (-1)2 + 32 + 102 = 114).
b. bool isSorted(int arr[], int arrSize)
This function is given arr, an array of integers, and its logical size, arrSize. When called, it should return true if the elements in arr are sorted in an ascending order, or false if they are not.
#include <iostream>
#include <math.h>
using namespace std;
int sumOfSquares(int arr[], int arrSize);
bool isSorted(int arr[], int arrSize);
int main() {
int arr[] = {2, -1, 3, 10};
int sum = sumOfSquares(arr, 4);
cout << "Sum = " << sum << endl;
bool sorted = isSorted(arr, 4);
if(sorted){
cout << "Array is sorted"<< endl;
}else{
cout << "Array is NOT sorted"<< endl;
}
return 0;
}
int sumOfSquares(int arr[], int arrSize){
if(arrSize <= 0){
return 0;
}
return (sumOfSquares(arr, arrSize-1) + pow(arr[arrSize-1], 2));
}
bool isSorted(int arr[],int arrSize){
if(arrSize == 1 || arrSize == 0){
return true;
}
// If any unsorted pair is found, return false
if(arr[arrSize-1] < arr[arrSize-2]){
return false;
}
// Last pair was sorted
// Move to next pair
return isSorted(arr, arrSize-1);
}
Question #3
Write two recursive versions of the function minInArray. The function will be given a sequence of elements and should return the minimum value in that sequence. The two versions differ from one another in the technique we use to pass the sequence to the function.
In version 1 – The prototype of the function should be:
int minInArray1(int arr[], int arrSize)
Here, the function is given arr, an array of integers, and its logical size, arrSize. The function should find the minimum value out of all the elements in positions: 0, 1, 2, …, arrSize-1.
In version 2 – The prototype of the function should be:
int minInArray2(int arr[], int low, int high)
Here, the function is given arr, an array of integers, and two additional indices: low and high (low ≤ high), which indicate the range of indices that need to be considered. The function should find the minimum value out of all the elements in positions: low, low+1, …, high.
Use the following main to check your program:
int main() {
int arr[10] = {9, -2, 14, 12, 3, 6, 2, 1, -9, 15};
int res1, res2, res3, res4;
res1 = minInArray1(arr, 10);
res2 = minInArray2(arr, 0, 9);
cout<<res1<<” “<<res2<<endl; //should both be -9
res3 = minInArray2(arr, 2, 5);
res4 = minInArray1(arr+2, 4); //arr+2 is equivalent to &(arr[2])
cout<<res3<<” “<<res4<<endl; //should both be 3
return 0;
}
Answer
#include <iostream>
using namespace std;
int minInArray1(int arr[],int arrSize) {
if(arrSize == 1) {
return arr[0];
} else {
int min = minInArray1(arr, arrSize-1);
if(arr[arrSize-1] < min) {
min = arr[arrSize-1];
}
return min;
}
}
int minInArray2(int arr[], int low, int high) {
if(low == high) {
return arr[low];
} else {
int min = minInArray2(arr, low+1, high);
if(arr[low] < min) {
min = arr[low];
}
return min;
}
}
int main()
{
int arr[10] = { 9, -2, 14, 12, 3, 6, 2, 1, -9, 15 };
int res1, res2, res3, res4;
res1 = minInArray1(arr, 10);
res2 = minInArray2(arr, 0, 9);
cout << res1 << " " << res2 << endl;
res3 = minInArray2(arr, 2, 5);
res4 = minInArray1(arr + 2, 4);
cout<<res3<< " " <<res4<<endl;
return 0;
}
Question #4
The game of “Jump It” consists of a board with n positive integers in a row, except for the first column, which always contains zero. These numbers represent the cost to enter each column.
Here is a sample game board where n is 6:
| 0 | 3 | 80 | 6 | 57 | 10 |
The object of the game is to move from the first column to the last column with the lowest total cost.
The number in each column represents the cost to enter that column. You always start the game in the first column and have two types of moves. You can either move to the adjacent column or jump over the adjacent column to land two columns over. The cost of a game is the sum of the costs of the visited columns.
In the board shown above, there are several ways to get to the end. Starting in the first column, our cost so far is 0. We could jump to 80, then jump to 57, and then move to 10 for a total cost of 80 + 57 + 10 = 147. However, a cheaper path would be to move to 3, jump to 6, then jump to 10, for a total cost of 3 + 6 + 10 = 19.
Write a recursive function that solves this problem and returns the lowest cost of a game board represented and passed as an array.
Note: your function shouldn’t output the actual sequence of jumps, only the lowest cost of this sequence.
Photo by Oskar Yildiz on Unsplash