#!/usr/bin/env python # coding: utf-8 #
#
TP n°6 : Révisions et compléments - éléments de correction
# $\require{color}$ # $\require{xcolor}$ # $\require{cancel}$ # $\newcommand{\myfbox}[1]{\fcolorbox{red}{white}{$\textrm{#1}$}}$ # $\require{stmaryrd}$ # $\newcommand{\ient}{[\![}$ # $\newcommand{\rrbracket}{]\!]}$ # $\newcommand{\llbracket}{[\![}$ # $\newcommand{\fient}{]\!]}$ # $\newcommand{\R}{\mathbb R}$ # $\newcommand{\K}{\mathbb K}$ # $\newcommand{\N}{\mathbb N}$ # $\newcommand{\C}{\mathbb C}$ # $\newcommand{\P}{\mathbb P}$ # $\newcommand{\E}{\mathbb E}$ # $\newcommand{\V}{\mathbb V}$ # $\newcommand{\Z}{\mathbb Z}$ # $\newcommand{\dt}{\mathrm d}$ # $\newcommand{\sh}{\operatorname{sh}}$ # $\newcommand{\ch}{\operatorname{ch}}$ # $\newcommand{\th}{\operatorname{th}}$ # $\newcommand{\e}{\operatorname{e}}$ # $\newcommand{\id}{\operatorname{Id}}$ # $\newcommand{\mat}{\operatorname{mat}}$ # $\newcommand{\sp}{\operatorname{Sp}}$ # $\newcommand{\In}{\operatorname{I}}$ # $\newcommand{\vect}{\operatorname{Vect}\ }$ # $\newcommand{\rg}{\operatorname{rg}}$ # $\newcommand{\tr}{\operatorname{Tr}}$ # $\newcommand{\dis}{\displaystyle}$ # $\renewcommand{\Im}{\operatorname{Im}}$ # $\newcommand{\im}{\operatorname{Im}}$ # $\newcommand{\bordermatrix}[3]{ \begin{matrix} \begin{matrix}#1\end{matrix} & \\ #3 & \hspace{-1em} \begin{matrix}#2\end{matrix} \end{matrix}}$ # $\newcommand{\fonction}[5]{#1\ \colon \left\{\begin{array}{ccl}#2 & \longrightarrow & #3\\#4 & \longmapsto & #5\end{array}\right.}$ # $\newcommand{\fonctionsansnom}[4]{\left\{\begin{array}{ccl}#1 & \longrightarrow & #2\\#3 & \longmapsto & #4\end{array}\right.}$ # $\newcommand{\revdots}{\mathinner{\mkern1mu\raise1pt{\kern7pt\hbox{.}}\mkern2mu\raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}}$ # $\newcommand{\tendvers}[2]{\xrightarrow[#1\to#2]{}}$ # $\newcommand{\q}[1]{\mathbf{Q#1}\ \triangleright}$ # $\newcommand{\nicefrac}[2]{^{#1}/_{#2}}$ # # 1 - Arguments des fonctions ; variables locales ou globales #
# Exercice 1 #
# In[1]: def max_pos(L: [int], i: int) -> (int, int): """ Détermine le plus grand élément M d'une liste L jusqu'à l'indice i (inclus), ainsi que le premier indice pos réalisant ce maximum """ M = L[0] pos = 0 for k in range(i + 1): if L[k] > M: M = L[k] pos = k return M, pos # In[2]: max_pos([1, 2, 3, 5, 6, 3, 4], 9) #
# Exercice 2 #
# In[3]: def max_pos(L: [int], i: int) -> (int, int): """ Détermine le plus grand élément M d'une liste L à partir de l'indice i (inclus), ainsi que le premier indice pos réalisant ce maximum """ assert (0 <= i < len(L)) M = L[0] pos = 0 for k in range(i + 1): if L[k] > M: M = L[k] pos = k return M, pos # In[4]: max_pos([1, 2, 3, 5, 6, 3, 4], 9) #
# Exercice 3 #
# In[5]: help(max_pos) # On l'utilise alors dans la fonction ```tri``` de la manière suivante : # In[6]: def tri(L: [int]) -> [int]: for i in range(len(L) - 1, 0, -1): M, pos = max_pos(L, i) L[pos], L[i] = L[i], L[pos] return L # In[7]: L = [1, 2, 3, 5, 4, 3, 2, 6] # In[8]: tri(L) # In[9]: L # La liste ```L``` a été modifée par effet de bord ! # # Si l'on ne souhaite plus que la liste ```L``` soit modifiée par effet de bord, il suffit de la cloner au début de la fonction : # In[10]: def tri(L: [int]) -> [int]: N = L.copy() for i in range(len(N) - 1, 0, -1): M, pos = max_pos(N, i) N[pos], N[i] = N[i], N[pos] return N # In[11]: L = [1, 2, 3, 5, 4, 3, 2, 6] # In[12]: tri(L) # In[13]: L # # 2 - Recherche séquentielle #
# Exercice 4 #
# In[14]: def recherche_naive(x: float, L: [float]) -> bool: """ Implémente la recherche naive d'un nombre x dans une liste de nombres L. Renvoie True si x est dans L et False sinon. """ for elt in L: if x == elt: return True return False # atteint seulement si l'on sort de la boucle for # In[15]: recherche_naive(1, [2, 3, 4, 1, 2, 3, 5]) # In[16]: recherche_naive(6, [2, 3, 4, 1, 2, 3, 5]) # In[17]: recherche_naive(1, []) #
# Exercice 5 : recherche dichotomique #
# In[18]: def recherche_dicho(x: float, L: [float]) -> bool: """ Recherche dichotomique de l'élément x dans la liste triée par ordre croissant L Renvoie True si x est dans L et False sinon. """ a, b = 0, len(L) - 1 while a <= b: i = (a + b) // 2 if L[i] == x: return True elif L[i] > x: b = i - 1 else: a = i + 1 # arrivé ici, a > b et x n'est pas dans la liste L return False #
# Exercice 6 : recherche d'un motif dans un texte #
# Le plus simple à écrire est sans doute de "diviser pour régner", en écrivant d'abord une fonction qui teste la présence d’un mot à partir d’une position $i$ dans une chaîne de caractères : # In[19]: def test(M: str, T: str, i: int) -> bool: """ Teste la présence d’un mot M à partir d’une position i dans une chaîne de caractères T (on renvoie un booléen adéquat) """ for j in range(len(M)): if M[j] != T[i + j]: return False # cela met fin à la boucle for return True # seulement si la boucle for est allée jusqu'au bout ! # In[20]: def recherche_naive(M: str, T: str) -> int: """ Recherche le motif M dans la chaine T Renvoie l'indice de la premiere occurence de M dans T s'il y est present, et -1 sinon. """ assert (len(M) <= len(T)) # les longueurs du mot et du texte sont compatibles n, m = len(T), len(M) indice = 0 for i in range(n - m + 1): if test(M, T, i): return i # on a rencontré M à partir de la position i dans T return -1 # seulement si la boucle for est allée jusqu'au bout ! # In[21]: recherche_naive("bambou", "bambamboum") # In[22]: recherche_naive("bim", "bambamboum") # Si l'on souhaite maintenant renvoyer le nombre d'occurrences du mot ```M``` dans le texte ```T```, on peut adapter la fonction précédente de la manière suivante, en utilisant un compteur ```occ``` : # In[23]: def recherche_naive(M: str, T: str) -> int: """ Renvoie le nombre d'occurences de M dans T """ assert (len(M) <= len(T)) # les longueurs du mot et du texte sont compatibles n, m = len(T), len(M) occ = 0 indice = 0 for i in range(n - m + 1): if test(M, T, i): occ += 1 # on a rencontré M à partir de la position i dans T return occ # In[24]: recherche_naive("bambou", "bambamboum") # In[25]: recherche_naive("bam", "bambamboum") # In[26]: recherche_naive("bim", "bambamboum")