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
