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.