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
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).
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
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)
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.
- 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.
- 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).
- 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.
- Pour trouver la longueur maximale du sous-tableau à partir d'index 0, parcourir sommeleft[] et recherchez le maximum i où sommeleft[i] = 0.
- 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 - 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.
- 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".
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
ESSADDOUKI
Mostafa