MTH 4300: Final Practice 4

The variable \( S \) is a set of integers. The program inserts the numbers in the set. If the number is already in \( S \), then it won‘t be inserted again. The last command prints the the total number of elements, which is \( 7 \).

We will read the terms of the sequence one by one and the variable \( r \) will always contain the largest of all of the terms received so far that are divisible by \( 22 \).

#include<iostream>
 int main(){
     int n, userInput,r;
     std::cin>>n;
     r=-1;
     for(int i=0;i<n;++i){
          std::cin>>userInput;
          if(userInput % 22 == 0){
               if((r<0)||(userInput>r)){r=userInput;}
          }
     }
     std::cout<<r<<std::endl;
     return 0;
 }

The terms of the sequence are initialized to \( x[i]=8\cdot i+ 3 \). The value \( x[0] \) is updated to \( g(x) \). When the function \( g \) is executed its argument is the pointer to the first term of the sequence. Inside the function, the variable \( x \) is a pointer but this pointer is different from the global \( x \). We are allowed to change every occurrence of \( x \) inside the function to \( p \) without any change to the output of the program. Thus the line \( x+=10 \) will be considered as \( p+=10 \). The local pointer \( p \) now contains the address \( 10 \)-th term of the original sequence \( x \). Thus the value of \( *p \) is equal to \( x[10]=83 \). However, inside function \( f \), the variable \( x \) is passed by reference. Therefore the line \( x+=3 \) changes the term \( x[10] \) to become \( 86 \). This value is returned by \( f \) to the function \( g \) who immediately returns the same value to the main program. Hence after the function \( g \) is executed, the sequence \( x \) has updated the values \( x[0] \) and \( x[10] \). They are both equal to \( 86 \). The program then prints \[ x[0]+x[3]+x[10]=86+27+86=199.\]

When the objects a and b are created their attributes name have values "A" and "B", respectively. The execution of the line b=sing(a) consists of the following steps:

• 1. Creation of the variable z. It is created using copy constructor from the variable a. The value of z.name is "MA".
• 2. Creation of the variable w. It is created using the default constructor and w.name="T".
• 3. The variable r is created using copy constructor from z. We obtain r.name="MMA".
• 4. Creation of the temporary variable temp from w. This is achieved using the move constructor. We have temp.name="NT". The variable w is a victim of the move constructor and consequently its attribute name becomes equal to "TP".
• 5. Destruction of local variables. The first to be destroyed is r. The destructor prints "MMA". The second to be destroyed is w and the destructor prints "TP".
• 6. The move assignment is used to assign temp to b. The value of b.name is "BRNT". The move assignment modifies temp.name to "NTS".
• 7. The variable temp is destroyed. Its destructor prints "NTS".
• 8. The variable z is destroyed. Its destructor prints "MA".
• 9. The variable b is destroyed. The program prints "BRNT".
• 10. The variable a is destroyed and "A" is printed.

Thus the program prints

 MMA
 TP
 NTS
 MA
 BRNT
 A

We will create the map visitedCities that with each country associates the set of all cities that the user has visited.

#include<map>
 #include<set>
 #include<iostream>
 int main(){
     std::string cityName, countryName;
     std::set<std::string> cityCollection;
     std::map<std::string,std::set<std::string> > visitedCities;
     std::map<std::string,std::set<std::string> >::iterator it; 
     std::set<std::string>::iterator itSet;
     int n;
     std::cin>>n;
     for(int i=0;i<n;++i){
          std::cin>>cityName>>countryName; 
          visitedCities[countryName].insert(cityName);
     }
     for(it=visitedCities.begin();it!=visitedCities.end();++it){
          cityCollection=(*it).second;
          std::cout<<"The user has been in ";
          std::cout<<(*it).first;
          std::cout<<" and visited: ";
          for(itSet=cityCollection.begin();itSet!=cityCollection.end();++itSet){
               if(itSet!=cityCollection.begin()){
                    std::cout<<", ";
               }
               std::cout<<*itSet;
          }
          std::cout<<std::endl;
     }
     return 0;
}

As we read each line, we form the pair whose components are the string from the input and the number from the input. We check whether the number satisfies the desired property. If it does, we place the obtained pair on the stack. Once the number fail to satisfy the desired property, we test whether the stack is longer than the largest possible stack. In that case we replace the largest possible stack with the new one and reverse its order. In the end we print the content of the largest stack.

