Description

Create a class Matrix to represent a N * N matrix.

Provide public member functions that perform or derive:

1. Matrix addition.
2. Matrix subtraction.
3. Matrix Multiplication.
4. Adding cell value by 1 (module 10). That is, if after adding 1, a cell value becomes 10 we change it to 0.
5. Matrix Transpose.

 

Hint:

Transpose of a Matrix:

A matrix which is formed by turning all the rows of a given matrix into column and vice-versa.

 

Example：

Note:

1.  This problem involves three files.

• function.h: Class definition of Matrix.
• function.cpp: Member-function definitions of Matrix.
• main.cpp: A driver program to test your class implementation.

You will be provided with function.h and main.cpp, and asked to implement function.cpp.

 

 

function.h

#ifndef MATRIX_H #define MATRIX_H class Matrix { public: Matrix(); Matrix (const int , const int [50][50]); Matrix add(const Matrix) const;//add function Matrix subtract(const Matrix) const;//subtract function Matrix multiplication(const Matrix) const;//multiply function Matrix inc() const;//increased by 1 void Transpose() const;//Transpose function void output() const;//Note that each output should be followed by a new //line character. private: int matrix[50][50]; int matrix_size; }; //end class Matrix #endif /* function_h */

main.cpp

#include <iostream> #include <stdio.h> #include "function.h" using namespace std; int main(){ int N; int matrix1[50][50], matrix2[50][50]; Matrix ans; cin >> N; for (int i = 0; i<N; i++) { for (int j = 0; j<N; j++) { cin >> matrix1[i][j]; } } for (int i = 0; i<N; i++) { for (int j = 0; j<N; j++) { cin >> matrix2[i][j]; } } Matrix a(N, matrix1), b(N, matrix2); ans = a.add( b ); ans.output(); cout << endl; ans = a.subtract( b ); ans.output(); cout << endl; ans = a.multiplication( b ); ans.output(); cout << endl; a.inc().output(); cout << endl; b.inc().output(); cout << endl; a.Transpose(); cout << endl; b.Transpose(); } // end main

2. For OJ submission:

       Step 1. Include function.h into function.cpp and then implement your function.cpp. (You don’t need to modify function.h and main.cpp)

       Step 2. Submit the code of function.cpp into submission block.

       Step 3. Check the results and debug your program if necessary.

 

Input

The first line has an integer N (1<=N<=50), which means the size of the matrix. The total number of elements in the matrix is thus N * N.

 

For the next 2N lines: the first N lines specify the elements of the first matrix a, and the following N lines specify those of the second matrix b. All of the integers in the same line are separated by a space.

Output

Your program should print the corresponding results followed by a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10992.cpp

Partial Judge Header

10992.h

Tags

Discuss

Description

Create a class Polynomial. The internal representation of a Polynomial is an array of terms. Each term contains a coefficient and an exponent, e.g., the term 2x⁴ has the coefficient 2 and the exponent 4.

• Use a 51-element array, coefficients, of digits to store each coefficient.
• Use a integer variable, greatestPower, to store an exponent.

 

Provide public member functions that perform each of the following tasks:

1. Adding two Polynomial.
2. Subtracting two Polynomial.
3. Multiplying two Polynomial.
4. Printing coefficients of the Polynomial in descending order.

 

Note:

1.      This problem involves three files.

• function.h: Class definition of Polynomial.
• function.cpp: Member-function definitions of Polynomial.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp, and asked to implement function.h and function.cpp.

function.h

#ifndef POLYNOMIAL_H #define POLYNOMIAL_H #include <iostream> class Polynomial { public: Polynomial(); Polynomial(const int , const int [51]); Polynomial add( const Polynomial) const; // add function Polynomial subtract( const Polynomial ) const; // subtract function Polynomial multiplication( const Polynomial ) const; // multiplication function void output() const; private: int coefficients[101]; // integer coefficients int greatestPower; // integer greatestPower }; // end class Polynomial #endif

main.cpp

#include <iostream> #include <stdio.h> #include <string> #include "function.h" using namespace std; int main() { int greatestPower1, greatestPower2; int coefficient1[51], coefficient2[51]; Polynomial ans; cin>>greatestPower1; for(int i = greatestPower1 ; i >= 0; i--) { cin>>coefficient1[i]; } cin>>greatestPower2; for(int i = greatestPower2 ; i >= 0 ; i--) { cin>>coefficient2[i]; } Polynomial a(greatestPower1, coefficient1), b(greatestPower2, coefficient2) ; ans = a.add( b ); ans.output(); cout << endl; ans = a.subtract( b ); ans.output(); cout << endl; ans = a.multiplication( b ); ans.output(); cout << endl; } // end main

2.     For OJ submission:

       Step 1. Submit only your function.cpp into the submission block.

       (***Note that you don’t need to submit your function.h.)

       Step 2. Check the results and debug your program if necessary.

