Description

[Josephs problem]

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 square numbers succession (1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, ...). So in order to kill the i-th person, Josephus counts up to the i-th square number.

For example, there are 5 people in a circle, and the sequence of couting is square number succession (1, 4, 9, 16, …).

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 4)

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

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

2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3.........(kill 3)

    Then print 2 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( const int &info ) //constructor

      :number( info ), next( NULL ), prev(NULL)

      {

      } //end ListNode constructor

   private:

          Node *next;

          Node *prev;

          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 generateSquare(const int &); // generate square sequence table

        int sequence[10005]; // store square number

        int noOfPeople;

        Node *head, *current;

};

 

REQUIREMENTS:

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

 

Josephus class:

• constructor
• destructor
• int kill();
• void generatecircularlinkedList(const int &);
• void generateSquare(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.

 

<code>function.h</code>

#ifndef FUNCTION_H

#define FUNCTION_H

#include <iostream>

class Node

{

   friend class Josephus;

   public:

          Node( const int &info ) //constructor

      :number( info ), next( NULL ), prev(NULL)

      {

      } //end ListNode constructor

   private:

          Node *next;

          Node *prev;

          int number;

};//end class Node

 

class Josephus

{

    public:

         Josephus();

         ~Josephus();

         Josephus(const int &);

         int kill();

    private:

        void generatecircularlinkedList(const int &); 

        void generateSquare(const int &); 

        int sequence[10005];

        int noOfPeople;

        Node *head, *current;

};

#endif // FUNCTION_H

 

<code>main.cpp</code>

#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 with 1 integers, n. n is the number of people. Input terminated by EOF.

 

Testcase 1 : 1<=n<10

Testcase 2 : 10<=n<100

Testcase 3 : 100<=n<1000

Testcase 4 : 1000<=n<5000

Testcase 5 : 5000<=n<10000

 

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

10591.cpp

Partial Judge Header

10591.h

Tags

Discuss

Description

NOTICE: You are asked to use C++11 compile setting while submitting your code.

In function.h we define a class called Block. Several constructors and member functions are implemented. Your task is to complete the implementation of the following three functions:

1. void clockwise90();
This function rotates the pattern by 90 degrees clockwise. For example,

@OOX
OOXX
XXXX
XXXX

becomes

XXO@
XXOO
XXXO
XXXX

2. Block& doublesize();
This function enlarges the pattern to make it twice as wide and twice as tall. For example,

CCCC
OOOO
OOOO
LLLL

becomes

CCCCCCCC
CCCCCCCC
OOOOOOOO
OOOOOOOO
OOOOOOOO
OOOOOOOO
LLLLLLLL
LLLLLLLL

3. friend bool equal(const Block& a, const Block& b);
This function checks if two blocks a and b have the same pattern under rotation. You need to take into consideration the four orientations. For example,

@OOX
OOXX
XXXX
XXXX

and

XXXX
XXXX
XXOO
XOO@

are EQUAL

But

@OOX
OOXX
XXXX
XXXX

and

XOO@
OOXX
XXXX
XXXX

are DIFFERENT

You need to implement the three functions in function.cpp.

You can use main.cpp and function.h in 10596 to accomplish it.

Input

The input will be given in main.cpp.

Output

The output will be generated by main.cpp

Sample Input  Download

Sample Output  Download

Partial Judge Code

10594.cpp

Partial Judge Header

10594.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
};

And the program flow is described in the main.cpp

// 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

10597.cpp

Partial Judge Header

10597.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 two different approaches to implement stack: array and linked list. Thus, we define three classes as follows:

 

class Stack{

    friend std::ostream &operator<<(std::ostream &, Stack &);

    public:

        virtual ~Stack() {};

        virtual void push(const int &) = 0;

        virtual int pop() = 0;

        virtual void print(std::ostream &output)=0;

};

class Array_stack : public Stack{

    public:

        Array_stack();

        virtual ~Array_stack();

        void push(const int &);

        int pop();

        void print(std::ostream &output);

    private:

        int number[100];

        int max_size;

};

 

class List_stack : public Stack{

    public:

        List_stack();

        virtual ~List_stack();

        void push(const int &);

        int pop();

        void print(std::ostream &output);

    private:

        ListNode *head;

        ListNode *tail;

};

 

where

1. Class Stack serves as the abstract base class for realizing polymorphism
2. Array_stack and List_stack provide the two different approaches to implement the stack data structure

 

Besides, we also overload the stream insertion operator (<<) to print the content of a stack object no matter if the stack object is an Array_stack object or a List_stack object (note that this is polymorphism).

 

REQUIREMENTS:

1. Implement the push(), pop() and print() member functions of both the Array_stack and List_stack classes.
2. Implement overloaded stream insertion operator (<<), which will call the correct member function print() polymorphically.

 

 

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.

 

<code>function.h</code>

#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 Stack{

    friend std::ostream &operator<<(std::ostream &, Stack &);

    public:

        virtual ~Stack() {};

        virtual void push(const int &) = 0;

        virtual int pop() = 0;

        virtual void print(std::ostream &output)=0;

};

class Array_stack : public Stack{

    public:

        Array_stack();

        virtual ~Array_stack();

        void push(const int &);

        int pop();

        void print(std::ostream &output);

    private:

        int number[100];

        int max_size;

};

class List_stack : public Stack{

    public:

        List_stack();

        virtual ~List_stack();

        void push(const int &);

        int pop();

        void print(std::ostream &output);

    private:

        ListNode *head;

        ListNode *tail;

};

#endif // FUNCTION_H

 

<code>main.cpp</code>

#include<iostream>

#include<string.h>

#include "function.h"

using namespace std;

int main(){

    Array_stack A_stack;

    List_stack L_stack;

    char command[10];

    int n;

    while(cin>>command){

 

        if(strcmp(command,"pop")==0){

            n=A_stack.pop();

            n=L_stack.pop();

        }else if(strcmp(command,"push")==0){

            cin >> n;

            A_stack.push(n);

            L_stack.push(n);

        }else if(strcmp(command, "print") == 0){

            cout << A_stack << endl;

            cout << L_stack << 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

10598.cpp

Partial Judge Header

10598.h

Tags

Discuss