Pagini recente » Diferente pentru utilizator/darth_niculus intre reviziile 86 si 53 | Profil biro | Diferente pentru problema/gugustiuc intre reviziile 65 si 59 | Diferente pentru utilizator/darren intre reviziile 176 si 194 | Diferente pentru grigore-moisil-2010/solutii/egipt intre reviziile 2 si 3
Nu exista diferente intre titluri.
Diferente intre continut:
h2(#egipt). 'Egipt':problema/egipt
Fie n1 numărul elementelor egale cu 1, n2 numărul elementelor egale cu 2 şi n3 numărul elementelor egale cu 3 în şirul dat a. Altfel spus, în şirul ordonat vom avea valori egale cu 1 începând cu poziţia 1 până la poziţia n1, valori egale cu 2 începând cu poziţia n1+1 până la poziţia n1+n2, după care vom avea elemente egale cu 3.
Notăm cu mij numărul elementelor egale cu j care se află pe o poziţie pe care ar trebui să avem valoarea i. (Matricea m are 3 linii şi 3 coloane.)
!grigore-moisil-2010/solutii/egipt?1.png!
Fig. 1. În mij avem numărul elementelor care trebuie duse de pe poziţia i pe poziţia j
Observăm că
m12 + m13 = m21 + m31
m21 + m23 = m12 + m32
m31 + m32 = m13 + m23
Dacă avem 2 pe poziţia unui 1 şi 1 pe poziţia unui 2, avem nevoie de o singură interschimbare.
Dacă avem o configuraţie 2 3 1, sau 3 1 2, avem nevoie de două interschimbări.
!grigore-moisil-2010/solutii/egipt?2.png!
Rezultă că numărul minim de interschimbări care sunt necesare pentru ordonarea şirului este:
min(m12, m21) + min(m23, m32) + min(m13, m31) + 2|m12 − m21|
Realizarea interschimbărilor:
!grigore-moisil-2010/solutii/egipt?3.png!
Fig. 3. Poziţiile interschimbărilor: pij este indicele elementului egal cu j aflat pe poziţia i
Rezolvare cu metoda greedy
Rezolvarea se face în două faze. În prima fază vom pune la loc elementele egale cu 1. Pornim cu trei variabile: i va itera pornind din prima poziţie şi va merge până în ultima poziţie unde trebuie să ajungă un element egal cu 1; i2 va porni din prima poziţie unde trebuie să ajungă un element egal cu 2 şi va merge pâna la ultima poziţie de acest fel; similar i3 va itera pe intervalul unde trebuie să ajungă elementele egale cu 3.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.