Input

There are four lines.

The first two lines represent the greatest power and the corresponding coefficients of the first polynomial.

The last two lines represent the greatest power and the corresponding coefficients of the second polynomial.

Note that the coefficients are in descending order and each element is separated by a blank.

Output

Your program should print the coefficients of the sum, difference and product of these two polynomials in descending order, respectively.

Note that every answer should be followed by a new line character.

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

10993.cpp

Partial Judge Header

10993.h

Tags

Discuss

Description

Create a class Matrix to represent an N x N matrix.

Provide public member functions that perform or derive:

1. Interchanging two rows.
2. Rotating Matrix by 90° clockwise.
3. Rotating Matrix by 90° counter clockwise.
4. Checking if Matrix is symmetric or not. If yes, print “yes”, otherwise, print “no”.

Hint:

• Symmetric

A matrix A = (a_ij) is symmetric if its entries are symmetric with respect to the main diagonal, that is, a_ij = a_ji, for all indices i and j.

The following 3 x 3 matrix is symmetric:

1 7 3

7 4 -5

3 -5 6

 

Note:

1.  This problem involves three files.

• function.h: Class definition of Matrix.
• function.cpp: Member-function definitions of Matrix.
• main.cpp: A driver program to test your class implementation.

You will be provided with function.h and main.cpp, and asked to implement function.cpp.

function.h

#ifndef MATRIX_HPP #define MATRIX_HPP class Matrix { public: Matrix(); Matrix (const int , const int[50][50]); Matrix row( const int, const int) const; Matrix rotate90() const; Matrix rotatecounter90() const; void symmetric() const; void output() const; private: int matrix[50][50]; int matrix_size; }; //end class Matrix #endif

main.cpp

#include <iostream> #include <stdio.h> #include "function.h" using namespace std; int main(){ int matrixsize; int matrix1[50][50]; cin >> matrixsize; for (int i = 0; i<matrixsize; i++) { for (int j = 0; j<matrixsize; j++) { cin >> matrix1[i][j]; } } int s1, s2; cin >> s1 >> s2; Matrix a(matrixsize, matrix1); Matrix ans; ans = a.row(s1,s2); ans.output(); cout << endl; ans = a.rotate90(); ans.output(); cout << endl; ans = a.rotatecounter90(); ans.output(); cout << endl; a.symmetric(); } // end main

2. For OJ submission:

       Step 1. Include function.h into function.cpp and then implement your function.cpp. (You don’t need to modify function.h and main.cpp)

       Step 2. Submit the code of function.cpp into submission block.

       Step 3. Check the results and debug your program if necessary.

Input

The first line has an integer N (2<=N<=50), which means the size of the matrix. The total number of elements in the matrix is thus N x N.

For the next N lines, each contains N integers, specifying the elements of the matrix.

The last line has two integers, which mean two row indices for performing row exchange.

All of the integers in the same line are separated by a space.

Output

Your program should print the corresponding results, and each is followed by a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10994.cpp

Partial Judge Header

10994.h

Tags

Discuss

Description

The Josephs problem is notoriously known. For those who are not familiar with the problem, among n people numbered 1, 2, . . . , n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give the message about the incident.

The persons are eliminated in a very peculiar order; m is a dynamical variable, which each time takes a different value corresponding to the Fibonacci numbers succession (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...). So in order to kill the i-th person, Josephus counts up to the i-th Fibonacci number.

For example, there are 6 people in a circle, and the sequence of counting is Fibonacci number succession (1, 1, 2, 3, 5 …).

In the beginning, the step to kill m = 1. The sequence of killing people is as follows.

1.............................(kill 1, and m is changed to 1)

2.............................(kill 2, and m is changed to 2)

3, 4.........................(kill 4 ,and m is changed to 3)

5, 6, 3.....................(kill 3 ,and m is changed to 5)

5, 6, 5, 6, 5.............(kill 5)

Then print 6 as answer.

 

Let’s solve this problem using C++. You have been provided with the following class definitions:

 

class Node

{

   friend class Josephus;

   public:

        Node():next( NULL ){

        }

          Node( const int &info ) //constructor

      :number( info ), next( NULL )

      {

      } //end ListNode constructor

   private:

          Node *next;

        int number;

};//end class Node

 

class Josephus

{

    public:

         Josephus();

         ~Josephus();

         Josephus(const int &);

         int kill(); // return the survival’s position

 

    private:

        void generatecircularlinkedList(const int &); // generate circular linked-list

        void generateFib(const int &); // generate a Fibonacci sequence table

        int sequence[50]; // store Fibonacci number

        int noOfPeople;

        Node *head;

};

 

REQUIREMENTS:

In this practice, you are asked to implement the following member functions:

Josephus class:

• constructor
• destructor
• int kill();
• void generatecircularlinkedList(const int &);
• void generateFib(const int &);

Note:

1.This problem involves three files.

