Diviser pour régner


Thème 5 - Partie A

La dichotomie



https://exomorphisme.fr/game/cle



def recherche_dicho(tab valeur):
    """
    tab – list, tableaux ordonné d’éléments
    valeur – de même type que les éléments de tab
    Sortie: bool – True si valeur est dans tab, False sinon
    """
    debut = 0
    fin = len(tab) - 1
    while debut < fin
        milieu = (debut + fin) // 2
        if tab[milieu] = valeur:
            return True
        elif tab[milieu] < valeur:
            debut = milieu
        else tab[milieu] > valeur:
            fin = milieu
    return False
  1. Que fait l'opérateur // ? Quel est le résulat de 5//2 ?


  2. Comment s'appelle les lignes de 2 à 6 ? A quoi servent-elles ?


  1. On fait l'appel suivant :
    recherche_dicho([1,3,5,7,9,12,15,16,17,21,25,27,32], 5)


Le principe

Le paradigme de programmation « diviser pour régner» consiste à décomposer un problème général en petits sous-problèmes plus simples à résoudre, permettant par recomposition d’aboutir à la résolution du problème général.

Il y a donc 3 étapes :
  • ➀ Diviser
  • ➁ Régner / Résoudre
  • ➂ Combiner

Le principe


  • ➀ Diviser : On part du problème général et on le décompose en sous problèmes identiques mais sur des jeux de données différents.
  • ➁ Régner / Résoudre : On résoud les sous-problèmes.
  • ➂ Combiner: On construit la solution générale à partir de la solution de chaque sous-problèmes .

Le principe

Le principe

Le tri-fusion

Slice

En Python, le slicing est une méthode qui permet d'extraire une partie d'une séquence, liste ou chaîne de caractère par exemple.
Si seq une séquence, alors seq[4:8] sera une séquence de même type que seq contenant les éléments d'indice :
  • supérieur ou égal à 4
  • strictement inférieur à 8
Par exemple : 
alpha = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
s = alpha[4:8]
print(s)

pop()

En Python, le slicing est une méthode qui permet d'extraire une partie d'une séquence, liste ou chaîne de caractère par exemple.
Si seq une séquence, alors seq[4:8] sera une séquence de même type que seq contenant les éléments d'indice :
  • supérieur ou égal à 4
  • strictement inférieur à 8
Par exemple : 
alpha = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
s = alpha[4:8]
print(s)
pop()
La méthode pop s'applique aux listes. Elle permet d'enlever et de récupérer un élément de la liste. Si la fonction pop est appeler sans paramètre, elle retire et renvoie le dernier élement de la liste. Si un entier n est passé en paramètre alors, c'est l'élément se trouvant à l'indice n qui est renvoyer et supprimer de la liste.
pop()
Par exemple : 

tab = [1,2,3] 
elmt = tab.pop(0)