Programme JavaScript pour l'algorithme d'échange de blocs pour la rotation des tableaux

La rotation des éléments d'un tableau signifie déplacer les éléments d'un tableau donné vers la gauche ou la droite d'un nombre spécifique de positions. Nous supposons que le tableau se présente sous la forme d’une boucle et faisons pivoter les éléments de bord vers l’autre extrémité. L'algorithme d'échange de blocs pour la rotation du tableau consiste à faire pivoter les éléments du tableau d'une quantité donnée, mais au lieu d'utiliser des rotations en utilisant la technique d'échange. Nous mettrons en œuvre des méthodes récursives et itératives.

Entrez

The given array is [ 1, 2, 3, 4, 5, 6, 7].
The number of rotations by which we have to rotate is 3. 

Sortie

[4, 5, 6, 7, 1, 2, 3]

Instructions

Nous pouvons utiliser l'algorithme d'échange et obtenir le résultat, nous le mettrons en œuvre dans la section suivante.

Méthode récursive

Dans cette méthode, nous essaierons de supposer que nous avons deux tableaux, le premier a la taille du nombre de rotations donné et l'autre a la taille de la taille totale moins le nombre d'éléments donné.

Si la taille du premier tableau est petite alors nous échangerons les éléments du premier tableau et le dernier élément est égal à la taille du premier tableau, si la taille du premier tableau est plus grande que nous échangerons les éléments de le premier tableau est égal à la taille du deuxième tableau du tableau donné.

Pour les éléments restants, nous appellerons la fonction récursive en changeant le tableau d'échange.

Exemple

function swap(arr, st, si, k){    
   // function to traverse over the array and swap the elements 
   for(var i = 0; i < k; i++) {
      var temp = arr[st + i];
      arr[st + i] = arr[si + i];
      arr[si + i] = temp;
   }
   return arr;
}
function rotate(arr, k, n){

   // if the number of rotations is zero or equal to the size of array
   // in this case we don't have to rotate the array 
   if(k == 0 || k == n){
      return;
   }
   
   // special case when the number of elements to rotate 
   // is half of the size of the given array
   if(n == 2*k){
      arr = swap(arr, 0, n - k, k);
      return;
   }		
   
   // if the first part is short	
   if(2*k < n) {
      arr = swap(arr, 0, n - k, k);
      rotate(arr, k, n - k);	
   }
   else{	
   
      // if second part is short
      arr = swap(arr, 0, k, n - k);
      rotate(arr + n - k, 2 * k - n, k);
   }
}

// function to print the given array 
function print(arr){
   var temp = "";
   for(var i = 0; i < arr.length; i++){
      temp += arr[i] + " ";
   }
   console.log(temp);
}

//Defining the array 
var arr = [1, 2, 3, 4, 5, 6, 7];
var num = 3;
console.log("The given array is: ");
print(arr);

// rotating the array 
rotate(arr, num, arr.length);
console.log("The given array after " + num + " number of rotations is: ")
print(arr);

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est N, où N est la taille du tableau donné.

Le code ci-dessus a une complexité spatiale de N, mais c'est seulement si l'on considère la mémoire occupée par la pile récursive.

Méthode itérative

La méthode itérative est la même que la méthode récursive, la seule différence est que nous travaillons dans une boucle while au lieu d'utiliser des appels récursifs. Regardons le code.

Exemple

function swap(arr, st, si, k){    
   // function to traverse over the array and swap the elements 
   for(var i = 0; i < k; i++) {
      var temp = arr[st + i];
      arr[st + i] = arr[si + i];
      arr[si + i] = temp;
   }
   return arr;
}
function rotate(arr, k, n){

   // if the number of rotations is zero or equal to the size of array
   // in this case we don't have to rotate the array 
   if(k == 0 || k == n){
      return;
   }
   var i = k;
   var j = n - k;
   while (i != j){
      if(i < j){
      
         // if the first array is shorter 
         arr = swap(arr, k - i, k + j - i, i);
         j -= i;
      }
      else{ 
      
         // if the second array is shorter 
         arr = swap(arr, k - i, k, j);
         i -= j;
      }
   }
   arr = swap(arr, k - i, k, i);
}

// function to print the given array 
function print(arr){
   var temp = "";
   for(var i = 0; i < arr.length; i++){
      temp += arr[i] + " ";
   }
   console.log(temp);
}

// defining the array 
var arr = [1, 2, 3, 4, 5, 6, 7];
var num = 3;
console.log("The given array is: ");
print(arr);

// rotating the array 
rotate(arr, num, arr.length);
console.log("The given array after " + num + " number of rotations is: ")
print(arr);

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est N, où N est la taille du tableau donné.

La complexité spatiale du code ci-dessus est de 1 ou constante car nous n'utilisons aucun espace supplémentaire ici.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript pour faire pivoter un tableau d'un nombre de rotations donné en utilisant l'algorithme d'échange de blocs. Nous avons implémenté l'algorithme d'échange de blocs en utilisant une approche itérative avec une complexité temporelle O(N) et une complexité spatiale O(1), tout en utilisant une approche récursive avec une complexité spatiale O(N).

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!