CEOI'98 și Balcaniada

Soluțiile problemelor propuse

În perioada 14-30 aprilie s-a desfășurat la Liceul de Informatică din Cluj tabăra de antrenament a lotului lărgit (informatică) având ca scop pregătirea și selecționarea echipelor participante la CEOI'98 și Balcaniada de Informatică. vă prezentăm în continuare soluțiile problemelor date cu această ocazie.

P049801: Funcții surjective

Soluția autorului (prof. Doina Rancea, Liceul de Informatică, Cluj)

Fie o funcție f : N * N ź N definită prin f(x,y) = b, unde b este numărul funcțiilor surjective care pot fi definite de la o mulțime având cardinalul x, la o mulțime având cardinalul y.

Se demonstrează matematic foarte ușor că relația

f(x,y) = f(x-1, y) * y + f(x-1, y-1) * y

este adevărată pentru valori ale lui x mai mari decât 1. Observăm că pentru x = 1 avem f(1,1) = 1. Pe de altă parte se observă că pentru valori suficient de mari ale variabilelor x și y, valoarea b depășește 1020 și deci nu poate fi reprezentată intern, folosind tipurile standard oferite de limbajele de programare actuale, decât cu o anumită marjă de eroare. De aceea trebuie simulate operațiile de adunare a două numere mari și de înmulțire dintre un număr mare și un număr mic.

Se mai observă că dacă y > x nu există funcții surjective de la o mulțime având cardinalul x la una ce are cardinalul y. Pornind de la formula recursivă pentru calcularea valorilor funcției f, putem ajunge, printr-un procedeu matematic destul de complicat, la termenul general al funcției f. Folosirea acestei formule ar implica implementarea mai multor tipuri de operații cu numere mari, ceea ce ar duce la scăderea performanțelor algoritmului.

Listing Functii.PAS

P049802: Fractal

(Soluția autorului, student, Cătălin Frâncu, Universitatea Politehnică, București)

Problema este o generalizare a următoarei probleme: fie intervalul [0,1) care se împarte în trei părți egale. Partea din mijloc se elimină. Se repetă această operație la infinit, pentru fiecare din subintervalele rămase. Se cere să se determine dacă un număr rațional p/q aparține mulțimii rămase.

Dacă notăm cu Ai mulțimile obținute la pasul i, atunci

avem:

A1=[0,1/3)U[2/3,1)

...

și în plus: A...AnÌ...A2ÌA1.

Pentru ca numărul rațional p/q să aparțină mulțimii A1 trebuie ca prima cifră zecimală să fie pară. Pentru ca p/q să aparțină lui A2 trebuie ca și a doua cifră să fie pară... Deci pentru ca p/q să aparțină lui A trebuie ca acesta (p/q) să aibă toate cifrele de după virgulă pare. Deoarece p/q este rațional înseamnă că partea lui zecimală va fi finită sau periodică, deci testarea apartenenței la mulțimea finală se poate face după un număr finit de pași. în plus, se observă că este necesar să testăm doar dacă primele q zecimale sunt pare.

Acum să ne ocupăm de problema generalizată în plan. Pentru a reduce numărul de calcule, simplificăm numerele (px,qx) prin cel mai mare divizor comun al lor și numerele (py,qy) tot prin cel mai mare divizor al lor. Deci numerele px, qx respectiv py, qy vor fi prime între ele. Acest lucru îl realizăm la citirea datelor cu ajutorul funcției cmmdc. Pătratele care se elimină sunt reținute în matricea Cut, astfel:

Cut[i,j]=true dacă pătratul (i,j) se elimină și

Cut[i,j]=false în caz contrar. (i,j=1..3).

Aici nu testăm la fiecare pas dacă cifra zecimală corespunzătoare este pară, ci dacă perechea formată din (px*3 div qx, py*3 div qy) aparține unuia din pătratele care nu este eliminat. Numărul de pași (necesari pentru a vedea dacă avem sau nu soluție) este contorixat în max(qy,qx). Procedura TakeDigit va elimina la fiecare pas zecimala cea mai semnificativă din p/q, actualizând bineînțeles valoarea lui p.

Listing FRACTAL.PAS

P049803: Cuvinte încrucișate

(soluție propusă de Cătălin Frâncu, student, Universitatea Politehnică, București)

Rezolvarea se bazează pe metoda backtracking, însă fără o optimizare corespunzătoare programul nu se va încadra în limita de timp impusă. De aceea, inițial vom extrage din rebusul necompletat toate lungimile posibile ale cuvintelor care ar putea fi amplasate în el. Pentru aceasta ne vom folosi de o matrice (denumită d) cu 5 coloane și r>p linii, în care pe o linie vom reține informațiile despre o amplasare posibilă a unui cuvânt și anume:

  • pe primele două poziții reținem poziția unde am putea amplasa prima literă a cuvântului
  • pe a treia poziție reținem lungimea posibilă a unui cuvânt care urmează a fi amplasat
  • pe a patra poziție avem 1 dacă acest cuvânt este plasat orizontal și 2 dacă este amplasat vertical
  • pe a cincea poziție avem 1 dacă în căsuțele specificate de primele 4 poziții este amplasat un cuvânt și 0 în caz contrar.

Procedura care rezolvă efectiv problema se numește back și are ca prim parametru numărul de ordine al cuvântului care urmează a fi amplasat. Dacă această amplasare este posibilă, se trece la amplasarea următorului cuvânt (din cele date) : back(k+1).

Listing Careu.PAS

P049804: Comerț interplanetar

(rezolvare propusă de Mihai Pătrașcu, Colegiul Carol I, Craiova)

