Nombre minimum de mouvements requis pour créer un palindrome de chaîne en incrémentant tous les caractères de la sous-chaîne

Dans le domaine de l'informatique et de la programmation, il est très important de découvrir des algorithmes efficaces pour résoudre des problèmes. Un problème intéressant consiste à identifier le nombre minimum d’opérations nécessaires pour convertir une chaîne en palindrome en ajoutant tous les caractères de la sous-chaîne. Cet article explore deux manières d’aborder ce problème à l’aide du langage de programmation C++.

Grammaire

Avant de plonger dans ces méthodes, définissons la syntaxe des fonctions que nous allons utiliser −

int minMovesToMakePalindrome(string str);

Algorithme

• Notre objectif est de minimiser le nombre de mouvements lors de la conversion d'une chaîne en palindrome - ce problème est résolu par notre algorithme à travers les étapes clés suivantes −

• Tout d'abord, créez deux variables de pointeur des deux côtés de la chaîne. Le pointeur gauche commence au début de la chaîne et le pointeur droit commence à la fin de la chaîne.

• Continuez notre processus aussi longtemps que les limites de configuration le permettent, c'est-à-dire une fois que l'un des pointeurs dépasse l'autre, arrêtez −

• Chaque fois que les valeurs des caractères sont les mêmes, continuez à rapprocher les deux pointeurs. Chaque fois que les valeurs des caractères diffèrent, la valeur du caractère à droite est incrémentée (en fonction de leur différence) avant d'effectuer d'autres opérations. Cette augmentation est proportionnelle à la différence entre 'a' et 'c', donc si str[right] est égal à 'c' et str[left] est égal à 'a', nous augmentons str[right] de 2 (car 'a '- 'c'=2). Mettez à jour le nombre de mouvements en conséquence.

• Une fois que le côté gauche est plus grand que le côté droit, la corde deviendra un palindrome.

Méthode 1 : Fissuration par force brute

Dans cette méthode, nous considérerons toutes les sous-chaînes possibles et calculerons le nombre minimum de mouvements requis pour chaque sous-chaîne. Enfin, nous renverrons le minimum de tous les mouvements calculés.

Exemple

#include <iostream>
#include <string>
using namespace std;

int minMovesToMakePalindrome(string str) {
   int moves = 0;
   int length = str.length();

   for (int i = 0; i < length / 2; i++) {
      moves += abs(str[i] - str[length - i - 1]);
   }

   return moves;
}

int main() {
   string str = "abcde";
   int minMoves = minMovesToMakePalindrome(str);
   cout << "Minimum moves to make the string palindrome: " << minMoves << endl;

   return 0;
}

Sortie

Minimum moves to make the string palindrome: 6

Explication

se traduit par :

Explication

Une fonction appelée minMovesToMakePalindrome a été créée pour convertir la chaîne d'entrée str en palindrome avec le nombre minimum de mouvements requis. Nous expliquons comment cela fonctionne avec quelques instructions étape par étape :

Nous initialisons la variable de mouvements à 0, qui est chargée de suivre le nombre total de mouvements requis. - Puisque la variable length enregistre la longueur de la chaîne d'entrée str, notre étape suivante consiste à utiliser une boucle for pour parcourir la moitié de la chaîne afin que les positions symétriques ne se chevauchent pas. - Enfin, à l'intérieur de cette boucle, abs(str[i] - str[length - i - 1]) calcule la différence absolue entre les deux caractères de fin.

La différence calculée représente le nombre de mouvements nécessaires pour rendre les personnages à ces positions égaux. Nous ajoutons cette différence au nombre de mouvements.

Après avoir parcouru toutes les positions nécessaires, nous stockons le nombre total minimum de mouvements requis dans la variable de mouvements. Nous renvoyons cette valeur.

Dans la fonction principale, on initialise une chaîne str avec la valeur "abcde". Ensuite, nous appelons la fonction minMovesToMakePalindrome, en passant str comme paramètre. Le nombre minimum de mouvements renvoyés est stocké dans la variable minMoves. Enfin, nous imprimons les résultats sur la console.

Méthode 2 : La méthode optimale du double pointeur

Cette méthode utilise deux pointeurs pour parcourir les deux extrémités de la chaîne en même temps. Dans un souci d'efficacité, nous avons utilisé une technique pour convertir une chaîne en palindrome qui consiste à ajouter et à faire correspondre progressivement des caractères aux deux extrémités de l'entrée. Cette approche minimise les opérations inutiles et permet des conversions plus rapides sans compromettre la précision ou la fonctionnalité.

Exemple

#include <iostream>
#include <string>
using namespace std;

int minMovesToMakePalindrome(string str) {
   int moves = 0;
   int left = 0;
   int right = str.length() - 1;

   while (left <= right) {
      moves += abs(str[right] - str[left]);
      left++;
      right--;
   }

   return moves;
}

int main() {
   string str = "abcde";
   int minMoves = minMovesToMakePalindrome(str);
   cout << "Minimum moves to make the string palindrome: " << minMoves << endl;

   return 0;
}

Sortie

Minimum moves to make the string palindrome: 6

Explication

se traduit par :

Explication

L'objectif de l'exemple de code ci-dessous est d'utiliser l'approche optimale à deux points pour déterminer le nombre minimum de mouvements requis pour convertir une chaîne donnée en palindrome.

Pour y parvenir, nous avons créé une fonction appelée minMovesToMakePalindrome. Cette fonction accepte un argument de chaîne et renvoie le nombre total de mouvements requis. Tout d’abord, nous définissons la variable utilisée pour compter le nombre de mouvements à 0 et initialisons les pointeurs gauche et droit : le pointeur gauche commence au début de la chaîne d’entrée (index 0) et le pointeur droit commence à la fin (index str. longueur() - 1).

Notre boucle while itère jusqu'à ce que la gauche soit supérieure ou égale à la droite pour couvrir tous les éléments de la chaîne. Dans chaque itération, nous trouvons la différence entre les caractères aux positions gauche et droite en utilisant abs(str[right] - str[left]), qui représente le nombre de mouvements nécessaires pour que ces deux caractères soient identiques. Nous ajoutons cette valeur de différence à notre compteur de courses pour obtenir le nombre total de mouvements.

À mesure que nous nous dirigeons vers le centre de la chaîne d'entrée, incrémentez le pointeur gauche et décrémentez le pointeur droit. Une fois qu’il n’y a plus de chevauchement entre les pointeurs gauche et droit, nous convertissons la chaîne en palindrome.

À ce stade, nous renvoyons notre nombre total de mouvements stockés dans 'moves'. Dans main(), des étapes identiques sont suivies comme précédemment où nous déclarons une nouvelle chaîne d'entrée 'abcde' appelant minMovesToMakePalindrome avec cet argument qui renvoie la valeur totale minimale du nombre de mouvements qui est attribué à la nouvelle variable 'minMoves' avant d'imprimer cette valeur sur la console.

Conclusion

Dans le texte suivant, deux alternatives sont présentées, visant à fournir un aperçu et des réponses potentielles à l'obstacle du calcul du nombre de mouvements requis pour convertir une chaîne donnée en palindrome dans une sous-chaîne via des opérations sur les caractères. Une méthode, appelée méthode par force brute, englobe toutes les sous-chaînes possibles, tandis que l'autre méthode, appelée méthode optimale à deux pointeurs, réduit considérablement le nombre de mouvements requis. Les codeurs peuvent facilement appliquer ces mécanismes pour résoudre des obstacles similaires et améliorer leurs solutions.

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!