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

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!

        !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(m12, m21)$ + min(m23, m32) + min(m13, m31) + 2|m12 − m21|$

Realizarea interschimbărilor:
        !grigore-moisil-2010/solutii/egipt?3.png!