Clasa VII/VIII lecția 10 - 10 dec 2013

Anunţ calificare cerc informatică

Elevii în probe au trimis teme astfel:

Nume	Problema 1	Problema 2	Problema 3	Problema 4
Bonciocat Ciprian	decodare	pom	avioane	capitala
Cioltan Alex			avioane(30)
Coman Mara	decodare	pom
Enache Adelina	decodare	pom		capitala(C++)
Ionescu Victor
Moanță Victor			avioane(30)
Moroianu Theodor				capitala(incercat)
Niculescu Tudor		pom
Vasilescu Andreea	decodare (cu probleme)
Vecerdea Dragoș	decodare (cu probleme)		avioane
Zaharia Andreea

Elevi care ramîn la cerc:

• Bonciocat Ciprian
• Coman Mara
• Enache Adelina (cu condiţia să înceteze cu C++)
• Vecerdea Dragoș

Pe lîngă cei care nu erau în probe:

• Hărșan Răzvan
• Mucenic Bogdan
• Petrescu Alex
• Zloteanu Anastasia

Tema - rezolvări

Rezolvări aici[1]

Lecţie

Problema regine

Mică discuţie despre backtracking şi problema regine. Care sînt diferenţele între recursivitate şi backtracking.

Discuţii probleme Şumen

Rezolvări aici [2]

Permutări, cicluri

O permutare poate fi văzută ca o funcție de rearanjare a valorilor inițiale. Dacă urmărim felul în care valorile își schimbă locurile vom observa că orice permutare conține cicluri, adică submulțimi ale mulțimii de valori care își schimbă circular valorile între ele. Ciclurile sînt disjuncte. Exemplu: fie permutarea (2 5 4 3 1). Pornim cu poziția 1, unde p[1] este 2. Avansăm pe poziția 2, unde p[2] este 5. Avansăm pe poziția 5, unde p[5] = 1, revenind astfel pe poziția 1. Am detectat astfel primul ciclu al permutării, format din (2, 5, 1). Continuăm cu primul element care nu face parte din ciclul găsit, care se află pe poziția 3. p[3] este 4, avansăm pe poziția 4. p[4] este 3, care încheie ciclul. Astfel, permutarea noastră se descompune în două cicluri disjuncte, (2, 5, 1) și (4, 3). Cum putem folosi această proprietate? Iată două exemple:

Exemplul 1: să se spună dacă un vector de n elemente conține toate numerele de la 1 la n. Memoria suplimentară disponibilă este O(1). Avem voie să modificăm vectorul original. O soluție bazată pe ciclurile permutărilor este să parcurgem aceste cicluri și să facem elementele 0 pe măsură ce le parcurgem. Dacă vectorul conține o permutare a numerelor 1-n atunci fiecare ciclu trebuie să se încheie acolo unde a început. Dacă parcurgînd ciclurile vectorului ajungem pe o poziție marcată cu 0 dar diferită de începutul ciclului înseamnă că nu avem o permutare. Ciclurile le parcurgem astfel: pornim cu primul element și parcurgem elementele pînă ne întoarcem. Apoi căutăm primul element diferit de 0 și reluăm. Ne oprim fie cînd găsim un ciclu incorect (caz în care nu avem o permutare), fie cînd ieșim din vector (caz în care permutarea este corectă).

Exemplul 2: a aplica o permutare unor obiecte înseamnă a le schimba ordinea conform permutării. De exemplu, dacă permutarea este (2 5 4 3 1) și o aplicăm obiectelor (1 2 3 4 5), după prima aplicare obținem chiar permutarea, (2 5 4 3 1). După a doua aplicare obținem (5 1 3 4 2), după a treia (1 2 4 3 5) și așa mai departe. Dată o permutare, după cîte aplicări obținem din nou permutarea inițială? Observăm că la fiecare aplicare a permutării ciclurile se rotesc cu 1. Fiecare ciclu i va reveni la poziția inițială după un număr l_i, care este lungimea ciclului. De aceea va fi nevoie de cmmmc(l_i) pentru ca toate ciclurile să ajungă în poziția inițială.

Temă

• Leduri 1 dată la ONI 2007 clasa a 7^a
• Sport dată la ONI 2011 clasa a 8^a
• Lăcusta dată la OJI 2005 clasa a 10^a

Rezolvări aici [3]