Programación en C++: Problema de Joseph Ring.
/*
Requisitos básicos
Descripción básica de José:
Un juez en la antigüedad quería sentenciar a muerte a N prisioneros. Es una ley ridícula que pone a los prisioneros en un círculo.
A partir de la enésima persona, cada vez que se cuenta al prisionero enésimo, se lo saca y ejecuta, y luego se vuelve a contar a las personas D. ,
hasta que se pueda perdonar al último que queda.
Descripción del desarrollo de José:
Un juez en la antigüedad quería sentenciar a muerte a N prisioneros
Pero cada una de las N personas tenía una contraseña. Hay una ley ridícula que pone a los prisioneros en un círculo.
El juez primero da una contraseña M y comienza a contar desde la enésima persona. Cada vez que se cuenta al enésimo prisionero, lo sacarán y. ejecutado.
Luego cuente F de acuerdo con la contraseña F que posee esta persona, y las personas contadas serán ejecutadas,
Y así sucesivamente hasta que la última persona restante pueda ser perdonada.
Datos de prueba
Agregue los datos usted mismo.
*/
#include
usando el espacio de nombres std;
// Representa una estructura prisionera
struct Prisionero
{
// Número
int id;
// Contraseña
int pass;
// Puntero para lista enlazada
struct Prisoner * pre
struct Prisoner * next
} ;
struct Prisoner * next; p>
clase JosephCircle
{
público:
// constructor básico de Joseph
JosephCircle( int N,int S ,int D);
// Constructor Joseph desarrollado
JosephCircle(int N,int S,int M,int contraseña[]); // Salida Joseph Ring
void print();
// Comienza a ejecutar al prisionero
void start();
private :
// El puntero principal de Joseph Ring
struct Prisoner * head
// El puntero de nodo del primer prisionero ejecutado
struct Prisionero * firstPunishedPrision
};
JosephCircle::JosephCircle(int N,int S,int D)
{
struct Prisoner * p , *pr;
// El puntero principal del anillo de Joseph se inicializa a NULL
this->head = NULL;
//Construir un anillo de José compuesto por N prisioneros
for(int i=1;i<=N;i++)
{
// El El prisionero agregado actualmente es el primer prisionero, por lo que se requiere un tratamiento especial
if(this->head == NULL)
{
// Agregar un nuevo prisionero
p = new struct Prisoner();
// Número de prisionero
p -> id = i;
// Contraseña del prisionero
p -> pass = D;
// El próximo prisionero (porque es un anillo, todos tendrán uno al lado) (otros prisioneros)
p -> pre = p;
p -> next = p;
// Puntero de cabeza de Joseph Ring
this->head = pr = p;
}
else
{
p = nueva estructura Prisionero() ;
p -> id = i;
p -> pasar = D;
p -> pre = pr;
p -> siguiente = pr-> siguiente;
pr -> siguiente -> pre =
p;
pr -> siguiente = p;
pr = p;
}
}
// Encuentra el puntero de nodo del primer prisionero ejecutado en Joseph Ring
firstPunishedPrision = head;
for(int i=2;i<=(S+D-1 ) ;i++)
{
this->firstPunishedPrision = this->firstPunishedPrision -> siguiente
}
}
JosephCircle::JosephCircle(int N,int S,int M,int contraseña[])
{
struct Prisoner * p , *pr;
// El puntero principal del Joseph Ring se inicializa en NULL
this->head = NULL;
// Construye un Joseph Ring compuesto por N prisioneros
for(int i=1;i<=N;i++)
{
// El prisionero agregado actualmente es el primer prisionero, por lo que se requiere un tratamiento especial
if(this->head == NULL)
{
// Agregar un nuevo prisionero
p = new struct Prisoner( );
// Número de prisionero
p -> id = i;
// Contraseña de prisionero
p -> pass = contraseña[i-1];
// El próximo prisionero (porque es un anillo, todos tendrán otros prisioneros a su lado)
p - > pre = p; /p>
p -> next = p;
// El puntero principal del anillo de José
this->head = pr = p;
}
else
{
p = nueva estructura Prisionero();
p -> id = i;
p -> pass = contraseña[i-1];
p -> pre = pr;
p -> next = pr-> next;
pr -> siguiente -> pre = p;
pr -> siguiente = p;
pr = p;
}
}
// Encuentra el puntero de nodo del primer prisionero ejecutado en Joseph Ring
firstPunishedPrision = head;
for(int i= 2;i<=(S+M-1);i++)
{
this->firstPunishedPrision = this->firstPunishedPrision -> siguiente
}
}
// Salida Círculo de Joseph
void JosephCircle::print()
{
estructura pri
soner * p = this->head;
if(p != NULL)
{
hacer
{
cout << "[número: " << p->id << ", contraseña: " << p->contraseña << "]" ;
if(p->siguiente != this->head)
{
cout<<" -> ";
}
p = p-> siguiente;
} while(p != this->head
}
cout << endl << endl;
}
//Comienza a ejecutar al prisionero
void JosephCircle::start()
{
struct Prisoner * p = this - >firstPunishedPrision,*pr,*q;
int counter = 1;
/*
Porque el anillo de Joseph es una lista circular enlazada (es decir , un ciclo),
Cuando p->siguiente != p, significa que hay un nodo más (prisionero) en el círculo,
Continúa contando y ejecuta al prisionero
*/
while(p->next != p)
{
// q al prisionero actualmente ejecutado
q = p;
// Eliminar a los prisioneros ejecutados del Anillo de José
q -> pre -> next = q -> next;
q -> siguiente -> pre = q -> pre;
p = p -> siguiente;
// Muestra la información del prisionero ejecutado
cout << "El "th"<< (counter++) << "El número del prisionero ejecutado:" << q->id < // Encuentra el siguiente prisionero a ser ejecutado for(int i=1;i<=(q->pass-1);i++) { p = p-> next; } // Liberar memoria (prisioneros ejecutados). free(q); } // Muestra la información del prisionero perdonado cout << "El prisionero perdonado Número de prisionero: " << p->id << endl << endl;; } int main(int argc, char *argv[]) { //Círculo básico de Joseph: JosephCircle(int N,int S,int D); JosephCircle j1 = JosephCircle(3,1,2); j1.print(); j1.start(); // Desarrollado Joseph Circle: JosephCircle(int N,int S,int M, int contraseña[ ]); int pass[]={1,5,3}; JosephCircle j2 = JosephCircle(3,1,2,pass);
j2.start();
devuelve 0;
}