• function.h: Class definitions.
• function.cpp: Member-function definitions.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

function.h

#ifndef FUNCTION_H #define FUNCTION_H #include <iostream> class Node { friend class Josephus; public: Node():next( NULL ){ } Node( const int &info ) //constructor :number( info ), next( NULL ) { } //end ListNode constructor private: Node *next; int number; };//end class Node class Josephus { public: Josephus(); ~Josephus(); Josephus(const int &); int kill(); // return the survival’s position private: void generatecircularlinkedList(const int &); // generate circular linked-list void generateFib(const int &); // generate a Fibonacci sequence table int sequence[50]; // store Fibonacci number int noOfPeople; Node *head; }; #endif // FUNCTION_H

main.cpp

#include <iostream> #include "function.h" using namespace std; int main(){ int numofpeople; while(cin>>numofpeople){ Josephus Jose(numofpeople); int survival = Jose.kill(); cout<<survival<<endl; } }

2.For OJ submission:

       Step 1. Submit only your function.cpp into the submission block.

       Step 2. Check the results and debug your program if necessary.

Input

Each line contains a number n<=45, which is the number of people. Input is terminated by EOF.

Output

The output will consist in separate lines containing the position of the person which life will be saved.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10996.cpp

Partial Judge Header

10996.h

Tags

Discuss

Description

A queue is an abstract data type that serves as a collection of elements, where nodes are removed only from the head of the queue and are inserted only at the tail of the queue. Two principal operations can be used to manipulate a queue: enqueue, which inserts an element at the tail, and dequeue, which removes the element at the head of the collection.

Let’s see how the queue data structure can be realized in C++.We have an approach to implement queue: linked list. Thus, we define a class as follows:

 class List_queue {

    public:

        List_queue();

        ~List_queue();

        void enqueue(const int &);

        void dequeue();

        void print();

    private:

        ListNode *head;

        ListNode *tail;

};

where List_queue implements the queue data structure.

REQUIREMENTS:

Implement the constructor, destructor, enqueue(), dequeue() and print() member functions of the List_queue class.

Note:

1.This problem involves three files.

• function.h: Class definitions.
• function.cpp: Member-function definitions.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

function.h

#ifndef FUNCTION_H #define FUNCTION_H #include <iostream> class ListNode { friend class List_queue; //make List_queue a friend public: ListNode( const int &info ) //constructor : data( info ), nextPtr( NULL ), prevPtr( NULL ) { } //end ListNode constructor private: int data; //data ListNode *nextPtr; // next node in list ListNode *prevPtr; }; //end class ListNode class List_queue { public: List_queue(); ~List_queue(); void enqueue(const int &); void dequeue(); void print(); private: ListNode *head; ListNode *tail; }; #endif

main.cpp

#include<iostream> #include<string.h> #include "function.h" using namespace std; int main(){ List_queue L_queue; char command[10]; int n; while(cin>>command){ if(strcmp(command,"dequeue")==0){ L_queue.dequeue(); }else if(strcmp(command,"enqueue")==0){ cin >> n; L_queue.enqueue(n); }else if(strcmp(command, "print") == 0){ L_queue.print(); cout << endl; } } return 0; }

2.For OJ submission:

       Step 1. Submit only your function.cpp into the submission block.

       Step 2. Check the results and debug your program if necessary.

Input

There are three kinds of commands:

• “enqueue integerA” represents inserting an element with int value A at the tail of the queue.
• “dequeue” represents removing the element at the head of the queue.
• “print” represents showing the current content of the queue.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output should consist of the current state of the queue.

When the queue is empty, you don’t need to print anything except a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10997.cpp

Partial Judge Header

10997.h

Tags

Discuss

Description

A stack is an abstract data type that serves as a collection of elements, where a node can be added to a stack and removed from a stack only at its top. Two principal operations can be used to manipulate a stack: push, which adds an element at the top, and pop, which removes the element at the top of the collection.

Let’s see how the stack data structure can be realized in C++.We have an approach to implement stack: linked list. Thus, we define a class as follows:

class List_stack {

    public:

        List_stack();

        ~List_stack();

        void push(const int &);

        void pop();

        void print();

    private:

        ListNode *head;

        ListNode *tail;

};

where List_stack implements the stack data structure

 

REQUIREMENTS:

Implement the constructor, destructor, push(), pop() and print() member functions of List_stack classes.

Note:

1.This problem involves three files.

• function.h: Class definitions.
• function.cpp: Member-function definitions.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

function.h

#ifndef FUNCTION_H #define FUNCTION_H #include <iostream> class ListNode { friend class List_stack; //make List_stack a friend public: ListNode( const int &info ) //constructor : data( info ), nextPtr( NULL ), prevPtr( NULL ) { } //end ListNode constructor private: int data; //data ListNode *nextPtr; // next node in list ListNode *prevPtr; }; //end class ListNode class List_stack { public: List_stack(); ~List_stack(); void push(const int &); void pop(); void print(); private: ListNode *head; ListNode *tail; }; #endif // FUNCTION_H

