MTH 4300: Final Practice 3

Recursion is a function that contains a call to itself. One problem that can be solved using the recursion is: "For given \(n\), evaluate \(n!=1\cdot2\cdot\cdots \cdot n\)." The solution is

#include<iostream>
 int fact(int n){
      if(n==0){
          return 1;
     }
     return n*fact(n-1);
 }
 int main(){
     int n;
     std::cin>>n;
     std::cout<<fact(n)<<std::endl;
     return 0;
} 

The program is displayed below

#include<iostream>
 int main(){
      int elementZero, elementOne, numElements, *elements, i;
     std::cin>>elementZero>>elementOne>>numElements;
     elements=new int [numElements];
     elements[0]=elementZero;
     elements[1]=elementOne;
     for(i=0;i<numElements-2;++i){
          elements[i+2]=(elements[i+1])*(elements[i+1])- elements[i]*elements[i];
     }
     for(i=0;i<numElements;++i){
          std::cout<<elements[i]<<" ";
     }
     std::cout<<std::endl;
     delete[] elements;
     return 0;
 }

class ComputerFolder{
 private:
     int numberOfFiles;
     std::string* namesOfFiles;
 public:
     ComputerFolder();
     ComputerFolder(const ComputerFolder&);
     ComputerFolder(ComputerFolder&&);
     int getNumFiles() const;
     void setNumFiles(const int &);
     std::string getFileName(const int &) const;
     void setFileName(const int &, const std:: string &);
     void operator=(const ComputerFolder&);
     void operator=(ComputerFolder&&);
     ~ComputerFolder();
 };
 ComputerFolder::ComputerFolder(){
     numberOfFiles=0;
     namesOfFiles=nullptr;
 }
 ComputerFolder::ComputerFolder(const ComputerFolder& copyFrom){
     numberOfFiles=copyFrom.numberOfFiles;
     namesOfFiles=new std::string[numberOfFiles];
     for(int i=0;i<numberOfFiles;++i){
          namesOfFiles[i]=copyFrom.namesOfFiles[i];
     }
 }
 ComputerFolder::ComputerFolder(ComputerFolder&& moveFrom){
     numberOfFiles=moveFrom.numberOfFiles;
     namesOfFiles=moveFrom.namesOfFiles;
     moveFrom.namesOfFiles=nullptr;
     moveFrom.numberOfFiles=0;
 }
 int ComputerFolder::getNumFiles() const{
     return numberOfFiles;
 }
 void ComputerFolder::setNumFiles(const int & n){
     if(n!=numberOfFiles){
          std::string* newSeq=nullptr;
          if(n>0){newSeq=new std::string[n];}
          int min=n;
          if(min>numberOfFiles){
               min=numberOfFiles;
          }
          for(int i=0;i<min;++i){
               newSeq[i]=namesOfFiles[i];
          }
          if(namesOfFiles!=nullptr){delete[] namesOfFiles;}
          namesOfFiles=newSeq;
          numberOfFiles=n;
     }     
 }
 std::string ComputerFolder::getFileName(const int & i) const{
     if(i<numberOfFiles){
          return namesOfFiles[i];
     }
     return "Not Found";
 }
 void ComputerFolder::setFileName(const int &i, const std:: string &newFileName){
     if(i<numberOfFiles){
          namesOfFiles[i]=newFileName;
     }
 }
 void ComputerFolder::operator=(const ComputerFolder& assignFrom){
     if(&assignFrom!=this){
     if(numberOfFiles!=assignFrom.numberOfFiles){
          numberOfFiles=assignFrom.numberOfFiles;
          if(namesOfFiles!=nullptr){
               delete[] namesOfFiles;
          }
          namesOfFiles=nullptr;
          if(numberOfFiles>0){namesOfFiles=new std::string[numberOfFiles];}
     }
     for(int i=0;i<numberOfFiles;++i){
          namesOfFiles[i]=assignFrom.namesOfFiles[i];
     }
     }
 }
 void ComputerFolder::operator=(ComputerFolder&& moveFrom){
     if(&moveFrom!=this){
     if(namesOfFiles!=nullptr){
          delete[] namesOfFiles;
     }
     numberOfFiles=moveFrom.numberOfFiles;
     moveFrom.numberOfFiles=0;
     namesOfFiles=moveFrom.namesOfFiles;
     moveFrom.namesOfFiles=nullptr;
 }
 }

 ComputerFolder::~ComputerFolder(){
     if(namesOfFiles!=nullptr){
          delete[] namesOfFiles;
     }
 }

