Élément minimum dans un vecteur trié et roté

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.

Skills Graph

Inclure les bibliothèques nécessaires et déclarer l'espace de noms

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;

Créer une fonction pour trouver l'élément minimum

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];
}

Écrire la fonction principale pour tester le code

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;
}

Compiler et exécuter le code

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.

Sommaire

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.