Algorithme d'inversion pour la rotation des tableaux écrit en C++

Dans le problème donné, nous avons un tableau et nous devons faire pivoter le tableau de d éléments en utilisant un algorithme d'inversion comme −

Input : arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2
Output : arr[] = [3, 4, 5, 6, 7, 1, 2]
Explanation : As you can see we have to rotate this array by d = 2 but our main task is to achieve this by using a reversal technique.

Nous avons fait quelques calculs sur la rotation du tableau avec la technique d'inversion et Conclusion :

• Tout d’abord, nous inversons les d premiers éléments du tableau.
• Deuxièmement, nous inversons les éléments restants.
• Troisièmement, nous inversons tout le tableau.

En appliquant ces trois étapes, nous pouvons obtenir le tableau pivoté.

Méthode de solution

Dans ce problème, nous allons d'abord écrire une fonction qui inverse les éléments ;

Exemple

#include <bits/stdc++.h>
using namespace std;

void reverseArray(int arr[], int start, int end) { // our reversal algorithm
   while (start < end) { // if start becomes equal to end we break the loop
      int temp = arr[start];
      arr[start] = arr[end];
      arr[end] = temp;
      start++;
      end--;
   }
   return ;
}
void Rotate(int arr[], int d, int n) { // rotation function
   if (d == 0) // no rotation required
      return;
   d = d % n; // when d becomes equal to n so our array comes to its original form
   reverseArray(arr, 0, d - 1); // reversing first d elements
   reverseArray(arr, d, n - 1); // reversing the remaining elements
   reverseArray(arr, 0, n - 1); // reversing the whole array

   return ;
}
int main() {
   int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // given array
   int n = sizeof(arr) / sizeof(arr[0]); // size of our array
   int d = 2;
   Rotate(arr, d, n);
   for(int i = 0; i < n; i++) // printing the array
      cout << arr[i] << " ";
   cout << "\n";
   return 0;
}

Output

3 4 5 6 7 1 2

Explication du code ci-dessus

Dans la méthode ci-dessus, nous créons d'abord une technique d'inversion qui acceptera trois paramètres, à savoir le tableau, l'index de début et l'index de fin, et nous convertira. Le tableau est inversé par rapport au de la position de départ à la position finale. Puisque nous avons déjà développé l'algorithme, nous utiliserons cette fonction pour appliquer l'algorithme. Tout d’abord, nous inversons les d premiers éléments. Ensuite, nous inversons les éléments restants et enfin, nous inversons l’ensemble du tableau. En conséquence, notre tableau subit une rotation de d positions. Dans la fonction de rotation, nous définissons d sur d % n. En effet, si nous faisons pivoter les n premiers éléments du tableau, nous obtiendrons la même réponse que précédemment, nous prenons donc d modulo n.

Conclusion

Dans cet article, nous avons résolu un problème d'application de l'algorithme d'inversion pour la rotation des tableaux. Nous avons également appris un programme C++ et la manière complète (normale) de résoudre ce problème. Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et d'autres langages. J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!