MTH 4300: Algorithms, Computers, and Programming II

Functions and recursions

Problem 1. The user input consists of a sequence of real numbers \(x_0\), \(y_0\), \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(\dots\) We do not know the length in advance. A negative number instead of value for \(y_n\) is the signal that the input is over. Create the program that calculates \[\left(\max\left\{x_0,y_0\right\}+x_0y_0\right)+\left(\max\left\{x_1,y_1\right\}+x_1y_1\right)+\cdots+ \left(\max\left\{x_{n-1},y_{n-1}\right\}+x_{n-1}y_{n-1}\right).\]

Problem 2. What happens when the following code is executed?
#include<iostream>
int alpha(int x){
    int z;
    z=x+3;
    return z;
}
int beta(int x){
    int z;
    z=2*x+5;
    return z;
}
int main(){
    int w=7;
    int r=alpha(w)+alpha(beta(w+2));
    std::cout<< r << "\n";
    return 0;
}

2. Recursions

The functions are allowed to call themselves. The following examples illustrate such behavior.
Problem 3. For a given positive integer \(n\), determine the sum of all digits of \(n\) in decimal expansion.

Problem 4.

A sequence is called lucky if the numbers \(1\) and \(3\) are never adjacent and in this order. The user input consists of a positive integer \(n\). Create the program that counts the number of lucky sequences of length \(n\).

For example, when \(n=3\), the number of lucky sequences is \(21\). The sequences are \begin{eqnarray*} 111, \; 112,\; 121,\; 122,\; 123,\; 211,\; 212,\; 221,\; 222,\; 223,\;231,\; 232,\; 233,\; 311,\; 312,\; 321,\; 322, \; 323,\; 331,\; 332,\; 333 \end{eqnarray*}

Problem 5.

For a given positive integer \(n\), determine the number of sequences of length \(n\) whose terms are from the set \(\{1,2,3\}\) in which \(1\) and \(3\) are never next to each other.

For example, when \(n=3\), the number of sequences is \(17\). The sequences are \begin{eqnarray*} 111, \; 112,\; 121,\; 122,\; 123,\; 211,\; 212,\; 221,\; 222,\; 223,\; 232,\; 233,\; 321,\; 322, \; 323,\; 332,\; 333 \end{eqnarray*}