Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité

Défi de conversion de mots - Programmation compétitive

 

Défi de conversion de mots - Programmation compétitive

Un enseignant de français dans une école primaire veut motiver ses élèves à apprendre l'alphabet et à comparer des mots en créant des activités amusantes.

Dans l'une des activités, l'enseignant choisit au hasard deux élèves, puis chaque élève écrit un mot au tableau, et l'enseignant demande aux autres élèves combien d'opérations ont été nécessaires pour convertir le premier mot (mot1) en deuxième (mot2).

Le premier élève qui a réussi de convertir le premier mot en second en un nombre minimum d'opérations reçoit une barre de chocolat.

Les opérations autorisées pour convertir les mots sont les suivantes

  •  Insérer : ajouter un caractère au mot
  •  Supprimer : supprimer un caractère
  •  Remplacer : remplacer un caractère
Entrée

Une ligne contient les deux mots séparés par un espace; mot1 et mot2

Sortie

Le nombre minimum d'opérations requises pour convertir mot1 en mot2.

  Exemples
Entrée du programmeSortie du programme
bonsoir bonjour2
meknes meknes0
hllo hello1

Solution naive (récursive)

L'idée est de traiter tous les caractères un par un en partant du côté gauche ou droit des deux mots.

la longueur des mots mot1 et mot2 sont respectivement m et n

il y a deux possibilités pour chaque paire de caractères en cours de traitement.

  •  Si les derniers caractères de deux mots sont identiques, rien à faire. Ignorer les derniers caractères et obtenir le nombre d'opérations pour les caractères restants. On récure donc pour les longueurs m-1 et n-1.
  •  Sinon (si les derniers caractères ne sont pas les mêmes), nous considérons toutes les opérations sur 'mot1', considérons les trois opérations sur le dernier caractère du premier mot, calculons récursivement le nombre minimum d'opérations pour les trois opérations et prenons le minimum de trois.
    •  Insérer : Nous récurons pour m et n-1
    •  Supprimer : Nous récurons pour m-1 et n
    •  Remplacer : Nous récurons pour m-1 et n-1
#include <iostream>
#include <string>

using namespace std;

int minOperations(string &mot1, string &mot2, int m, int n){
    /* 
        Si le premier mot est vide, la seule option est 
        d'insérer tous les caractères du deuxième mot dans le premier 
    */
    if (m == 0)
        return n;
 
    /* 
        Si le deuxième mot est vide, la seule option 
        est de supprimer tous les caractères du premier mot
    */
    if (n == 0)
        return m;
 
    // Option 1
    // Les derniers caractères de deux mots sont identiques
    if (mot1[m-1] == mot2[n-1])
        return minOperations(mot1, mot2, m-1, n-1);
 
    // option2
    return 1 + min(minOperations(mot1, mot2, m, n-1),min(    // Insérer
                   minOperations(mot1, mot2, m-1, n),    // Supprimer
                   minOperations(mot1, mot2, m-1, n-1))    // Remplacer
                   );
}

int main()
{
    string mot1, mot2;
    cin >> mot1 >> mot2;

    cout << minOperations(mot1,mot2,mot1.size(),mot2.size());
    
    return 0;
}
                    
import sys

def minOperations(mot1, mot2, m, n):
 
    # Si le premier mot est vide, la seule option est 
    # d'insérer tous les caractères du deuxième mot dans le premier
    if m == 0:
        return n
 
    # Si le deuxième mot est vide, la seule option 
    # est de supprimer tous les caractères du premier mot
    if n == 0:
        return m
 
    # Option 1
    # Les derniers caractères de deux mots sont identiques
    if mot1[m-1] == mot2[n-1]:
        return minOperations(mot1, mot2, m-1, n-1)
 
    # option2
    return 1 + min(minOperations(mot1, mot2, m, n-1),    # Insérer
                   minOperations(mot1, mot2, m-1, n),    # Supprimer
                   minOperations(mot1, mot2, m-1, n-1)    # Remplacer
                   )


mot1, mot2=map(str, sys.stdin.readline().strip().split())

print(minOperations(mot1,mot2,len(mot1),len(mot2)))
                    
Complexité :

La complexité temporelle de la solution ci-dessus est exponentielle. Dans le pire des cas, nous pouvons finir par faire \(O(3^m)\) opérations. Le pire des cas se produit lorsqu'aucun des caractères de deux mots ne correspond.

Solution optimale (Programmation dynamique)

#include <iostream>
#include <string>

using namespace std;

// approche bottom-up
int minOperations(string &mot1, string &mot2, int m, int n){

    // Tableau qui stocke les résultats des sous-problèmes
    int dp[m+1][n+1];
 

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
 
            // Si le premier mot est vide, la seule option est 
            // d'insérer tous les caractères du deuxième mot dans le premier
            if (i == 0)
                dp[i][j] = j;    // Min. operations = j
 
            // Si le deuxième mot est vide, la seule option 
            // est de supprimer tous les caractères du premier mot
            else if (j == 0)
                dp[i][j] = i;    // Min. operations = i
 
            // Option 1
            // Les derniers caractères de deux mots sont identiques
            else if (mot1[i-1] == mot2[j-1])
                dp[i][j] = dp[i-1][j-1];
 
            // Option 2
            else
                dp[i][j] = 1 + min(dp[i][j-1],        // Insérer
                                   min(dp[i-1][j],        // Supprimer
                                   dp[i-1][j-1]));    // Remplacer
        }
    }
 
    return dp[m][n];
}

int main()
{
    string mot1, mot2;
    cin >> mot1 >> mot2;

    cout << minOperations(mot1,mot2,mot1.size(),mot2.size());
    
    return 0;
}
                    
import sys

# approche bottom-up
def minOperations(str1, str2, m, n):

    # Tableau qui stocke les résultats des sous-problèmes
    dp = [[0 for x in range(n + 1)] for x in range(m + 1)]
 

    for i in range(m + 1):
        for j in range(n + 1):
 
            # # Si le premier mot est vide, la seule option est 
            # d'insérer tous les caractères du deuxième mot dans le premier
            if i == 0:
                dp[i][j] = j    # Min. operations = j
 
            # Si le deuxième mot est vide, la seule option 
            # est de supprimer tous les caractères du premier mot
            elif j == 0:
                dp[i][j] = i    # Min. operations = i
 
            # Option 1
            # Les derniers caractères de deux mots sont identiques
            elif str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
 
            # Option 2
            else:
                dp[i][j] = 1 + min(dp[i][j-1],        # Insérer
                                   dp[i-1][j],        # Supprimer
                                   dp[i-1][j-1])    # Remplacer
 
    return dp[m][n]


mot1, mot2=map(str, sys.stdin.readline().strip().split())
print(minOperations(mot1,mot2,len(mot1),len(mot2)))
                    
Complexité :
  •  Complexité temporelle : O(m*n)
  •  Complexité spatiale : O(m*n)

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.