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.
More Questions From This User See All
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...