h2(#egipt). 'Egipt':problema/egipt

*Rezolvare $1$*

*Soluţie $1$*

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.)

Notăm cu $m{~ij~}$ 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$

$m{~12~} + m{~13~} = m{~21~} + m{~31~}$
$m{~21~} + m{~23~} = m{~12~} + m{~32~}$
$m{~31~} + m{~32~} = m{~13~} + m{~23~}$

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|$

$min(m{~12~}, m{~21~}) + min(m{~23~}, m{~32~}) + min(m{~13~}, m{~31~}) + 2|m{~12~} − m{~21~}|$

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$

Fig. $3$. Poziţiile interschimbărilor: $p{~ij~}$ este indicele elementului egal cu $j$ aflat pe poziţia $i$

*Rezolvare $2$*

*Soluţie $2$*

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$.
$i2$ şi $i3$ vor fi poziţionate întotdeauna asupra unui element egal cu $1$. Dacă elementul pe care am poziţionat $i$ este egal cu $1$, nu trebuie să facem nimica, doar incrementăm $i$. Dacă acesta este egal cu $2$, vom schimba elementele de pe locurile $i$ şi $i2$ şi vom incrementa $i$, iar pe $i2$ îl poziţionăm pe următorul element egal cu $1$. Dacă cu $i2$ am depăşit pragul din dreapta al intervalului (adică ultimul loc unde trebuie să ajungă $2$), elementul de pe poziţia $i$ îl vom schimba cu elementul arătat de $i3$. Procedăm similar pentru elementele egale cu $3$.