Problema Permutării Circulare la Dreapta într-un Vector în C++ 26
1. Obiectivele lecției:
- Să înțeleagă conceptul de permutare circulară la dreapta într-un vector.
- Să implementeze un algoritm pentru realizarea permutării circulare la dreapta.
- Să aplice permutarea circulară la dreapta pentru rezolvarea unor probleme practice.
2. Conținutul lecției:
Ce este permutarea circulară la dreapta?
- Definiție: Permutarea circulară la dreapta presupune mutarea fiecărui element al unui vector cu o poziție spre dreapta, iar ultimul element este mutat în prima poziție.
- Exemplu:
- Vector inițial: [1, 2, 3, 4, 5]
- După o permutare circulară la dreapta: [5, 1, 2, 3, 4]
Pașii algoritmului pentru permutare circulară la dreapta
- Stocați ultimul element al vectorului într-o variabilă temporară.
- Deplasați toate elementele din vector cu o poziție spre dreapta.
- Plasați elementul din variabila temporară în prima poziție.
Pseudocod:
Intrare: vector, dimensiune
Stochează vector[dimensiune – 1] în temp
Pentru i = dimensiune – 2 la 0:
vector[i + 1] = vector[i]
vector[0] = temp
Ieșire: vector permutat
3. Cod în C++
Exemplu 1: Permutare circulară la dreapta cu o singură rotație
#include <iostream>
using namespace std;
void permutareCircularaDreapta(int arr[], int dim) {
int temp = arr[dim – 1]; // Stocăm ultimul element
// Deplasăm elementele spre dreapta
for (int i = dim – 2; i >= 0; i–) {
arr[i + 1] = arr[i];
}
// Plasăm ultimul element în prima poziție
arr[0] = 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);
permutareCircularaDreapta(arr, dim);
cout << „Vector dupa permutare circulara la dreapta: „;
afisareVector(arr, dim);
return 0;
}
Exemplu 2: Permutare circulară la dreapta cu mai multe rotații
#include <iostream>
using namespace std;
void permutareCircularaDreapta(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[dim – 1]; // Stocăm ultimul element
for (int i = dim – 2; i >= 0; i–) {
arr[i + 1] = arr[i];
}
arr[0] = temp; // Plasăm ultimul element în prima poziție
}
}
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 dreapta: „;
cin >> k;
permutareCircularaDreapta(arr, dim, k);
cout << „Vector dupa ” << k << ” permutari circulare la dreapta: „;
afisareVector(arr, dim);
return 0;
}
4. Complexitatea algoritmului
- Complexitate temporală:
- O rotație: O(n), unde n este dimensiunea vectorului.
- k rotații: O(k⋅n).
- Complexitate spațială:
- O(1), deoarece se folosește doar o variabilă temporară.
5. Activități practice pentru elevi
- Scrieți un program care realizează permutarea circulară la stânga a unui vector.
- Implementați o funcție care efectuează permutarea circulară la dreapta fără utilizarea unei variabile temporare.
- Realizați un program care citește un vector de la utilizator și aplică k permutări circulare la dreapta.
6. Scheme logice
- Permutare circulară la dreapta:
- Start -> Stochează ultimul element -> Deplasează restul elementelor spre dreapta -> Plasează ultimul element la început -> Stop.
- Permutare circulară cu mai multe rotații:
- Start -> Redu kkk modulo dimensiune -> Repetă algoritmul de k ori -> Stop.
7. Concluzie:
- Permutarea circulară la dreapta este o operație frecvent utilizată în aplicații ce implică manipularea vectorilor.
- Optimizarea pentru rotații multiple poate reduce semnificativ timpul de execuție.
- Înțelegerea acestui algoritm ajută elevii să rezolve probleme complexe legate de procesarea vectorilor.