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 surjectiveSoluț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. 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. 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:
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). 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. 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:
[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);
Pașii necesari simulării mutațiilor sunt următorii:
Pentru a realiza recombinarea vom parcurge următoarele etape:
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. P049806: AsemănareSoluț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:
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:
Programul prezentat aici folosește algoritmul bazat pe primul din aceste două cazuri de asemănare. Paginile "Soluții" au fost coordonate de Clara Ionescu E-mail: cionescu@ginfo.ro [cuprins] |