infoarena

Am dat de o problema in care mi se da un sir de numere si eu trebuie sa le ordonez crescator in asa fel in cat costul sa fie minim! COSTUL= suma numerelor pe care la interschimb.
ex se da sirul 3 2 1 costul minim e 4. se interschimba 3 cu 1 costul fiind suma acestora
ex2:  8 1 2 4 costul minim e 17 ..
Nu am nici cea mai vaga idee:|
 ](*,)

Au voie sa se repete numere?

In cazul in care nu au voie, ai putea sa consideri vectorul normalizat ca o permutare, sa identifici ciclii in aceasta permutare, iar pentru rezolvarea pozitiilor care nu corespund sa folosesti ca pivot cel mai mic element din ciclu.

nu este mentionat faptul ca nu pot sa se repete dar dupa cerinta s-ar putea deduce ca nu pot sa se repete numerele..

am inteles ideea ta la ceva asemanator ma gandeam si eu acu sa vad cum reusesc sa o implementez :) Respect!

In cazul in care se repeta, va trebui sa fi atent sa nu interschimbi elemente cu valori egale, dar cred ca ideea de baza va ramane aceeasi.

Bafta!  :thumbup:

Cred ca problema este in momentul in care pivotul(elementul minim ajunge pe pozitia lui finala) nu va mai functiona
ex 8 4 5 3 2 7 si costul minim stiu ca trebuie sa fie 34 
interschimbarile vor fi asa:
8 4 5 3 7 2(cost 9)
2 4 5 3 7 8(cost 10)
2 3 5 4 7 8 (cost 7)
2 3 4 5 7 8 (cost 9)
costul fiind 35

Eu nu am reusit sa ajung la costul 34, dar oricum este posibil sa apara cazul in care este necesar sa strici un ciclu pentru a rezolva un altul.

Ce am scris mai sus a fost o idee, data fara o analiza minutioasa a cazurilor ce pot aparea :)

ma poate ajuta careva sa fac o sortare cu un pivot care va fi elementul minim din sir si va ajunge pe pozitia lui finala dupa ce s-au epuizat toate interschimbarile
ex
de la 2 4 1 3 sa ajung la 1 2 3 4 prin interschimbarile
2 4 3 1->2 1 3 4 ->1 2 3 4
iar daca pivotul ajunge in pozitia lui finala si inca nu este sortat sirul se ia ca pivot urmator elemen ca valoare minima

cred ca se face cu programare dinamica nu stiu  :fool:
as mai aveea o idee dar care tot asa nu cred ca e buna sa pun toate costurile intr-o matrice .. si sa incerc sa ordonez asa dar nici asta nu ma condus la nici un rezultat pana acuma ](*,)