Initiation à l'algorithmique

Notification de cookies

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

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 M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :