Initiation à l'algorithmique

exercices corrigés sur les tableaux -TD3-

Exercice 1 : 

Étant donné un tableau tab[] et deux entiers X et Y. La tâche consiste à trouver un sous-tableau de taille supérieure ou égale à X et d'au plus Y, qui contient la moyenne maximale (moyenne des éléments du sous-tableau).

Exemple :
tab[] = {1, 2, 3, 4, 5} X = 2, Y = 3
  4.5

tab[] = {6, 7, 8, 3, 2, 4, 2} X = 2, Y = 4
 7.5
Parcourez tous les sous-tableaux de taille allant de X à Y et trouvez la moyenne maximale parmi tous ces sous-tableaux.
Nous pouvons utiliser deux boucles pour imbriquées pour effectuer une itération sur tous les sous-tableaux dont la taille varie de X à Y.
Pour réduire la complexité, nous pouvons utiliser le tableau de préfixes somme pour obtenir la somme de tous les sous-tableaux de complexité O (1).
                def MoyenneSousTab(tab, n, x, y):

                    # calculer la somme cumulative
                    cumule = [0] * n
                    cumule[0] = tab[0]
                    for i in range(1, n):
                        cumule[i] = cumule[i - 1] + tab[i]
                
                    maximum = 0
                
                    # parcourir les sous tableaux
                    for i in range(n):
                        j = i + x - 1
                
                        # sous tableau de taille [X à Y]
                        while(j < i + y and j < n):
                
                            # récupérer la somme du sous tableau
                            somme = cumule[j]
                
                            if (i > 0):
                                somme -= cumule[i - 1]
                
                            # calculer la moyenne
                            moyenneCourante = somme / (j - i + 1)
                
                            # stocker le maximum
                            maximum = max(maximum, moyenneCourante)
                
                            j += 1
                    return maximum
                
                
                T = [1, 2, 3, 4, 5]
                X = 2
                Y = 3
                
                print(MoyenneSousTab(T, len(T), X, Y))
            
Exercice 2 : 

Étant donné un tableau contenant uniquement des 0 et des 1, recherchez le plus grand sous-tableau contenant le même nombre de 0 et de 1. La complexité attendue est O(n).

Exemple :
tab[] = {1, 0, 1, 1, 1, 0, 0}
  1 à 6

tab[] = {0, 0, 1, 1, 0}
 0 à 3 ou 1 to 4

Méthode 1 

Une méthode simple consiste à utiliser deux boucles imbriquées.
La boucle extérieure choisit un point de départ i.
La boucle interne considère tous les sous-tableaux à partir de i.
Si la taille d'un sous-tableau est supérieure à la taille maximale jusqu'à présent, mettez à jour la taille maximale.
Si somme devient 0, alors la taille de ce sous-tableau est comparée à la plus grande taille jusqu'à présent.
Complexité O(n2)
def SameZeroOne(tab, n):

    somme = 0
    fin = -1
    for i in range(0, n-1):
        somme = -1 if (tab[i] == 0) else 1

        # parcourir les sous tableaux
        for j in range(i + 1, n):

            somme = somme + (-1) if (tab[j] == 0) else somme + 1

            # Si somme devient 0, alors la taille de ce sous-tableau est comparée
            # à la plus grande taille jusqu'à présent.
            if (somme == 0 and fin < j-i + 1):
                fin = j - i + 1
                debut = i

    if (fin == -1):
        print("tableau n'exist pas")
    else:
        print(debut, " à ", debut + fin-1)

    return fin


T = [0, 0, 1, 1, 0]
SameZeroOne(T, len(T))

            

Méthode 2 

Soit un tableau en entrée de taille n et max_taille est la taille de sous-tableau en sortie.

  1. Considérons toutes les valeurs 0 comme -1. Le problème se réduit maintenant pour trouver la longueur maximale du sous-tableau avec somme = 0.
  2. Créez un tableau temporaire sommeleft[] de taille n. Stocke la somme de tous les éléments de tab [0] à tab [i] dans sommeleft [i]. Cela peut être fait en un temps O (n).
  3. Il existe deux cas, le sous-tableau de sortie peut commencer à partir d'index 0 ou peut-être à partir d'un autre index. Nous renverrons le maximum des valeurs obtenues par ces deux cas.
  4. Pour trouver la longueur maximale du sous-tableau à partir d'index 0, parcourir sommeleft[] et recherchez le maximum i où sommeleft[i] = 0.
  5. Maintenant, nous devons trouver le sous-tableau où somme est 0 et index début n'est pas 0.
    Ce problème revient à trouver deux indices i & j dans sommeleft[] tels que sommeleft[i] = sommeleft[j] et j-i est maximum.
    Pour résoudre ce problème, nous pouvons créer une table de hachage de taille=max-min + 1 où min est la valeur minimale dans le sommeleft[] et max est la valeur maximale dans sommeleft[].
    L'idée est de hacher les occurrences les plus à gauche de toutes les valeurs différentes dans sommeleft[]. La taille de hash est choisie comme max-min + 1 car il peut y avoir autant de valeurs possibles dans sommeleft[]. Initialise toutes les valeurs dans hash avec -1
  6. Pour remplir et utiliser le hash[], traversez sommeleft[] de 0 à n-1. Si une valeur n'est pas présente dans hash[], stockez son index dans hash. Si la valeur est présente, calculez la différence entre l'index actuel de sommeleft[] et la valeur précédemment stockée dans hash[]. Si cette différence est supérieure à max_taille, mettez à jour max_taille.
  7. Pour gérer les cas de coin (tous les 1 et tous les 0), nous initialisons max_taille à -1. Si la taille maximale reste égale à -1, affichez alors "ce sous-tableau n'existe pas".
complexité O(n)
                def SameZeroOne(tab, n):

                    # créer un tableau de hashage
                    #  ce tableau de hashage est implémenté à l'aide du dictionnaire en python
                    hash = {}
                
                    max_taille = 0
                
                    sommeLeft = []
                    max = min = tab[0]
                    sommeLeft.append((-1 if tab[0] == 0 else 1))
                
                    for i in range(1, n):
                        val = sommeLeft[i-1] + (-1 if tab[i] == 0 else 1)
                        sommeLeft.append(val)
                        if sommeLeft[i] < min:
                            min = sommeLeft[i]
                
                        if sommeLeft[i] > max:
                            max = sommeLeft[i]
                
                    # Initialiser le tableau de hashage avec -1
                    for i in range((max-min+1)):
                        hash[i] = -1
                
                    for i in range(n):
                        if sommeLeft[i] == 0:
                            max_taille = i+1
                            debut = 0
                
                        if hash[sommeLeft[i]-min] == -1:
                            hash[sommeLeft[i]-min] = i
                        else:
                            if (i-hash[sommeLeft[i]-min]) > max_taille:
                                max_taille = i-hash[sommeLeft[i]-min]
                                debut = hash[sommeLeft[i]-min]+1
                
                    if max_taille == -1:
                        print("sous tableau n'existe pas ")
                    else:
                        print(debut, " à ", debut+max_taille-1)
                
                    return max_taille
                
                
                T = [0, 0, 1, 1, 0]
                SameZeroOne(T, len(T))
                
            

Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Professeur d'Informatique dans les CPGE

Cours Similaires :