In C++ . For each of the following problems, write a function that solves the pr
ID: 3869053 • Letter: I
Question
In C++ . For each of the following problems, write a function that solves the problem recursively. No for loops or while loops allowed! You should test each function in your main method. You should just submit a single .cpp file. No separate compilation needed.
Problem 1
Write a function that takes a string and returns true if that string is a palindrome and false otherwise. The function should look like this:
bool isPalindrome(const string& input) {
// ...
}
Problem 2
Write a function that takes an integer and returns the sum of its digits. For this function, you will have to make clever use of the / and % operators! Your function should look like this:
int digitSum(int input) {
// ...
}
Problem 3
You are standing at the base of a staircase. At each step as you climb the staircase, you have the option of taking a small stride (one stair) or a large stride (two stairs - assuming there are at least two stairs remaining). Given that a staircase has X number of stairs, how many ways are there to climb the staircase using different combinations of small and large strides? Write a function that takes a total number of stairs in the staircase and returns the number of ways to climb it. If the staircase has three steps, for example, there are three ways to climb it (three small strides, or a large stride followed by a small stride, or a small stride followed by a large stride). Your function should look like this:
int waysToClimb(int numStairs) {
// ...
}
Explanation / Answer
Problem 1:
#include <cctype>
#include <iostream>
#include <string>
using namespace std;
bool isPalindrome( const char* x)
{
string str = *x;
int n = str.length();
for (int i = 0; i < n; ++i)
{
int j = 0;
while (isalpha(str[i]))
{
if (isalpha(str[n-j-1]))
{
if (tolower(str[i]) == tolower(str[n-j-1]))
return true;
else
return false;
}
j += 1;
}
}
return true;
}
int main()
{
string str;
cout << "Enter your string: ";
getline (cin, str);
const char * x ;
x = &str;
if (isPalindrome(x) == true)
{
cout << "Yes it is!" << endl;
}
else
{
cout << "No, it's not." << endl;
}
cout << str << endl;
return 0;
}
Problem 2:
#include <iostream>
using namespace std;
int n = 1, sum = 0;
int sumDigits(int n, int sum)
{
if (n== 0)
{
return sum;
}
else
{
sum = sum + n%10;
n= n/10;
return sumDigits(n, sum);
}
}
int main(int argc, char* argv[])
{
n = 1, sum = 0;
cout << "Enter a non-negative integer (enter 0 to end): ";
cin >> n;
sum = sumDigits (n, sum);
cout << "The sum of all digits "<< n << " is: " << sum << " ";
system ("Pause");
return 0;
}
Problem 3:
public void waysToClimb(int n) {
Stack<Integer> steps = new Stack<Integer>();
waysToClimb(n, steps);
}
public void waysToClimb(int n, Stack<Integer> steps) {
if(n <= 0)
return;
if(n == 1) {
steps.push(1);
System.out.println(steps);
steps.pop();
return;
}
if(n == 2) {
steps.push(2);
System.out.println(steps);
steps.pop();
}
steps.push(1);
waysToClimb(n - 1, steps);
steps.pop();
steps.push(2);
waysToClimb(n - 2, steps);
steps.pop();
}