Initiation à l'algorithmique

exercices corrigés sur les tableaux -TD2-

Exercice 1 : 

É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.

Exemple :
A[] = {9, 14, 6, 2, 11}, B[] = {8, 4, 7, 20}
  3 ; {9, 20}, {14, 7} et {11, 8}

A[] = {2, 4, 6}, B[] = {8, 10, 12}
  0
  1. Comptez le nombre de nombres pairs et impairs dans les deux tableaux
  2. 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))
                
            
Exercice 2 : 

É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.

Exemple :
k = 3, tab[] = {1, 2, 3, 4, 1, 2, 3, 4}
  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
            
Exercice 3 : 

É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.

Exemple :
tab[] = {5, 8, 1, 4, 2, 9, 3, 7, 6}
  [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.

  1. Triez les éléments du tableau.
  2. Prenez deux variables dites i et j et pointez-les respectivement sur le premier et le dernier index du tableau.
  3. Lancez une boucle et stockez les éléments du tableau un par un en incrémentant i et décrémentant j.
complexité de cette solution est O(nLogn) (complexité de l'algorithme de tri)
                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
            

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

Cours Similaires :