Question

N copii joacă bine-cunoscutul joc ala-bala-portocala.
Aceștia sunt plasați pe un cerc și încep să numere de la 1 la k. Copilul k este
eliminat din joc. Procesul continuă cu restul copiilor,
de fiecare dată când numărăm de la 1 până la k, până când toți copiii sunt eliminați din
joc.

Implementați un algoritm eficient pentru tipărirea ordinii în care
copiii sunt eliminați din joc folosind o listă circulară.

In limbajul C vă rog.

Answer 1

Răspuns:

#include <iostream>

using namespace std;

struct nod{

   int nr;

   nod *urm;

};

nod *prim=NULL, *ultim=NULL;

void adauga(nod *&prim, nod *&ultm, int num)

{

   nod *p=new nod;

   p->nr=num;

   if (prim==NULL)

   {

       prim=p; ultim=p;

       prim->urm=p; ultim->urm=p;

   }

   else

   {

       p->urm=ultim->urm;

       ultim->urm=p;

       ultim=p;

   }

}

void afisare(nod *prim, nod *ultim)

{

   nod *p=prim;

   do

   {

       cout << p->nr << " ";

       p=p->urm;

   }while (p!=prim);

   cout << "\n";

}

void joc(nod *&prim, nod *&ultim, int k)

{

   int i;

   nod *q=prim, *p;

   while (prim!=ultim)

   {

       for (i=1; i<k; ++i)

       {

           p=q;

           q=q->urm;

       }

       cout << q->nr << " ";

       if (q!=prim && q!=ultim)

       {

           p->urm=q->urm;

           p=q->urm;

       }

       if (q==prim)

       {

           p->urm=q->urm;

           prim=q->urm;

           p=prim;

       }

       if (q==ultim)

       {

           p->urm=ultim->urm;

           ultim=p;

           p=prim;

       }

       delete(q);

       q=p;

   }

   cout << prim->nr;

}

int main()

{

   int n,i,k;

   cout << "n= "; cin >> n;

   cout << "k= "; cin >> k;

   for (i=1; i<=n; ++i)

       adauga(prim,ultim,i);

   cout << "paricipantii la joc:" << "\n";

   afisare(prim,ultim);

   cout << "ordinea eliminarii din joc:" << "\n";

   joc(prim,ultim,k);

}

Explicație:

Am folosit lista circulară simplu înlănţuită, am afişat numerele de ordine a participanţilor la joc şi ordinea eliminării din joc...