MTH4300 Home

MTH 4300: Final Practice 3

Problem 1

What is recursion? Provide a formulation of one problem that can be solved using recursion. Write a program that uses recursion to solve the problem you chose.

Problem 2

The user enters the positive integers elementZero, elementOne, and numElements. Make a program that creates and prints the sequence

elements[0], elements[1], ..., elements[numElements-1] 

with numElements terms that satisfy elements[0]=elementZero, elements[1]=elementOne and for i \( \geq 0 \)

elements[i+2] = (elements[i+1])^2-   (elements[i])^2  

Example

Input:
 1 1 11
 Output:
 1 1 0 -1 1 0 -1 1 0 -1 1

Problem 3

Create an appropriate class and methods that solve the problem presented below. You must use the keyword const whenever possible.

The class ComputerFolder should have two private attributes with the following declaration

int numberOfFiles;
 std::string* namesOfFiles;

The sequence namesOfFiles should always be of length numberOfFiles and represents the list of files in a computer folder.

Your class must contain the following methods:

  • (a) getNumFiles should return the value of the attribute numberOfFiles;

  • (b) setNumFiles with one argument of type int. The method should change the value of the attribute numberOfFiles to be equal to the supplied argument. Notice that you may need to change the length of the sequence and maybe move the sequence to a different place in RAM.

  • (c) getFileName with one argument \(i\) of type int. The method should return the \( i \)th element of the sequence namesOfFiles;

  • (d) setFileName with two arguments: \(i\) of type int and newFileName of type std::string. The function should set the \( i \)th element of the sequence namesOfFiles to be equal to newFileName.

  • (e) Default constructor (that creates an empty sequence with numberOfFiles\( =0 \), copy constructor, copy assignment, move constructor, and move assignment. The move constructor and move assignment should not allocate additional memory for the sequence, but instead should use the resources of the supplied argument.

  • (f) Destructor that frees the memory taken by the sequence.

Problem 4

What happens when the following code is executed? Provide a rigorous justification for your answer.

// compile with 
 // c++ -o myProgram mySource.cpp -std=c++11
 // execute with
 // ./myProgram
 #include<iostream>
 int main(){
     int *x;
     int i=10;
     x=new int[i];
     while(i>0){
          --i;
          x[i]=7*i;
     }
     *(x+2)=*x+2;
     for(i=0;i<5;++i){
          std::cout<<x[i]<<std::endl;
     }
     delete[] x;
     return 0;
 } 

Problem 5

The user is interested in purchasing different products. However, they are sold by different shops at different prices. Create the program that for each product tells the user the cheapest price and the name of the store that offers this cheapest price.

The user provides a sequence of lines. Each line consists of two strings and one positive real number. We do not know in advance the total number of lines. However, once the user supplies a negative number or 0 instead of a price, then we know that the input is over.

The first string of each line of the input represents the name of the product, the second string is the name of the store, and the number represents the price of the product at the given store.

After the input is over the program should output for each of the products the smallest possible price and the store that offers such price.

Example:
 Input:
 deadParrot storeInIpswitch 7.99
 fishSmoothy untastySuperMarket 5.99
 deadParrot storeInBolton 2.95
 mouse petShopA 7.99
 mouse newYorkSubway 2.75
 mouse computerStore 39.99
 end end -9
 Output:
 deadParrot sold for 2.95 at storeInBolton
 fishSmoothy sold for 5.99 at untastySuperMarket
 mouse sold for 2.75 at newYorkSubway

Problem 6

The user provides two positive integers \(n\) and \(k\), and a sequence \(x\) of \(nk+1\) positive integers. However, the sequence contains repetitions. There are only \(n\) unique numbers in the sequence. Each of them appears exactly \(k\) times, except for one number that appears exactly \(k+1\) times. Determine the number with this extra appearance.

Do not use pointers, vectors, or any data structures that allocate memory whose size depends on \(n\).

Example: In this example \(n=5\) and \(k=3\)

 
Input:
 5 3
 17 15 18 17 29 37 37 17 15 18
 18 29 15 37 37 29
 Output:
 37