#!/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")