main.cpp

#include<iostream> #include<string.h> #include "function.h" using namespace std; int main(){ List_stack L_stack; char command[10]; int n; while(cin>>command){ if(strcmp(command,"pop")==0){ L_stack.pop(); }else if(strcmp(command,"push")==0){ cin >> n; L_stack.push(n); }else if(strcmp(command, "print") == 0){ L_stack.print(); cout << endl; } } return 0; }

2.For OJ submission:

       Step 1. Submit only your function.cpp into the submission block.

       Step 2. Check the results and debug your program if necessary.

Input

There are three kinds of commands:

• “push integerA” represents adding an element with int value A at the top of the stack.
• “pop “ represents removing the element at the top of the stack.
• “print” represents showing the current content of the stack.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output should consist of the current state of the stack.

When the stack is empty, you don’t need to print anything except a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10998.cpp

Partial Judge Header

10998.h

Tags

Discuss

Description

function.h

#ifndef POLYNOMIAL_H #define POLYNOMIAL_H #include <iostream> class Polynomial { friend std::ostream &operator<<(std::ostream &, const Polynomial &); public: Polynomial(); Polynomial(const int &, const int [51]); Polynomial operator+( const Polynomial & ) const; // addition Polynomial operator-( const Polynomial & ) const; // subtraction Polynomial operator*( const Polynomial & ) const; // multiplication private: int coefficients[101]; int greatestPower; }; // end class Polynomial #endif

 

main.cpp

 

#include <iostream> #include <string> #include "function.h" using namespace std; int main() { int greatestPower1, greatestPower2; int coefficient1[51], coefficient2[51]; Polynomial ans; cin>>greatestPower1; for(int i = greatestPower1 ; i >= 0; i--) { cin>>coefficient1[i]; } cin>>greatestPower2; for(int i = greatestPower2 ; i >= 0 ; i--) { cin>>coefficient2[i]; } Polynomial a(greatestPower1, coefficient1), b(greatestPower2, coefficient2); ans = a + b; cout<<ans<<endl; ans = a - b; cout<<ans<<endl; ans = a * b; cout<<ans<<endl; } // end main

2.     For OJ submission:

Step 1. Submit only your function.cpp into the submission block. (***Note that you don’t need to submit your function.h.)

Step 2. Check the results and debug your program if necessary.

​

Input

There are four lines.

The first two lines represent the greatest power and the corresponding coefficients of the first polynomial.

The last two lines represent the greatest power and the corresponding coefficients of the second polynomial.

Note that the coefficients are in descending order and each element is separated by a blank.

Output

Your program should print the coefficients of the sum, difference and product of these two polynomials in descending order, respectively.

Note that every answer should be followed by a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11001.cpp

Partial Judge Header

11001.h

Tags

Discuss

Description

Develop a class called Rational for performing arithmetic with fraction.

• Use integer variables to represent the private data of the class ─ the numerator and the denominator.
• Provide a constructor that enables an object of this class to be initialized when it’s declared. The constructor should contain default values in case no initializers are provided and should store the fraction in reduced form. For example, the fraction 2/4 would be stored in object as 1 in the numerator and 2 in the denominator.
• Develop a complete class containing proper constructor functions. The class should also provide the following overloaded operator capabilities:

1.Overload the addition operator (+) to add two Rational numbers.

   The result should be stored in reduced form.

2.Overload the subtraction operator (-) to subtract two Rational numbers. 

   The result should be stored in reduced form.

3.Overload the multiplication operator (*) to multiply two Rational numbers.

  The result should be stored in reduced form.

4.Overload the division operator (/) to divide two Rational numbers.

   The result should be stored in reduced form.

5.Overload the stream insertion operator (<<).

   Printing Rational numbers in form a/b, where a is the numerator and b is the denominator.) 

 

• You need to implement a private member function reduce() that will be used in your constructor and the about public arithmetic member functions to derive the required reduced form. ***In reduce(), pay attention to the case that one of the numerator and denominator of a rational number is negative. In this case, the negative sign “-” should be placed at the numerator.

Note:

1. This problem involves three files.
2. function.h: Class definition of Rational.
3. function.cpp: Member-function definitions of Rational.
4. main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

 

function.h

#ifndef RATIONAL_H #define RATIONAL_H class Rational { friend std::ostream &operator<<(std::ostream &, const Rational &); public: Rational( int = 0, int = 1 ); // default constructor Rational operator+( const Rational & ) const; // function addition Rational operator-( const Rational & ) const; // function subtraction Rational operator*( const Rational & ) const; // function multi. Rational operator/( const Rational & ) const; // function division //void printRational () const; // print rational format private: int numerator; // integer numerator int denominator; // integer denominator void reduce(); }; // end class Rational #endif