#include<map>
 #include<iostream>
 class MountainData{
 public:
     std::string st;
     double d;
 };
 class ListNode{
 public:
     MountainData content;
     ListNode* pNext;
 };
 class MyStack{
 private:
     ListNode* top;
 public:
     MyStack();
     void push(MountainData );
     MountainData pop();
     int isEmpty();
     void emptyStack();
     ~MyStack();
 };
 MyStack::MyStack(){top=nullptr;}
 void MyStack::push(MountainData x){
     ListNode* newTop;
     newTop=new ListNode;
     newTop->content=x;
     newTop->pNext=top;
     top=newTop;
 }
 MountainData MyStack::pop(){
     MountainData returnValue;  returnValue.d=0.0;
      if(top!=nullptr){
          returnValue=top->content;
          ListNode* newTop=top->pNext;
          top->pNext=nullptr;
          delete top;  top=newTop;
     }
     return returnValue;
 }
 int MyStack::isEmpty(){
     if(top==nullptr){return 1;}
     return 0;
 }
 void MyStack::emptyStack(){ while(top!=nullptr){ pop();} }
 MyStack::~MyStack(){emptyStack();}
 int correctValue(double x){
     if(x>3000.0){ return 1;}
     return 0;
 }
 int main(){
     	MyStack currentData, maxData;
     	MountainData userInput,currentLine;
     	int longestLength=0; int currentLength=0;
     	std::cin>>userInput.st>>userInput.d;
     	while(userInput.d>=0.0){
        if(correctValue(userInput.d)){
              currentData.push(userInput);  ++currentLength;
          }
          else{
              if(currentLength>longestLength){
                        longestLength=currentLength; maxData.emptyStack();
                        while(! currentData.isEmpty()){maxData.push(currentData.pop());}
              }
              currentLength=0;
          }
          std::cin>>userInput.st>>userInput.d;
     	}
     	if(currentLength>longestLength){
                longestLength=currentLength; maxData.emptyStack();
                while(! currentData.isEmpty()){ maxData.push(currentData.pop()); }
     	}
        while(!maxData.isEmpty()){
                currentLine=maxData.pop();
                std::cout<<currentLine.st<<" "<<currentLine.d<<std::endl;
     }
     return 0;
 }

Observe that this is the same problem as finding the subsequence of \(\left(b_0,b_1,b_2,\dots, b_{n-1}\right)\) that has maximal sum and whose every two terms are at least \(2\) apart.

For each \(i\in\{0,1,2,\dots, n-1\}\) denote by \(l_i\) the maximal number of birds that the cat can eat by only accessing the trees with labels in \(\left\{0,1,2,\dots, i\right\}\). Notice that the following recursion holds for \(i\geq 3\) \[L_i=\max\left\{b_i+L_{i-3},L_{i-1}\right\}.\]

The entire program is listed below.

  
#include<iostream>
 int main(){
    int n;
    std::cin>>n;
    // L_i=max{b_i+L_{i-3}, L_{i-1}
    int b_i, L_i, L_iMinus3, L_iMinus2, L_iMinus1;

    //Step 1: Initialization:
    // // // Step 1.1: L_0=b_0
    // // // Step 1.2: L_1=max{b_0,b_1}
    // // // Step 1.3: L_2=max{L_1,b_2}
    
    // Step 1.1:
    std::cin>>L_iMinus3;
    
    // Step 1.2
    std::cin>>b_i; // at the moment we have b_i=b_1
    if(b_i> L_iMinus3){
        L_iMinus2=b_i;
    }
    else{
        L_iMinus2=L_iMinus3;
    }
    
    // Step 1.3
    std::cin>>b_i;
    if(b_i>L_iMinus2){
        L_iMinus1=b_i;
    }
    else{
        L_iMinus1=L_iMinus2;
    }
    
    // Step 2: Loop
    for(int i=3; i<n; ++i){
        std::cin>>b_i;
        // Step 2.1: Calculation of L_i
        L_i=b_i+L_iMinus3;
        if(L_iMinus1>L_i){
            L_i=L_iMinus1;
        }
        // Step 2.2: Shift:
        // (L_{i-1},L_{i-2},L_{i-3}) =  (L_i, L_{i-1}, L_{i-2})
        L_iMinus3=L_iMinus2;
        L_iMinus2=L_iMinus1;
        L_iMinus1=L_i;
    }
    std::cout<<L_i<<std::endl;
    return 0;
}