Din GInfo nr. 7

SOLUȚIILE problemelor propuse

Între 26 iulie - 9 august la Constanța s-a desfășurat a doua tabără de antrenament a lotului olimpic național de informatică. La sfârșitul celei de a doua săptămâni membrii lotului lărgit au primit șapte probleme. Vă prezentăm în continuare soluțiile problemelor.

P079801: Coloane

Problemă propusă de conf. dr. Henri Luchian, Universitatea "Al. I. Cuza", Iași
Soluția îi aparține lui Mihai Scorțaru, student, Universitatea Tehnică, Cluj

Deoarece pentru această problemă nu se cunoaște o soluție polinomială, algoritmul propus pentru rezolvare este unul genetic. Rezultă că metoda de rezolvare va fi una nedeter mi nistă, negarantându-se obținerea unui re zul tat corect la fie care rulare.

Pentru început vom observa că nu există soluție în ca zul în care o anumită linie conține numai zerouri. În cazul în care nu există o asemenea linie, prin selectarea tuturor co loanelor sigur se obține o soluție.

Pentru implementarea algoritmului genetic vom folosi o populație de zece cromozomi, probabilitatea de mutație va fi 0.2 și va crește cu 10% la fiecare 100 de generații, iar pro babilitatea de recombinare va fi 0.6.

Un cromozom va conține n gene (n = numărul de coloane), fiecare genă putând avea valoarea 0 (caz în care coloana corespunzătoare nu trebuie aleasă) sau 1 (caz în care co loana co res punzătoare trebuie aleasă).

Pentru fiecare cromozom trebuie calculat un punctaj care să-i caracterizeze adaptarea. Acest punctaj va fi dat de for mula: P=4*n+1-c-2*l-x*n, unde:

N reprezintă numărul de coloane ale matricei

C reprezintă numărul de coloane selectate

L reprezintă numărul de linii pentru care suma elemen te lor de pe linie este 0

X=0 dacă L=0 și X=1 dacă Lč0;

Pentru fiecare generație trebuie să realizăm o selecție, să efectuăm câteva mutații și să recombinăm cromozomii.

Selecția se realizează astfel:

  • se determină punctajul fiecărui cromozom;
  • se calculează suma S a punctajelor cromozomilor;
  • se calculează probabilitatea de selecție a fiecărui cro mo zom; aceasta va fi egală cu raportul dintre punctajul său și valoarea S;
  • se împarte intervalul [0,1) în zece subintervale astfel în cât lungimea intervalului corespunzător unui cromozom să fie egală cu probabilitatea de selecție a acelui cromo zom; de exemplu, pentru o populație care are cromozomii 1, 3, 5, 7, 9 cu probabilitatea de selecție 0.15 și cro mo zomii 2, 4, 6, 8, 10 cu probabilitatea de selecție 0.05, in tervalele corespunzătoare vor fi:

[0,0.15), [0.15,0.2), [0.2,0.35), [0.35,0.4), [0.4,0.55), [0.55,0.6), [0.6,0.75), [0.75,0.8), [0.8,0.95), [0.95,1);

  • se generează zece numere aleatoare subunitare și pentru fie care din aceste numere se determină intervalul din care fa ce parte iar cromozomul corespunzător este selectat (se observă că un același cromozom poate fi ales de mai mul te ori).

Pentru mutații vom proceda în felul următor:

  • se generează câte un număr aleator subunitar pentru fie ca re cromozom; dacă acest număr este mai mic decât probabilitatea de mutație atunci acest cromozom va de ve ni mutant;
  • pentru a realiza mutația propiu-zisă se selectează o genă și i se schimbă valoarea.

Recombinarea va necesita următoarele operații:

  • se generează câte un număr aleator subunitar pentru fie ca re cromozom; dacă acest număr este mai mic decât pro babilitatea de recombinare atunci acest cromozom va fi selectat pentru a fi recombinat;
  • se aleg perechi de câte doi cromozomi din lista celor se lec tați pentru recombinare;
  • pentru fiecare pereche de cromozomi se aleg două nu me re aleatoare întregi P1 și P2 (P1 < P2) din intervalul [1,n] care vor indica faptul că fiecare cromozom își va păstra primele P1 și ultimele n-P2 gene;
  • se copiază din cromozomul pereche informațiile corespunzătoare celorlalte gene;
  • noii cromozomi își vor înlocui "părinții" în populație.

La fiecare generație cel mai bine adaptat cromozom va fi păstrat chiar dacă, în urma selecției, mutației sau re com bi nării, el nu ar mai trebui să facă parte din populație.

Listing COLOANE.PAS

P079802: Cuburi

Soluție propusă de autorii problemei, prof. Maria și Adrian Niță, Liceul "Emanoil Gojdu", Oradea

Metoda de rezolvare "reface" cuburile și verifică dacă cele două cuburi date sunt identice. În acest scop unul din cu buri este "rotit" astfel încât fețele superioare ale celor două cuburi să coincidă, apoi se verifică dacă și restul fețelor coincid.

Listing: CUBURI.CPP

P079803: Eschimoși

Problemă propusă de lect. Clara Ionescu, și rezolvată de conf. dr. Teodor Toadere Universitatea "Babeș Bolyai", Cluj

Fie Gn = (X, U) cu X = {0, 1,?, n} și

U = {(i, j) | i, j Î X, i = 0 sau i - j = 1}

Notăm cu An = { P | P = (X, V), V Ì U și P arbore} și cu |An| = an.Dorim să determinăm o relație de recurență pen tru șirul (an)nÎN.

Mai întâi să constatăm că:

a) a1 = 1 pentru că A1 = {G1}

b) a2 = 3 pentru că:

c) |a3| = 8 pentru că arborii de acoperire a lui G3, adică

Tot prin enumerarea arborilor lui G4 se obține a4 = 21

Pentru a exprima pe an facem următoarea des com pu ne re (partiționare) de mulțimi

An = E È F È G, unde

E = mulțimea arborilor din An care conțin muchia (0, n) și nu conțin muchia (n, n - 1);

F = mulțimea arborilor din An care conțin muchia (n, n -1) și nu conțin muchia (0, n);

G = mulțimea arborilor din An care conțin atât muchia (0, n) cât și muchia (n, n - 1).

Se deduce că E Ç F = E Ç G = F Ç G = Æ și deci

an = |An| = |E| + |F| + |G|

Vom demonstra că

a) |E| = |An-1| = an-1

b) |F| = |An-1| = a1

c)

prin a preciza niște bijecții íntre mulțimile respective.

Astfel:

a) f:EźAn-1, unde pentru fiecare P Î E, f(P) este graful ob ți nut din P prin eliminarea vârfului n și a muchiei (0, n). Din definiție deducem că f(P) are n-1 vârfuri este conex și are n-2 muchii deci f(P) Î An-1. Se verifică ușor că f este in jec tivă (" P1 č P2 din E Ț f(P1) č f(P2)) și că f este sur jec ti vă (" PÎAn-1 prin adăugarea vârfului n și a muchiei (0, n) se obține arborele P' cu P' Î E și f(P') = P).

b) analog, h:FźAn-1, definită prin h(P) este graful obținut din arborele P Î F prin eliminarea vârfului n și a mu chi ei (n, n - 1), este o bijecție

c) pentru demonstrarea egalității considerăm func ția ,

