|

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

  1. Stocați ultimul element al vectorului într-o variabilă temporară.
  2. Deplasați toate elementele din vector cu o poziție spre dreapta.
  3. 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

  1. Complexitate temporală:
    • O rotație: O(n), unde n este dimensiunea vectorului.
    • k 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 stânga a unui vector.
  2. Implementați o funcție care efectuează permutarea circulară la dreapta 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 dreapta.

6. Scheme logice

  1. Permutare circulară la dreapta:
    • Start -> Stochează ultimul element -> Deplasează restul elementelor spre dreapta -> Plasează ultimul element la început -> Stop.
  2. 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.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *