Exercice 1 - Partie C · Bac Numérique et Sciences Informatiques Asie 2024 (jour 2)

EXERCICE 1 (6 points)

Cet exercice porte sur la programmation Python (listes, dictionnaires) et la méthode “diviser pour régner”.

Cet exercice est composé de trois parties indépendantes.

Dans cet exercice, on s'intéresse à des algorithmes pour déterminer, s'il existe, l'élément absolument majoritaire d'une liste.

On dit qu'un élément est absolument majoritaire s'il apparaît dans strictement plus de la moitié des emplacements de la liste.

Par exemple, la liste [1, 4, 1, 6, 1, 7, 2, 1, 1] admet 1 comme élément absolument majoritaire, car il apparaît 5 fois sur 9 éléments. Par ailleurs, la liste [1, 4, 6, 1, 7, 2, 1, 1] n'admet pas d'élément absolument majoritaire, car celui qui est le plus fréquent est 1, mais il n'apparaît que 4 fois sur 8, ce qui ne fait pas plus que la moitié.

Partie C: par la méthode « diviser pour régner »

Un dernier algorithme consiste à partager la liste en deux listes. Ensuite, il s'agit de déterminer les éventuels éléments absolument majoritaires de chacune des deux listes. Il suffit ensuite de combiner les résultats sur les deux listes afin d'obtenir, s'il existe, l'élément majoritaire de la liste initiale.

Les questions suivantes vont permettre de concevoir précisément l'algorithme.

On considère lst une liste de taille $n$.

8.

Déterminer l'élément absolument majoritaire de lst si $n = 1$. C'est le cas de base.

On suppose que l'on a partagé lst en deux listes:

lst1 = lst[:n//2] ( lst1 contient les $n//2$ premiers éléments de lst)

lst2 = lst[n//2:] ( lst2 contient les autres éléments de lst)

9.

Si, ni lst1 ni lst2 n'admet d'élément absolument majoritaire, expliquer pourquoi lst n'admet pas d'élément absolument majoritaire.

10.

Si lst1 admet un élément absolument majoritaire maj1, donner un algorithme pour vérifier si maj1 est l'élément absolument majoritaire de lst.

11.

Recopier et compléter les lignes 4, 11, 13, 15 et 17 pour la fonction récursive majo_abs3 qui implémente l'algorithme précédent. Vous pourrez utiliser la fonction effectif de la question 2.

1 def majo_abs3(lst):

2 n = len(lst)

3 if n == 1:

4 return...

5 else:

6 lst_g = lst[:n//2]

7 lst_d = lst[n//2:]

8 maj_g = majo_abs3(lst_g)

9 maj_d = majo_abs3(lst_d)

10 if maj_g is not None:

11 eff =......

12 if eff > n/2:

13 return...

14 if maj_d is not None:

15 eff =......

16 if eff > n/2:

17 return...