prin "kÎ{0,?,n-2} și " PÎAk definim pe g(P) ca fiind gra ful obținut din P prin adăugarea lanțului {k+1,?,n-1, n,0} și a vârfurilor corespunzătoare (deci între vârfurile k și k+1 în g(P) nu există muchie. Se demonstrează ușor că g(P) (este arbore din Gn care conține muchiile (n - 1, n) și (n, 0)) și că g este o bijecție (din P1 č P2 Ț g(P1) č g(P2) și că " P Î G $ k astfel încât " i Î { k + 1, ?, n}, (0, i) Ï P și deci P este format din lanțul {k + 1, ?, n, 0} și un ar bo re al lui Gk.

Prin urmare

an = | E | + | F | + | G | = 2an-1+

+

Deci, relația de recurență este: an = 3an-1 -an -2

Cum rădăcinile ecuației caracteristice x2 - 3x + 1 = 0 sunt , expresia termenului general este:

.

Constantele c1 și c2 se obțin din sistemul a1 = 1 și a2=8 și sunt

Deci

Cum se știe că termenii șirului lui Fibonacci sunt

constatăm că an = f2n-1 " n ÎN*.

Implementarea, deosebit de simplă, conține totuși un "apel" la cunoștințe de programare: pentru a calcula și afi șa numărul cerut (poate avea 15 cifre!), acesta trebuie să fie de clarat de tipul Comp. Pentru a lucra cu acest tip, este ne vo ie ca opțiunea de compilare Numeric Processing 80x87 să fie activată. Activarea se realizează folosind directiva de compilare {$N+}.

Listing ESCHIMOSI.PAS

P079804: Rezistențe

Problemă propusă și rezolvată de Valentin Gheorghiță, student, Universitatea Politehnică, București

Pri mul lucru delicat în rezolvarea acestei probleme este struc turarea datelor. Pentru a putea păstra informațiile des pre fiecare rezistență vom crea o listă cu N (numărul de re zistențe la un moment dat) înregistrări, pentru fiecare re zistență păstrând nodurile i și j (i<j) între care se află re zistența și valoarea rezistenței.

În continuare vom crea cele trei proceduri ce tratează trans formările prezentate (serie, paralel, triunghi-stea) în pro blemă. Totdeauna, în momentul apelării uneia dintre aceste proceduri lista cu rezistențe va fi sortată crescător în func ție de i (nodul cu valoarea cea mai mică de care este le gată rezistența) iar în caz de egalitate în funcție de j (no dul cu valoarea cea mai mare de care este legată rezistența). Sor tarea se va face utilizând algoritmul qsort, com ple xi ta tea lui medie fiind n*log2n.

Procedura de legare în paralel are complexitatea liniară, egală cu numărul de rezistențe aflate în circuit. În pro ce dură se va parcurge lista cu rezistențe, iar dacă două sau mai multe rezistențe se află între aceleași două noduri, atunci acele rezistențe vor fi eliminate din listă și în locul lor se va adăuga o singură rezistență aflată între aceleași no duri, dar cu valoare calculată după formula dată în pro ble mă.

Pentru transformarea triunghi-stea se va defini gra dul unui nod ca fiind numărul de rezistențe care sunt le gate de acel nod. În continuare, în procedura care rezolvă această trans formare, pentru fiecare două rezistențe afla te între no durile i și j, respectiv i și k (adică au un nod comun), da că nodurile i, j, k au gradul mai mare decât 2 se va ve ri fica dacă există o rezistență între nodurile j și k. Dacă exis tă, atunci se vor elimina cele trei rezistențe, in tro du cân du-se în locul lor alte trei cu valori calculate după for mu lele date, legate la un capăt de un nod nou in tro dus, iar la celălalt de nodurile i, j, respectiv k.

Pentru legarea în serie, se observă că, dacă un nod are gra dul doi și nu este unul dintre nodurile între care trebuie cal culată rezistența echivalentă, atunci el poate fi eliminat îm preună cu rezistențele care se leagă de el. În cazul găsirii unui astfel de nod se parcurge recursiv circuitul într-o par te și în cealaltă, până se va ajunge la noduri care au gradul di fe rit de 2. Rezistențele și nodurile (cu gradul egal cu 2) prin care s-a trecut în această parcurgere, sunt eliminate, in troducându-se o nouă rezistență care are ca valoare su ma rezistențelor eliminate și este legată de cele două no duri în care ne-am oprit cu parcurgerea.

În final se vor utiliza procedurile definite pentru a cal cu la rezistența echivalentă. Pentru aceasta, vom repeta ur mă toarea secvență până când lista rezistențelor va conține o singură înregistrare care este chiar rezistența echivalentă ce trebuia calculată:

  • sortare
  • procedura legare în paralel
  • sortare
  • procedura transformare triunghi-stea
  • sortare
  • procedura legare în serie

Observație: rezultatul se cere cu trei ze cimale exacte, deci trebuie puțină atenție la afișarea cu au toformatare, pen tru că de exemplu, în Pascal, aceasta pro duce ro tun ji rea și nu trunchierea rezultatului.

Listing: REZISTENTE.PAS

P079805: Seiful

Problemă propusă și rezolvată de prof. Dana Lica, Liceul "I. L. Caragiale", Ploiești

Pentru orice grup care trebuie format din n-2 persone (conform cerințelor problemei) trebuie să exis te cel puțin un lacăt pe care nu-l va deschide nimeni din grup. Rezultă că celelalte două persoane rămase în afara grupului dețin fiecare cheia lacătului respectiv. Astfel, atunci când una din cele două persoane intră în grupul de n-2 persoane, lacătul va putea fi deschis.

Deducem că la fiecare lacăt trebuie să existe exact două chei. Tot de aici se deduce că numărul de lacăte este egal cu numărul grupurilor distincte formate din n-2 per soa ne, adică n(n-1)/2.

Atunci numărul total de chei va fi n(n-1).

Listing: LACATE.PAS

P079806: Piramida lui Keops

Problemă propusă și rezolvată de Marius Vlad, student, Universitatea Politehnică, București

Deoarece problema cere determinarea unui minim care ar tre bui căutat în mulțimea unor soluții posibile care se pot ge nera arborescent, s-a ales ca metodă de rezolvare me to da pro gra mă rii dinamice.

Vom calcula cu ajutorul unei pro ce duri re cur sive (AjungeIn) drumurile minime de la fie ca re bloc de pe o la tură exterioară a bazei piramidei la celelalte blo curi ale bazei.

Pentru fiecare nivel (diferit de bază) și pentru fie care bloc în parte de pe acest nivel, presupunem că ajun gem în acel bloc venind de pe nivelul inferior și calculăm cu aju to rul aceleiași proceduri recursive lungimea dru mu lui ple când de la blocul respectiv la toate blocurile exis ten te pe acel nivel.

Procedura recursivă AjungeIn este asemănătoare cu o pro cedură fill obișnuită și poate fi rapid implementată în timp de concurs. Se oprește în momentul în care lun gi mea drumului pe calea urmată este mai mare decât lungimea drumului minim găsit.

De fiecare dată când se găsește un drum de lungime mai mică decât cel existent se salvează adresa blocului pre ce dent pentru a reconstrui drumul de întoarcere plecând de la blocul din vârf.

Listing PIRAMIDA.PAS

P079807: Rigle Golomb

Problemă propusă de conf. dr. Henri Luchian, Universitatea "Al. I. Cuza", Iași

În loc de analiza riguroasă a problemei vă vom "istorisi" cele întîmplate la Constanța. "Ideile" olimpicilor pot fi uti le ori de câte ori vă veți afla în fața unei probleme având ace leași caracteristici.

Aceasta a fost o problemă la care aproape toți con cu ren ții au reu șit să "păcălească" juriul. Problema a fost con si derată ca fiind destul de dificilă, comisia așteptându-se la so luții "speciale" din partea concurenților cum ar fi cele ba zate pe al goritmii genetici. Nu a fost să fie așa, deoarece co misia a scă pat din vedere faptul că datele de intrare con ți neau un singur număr și acesta putea lua valori între 1 și 16. Din această cauză nu existau decât 16 posibilități pen tru rezultate, iar fișierul de ieșire nu conținea decât maxim 16 nu mere. Așa că, spre mai mica sau mai marea sur prin de re a comisiei, concurenții au declarat niște constante care erau afișate în funcție de valoarea care se găsea in fișierul de intrare. Singurul impediment în obținerea punctajului ma xim era determinarea celor 16 soluții posibile. Concurenții au folosit diferite metode pentru a le de termina în cele 4 ore pe care le-au avut la dispoziție. S-au folosit al go ritmi probabiliști (dar nu genetici), me tode backtracking, me tode euristice etc. Au rulat programele respective în "back ground" și au copiat rezultatele în constantele de cla ra te în programele predate pentru evaluare. (Se pare că mul ti-taskingul din Windows poate fi folosit la ceva!) Și pen tru ca participanții să nu se plângă că problema a fost prea dificilă, cea mai mare valoare cu care au fost tes ta te pro gramele a fost 11 (unsprezece). Mai mult, s-a acor dat punctaj maxim chiar dacă soluția nu era optimă, ci doar re la tiv apropiată de ceea ce ar fi trebuit să se obțină, așa că unii concurenți au obținut cele 50 de puncte cu problema rezolvată doar pe jumătate. Mai trebuie precizat faptul că olim picii nu au ezitat să-și arate "recunoștința" față de ge ne rozitatea comisiei și și-au manifestat dorința de a mai rezolva câteva probleme de acest fel. Având în vedere cele pre cizate mai sus, programul următor ar fi obținut cu si gu ran ță punctajul maxim.

Listing RIGLA.CPP

[cuprins]