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

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&amp;’:

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

void encode_decode(Codec&amp; 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 ‘QCAQGDQBBQEGQACQDE’, where QCA means that there are 3 A’s and 3 can be encoded as C (the third character in alphabet), QGD means that there are 7 D’s and 7 can be encoded as G (the 7 th character in alphabet), and QBB means we have 2 B’s and 2 can be encoded as B (the second character in alphabet) … etc. Note that every encoding segment starts with a Q.

If there are 27 A’s in a string, it is separated into two segments ‘QZAQAA’, which means the first segment ‘QZA’ represents 26 A’s, and the second segment ‘QAA’ represents 1 A.

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

#include <iostream> #include <string> #include <sstream> #include <cctype> #include "function.h" void RleCodec::encode() { } void RleCodec::decode() { std::stringstream os; std::string int_str; char q = 'A'; char number = ' '; int cnt = 0; for (auto c : code_str) { if (q=='A') { q = c; }else if(number == ' '){ number = c; } else { int_str.push_back(c); int cnt = 0; cnt = number - 'A' +1; for (int i=0; i<cnt; ++i) os << c; int_str.clear(); number = ' '; q = 'A'; } } code_str = os.str(); encoded = false; }

Input

A line contains of several characters .(n <= 100)

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

11021.cpp

Partial Judge Header

11021.h

Tags

Discuss

Description

Array.cpp
// overloaded assignment operator;
// const return avoids: ( a1 = a2 ) = a3
const Array &Array::operator=( const Array &right )
{
   if ( &right != this ) // avoid self-assignment
   {
      // for Arrays of different sizes, deallocate original
      // left-side Array, then allocate new left-side Array
      if ( size != right.size )
      {
         delete [] ptr; // release space
         size = right.size; // resize this object
         ptr = new int[ size ]; // create space for Array copy
      } // end inner if

      for ( size_t i = 0; i < size; ++i )
         ptr[ i ] = right.ptr[ i ]; // copy array into object
   } // end outer if

   return *this; // enables x = y = z, for example
} // end function operator=

// determine if two Arrays are equal and
// return true, otherwise return false
bool Array::operator==( const Array &right ) const
{
   if ( size != right.size )
      return false; // arrays of different number of elements

   for ( size_t i = 0; i < size; ++i )
      if ( ptr[ i ] != right.ptr[ i ] )
         return false; // Array contents are not equal

   return true; // Arrays are equal
} // end function operator==

// overloaded subscript operator for non-const Arrays;
// reference return creates a modifiable lvalue
int &Array::operator[]( int subscript )
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // reference return
} // end function operator[]

// overloaded subscript operator for const Arrays
// const reference return creates an rvalue
int Array::operator[]( int subscript ) const
{
   // check for subscript out-of-range error
   if ( subscript < 0 || subscript >= size )
      throw out_of_range( "Subscript out of range" );

   return ptr[ subscript ]; // returns copy of this element
} // end function operator[]

// overloaded input operator for class Array;
// inputs values for entire Array
istream &operator>>( istream &input, Array &a )
{
   for ( size_t i = 0; i < a.size; ++i )
      input >> a.ptr[ i ];

   return input; // enables cin >> x >> y;
} // end function

// overloaded output operator for class Array
ostream &operator<<( ostream &output, const Array &a )
{
   // output private ptr-based array
   for ( size_t i = 0; i < a.size; ++i )
   {
      output << setw( 12 ) << a.ptr[ i ];

      if ( ( i + 1 ) % 4 == 0 ) // 4 numbers per row of output
         output << endl;
   } // end for

   if ( a.size % 4 != 0 ) // end last line of output
      output << endl;

   return output; // enables cout << x << y;
} // end function operator<<

Inheritance type	Public	Protected	Private
Public data/ functions in the base class	Public in the derived class	Protected in the derived class	Private in the derived class
Protected data/ functions in the base class	Protected in the derived class	Protected in the derived class	Private in the derived class
Private data/fun in the base class	Not accessible in the derived class	Not accessible in the derived class	Not accessible in the derived clas

 
 
 
 
 
 

 

 

 

 

 

