Putem observa urmatorul lucru care ne poate ajuta sa scriem un program mai scurt:
practic, cand inversam ordinea, observam ca primul (lementul de pe 0), schimba locuri cu cel de pe n-1, cel de pe 1 cu cel de pe n-2, cel de pe 2 cu cel de pe n-3-- si tot asa. si putem spune ca acesti indecsi formeaza cateva perechi
daca nu observi un model -- pai cam despre asta e vorba in informatica.. dar totul se imbunatateste cu mai mult antrenament! Sugerez sa incerci problemele listate pentru clasa a 9-a de pe pbinfo.ro
dar uite ca te ajut:
suma oricaror doua numere dni perechile listate anterior au o suma de n-1! ce tare! acum stim exact ce trebuie sa facem.
putem incepe cu algoritmul acesta naiv:
pentru fiecare index ( sa-l numim i) mai mic ca n/2 ( nu vrem sa repetam operatiile, si aici e de ce:)
si penntru fiecare index (sa-l numim j) mai mare ca n/2 (se observa ca nu se poate ca doau numere mai mici ca n/2 sa aiba suma n-1 din motive evidente)
verificam daca i+j=n-1
daca da, atunci interschimbam i si j
daca nu, atunci continuam.
Dar-- dar, asta e prea costisitor! Sigur putem mai bine, nu?
observam ca pentru un i variabil, j depinde de valoarea lui i si este constant astfel, cum
i+j=n-1
j=(n-1) - i
daca fixam i-ul j e constant, deci, putem face urmatoarea chestie
pentru i de la 0, pana la n/2,
j=n-1-i
interschimba(valoarea de pe i, valoarea de pe j)
de asemenea, putem schimba doi indici maxim o data, pentru ca altfel, ajungem de unde am venit
deci, daca trebuie sa interschimbam si indicii din mijloc, putem cand parcurgem vectorul pentru a inversa vectorul sa nu ii mai interschimbam!
te las pe tine sa implementezi :), copiatul nu iti va aduce nimic in viata
