exercices corrigés sur les tableaux -TD2-
Étant donné deux tableaux d'entiers de taille N et M . La tâche consiste à trouver le nombre de paires non ordonnées formées d'éléments des deux tableaux de manière à ce que leur somme soit un nombre impair.
3 ; {9, 20}, {14, 7} et {11, 8}
A[] = {2, 4, 6}, B[] = {8, 10, 12}
0
- Comptez le nombre de nombres pairs et impairs dans les deux tableaux
- le nombre de paires est min(impair1, pair2) + min (impair2, pair1), parce que impair + pair est seulement impair.
def compter(A, B):
n = len(A)
m = len(B)
pair1 = impair1 = 0
pair2 = impair2 = 0
# compteur nombre d'impairs et pairs dans A
for i in range(n):
if A[i] % 2 == 0:
pair1 += 1
else:
impair1 += 1
# compteur nombre d'impairs et pairs dans B
for i in range(m):
if A[i] % 2 == 0:
pair2 += 1
else:
impair2 += 1
pairs = min(impair1, pair2) + min(impair2, pair1)
return pairs
T1 = [9, 14, 6, 2, 11]
T2 = [8, 4, 7, 20]
print(compter(T1, T2))
Étant donné un tableau non trié pouvant contenir des doublons. Également donné un nombre k inférieur à la taille du tableau. Ecrivez une fonction qui retourne vrai si le tableau contient des doublons dans un rayon de k.
false, Tous les doublons sont de distance plus que K.
k = 3, tab[] = {1, 2, 3, 1, 4, 5}
true.
Solution naive
Une solution simple consiste à exécuter deux boucles.
La boucle externe sélectionne chaque élément «tab[i]» comme élément de départ,
la boucle interne compare tous les éléments situés à une distance inférieure à k de «tab[i]».
La complexité de cette solution est O(kn).
def solutionSimple(tab, n, k):
for i in range(n):
for j in range(k):
if tab[i] == tab[k]:
return True
return False
Solution Efficace
Nous pouvons résoudre ce problème en O(n) en utilisant le Hashing.
L’idée est d’ajouter des éléments au hash. Nous enlevons également les éléments qui sont à plus de k distance de l’élément courant.
def DoublonsHash(tab, n, k):
# créer un table de hash
liste = []
for i in range(n):
# si il exist déjà dans le hash
if tab[i] in liste:
return True
# ajouter cette element au hash
liste.append(tab[i])
# supprimer l'élément de distance k+1
if (i >= k):
liste.remove(tab[i - k])
return False
Étant donné un tableau d'entiers, la tâche consiste à afficher le tableau dans l'ordre suivant:
le plus petit nombre, le plus grand nombre, le deuxième plus petit nombre, le deuxième plus grand nombre, le troisième plus petit nombre, le troisième plus grand nombre, etc.
[1, 9, 2, 8, 3, 7, 4, 6, 5].
tab[] = {1, 2, 3, 4}
[1, 4, 2, 3]
Solution naive
Une solution simple consiste à rechercher d’abord le plus petit élément et à l’échanger avec le premier.
Recherchez ensuite le plus grand élément, échangez-le avec le deuxième élément,
etc. La complexité de cette solution est O (n2).
def OrdreMinMax(tab, n):
# tour=1 rechercher min
# tour=2 rechercher max
tour = 1
for i in range(n-1):
candidat = i
for j in range(i+1, n):
# rechercher min
if tour == 1 and tab[j] < tab[candidat]:
candidat = j
# rechercher max
if tour == 2 and tab[j] > tab[candidat]:
candidat = j
tab[i], tab[candidat] = tab[candidat], tab[i]
# changer le tour
tour = 1 if tour == 2 else 2
return tab
Solution Efficace
Une solution efficace consiste à utiliser le tri.
- Triez les éléments du tableau.
- Prenez deux variables dites i et j et pointez-les respectivement sur le premier et le dernier index du tableau.
- Lancez une boucle et stockez les éléments du tableau un par un en incrémentant i et décrémentant j.
def OrdreMinMax(tab, n):
# Trier le tableau
tab.sort()
print(tab)
# table temporaire pour stocker les éléments
tempTab = [0] * (n)
print(tempTab)
TabIndex = 0
# i=0 debut
# j=n-1 fin
i = 0
j = n-1
while(i < j):
tempTab[TabIndex] = tab[i]
TabIndex = TabIndex + 1
i = i + 1
tempTab[TabIndex] = tab[j]
TabIndex = TabIndex + 1
j = j - 1
# si la taille du tableau est impaire
# ajouter l'élément du milieu
if len(tab) % 2 != 0:
tempTab[TabIndex] = tab[i]
return tempTab