main.cpp

#include <iostream> #include "function.h" using namespace std; int main() { char s1; int s2, s3, s4, s5; Rational x; while(cin >>s1>>s2>>s3>>s4>>s5) { if(cin.eof()) { break; } Rational c(s2, s3), d(s4, s5); if(s1 == '+') { x = c + d; cout<< x <<endl; } else if(s1 == '-') { x = c - d; cout<< x <<endl; } else if(s1 == '*') { x = c * d; cout<< x <<endl; } else if(s1 == '/') { x = c / d; cout<< x <<endl; } } } // end main

 

Input

There are five strings in each line: S1 S2 S3 S4 S5

• ŸS1 represents an operator (+,-,*,/).
• S2 and S3 represent the numerator and denominator of the first operand, respectively.
• S4 and S5 represent the numerator and denominator of the second operand, respectively.

Input terminated by EOF.

Output

For every given operation, your program should print the corresponding result followed by a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11002.cpp

Partial Judge Header

11002.h

Tags

Discuss

Description

Palindrome is a string that is identical to its reverse, like "level" or "aba". Check whether a given string is a palindrome or not. 

Create a class SimpleString that manipulates a given string of characters. This class contains proper constructor functions (default constructor and copy constructor) and supports the following operations (in the form of member functions):

• Ÿ   Overloading the assignment operator (=) to assign one given SimpleString object to the current SimpleString object.
• Ÿ   Reversing the string which is stored in the SimpleString object.
• Ÿ   Overloading the relational operator (==) to check whether two strings, which are stored in two SimpleString objects, are the same or not.

To check if a given string is a palindrome, we have provided another class PalindromeChecker as follows:

class PalindromeChecker

{

public:

    PalindromeChecker(const SimpleString &s)

    {

        str = s;

        rev = s;

        rev.reverse();

    };

    void isPalindrome()

    {

        if(rev == str)

            std::cout << "Yes\n";

        else

            std::cout << "No\n";

    };

private:

    SimpleString str;

    SimpleString rev;

};

Note:

This problem involves three files.

•   function.h: Class definition of SimpleString.
•   function.cpp: Member-function definitions of SimpleString.
•   main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

Note that you don’t need to implement class PalindromeChecker

function.h

#ifndef SIMPLESTRING_H #define SIMPLESTRING_H #include <iostream> class SimpleString { public: SimpleString( char* = NULL, int = 0 ); // default constructor SimpleString( const SimpleString & ); // copy constructor ~SimpleString(); // destructor const SimpleString &operator=( const SimpleString & ); // assignment operator bool operator==( const SimpleString & ) const; // equality operator void reverse(); // reverse the string private: size_t size; // pointer-based string size char *ptr; // pointer to first element of pointer-based string }; // end class SimpleString class PalindromeChecker { public: PalindromeChecker(const SimpleString &s) { str = s; rev = s; rev.reverse(); }; void isPalindrome() { if(rev == str) std::cout << "Yes\n"; else std::cout << "No\n"; }; private: SimpleString str; SimpleString rev; }; #endif

main.cpp

#include <iostream> #include <cstring> #include "function.h" using namespace std; int main() { char input[100001]; while(cin >> input){ SimpleString s(input, strlen(input)); PalindromeChecker c(s); c.isPalindrome(); } return 0; }

Input

The input consists of multiple lines. Each line contains a string. The length of each string is less than 100000. The number of test case is less than 1000. 

Output

For each test case, output "Yes" if it's a palindrome or "No" if it's not a palindrome in a line. 

Sample Input  Download

Sample Output  Download

Partial Judge Code

11003.cpp

Partial Judge Header

11003.h

Tags

Discuss

Description

Google uses "word count" as a preprocessing for its search engine.  The program reads an article which has many words, and outputs the counts of each distinguished words.  The output words are sorted in the dictionary order.  A "word" is defined as a consecutive sequence of English letters (upper and/or lower case).

A class WordCount has been defined as follows:
 

function.h

#include <iostream> #include <string> using namespace std; class WordCount { public: WordCount(){}; ~WordCount(){}; /** read word into 'words' array and count words number 'numberOfTotalWords' at same time **/ void readWords(); /** sort words in the 'words' array in the dictionary order. **/ void sortWords(); /** find out number of different words and store in 'numberOfDiffWords' and put different words in string array 'diffwords' using the 'diffwords' array to count each words appear times and put in 'counting' **/ void countWords(); /** print out the result in format: <words><space><appear times> **/ void dumpResult(); private: static const int numberOfMaxWords=65536; string words[numberOfMaxWords]; ///store the input article int numberOfTotalWords; /// the total number of words string *diffwords; /// store the pointer to different words int numberOfDiffWords; /// the number of different words int *counting; /// counts for different words };

main.cpp

#include <iostream> #include "function.h" using namespace std; int main() { WordCount wc; wc.readWords(); wc.sortWords(); wc.countWords(); wc.dumpResult(); return 0; }

Your job is to implement each member function of the class.

Input

An article and end with EOF

Output

Print the counts of each distinguished words

Sample Input  Download

Sample Output  Download

Partial Judge Code

11008.cpp

Partial Judge Header

11008.h

Tags

Discuss

Description

Let’s implement a list class.

• Task 1:

First you are asked to implement class OWList (standing for “one-way list”). You have definitions of classes ListNode and OWList as follows:

         class ListNode
         {
                friend class OWList; //make OWList a friend
                friend class TWList; //make TWList a friend

          public:
                ListNode( const int &info ) //constructor
                : data( info ), nextPtr( NULL )
                {
                } //end ListNode constructor

           private:
               int data; //data
               ListNode *nextPtr; // next node in list

           }; //end class ListNode

           class OWList
           {
           public:
                //default constructor
                OWList();
                //destructor
                ~OWList();
                //insert node at front of list
                void insertAtFront( const int &value );
                //remove node from front of list
                void removeFromFront();
                //is List empty?
                bool isEmpty() const;
                //display contents of List
                void print() const;

            protected:
                ListNode *firstPtr; //pointer to first node
                ListNode *lastPtr;  //pointer to last node
             }; // end class OWList

            Requirement: Implement the member functions

             1. “OWList::OWList();”: initializes the two pointers firstPtr and lastPtr as NULL.

             2. “OWList::~OWList();”: deletes allocated dynamic memory space.

             3. “void OWList::insertAtFront( const int &value );”

             4. “int OWList::removeFromFront();”

             5. “bool OWList::isEmpty() const;”

             6. “void OWList::print() const;”

• Task 2:

Implement another class TWList (standing for “two-way list”), which is derived from class OWList:

        class TWList:public OWList
        {
        public:
             //default constructor
             TWList()
             :OWList()
              {
                    /*It will still work correctly if you omit the constructor call of the base class in the above member                            initializer list. The compiler will invoke this default constructor of OWList implicitly.*/
              }
              //destructor
              ~TWList()
              {
                     /*You don't need to delete the list again because the

                        compiler will invoke the destructor of the base class OWList to do this.*/
              }
              //insert node at back of list
             void insertAtBack( const int &value );
              //delete node from back of list
             void removeFromBack();

          };

            Besides the functions inherited from OWList, TWList has two more functions: insert a node at the end of             the list and remove a node from the end of the list.

           Requirement: Implement the member functions

            7. “void TWList:: insertAtBack( const int &value );”

          8.“int TWList:: removeFromBack();”

Note:

1.      This problem involves three files.

• function.h: Class definitions.
• function.cpp: Member-function definitions.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

#ifndef FUNCTION_H

#define FUNCTION_H

#include <iostream>

class ListNode

{

    friend class OWList; //make OWList a friend

    friend class TWList; //make TWList a friend

 

public:

    ListNode( const int &info ) //constructor

    : data( info ), nextPtr( NULL )

    {

    } //end ListNode constructor

 

private:

    int data; //data

    ListNode *nextPtr; // next node in list

}; //end class ListNode

 

 

class OWList

{

public:

    //default constructor

    OWList();

    //destructor

    ~OWList();

    //insert node at front of list

    void insertAtFront( const int &value );

    //remove node from front of list

    void removeFromFront();

    //is List empty?

    bool isEmpty() const;

    //display contents of List

    void print() const;

 

protected:

    ListNode *firstPtr; //pointer to first node

    ListNode *lastPtr;  //pointer to last node

 

}; // end class OWList

 

class TWList:public OWList

{

public:

    //default constructor

    TWList()

    :OWList()

    {

        /*It will still work correctly if you omit the constructor call of the base

          class in the above member initializer list. The compiler will invoke this

          default constructor of OWList implicitly.*/

    }

    //destructor

    ~TWList()

    {

        /*You don't need to delete the list again because the compiler

          will invoke the destructor of the base class OWList to do this.*/

    }

    //insert node at back of list

    void insertAtBack( const int &value );

    //delete node from back of list

    void removeFromBack();

};

#endif

#include <iostream>

#include <string>

#include "function.h"

using namespace std;

int main()

{

    TWList integerList;

    int command;

    int value; // store node value

 

    while (cin >> command)

    {

        switch(command)

        {

        case 1: // insert at beginning

            cin >> value;

            integerList.insertAtFront(value);

            break;

        case 2: // insert at end

            cin >> value;

            integerList.insertAtBack(value);

            break;

        case 3: // remove from beginning

            integerList.removeFromFront();

            break;

        case 4: // remove from end

            integerList.removeFromBack();

            break;

        }

    }

    integerList.print();

    cout<<endl;

}

2.      For OJ submission:

        Step 1. Submit only your function.cpp into the submission block.

        Step 2. Check the results and debug your program if necessary.

Input

