Clasa VI/VII/VIII lecția 15 - 11 dec 2012

Clasa a șasea

Exerciții recapitulative - probleme din urmă

Problema control1 (campion)

Rezolvare aici [1]

Problema talent (campion)

Discuție despre rezolvare, dar fără a scrie programul. A rămas ca temă. Rezolvare completă aici [2]

Problema cepe (vianuarena)

Discuție despre rezolvare, dar fără a scrie programul. A rămas ca temă. Rezolvare completă aici [3]

Temă clasa a șasea

• terminați problemele din urmă:
  • vianuarena: romb, integrame și cepe
  • campion: control1 (ONI 2010, clasa a 6-a) și talent (ONI 2011 clasa a 6-a)
• turn (campion, ONI 2007, clasa a 6-a)
• Opțional: roboti1 (campion, ONI 2010 clasa 7)

Clasa a șaptea și a opta

Exerciții recapitulative - probleme din urmă

Problema plimbare (vianuarena)

Discuție despre rezolvare, fără a scrie efectiv programul. Rezolvare aici [4]

Problema drenaj (campion)

Discuție despre rezolvare, fără a scrie efectiv programul. Rezolvare aici [5]

Clasa a 8-a: 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ă clasa a șaptea

• Terminați problemele din urmă:
  • vianuarena: numere, aranjamente și plimbare
  • campion: joc17 (ONI 2011 clasa a 7-a) și drenaj
• roboti1 (campion, ONI 2010 clasa 7)
• Opțional: sport2 (campion, ONI 2011 clasa 8)

Temă clasa a opta

• Terminați problemele din urmă:
  • vianuarena: numere, aranjamente și plimbare
  • campion: drenaj
• sport2 (campion, ONI 2011 clasa 8)
• Opțional: alee (campion, OJI 2007 clasa 10)
• Opțional: butoane (campion, ONI 2011 clasa 8)