Pagini recente » Diferente pentru problema/porcjoc intre reviziile 37 si 14 | Monitorul de evaluare | Istoria paginii utilizator/alexandru | Monitorul de evaluare | substitutii

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2021-03-19 11:03:55.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	substitutii.in, substitutii.out	Sursă	utcn-2021
Autor	Tudor Muresan	Adăugată de	Ciprian Oprisa •cypry
Timp execuţie pe test	0.1 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Substituții circulare cu element maxim

Se consideră elementele $1, 2, \ldots, n$ şi permutările formate cu ele. Permutarea $1, 2, \ldots, n$ se numeşte permutare principală. Se numeşte substituţie de grad $n$ operaţia prin care se trece de la permutarea principală la o permutare dată. De exemplu pentru grad 10 avem substituţia:

$\left(\begin{matrix} \pmb{1} & 2 & \pmb{3} & \pmb{4} & 5 & \pmb{6} & 7 & 8 & 9 & 10 \\ \pmb{3} & 2 & \pmb{4} & \pmb{6} & 5 & \pmb{1} & 8 & 9 & 10 & 7 \end{matrix}\right) \quad \text{ciclul lui 1} \rightarrow \left(\begin{matrix} \pmb{1} & 3 & 4 & 6 \\ 3 & 4 & \pmb{6} & 1 \end{matrix}\right) \quad \text{6 este maxim}$

Notăm cu $s(i)$ elementul permutării care corespunde în permutarea principală elementului $i$ . Pentru exemplul dat $s(1)=3, s(2)=2, s(3)=4$ , etc. Se numeşte substituţie circulară, sau ciclu, o substituţie în care plecând de la elementul $i$ şi aplicând succesiv operaţia $s()$ de $p$ ori se ajunge din nou la elementul $i$ . În exemplul de mai sus elementul 1 are un ciclu de 4 elemente: $s(1)=3, s(3)=4, s(4)=6, s(6)=1$ . La fel elementul 7 are un ciclu de 4 elemente, iar elementele 2 şi 5 au un ciclu de 1 element. În ciclul elementului 1 avem elementul maxim al ciclului egal cu 6. Elementele ciclului $1, 3, 4, 6$ din permutarea principală apar în permutarea substituţiei deplasate cu o poziţie la stânga $3, 4, 6, 1$ . (Pentru substituţia: $1, 6, 3, 4$ în permutarea principală ar fi $6, 3, 4, 1$ în permutarea substituţiei.)