Polymorphism
  In the base class
  virtual void foo();
  In the derived class
  virtual void foo() override;

Abstract class and pure virtual function
  virtual void foo() =0;

Prefix/postfix operators
  complex &operator++();  // prefix
  complex operator++(int); // postfix

Operator overloading
  Binary operators
  /*1.non-static member function */
     complex operator+ (const complex&);
  /* 2. non-member function */
     friend complex operator* (const
                      complex&, const complex&);
  Unitary operators
  /*1.non-static member function */
      complex operator-();
  /*2. non-member function */
      friend complex operator~(const complex&);

Inheritance
  class A {
  // A is a base class }
  class B: public A {
  // B inherits A.
  // B is a derived class}

Dynamic allocation
  int *ptr = new int;
  delete ptr;
  int *ptr = new int[100];
  delete [] ptr;

String object
  #include<string>
  using namespace std;
  ...
  string str1 = "Hello";
  string str2 = "World";

Standard C++ Library - <string>

operator[]	For string a, a[pos]: Return a reference to the character at position pos in the string a.
operator+=	Append additional characters at the end of current string.
operator+	Concatenate strings.
operator<	Compare string values. For string a and b, a < b: if a is in front of b in dictionary order, return 1, else return 0.
operator>	Compare string values. For string a and b, a > b: if a is in back of b in dictionary order, return 1, else return 0.
operator==	Compare string values. For string a and b, a == b: if equal, return 1, else return 0;
operator!=	Compare string values. For string a and string b, a != b: if not equal, return 1, else return 0;
compare()	Compare string. For string a and b, a.compare(b): if equal, return 0. If string a is in front of string b in dictionary order, return -1. If string a is in back of string b in dictionary order, return 1.
length()	Return length of string.
swap()	Swap string values.
push_back()	For string a, a.push_back(c): append character c to the end of the string a, increasing its length by one.

 

Standard C++ Library - <sstream>

operator<<	Retrieves as many characters as possible into the stream.
operator>>	Extracts as many characters as possible from the stream.
str	Returns a string object with a copy of the current contents of the stream.

For example(1):
stringstream ss{“Hello”};    // constructor
string str = ss.str();    // a = “Hello”

For example(2):
stringstream ss;
ss<<”75”;
ss<<”76”;
int num;
ss>>num;    // num = 7576

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

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, you only need to implement the linked list.

1.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.

 

REQUIREMENTS:

Implement the constructor, insert(), remove(), search() and createLeaf()member functions of  List_ BST 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.

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.

HINT1:

You don't have to take care of the height changing in insert() and remove(), the function height2() will take care of it.

HINT2:

There are three possible cases to remove a node from BST, after removing it will still maintain a BST:

1.Node to be deleted is leaf: Simply remove from the tree.

2.Node to be deleted has only one child: Copy the child to the node and delete the child

3.Node to be deleted has two children: Find node A with max key value in the left tree of the deleted node or minimim key value in the right tree of the deleted node, copy A to the deleted node. Then, replace A by it's child. In this test, please choose node A by finding minimum key value in the right tree. 

For example, we remove the node with key = 4, node A's key = 5

the BST will become

 

Input

There are five kinds of commands:

• “I A”: insert a node with int value A(A>0) into the BST
• “R A”:remove a node with int value A(A>0) into the BST, value A must appear in the tree.
• “S A”: if the integer A exists in the BST, print “yes”; otherwise, print “no”.
• “P”: show the current content of the BST in Level-order.
• “H”: print the BST’s height.

Each command is followed by a new line character.

Input terminated by EOF.

You can still get two ACs without doing remove() function.

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.

But there's already a new line character in the main function, so you don't have to do anything.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12259.cpp

Partial Judge Header

12259.h

Tags

Discuss