There are four types of command:

• “1 integerA” represents inserting a node with int value A at the head of the list.
• “2 integerB” represents inserting a node with int value B at the end of the list.
• “3” represents removing the node at the head of the list
• “4” represents removing the node at the end of the list

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output should consist of the final state of the list. 

Sample Input  Download

Sample Output  Download

Partial Judge Code

11010.cpp

Partial Judge Header

11010.h

Tags

Discuss

Description

The task is to define the class ‘RleCodec’ for run-length encoding.

About implementing the virtual function:

We have the base class ‘Codec’ as an interface. The member functions in ‘Codec’ are pure virtual functions. Therefore we need to implement those virtual functions in the derived class ‘RleCodec’. The functions ‘decode’, ‘show’, ‘is_encoded’ are already done. The only function you need to complete is ‘RleCodec::encode’ in ‘function.cpp’.

In ‘main.cpp’, we see two functions having an argument of type ‘Codec&’:

    std::ostream& operator<<(std::ostream& os, Codec& data);

    void encode_decode(Codec& data);

Since ‘RleCodec’ is a derived class of ‘Codec’, we may pass an object of ‘RleCodec’ to the above two functions by reference as if it is an object of ‘Codec’. Calling ‘data.show(os);’ will invoke the virtual function of the corresponding derived class.

About run-length encoding:

The rule of run-length encoding is simple: Count the number of consecutive repeated characters in a string, and replace the repeated characters by the count and a single instance of the character. For example, if the input string is ‘AAADDDDDDDBBGGGGGCEEEE’, its run-length encoding will be ‘3A7DBB5GC4E’, because there are three A’s, seven D’s, … etc. Note that we do not need to encode runs of length one or two, since ‘2B’ and ‘1C’ are not shorter than ‘BB’ and ‘C’.

In ‘function.h’, we add the class ‘DummyCodec’ as a sample of implementing a derived class of the base class ‘Codec’. You do not need to change anything in ‘function.h’. The only function you need to write for this problem is the function ‘RleCodec::encode’ in ‘function.cpp’.

Hint: std::stringstream could be useful in solving this problem. Please refer to ‘RleCodec::decode’ for how to use std::stringstream.

You only need to submit ‘function.cpp’. OJ will compile it with ‘main.cpp’ and ‘function.h’.

We have already provided partial function.cpp belowed.

Note that if you can't use "auto".

For codeblock, go to the codeblock menu Settings --> Compiler ... --> Compiler flags and check Have g++ follow the C++11 ISO C++ language standard [-std=c++11]

For command line compiler, use g++ myprog.cpp -std=c++11 -o myprog

main.cpp

#include <iostream> #include "function.h" std::ostream& operator<<(std::ostream& os, Codec& data) { data.show(os); return os; } void encode_decode(Codec & data) { if (!data.is_encoded()) data.encode(); else data.decode(); } int main() { std::string input_string; std::cin >> input_string; DummyCodec dummy{input_string}; encode_decode(dummy); std::cout << "Dummy encoding: "; std::cout << dummy << std::endl; encode_decode(dummy); std::cout << "Dummy decoding: "; std::cout << dummy << std::endl; RleCodec rle{input_string}; encode_decode(rle); std::cout << "RLE encoding: "; std::cout << rle << std::endl; encode_decode(rle); std::cout << "RLE decoding: "; std::cout << rle << std::endl; }

function.h

#ifndef _FUNC_H #define _FUNC_H #include <iostream> #include <string> class Codec { public: virtual void encode() = 0; virtual void decode() = 0; virtual ~Codec() { } // Do nothing virtual void show(std::ostream& os) const = 0; virtual bool is_encoded() const = 0; }; class DummyCodec: public Codec { public: DummyCodec(std::string s): encoded{false}, code_str{s} { } void encode() { encoded = true; } void decode() { encoded = false; } void show(std::ostream& os) const { os << code_str; } bool is_encoded() const { return encoded; } private: bool encoded; std::string code_str; }; class RleCodec: public Codec { public: RleCodec(std::string s): encoded{false}, code_str{s} { } void encode(); void decode(); void show(std::ostream& os) const { os << code_str; } bool is_encoded() const { return encoded; } private: bool encoded; std::string code_str; }; #endif

function.cpp

