Problema Permutării Circulare la Stânga într-un Vector în C++ 25

---

1. Obiectivele lecției:

• Să înțeleagă conceptul de permutare circulară la stânga într-un vector.
• Să implementeze un algoritm pentru realizarea permutării circulare la stânga.
• Să aplice permutarea circulară la stânga pentru rezolvarea unor probleme practice.

---

2. Conținutul lecției:

---

Ce este permutarea circulară la stânga?

• Definiție: Permutarea circulară la stânga presupune mutarea fiecărui element al unui vector cu o poziție spre stânga, iar primul element este mutat la sfârșitul vectorului.
• Exemplu:
  • Vector inițial: [1, 2, 3, 4, 5]
  • După o permutare circulară la stânga: [2, 3, 4, 5, 1]

---

Pașii algoritmului pentru permutare circulară la stânga

1. Stocați primul element al vectorului într-o variabilă temporară.
2. Deplasați toate elementele din vector cu o poziție spre stânga.
3. Plasați elementul din variabila temporară în ultima poziție.

---

Pseudocod:

Intrare: vector, dimensiune

Stochează vector[0] în temp

Pentru i = 1 la dimensiune – 1:

    vector[i – 1] = vector[i]

vector[dimensiune – 1] = temp

Ieșire: vector permutat

---

3. Cod în C++

---

Exemplu 1: Permutare circulară la stânga cu o singură rotație

#include <iostream>

using namespace std;

void permutareCircularaStanga(int arr[], int dim) {

    int temp = arr[0]; // Stocăm primul element

    // Deplasăm elementele spre stânga

    for (int i = 1; i < dim; i++) {

        arr[i – 1] = arr[i];

    }

    // Plasăm primul element la sfârșit

    arr[dim – 1] = temp;

}

void afisareVector(int arr[], int dim) {

    for (int i = 0; i < dim; i++) {

        cout << arr[i] << ” „;

    }

    cout << endl;

}

int main() {

    int arr[] = {1, 2, 3, 4, 5};

    int dim = sizeof(arr) / sizeof(arr[0]);

    cout << „Vector initial: „;

    afisareVector(arr, dim);

    permutareCircularaStanga(arr, dim);

    cout << „Vector dupa permutare circulara la stanga: „;

    afisareVector(arr, dim);

    return 0;

}

---

Exemplu 2: Permutare circulară la stânga cu mai multe rotații

#include <iostream>

using namespace std;

void permutareCircularaStanga(int arr[], int dim, int k) {

    k = k % dim; // Optimizare: eliminăm rotațiile complete

    for (int r = 0; r < k; r++) {

        int temp = arr[0]; // Stocăm primul element

        for (int i = 1; i < dim; i++) {

            arr[i – 1] = arr[i];

        }

        arr[dim – 1] = temp; // Plasăm primul element la sfârșit

    }

}

void afisareVector(int arr[], int dim) {

    for (int i = 0; i < dim; i++) {

        cout << arr[i] << ” „;

    }

    cout << endl;

}

int main() {

    int arr[] = {1, 2, 3, 4, 5};

    int dim = sizeof(arr) / sizeof(arr[0]);

    int k;

    cout << „Vector initial: „;

    afisareVector(arr, dim);

    cout << „Introdu numarul de permutari circulare la stanga: „;

    cin >> k;

    permutareCircularaStanga(arr, dim, k);

    cout << „Vector dupa ” << k << ” permutari circulare la stanga: „;

    afisareVector(arr, dim);

    return 0;

}

---

4. Complexitatea algoritmului

1. Complexitate temporală:
   • O rotație: O(n), unde nnn este dimensiunea vectorului.
   • kkk rotații: O(k⋅n).
2. Complexitate spațială:
   • O(1), deoarece se folosește doar o variabilă temporară.

---

5. Activități practice pentru elevi

1. Scrieți un program care realizează permutarea circulară la dreapta a unui vector.
2. Implementați o funcție care efectuează permutarea circulară la stânga fără utilizarea unei variabile temporare.
3. Realizați un program care citește un vector de la utilizator și aplică k permutări circulare la stânga.

---

6. Scheme logice

1. Permutare circulară la stânga:
   • Start -> Stochează primul element -> Deplasează restul elementelor -> Plasează primul element la sfârșit -> Stop.
2. Permutare circulară cu mai multe rotații:
   • Start -> Redu k modulo dimensiune -> Repetă algoritmul de k ori -> Stop.

---

7. Concluzie:

• Permutarea circulară la stânga este o operație simplă, dar utilă în multe aplicații practice.
• Optimizarea pentru mai multe rotații poate reduce semnificativ timpul de execuție.
• Înțelegerea acestui algoritm ajută elevii să gestioneze eficient datele într-un vector.