Clasa VII/VIII lecția 17 - 27 ian 2015

Tema - rezolvări

Rezolvări aici [1]

Lecţie

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. Fiecare număr din permutare semnifică poziţia care se va afla în final pe acea poziţie. 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), deoarece pe poziţia 1 va veni numărul de pe poziţia 2, pe pozitia 2 va veni numărul de pe poziţia 5 şi aşa mai departe. 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 7-a

Tema 17 clasa a 7^a

• sport dată la ONI 2011 clasa a 8^a
• lăcusta dată la OJI 2005 clasa a 10^a
• leduri 1 dată la ONI 2007 clasa a 7^a

Clasa a 8-a

Tema 17 clasa a 8^a

• dartz 1 dată la ONI 2010 baraj gimnaziu (formă modificată)
• tdrept dată la ONI 2014 clasa a 8^a

Rezolvări aici [2]