Din GInfo nr. 7
SOLUȚIILE problemelor propuseP079801: ColoaneProblemă propusă de conf. dr. Henri Luchian, Universitatea "Al.
I. Cuza", Iași 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:
[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);
Pentru mutații vom proceda în felul următor:
Recombinarea va necesita următoarele operații:
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. P079802: CuburiSoluț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. P079803: EschimoșiProblemă 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+}. P079804: RezistențeProblemă 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ă:
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. P079805: SeifulProblemă 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). P079806: Piramida lui KeopsProblemă 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. P079807: Rigle GolombProblemă 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. [cuprins] |