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