👤

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.


Răspuns :

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...

Vă mulțumim pentru vizita pe site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Nu ezitați să ne contactați pentru orice întrebare sau dacă aveți nevoie de asistență suplimentară. Vă așteptăm cu drag data viitoare și nu uitați să ne adăugați la favorite!


ID Learners: Alte intrebari