Pentru fiecare dintre planete se calculează numărul minim de planete diferite pe care o navă de transport ar trebui să le parcurgă pentru a ajunge pe Pământ. Valoarea exportului către Pământ se înmulțește cu 0.95 de fiecare dată când este necesară trecerea printr-una din planete. Se alege apoi planeta cu cel mai mare export către Pământ.

Listing comert.PAS

P049805: Aeroport

(soluție propusă de Mihai Scorțaru, student, Universitatea Tehnică din Cluj)

Până în prezent nu a fost descoperit un algoritm polinomial pentru rezolvarea acestei probleme, așa că o vom trata ca pe o problemă NP - completă. Algoritmul propus pentru rezolvarea acestei probleme va fi unul probabilist, mai precis un algoritm genetic.

Vom folosi o populație de zece cromozomi, cu o probabilitate de mutație de 0.2 ce se va mări la fiecare 1000 generații cu 10% și cu o probabilitate de recombinare de 0.6.

Structura unui cromozom va fi următoarea: va conține nro gene (nro reprezintă numărul de porți care vor fi folosite, adică numărul de orașe distincte care apar ca puncte de plecare sau ca destinații), fiecare element reprezentând indicele unei porți (un număr între 0 și m * n - 1).

Potrivit algoritmilor genetici pentru fiecare generație vom avea de parcurs trei etape: selecția, mutația și recombinarea.

Selecția se va realiza astfel:

  • se calculează suma lungimilor drumurilor pentru configurația corespunzătoare fiecărui cromozom;
  • se determină cromozomul cu cea mai defavorabilă configurație (fie L suma lungimilor drumurilor pentru acest cromozom);
  • indicele de adaptare pentru fiecare cromozom va fi egal cu raportul dintre L și suma lungimilor drumurilor pentru cromozomul respectiv;
  • se calculează suma S a indicilor de adaptare;
  • fiecare cromozom va avea o probabilitate de a fi selectat egală cu raportul dintre indicele de adaptare al respectivului cromozom și valoarea S;
  • împărțim intervalul [0,1) în zece subintervale astfel încât lungimea intervalului corespunzător unui cromozom să fie egală cu probabilitatea de selecție a acelui cromozom; de exemplu, pentru o populație care conține cinci cromozomi cu probabilitatea de selecție 0.3 și alți cinci cu probabilitatea de selecție 0.1, intervalele corespunzătoare vor fi:

[0, 0.15), [0.15, 0.3), [0.3, 0.45), [0.45, 0.6), [0.6, 0.75),

[0.75, 0.8), [0.8, 0.85), [0.85, 0.9), [0.9, 0.95), [0.95, 1);

  • se generează zece numere aleatoare subunitare; pentru fiecare din aceste numere se determină intervalul din care face parte numărul, iar cromozomul corespunzător este adăugat la noua populație (se observă că un anumit cromozom poate fi ales de mai multe ori).

Pașii necesari simulării mutațiilor sunt următorii:

  • pentru fiecare cromozom se generează un număr aleator subunitar; dacă acest număr este mai mic decât probabilitatea de mutație, atunci cromozomul este selectat pentru a deveni mutant;
  • pentru un cromozom ales se selectează două gene și se modifică porțile corespunzătoare lor.

Pentru a realiza recombinarea vom parcurge următoarele etape:

  • pentru fiecare cromozom se generează un număr aleator subunitar; dacă acest număr este mai mic decât probabilitatea de recombinare atunci cromozomul este selectat pentru a fi recombinat;
  • se aleg perechi de câte doi cromozomi din lista celor selectați pentru recombinare;
  • pentru fiecare pereche de cromozomi se alege un număr întreg P din intervalul [1,nro-1] care va indica faptul că fiecare cromozom va păstra primele sale P gene;
  • informațiile corespunzătoare restului genelor sunt copiate din cromozomul pereche; în cazul în care apare situația ca o genă nouă să indice o poartă care există deja în structura unui cromozom, ea va fi înlocuită de cea mai apropiată poartă nefolosită;
  • noii cromozomi își vor înlocui "părinții" în populație.

La fiecare generație vom păstra în populație cel mai bun cromozom obținut până atunci chiar dacă, în mod normal el ar fi fost pierdut.

Listing aero.PAS

P049806: Asemănare

Soluție propusă de Andrei Vancea, Liceul de Informatică, Cluj

Două poligoane se numesc asemenea dacă au unghiurile congruente și laturile respectiv proporționale. în cazul particular al triunghiurilor se știe că este suficient să demonstrăm una din următoarele afirmații pentru ca două triunghiuri să fie asemenea:

  • Triunghiurile au unghiurile congruente.
  • Triunghiurile au laturile respectiv proporționale.
  • Triunghiurile au câte două laturi respectiv proporționale și unghiurile formate de aceste laturi în aceste triunghiuri sunt congruente.

Un poligon cu N laturi poate fi triunghiularizat în N-2 triunghiuri. Dacă avem două poligoane pentru care cele N-2 triunghiuri sunt asemenea atunci putem afirma că cele două poligoane sunt asemenea. De aici deducem că primele două cazuri de asemănare pentru triunghiuri pot fi generalizate astfel:

  • Două poligoane sunt asemenea dacă au unghiurile congruente.
  • Două poligoane sunt asemenea dacă au laturile respectiv proporționale și diagonalele respectiv proporționale.

Programul prezentat aici folosește algoritmul bazat pe primul din aceste două cazuri de asemănare.

Listing polig.PAS

Paginile "Soluții" au fost coordonate de Clara Ionescu

E-mail: cionescu@ginfo.ro

[cuprins]