void RleCodec::encode() { // Your code here encoded = true; } void RleCodec::decode() { //No cheating : ) }

 

 

Input

A line contains of several characters .

Output

There are four lines.

The first and second lines are dummy encoding and decoding. You don't need to implement it.

The third and forth lines are RLE encoding and decoding.

Each line is followed by a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11014.cpp

Partial Judge Header

11014.h

Tags

Discuss

Description

If you are not familiar with partial judge , please check this handout

---

A. Definition of Binary Search Trees

A binary search tree (BST) is a binary tree, whose internal nodes each store a key and each have two sub-trees, commonly denoted left and right. The tree additionally satisfies the property: the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in the right sub-tree.

Based on the above property of BSTs, when a node is to be inserted into an existing BST, the location for the node can be uniquely determined. For example, if a node with key 6 needs to be inserted into the following BST

the BST will become

 

B. Implementation of the BST Data Structure

There are two approaches to BST implementation: array and linked list.

1. Array:

An approach to storing a BST is to use a single, contiguous block of memory cells, i.e., an array, for the entire tree. We store the tree’s root node in the first cell of the array. (Note that, for ease of implementation, we ignore the 0th cell and start from the 1st cell.) Then we store the left child of the root in the second cell, store the right child of the root in the third cell, and in general, continue to store the left and right children of the node found in cell n in the cells 2n and 2n+1, respectively. Using this technique, the tree below

would be stored as follows

 

2. Linked list:

We set a special memory location, call a root pointer, where we store the address of the root node. Then each node in the tree must be set to point to the left or right child of the pertinent node or assigned the NULL value if there are no more nodes in that direction of the tree.

 

C. Detailed C++ Implementation for BST

Let’s see how the BST data structure can be realized in C++.We have two different approaches to BST implementation: array and linked list. Thus, we define four classes and use polymorphism as follows:

function.h

#ifndef function_h #define function_h #include <iostream> #include <math.h> using namespace std; class BST{ public: BST():Height(0){} virtual ~BST() {} virtual void insert(const int &) = 0; virtual bool search(const int &) const = 0; virtual void print() const = 0; int height() const { return Height; }// An empty tree has height of 0. A tree with only root node has height of 1. protected: int Height; }; class Array_BST : public BST{ public: Array_BST(); virtual ~Array_BST() {} virtual void insert(const int &) override; //root node is stored at index 1. virtual bool search(const int &) const override; virtual void print() const override{ int k = pow(2, height()); for (int i = 1; i <= k-1; i++) { if (array[i] != 0) cout << array[i] << " "; } } private: int array[1025]; }; class ListNode{ friend class List_BST; //make List_BST a friend public: ListNode(const int &info):key( info ),left( NULL ),right( NULL ) //constructor { }//end ListNode constructor private: int key; ListNode *left; ListNode *right; };//end class ListNode class List_BST : public BST{ public: List_BST(); virtual ~List_BST() { deleteTree(root); } virtual void insert(const int &) override; virtual bool search(const int &) const override; virtual void print() const override{ int i; for(i = 1; i <= Height; i++){ printGivenLevel(root, i); } } private: ListNode *root; // private member functions ListNode* createLeaf(int key) const; //new a ListNode and return its address /* clean a tree.*/ void deleteTree(ListNode *root); void printGivenLevel(ListNode* Ptr, int level) const { if (Ptr == NULL) return; if (level == 1) cout << Ptr->key << " "; else if (level > 1) { printGivenLevel(Ptr->left, level-1); printGivenLevel(Ptr->right, level-1); } } }; #endif /* function_h */

main.cpp

#include <iostream> #include <string.h> #include "function.h" using namespace std; void BSTManipulator(BST& bstobj1,BST& bstobj2, char cmd ){ int n; if (cmd == 'I') { cin >> n; bstobj1.insert(n); bstobj2.insert(n); }else if (cmd == 'S'){ cin >> n; if (bstobj1.search(n)) { cout << "yes" << endl; }else{ cout << "no" << endl; } if (bstobj2.search(n)) { cout << "yes" << endl; }else{ cout << "no" << endl; } }else if (cmd == 'H'){ cout << bstobj1.height() << endl;; cout << bstobj2.height() << endl;; }else if (cmd == 'P'){ bstobj1.print(); cout << endl; bstobj2.print(); cout << endl; } } int main(){ Array_BST A_bst; List_BST B_bst; char cmd; while (cin >> cmd) BSTManipulator(A_bst, B_bst, cmd); return 0; }

REQUIREMENTS:

Implement the constructor, insert(), search() member functions of both the Array_ BST and List_ BST classes and createLeaf(), deleteTree() of List_ BST class.

Note:

1. This problem involves three files.

• function.h: Class definitions.
• function.cpp: Member-function definitions.
• main.cpp: A driver program to test your class implementation.

You will be provided with main.cpp and function.h, and asked to implement function.cpp.

2.  For OJ submission:

     Step 1. Submit only your function.cpp into the submission block.

     Step 2. Check the results and debug your program if necessary.

Input

There are four kinds of commands:

• “I A”: insert a node with int value A into the BST
• “S A”: if the integer A exists in the BST, print “yes”; otherwise, print “no”.
• “P”: show the current content of the BST.
• “H”: print the BST’s height.

Each command is followed by a new line character.

Input terminated by EOF.

Output

The output shows the result of each command.

When the BST is empty, you don’t need to print anything except a new line character.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11020.cpp

Partial Judge Header

11020.h

Tags

Discuss