Médiane de deux tableaux triés de même taille
Etant donné deux tableaux triés A et B de taille n chacun, le problème est de trouver la médiane du tableau obtenu après la fusion des deux tableaux (c'est-à-dire un tableau de longueur 2n).
Remarque ! La médiane est une valeur présente au centre d'un tableau trié.
Exemple :
Remarque ! Puisque la taille du tableau fusionné est paire (2n), nous devons prendre une moyenne des deux nombres du milieu et retourner la moyenne.
Méthode 1 - Idée de tri par fusion
Utilisez la procédure de fusion du tri par fusion. Gardez une trace du nombre compteur tout en comparant les éléments de deux tableaux. Si compteur devient n (pour 2n éléments), nous avons atteint la médiane. Prenez la moyenne des éléments aux indices n-1 et n dans le tableau fusionné.
Solution :
class Test { // Calculer la médiane static int Mediane(int tab1[], int tab2[], int n) { int i = 0; int j = 0; int compteur; int m1 = -1, m2 = -1; /* * Puisqu'il y a 2n éléments, la médiane sera la moyenne des éléments à l'indice * n-1 et n dans le tableau obtenus après la fusion de tab1 et tab2 */ for (compteur = 0; compteur <= n; compteur++) { if (tab1[i] < tab2[j]) { // Stocker m2 dans m1 (déclage) m1 = m2; m2 = tab1[i]; i++; } else { // Stocker m2 dans m1 (déclage) m1 = m2; m2 = tab2[j]; j++; } } return (m1 + m2) / 2; } /* Fonction principale */ public static void main(String[] args) { int A[] = { 3, 5, 7, 8, 11, 12 }; int B[] = { 2, 4, 6, 9, 17, 22 }; System.out.println("La médiane est " + Mediane(A, B, 6)); } }
#include <stdio.h> int Mediane(int tab1[], int tab2[], int n) { int i = 0; // indice actuel de tab1 int j = 0; // indice actuel de tab2 int compteur; int m1 = -1, m2 = -1; // m1=element 1, m2=element 2 ; mediane = (m1+m2)/2 /* Puisqu'il y a 2n éléments, la médiane sera la moyenne des éléments à l'indice n-1 et n dans le tableau obtenus après la fusion de tab1 et tab2 */ for (compteur = 0; compteur <= n; compteur++) { if (tab1[i] < tab2[j]) { m1 = m2; // Stocker m2 dans m1 m2 = tab1[i]; i++; } else { m1 = m2; // Store the prev median m2 = tab2[j]; j++; } } return (m1 + m2) / 2; } /* Fonction principale */ int main() { int A[] = {3, 5, 7, 8, 11, 12}; int B[] = {2, 4, 6, 9, 17, 22}; printf("La médiane est %d", Mediane(A, B, 6)); getchar(); return 0; }
def Mediane(tab1, tab2, n): i = 0 # indice actuel de tab1 j = 0 # indice actuel de tab2 m1 = -1 m2 = -1 # Puisqu'il y a 2n éléments, # la médiane sera la moyenne des éléments # à l'indice n-1 et n dans le tableau obtenus après la fusion de tab1 et tab2 compteur = 0 while compteur < n + 1: compteur += 1 if tab1[i] < tab2[j]: m1 = m2 # Stocker m2 dans m1 (déclage) m2 = tab1[i] i += 1 else: m1 = m2 # Stocker m2 dans m1 (déclage) m2 = tab2[j] j += 1 return (m1 + m2)//2 # Tester la fonction A = [3, 5, 7, 8, 11, 12] B = [2, 4, 6, 9, 17, 22] print("La médiane est ", Mediane(A, B, 6))
La complexité de la méthode 1 est \(O(n)\)
Méthode 2 - Diviser pour régner
C’est une meilleure solution et est basée sur le paradigme Diviser pour régner. L’idée est de comparer la médiane des deux tableaux, et de résoudre récursivement le problème jusqu'à obtenir un tableau de deux éléments
Procedure :
- Calculez les médianes m1 et m2 des tableaux d'entrée A [] et B [] respectivement.
- Si les valeurs m1 et m2 sont toutes les deux égales, alors nous avons terminé. retourner m1 (ou m2)
- Si m1 est supérieur à m2, alors la médiane est présente dans l'un des deux sous-réseaux ci-dessous.
- Du premier élément de A à m1 (A [0...n//2])
- Du m2 au dernier élément de B (B[n // 2 ... n-1])
- Si m2 est supérieur à m1, alors la médiane est présente dans l'un des deux sous-réseaux ci-dessous.
- De m1 au dernier élément de A (A[n / 2 ... n-1])
- Du premier élément de B au m2 (B[0 ... n / 2])
- Répétez le processus ci-dessus jusqu'à ce que la taille des deux sous-tableaux devienne 2.
- Si la taille des deux tableaux est de 2, utilisez la formule ci-dessous pour obtenir la médiane. $$Médiane = (max(A[0], B[0]) + min(A[1], B[1]))/2$$
Exemple :
class Test { static int getMediane(int[] A, int[] B, int debutA, int debutB, int finA, int finB) { if (finA - debutA == 1) { return (Math.max(A[debutA], B[debutB]) + Math.min(A[finA], B[finB])) / 2; } int m1 = mediane(A, debutA, finA); int m2 = mediane(B, debutB, finB); if (m1 == m2) { return m1; } // Si m1 < m2 else if (m1 < m2) { return getMediane(A, B, (finA + debutA + 1) / 2, debutB, finA, (finB + debutB + 1) / 2); } // SI m1 > m2 else { return getMediane(A, B, debutA, (finB + debutB + 1) / 2, (finA + debutA + 1) / 2, finB); } } /* * Médiane d'un tableau trié */ static int mediane(int[] tab, int debut, int fin) { int n = fin - debut + 1; if (n % 2 == 0) { return (tab[debut + (n / 2)] + tab[debut + (n / 2 - 1)]) / 2; } else { return tab[debut + n / 2]; } } // Fonction principale public static void main(String[] args) { int A[] = { 3, 5, 7, 8, 11, 12 }; int B[] = { 2, 4, 6, 9, 17, 22 }; System.out.println("La médiane est " + getMediane(A, B, 0, 0, 5, 5)); } }
#include <stdio.h> int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } /* Médiane d'un tableau */ int mediane(int tab[], int n) { if (n % 2 == 0) return (tab[n / 2] + tab[n / 2 - 1]) / 2; else return tab[n / 2]; } /* Fonction qui calcule la médiane de deux tableaux A, B */ int getMediane(int A[], int B[], int n) { /* taille 0 */ if (n <= 0) return -1; if (n == 1) return (A[0] + B[0]) / 2; if (n == 2) return (max(A[0], B[0]) + min(A[1], B[1])) / 2; int m1 = mediane(A, n); /* Médiane de A */ int m2 = mediane(B, n); /* Médiane de B */ if (m1 == m2) return m1; if (m1 < m2) { if (n % 2 == 0) return getMediane(A + n / 2 - 1, B, n - n / 2 + 1); return getMediane(A + n / 2, B, n - n / 2); } if (n % 2 == 0) return getMediane(B + n / 2 - 1, A, n - n / 2 + 1); return getMediane(B + n / 2, A, n - n / 2); } /* Fonction principale */ int main() { int A[] = {3, 5, 7, 8, 11, 12}; int B[] = {2, 4, 6, 9, 17, 22}; printf("La médiane est %d", getMediane(A, B, 6)); getchar(); return 0; }
def getMediane(A, B, n): # il n'y a aucun élément dans les deux tableaux if n == 0: return -1 # Il n'existe qu'un seul élément dans chaque tableau elif n == 1: # Médiane est la somme des deux éléments divisée par 2 return (A[0]+B[0])/2 # Il existe deux éléments dans chaque tableau elif n == 2: # médiane = (max(A[0],B[0])+min(A[1],B[1]))/2 return (max(A[0], B[0]) + min(A[1], B[1])) // 2 else: # Calculer la médiane des deux tableaux m1 = mediane(A, n) m2 = mediane(B, n) if m1 > m2: if n % 2 == 0: # taille pair # Appelez récursivement le getMediane avec les nouveaux sous-tableaux return getMediane(A[:n // 2 + 1], B[n // 2 - 1:], n // 2 + 1) else: # Appelez récursivement le getMediane avec les nouveaux sous-tableaux return getMediane(A[:n // 2 + 1], B[n // 2:], n // 2 + 1) else: if n % 2 == 0: # Appelez récursivement le getMediane avec les nouveaux sous-tableaux return getMediane(A[n//2 - 1:], B[:n//2 + 1], n // 2 + 1) else: # Appelez récursivement le getMediane avec les nouveaux sous-tableaux return getMediane(A[n / 2:], B[0:n // 2 + 1], n // 2 + 1) # Calculer la médiane d'un tableau def mediane(tab, n): if n % 2 == 0: return (tab[n // 2] + tab[n // 2 - 1]) / 2 else: return tab[n//2] # Tester la fonction A = [3, 5, 7, 8, 11, 12] B = [2, 4, 6, 10, 17, 22] print("La médiane est ", getMediane(A, B, 6))
La complexité de la méthode 2 est \(O(logn)\)
Exercices java
Exercices langage c
Exercices python
récursivité
Tableaux
Complexité
analyse des algorithmes
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa