Rotirea unui vector cu k poziții în C++

Rotirea la dreapta mută ultimul element la început și păstrează toate valorile. Pentru 10 20 30 40 50, rotirea cu două poziții produce 40 50 10 20 30. O deplasare care pierde ultimele valori este altă operație.

Intrare și convenții

Citim 1 ≤ n ≤ 1000, 0 ≤ k ≤ 10^18, apoi n numere întregi. Cerem exact k rotiri la dreapta. Tablourile clasice a și b au fiecare capacitatea 1000; numai pozițiile 0..n-1 fac parte din date. Nu acceptăm n=0, fiindcă expresia k % n nu ar fi definită.

Rotirea la dreapta cu două poziții transformă 10,20,30,40,50 în 40,50,10,20,30.Mărește schema ↗

De la rotiri repetate la o formulă

După n rotiri obținem vectorul inițial. Numărul efectiv de pași este k % n. Un element aflat inițial la i ajunge la (i + pas) % n. Pentru exemplul cu cinci elemente și pas=2, pozițiile finale ale elementelor sunt 2, 3, 4, 0, 1.

Construim rezultatul într-un al doilea tablou. Dacă am scrie direct în a, am putea suprascrie o valoare pe care încă trebuie să o mutăm. Formula trimite două poziții inițiale diferite către poziții finale diferite, deci fiecare celulă din b primește exact o valoare.

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n; long long k; cin >> n >> k;
    int a[1000], b[1000];
    for (int i = 0; i < n; ++i) cin >> a[i];
    int pas = static_cast<int>(k % n);
    for (int i = 0; i < n; ++i) b[(i + pas) % n] = a[i];
    for (int i = 0; i < n; ++i) cout << b[i] << (i+1 == n ? '\n' : ' ');
}

Varianta echivalentă cu std::vector

Indicii și datele de intrare rămân aceleași. Containerul este construit cu numărul de elemente folosite; accesul prin [] cere în continuare indici valizi.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n; long long k; cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int pas = static_cast<int>(k % n);
    for (int i = 0; i < n; ++i) b[(i + pas) % n] = a[i];
    for (int i = 0; i < n; ++i) cout << b[i] << (i+1 == n ? '\n' : ' ');
}

Verificarea direcției

Urmărește un element ușor de recunoscut, de exemplu 10. La rotirea la dreapta cu 2, indicele lui crește de la 0 la 2. La rotirea la stânga cu 2 ar ajunge la indicele 3. Nu folosi același exemplu cu toate valorile egale pentru a verifica direcția: ambele erori ar rămâne invizibile.

Pentru rotire la stânga poți folosi destinația (i + n - pas) % n, după normalizarea lui pas. Adăugarea lui n evită un operand negativ al operatorului %. Această lecție implementează doar direcția la dreapta, conform contractului.

Timpul este O(n), indiferent de mărimea lui k. Memoria auxiliară este O(n). Repetarea unei deplasări de câte k ori ar costa O(n·k), inutil când k este foarte mare. Există și metode cu memorie O(1), bazate pe inversări, dar cer un argument separat pentru ordinea transformărilor.

Exersează

Pentru n=5, k=7, folosește același rezultat ca pentru k=2. Pentru k=0 sau k=5, vectorul rămâne neschimbat. Pentru n=1, orice k permis produce același element. Aceste teste verifică normalizarea, fără a adăuga ramuri speciale în program.

Scrie pe hârtie rezultatul pentru 1 2 3 4 și k=1: 4 1 2 3. Apoi aplică o rotire la stânga cu același pas și verifică revenirea la intrare.

Recapitulează indexarea vectorilor, restul împărțirii și deplasarea la inserare și ștergere.

Întrebări frecvente

Cum rotesc un vector la dreapta cu k poziții?

După reducerea lui k modulo n, elementul de pe poziția i ajunge pe poziția (i+k)%n. Pentru 10 20 30 40 50 și k=2, rezultatul este 40 50 10 20 30.

De ce folosim k modulo n la rotire?

După n rotiri, fiecare element revine pe poziția inițială. Prin urmare, k și k%n produc aceeași ordine. Formula presupune n pozitiv; împărțirea modulo zero nu este permisă.

Care este diferența dintre rotire și deplasare?

Rotirea readuce la celălalt capăt elementele care trec de margine și păstrează toate valorile. O deplasare poate pierde valori sau poate introduce unele noi, după convenția problemei.