The structure x is a sequence with 10 terms. The terms are \(0\), \( 7 \), \( 14 \), \(21\), \(28\), \( \dots \). The command

*(x+2)=*x+2;

has the same effect as

x[2]=x[0]+2;

Thus x[2] becomes 2 after this command. The program prints the first 5 terms, which are

0 7 2 21 28

We will create the set of all products. The elements of the sets will be objects of the class ProductOffer which will have attributes productName, storeName, and price. However, the comparison operator \( < \) will only compare the names of the products, thus preventing us to store two objects of the same name. As we read product offers from the user input, we will first check whether the product is already in the set, and if it is, then we will check whether the new offer has a lower price before deciding to erase the old element and replace it with the new one.

 #include<set>
 #include<iostream>
 class ProductOffer{
 public:
    double price;
    std::string productName;
    std::string storeName;
    int operator<(const ProductOffer & _PO) const;
};
int ProductOffer::operator<(const ProductOffer & _PO) const{
    if(productName<_PO.productName){
        return 1;
    }
    return 0;
}
int main(){
    std::set<ProductOffer>  bestOffers;
    std::set<ProductOffer>::iterator it;
    ProductOffer newOffer;
    newOffer.price=1.0;
    while(newOffer.price>0.0){
        std::cin>>newOffer.productName;
        std::cin>>newOffer.storeName;
        std::cin>>newOffer.price;
        if(newOffer.price>0.0){
            it=bestOffers.find(newOffer);
            if(it==bestOffers.end()){
                bestOffers.insert(newOffer);
            }
            else{
                if(it->price>newOffer.price){
                    bestOffers.erase(*it);
                    bestOffers.insert(newOffer);
                }
            }
        }
    }
    for(it=bestOffers.begin();it!=bestOffers.end();++it){
        std::cout<<it->productName<<" sold for ";
        std::cout<<it->price<<" at ";
        std::cout<<it->storeName;
        std::cout<<std::endl;
    }
    return 0;
}

Assume that \(a\) and \(b\) are two positive integers. Let \(\left(\alpha_0,\alpha_1,\dots, \alpha_m\right)\) and \(\left(\beta_0,\beta_1,\dots, \beta_m\right)\) be their expansions in base \(k\). In other words, \begin{eqnarray*} a&=&\alpha_0+\alpha_1k+\alpha_2k^2+\cdots +\alpha_mk^m\newline b&=&\beta_0+\beta_1k+\beta_2k^2+\cdots+\beta_mk^m. \end{eqnarray*} Define the binary operation \(\oplus_k\) in the following way: \(a\oplus_k b\) is the unique integer whose expansion in base \(k\) is \[\Big((\alpha_0+\beta_0)\%k, (\alpha_1+\beta_1)\%k,\dots, (\alpha_m+\beta_m)\%k\Big).\]

Let us denote by \(x_0\), \(x_1\), \(\dots\), \(x_{N-1}\) the elements of the sequence \(x\). Here we have \(N=kn+1\). We will prove that the number that appears exactly \(k+1\) times is \[e = x_0\oplus_kx_1\oplus_kx_2\oplus_k\cdots\oplus_k x_{N-1}.\] Indeed, the desired statement holds from the fact that \(\oplus_k\) is commutative and associative since it is component-wise modulo \(k\) addition of integers from the set \(\{0,1,\dots, k-1\}\). In each component we are adding \(nk+1\) integers such that each of the \(n\) integers appears \(k\) times and thus add to \(0\). The integer that appears once more will have each of its digit in base-\(k\) representation remain.

The entire program is listed below.

  
#include<iostream>
int noCarryOverSum(int x, int y, int k){
    int result=0,multiplier=1;
    while((x>0)||(y>0)){
        result += (((x%k)+(y%k))%k)*multiplier;
        multiplier *= k;
        x /= k;
        y /= k;
    }
    return result;
}
int main(){
    int n,k,input,result=0;
    std::cin>>n>>k;
    int inputSize=n*k+1;
    for(int i=0;i<inputSize;++i){
        std::cin>>input;
        result=noCarryOverSum(result,input,k);
    }
    std::cout<<result<<std::endl;
    return 0;
}