Introduction
Dans ce laboratoire, nous allons créer un programme C++ pour trouver l'élément minimum dans un vecteur trié et roté. Un vecteur trié peut être roté autour d'un élément pivot inconnu pour vous à l'avance.
💡 Ce tutoriel est traduit par l'IA à partir de la version anglaise. Pour voir la version originale, vous pouvez cliquer ici
Dans ce laboratoire, nous allons créer un programme C++ pour trouver l'élément minimum dans un vecteur trié et roté. Un vecteur trié peut être roté autour d'un élément pivot inconnu pour vous à l'avance.
Tout d'abord, nous devons inclure les bibliothèques nécessaires et déclarer l'espace de noms. Ce code sera écrit dans le fichier ~/project/main.cpp
. Le code complet pour l'Étape 1 est donné ci-dessous :
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
Nous allons créer une fonction nommée findMin
pour trouver l'élément minimum dans le vecteur trié et roté. Dans cette fonction, nous allons parcourir chaque élément du vecteur et vérifier si cet élément est l'élément minimum. La logique pour vérifier si l'élément est minimum est expliquée dans les commentaires du bloc de code. Le code complet pour l'Étape 2 est donné ci-dessous :
int findMin(vector<int> &m)
{
int i;
int n = m.size();
for (i = 0; i < n; i++)
{
if (i == 0)
{
// vérifier le premier élément
if (m[i] < m[n - 1] && m[i] < m[1])
break;
}
else
{
// vérifier tous les autres éléments
if (m[i] < m[i - 1] && m[i] < m[(i + 1) % n])
break;
}
}
return m[i % n];
}
Dans la fonction principale, nous allons créer un vecteur nommé v
et l'initialiser avec certains éléments. Ensuite, nous appellerons la fonction findMin
pour trouver l'élément minimum dans le vecteur. Enfin, nous afficherons l'élément minimum. Le code complet pour l'Étape 3 est donné ci-dessous :
int main()
{
vector<int> v = {4, 5, 6, 7, 1, 3, 2};
int n = v.size();
int minimum = 0;
cout << "Les éléments du vecteur donné sont : ";
for (int i = 0; i < n; i++)
{
cout << v[i] << " ";
}
minimum = findMin(v);
cout << "\n\nL'élément minimum dans le vecteur donné est : " << minimum << endl;
return 0;
}
Dans une fenêtre de terminal, utilisez la commande cd
pour naviguer jusqu'au répertoire où se trouve le fichier main.cpp
. Ensuite, compilez le code à l'aide de la commande suivante :
g++ main.cpp -o main
Si aucun message d'erreur n'est affiché, exécutez l'exécutable à l'aide de la commande suivante :
./main
Vous devriez voir la sortie suivante :
Les éléments du vecteur donné sont : 4 5 6 7 1 3 2
L'élément minimum dans le vecteur donné est : 1
Cette sortie confirme que notre code a trouvé l'élément minimum correct dans le vecteur.
Dans ce laboratoire, nous avons créé un programme C++ pour trouver l'élément minimum dans un vecteur trié et roté. Nous avons atteint cela en parcourant chaque élément du vecteur et en vérifiant si cet élément est l'élément minimum. Enfin, nous avons affiché l'élément minimum à la console. Nous espérons que vous avez trouvé ce laboratoire utile dans votre parcours d'apprentissage de la programmation.