Explanation:
Here is the comlete question:
In a distant land, the death penalty is still in force. The king of the land, who likes to think that he is a nice chap, has made the execution of the prisoners part of the yearly Games. At the end of the Games, all the prisoners from death row are put in a circle in the arena. Guards with spears ensure that no prisoner can move out of the circle. One of the prisoners is designated number 1. Then the executioner takes position at the center of the circle, and starts reciting a rhyme he remembers from his childhood: 'EENIE MEENIE MINIE MOE, I THINK FOR YOU IT IS TIME TO GO'. For each word of the rhyme he aims at a different person, starting with prisoner 1 for 'EENIE', prisoner 2 for 'MEENIE', etc. (thus with each word he moves his aim to the right, or clockwise.) The prisoner he aims at with 'GO' is then executed, and, during the cheers of the crowd, removed from the scene. At the next reciting of the rhyme, the executioner starts at the neighbor of the most recently deceased, continuing to the executioner's right; i.e. the executioner begins at the next clockwise neighbor of the deceased.
The king (I told you he is a nice chap), releases the one prisoner left standing at the end of the game.
For example, if there were six prisoners and the rhyme only contained 3 words then initially the prisoners are arranged as:
123456 (with 1 and 6 next to each other in the circle)
The executioner counts off three words to end up on prisoner number 3 who is executed:
12456
The executioner is now on prisoner 4, and counts off another three words to end up on prisoner number 6 who is then executed:
1245
The executioner is now on prisoner 1, and counts off another three words to end up on prisoner 4 who is then executed:
125
The executioner is now on prisoner 5, and counts off another three words to end up on prisoner 2 who is then executed:
15
The executioner is now on prisoner 5 and counts off another three words to end up on prisoner 5 who is then executed:
1
Prisoner 1 is the survivor!
If you would ever participate in this "game," you will want to improve your chances by determining beforehand who is going to be released. To be able to calculate that, you need to know the number of prisoners and the length in words of the rhyme used by the executioner for this particular game. It might be nice to have a program that calculates the position quickly for you (maybe on the computer they let you use in prison). Write a program that inputs the number of prisoners and the number of words and calculates where you should stand. For example, print the following text: 'With P prisoners and S words, I'd like to be number X.', where X is the prisoner index of the one surviving (the prisoners are numbered from 1 through P in the direction of the aim of the executioner).
Example Output:
With 3 prisoners and 3 words, I'd like to be number 2.
With 6 prisoners and 2 words, I'd like to be number 5.
With 10 prisoners and 1 words, I'd like to be number 10.
You must use a CIRCULAR LINKED LIST of a Prisoner class to simulation the position of each prisoner in the "game" and calculate the correct position to survive. The Prisoner class only needs to store the number of the prisoner and a "next" pointer. (You could also have a "previous" pointer if you want to make a doubly-linked list). Your program should play the game, deleting the node in the circular linked list that corresponds to the prisoner that is executed.
#include <iostream>
using namespace std;
struct Node
{
int prisonerNo;
struct Node *next;
};
class CirList
{
Node *first,*last;
public:
CirList()
{
first=NULL;
last=NULL;
}
void create(int n);
int survivor(int n,int words);
};
//Create a circular link list
void CirList::create(int n)
{
Node *temp;
int i=1;
while(i<=n)
{temp=new Node;
temp->prisonerNo=i;
temp->next=NULL;
if(first==NULL)
{
first=temp;
last=first;
}
else
{
last->next=temp;
last=temp;
}
i++;
}
last->next=first;
}
// calculating the correct position of surviver by deleting nodes at every number of words
int CirList::survivor(int n,int words)
{
Node *p, *q;
int i;
q = p = first;
while (p->next != p)
{
if(words==1) //When number of words are 1
{ q=q->next;
last->next=q;
delete p;
p=q;
}
else
{
for (i = 0; i < words-1; i++) //When number of words are more than 1
{
q = p;
p = p->next;
}
q->next = p->next;
delete p;
p = q->next;
}
}
first = p;
cout<<endl<<"With "<<n<<" prisoners and "<<words<<" words, I'd like to be number "<<first->prisonerNo<<endl;
}
int main()
{
CirList list;
int skip,n,words;
cout<<"Enter the number of prisoners:";
cin>>n;
list.create(n); //calling create() function to create circular link list
cout<<"Enter the number of words:";
cin>>words;
list.survivor(n,words); //calling function to know correct position of surviver
return 1;
}
