# include < iostream >
struct Nod {
int val;
Nod* urmator ;
};
void adauga (Nod*& inceput , Nod*& sfarsit , int val) {
Nod* nodNou = new Nod{val, nullptr };
if (! inceput ) {
inceput = sfarsit = nodNou ;
} else {
sfarsit -> urmator = nodNou ;
sfarsit = nodNou ;
}
}
int scoate (Nod*& inceput , Nod*& sfarsit ) {
Nod* nodScoat = inceput ;
int val = nodScoat ->val;
inceput = inceput -> urmator ;
if (! inceput ) {
sfarsit = nullptr ;
}
delete nodScoat ;
return val;
}
void jocJosephusCuCoada ( int n, int k) {
Nod* inceput = nullptr ;
Nod* sfarsit = nullptr ;
for ( int i = 1 ; i <= n; ++i) {
adauga ( inceput , sfarsit , i);
}
while ( inceput ) {
for ( int i = 1 ; i < k; ++i) {
adauga ( inceput , sfarsit , scoate ( inceput , sfarsit ));
}
std :: cout << scoate ( inceput , sfarsit ) << " " ;
}
std :: cout << std :: endl ;
}
struct NodCircular {
int val;
NodCircular * urmator ;
};
NodCircular * construiesteListaCirculara ( int n) {
NodCircular * inceput = nullptr ;
NodCircular * sfarsit = nullptr ;
for ( int i = 1 ; i <= n; ++i) {
NodCircular * nodNou = new NodCircular {i, nullptr };
if (! inceput ) {
inceput = nodNou ;
sfarsit = nodNou ;
} else {
sfarsit -> urmator = nodNou ;
sfarsit = nodNou ;
}
}
if ( sfarsit ) {
sfarsit -> urmator = inceput ;
}
return inceput ;
}
void jocJosephusCuListaCirculara ( int n, int k) {
NodCircular * inceput = construiesteListaCirculara (n);
NodCircular * nodCurent = inceput ;
while (n > 0 ) {
for ( int i = 1 ; i < k - 1 ; ++i) {
nodCurent = nodCurent -> urmator ;
}
NodCircular * nodEliminat = nodCurent -> urmator ;
nodCurent -> urmator = nodEliminat -> urmator ;
std :: cout << nodEliminat ->val << " " ;
delete nodEliminat ;
nodCurent = nodCurent -> urmator ;
--n;
}
std :: cout << std :: endl ;
}
int main () {
int n = 7 ;
int k = 3 ;
std :: cout << "Ordinea de iesire a copiilor folosind coada: " ;
jocJosephusCuCoada (n, k);
std :: cout << "Ordinea de iesire a copiilor folosind lista circulara: " ;
jocJosephusCuListaCirculara (n, k);
return 0 ;
}