#! /usr/bin/env python3
# -*- coding: utf-8; mode: python -*-
""" TP2 au Lycée Lakanal (sujet rédigé par Arnaud Basson).
- *Date :* mercredi 30-09 et jeudi 01-10 (2015),
- *Auteur :* Lilian Besson, pour le cours d'informatique pour tous en prépa MP (http://perso.crans.org/besson/infoMP/),
- *Licence :* MIT Licence (http://lbesson.mit-license.org).
"""
from __future__ import print_function # Python 2 compatibility
# %% Exercice 1 : Nombres premiers
# a)
from math import sqrt
[docs]def estPremier(n):
r""" Teste si l'entier :math:`n \geq 0` est premier, par une méthode *très* naïve.
- Complexité temporelle : :math:`O(\sqrt{n})`,
- Complexité mémoire : :math:`O(1)`."""
if n < 2:
return False
for diviseur in range(2, int(sqrt(n))+1):
if n % diviseur == 0:
return False # diviseur | n
return True
# b)
[docs]def prochainPremier(n):
r""" Renvoie le plus petit nombre premier supérieur ou égal à n.
- Complexité temporelle : on sait qu'on est au moins en :math:`O(n^{3/2})` (mieux en vrai, car estPremier(n) est en :math:`O(n^{1/2})` et on sait que :math:`n \leq next_{n} < 2n`).
- Complexité mémoire : :math:`O(1)`.
- Remarque : cette procédure termine à tous les coups, car on sait que l'ensemble des nombres premiers est infini (cf. démonstration d'Euclide) et donc non borné.
- Référence : http://villemin.gerard.free.fr/Wwwgvmm/Premier/densite.htm"""
candidat = n
if n % 2 == 0:
candidat += 1 # On prend un nombre impair uniquement
while not estPremier(candidat):
candidat += 2 # Et on va de deux en deux pour être plus rapide
return candidat
# c)
[docs]def comptePremiersPremiers(k):
""" Compte le nombre de nombres premiers plus petit que k (naïvement avec la function estPremier)."""
res = 0
for i in range(k):
if estPremier(i):
res += 1
return res
[docs]def crible(n):
""" Construit la liste des nombres premiers plus petit que n, en écrivant la liste de tous les entiers de 2 à n, et en barrant les multiples de 2, puis les multiples de 3, etc."""
premier = [True]*(n+1) # Tableau pour cribler les entiers non premiers
# À la fin on aura : premier[k] = True s.s.i. k est premier
premier[0] = premier[1] = False
p = 2
listeNbPremiers = []
for p in range(2, n+1):
if premier[p]:
listeNbPremiers.append(p)
# Criblage des multiples de p :
mul = 2*p
while mul <= n:
premier[mul] = False
mul += p
return listeNbPremiers
[docs]def crible2(n):
""" Construit la liste des nombres premiers plus petit que n (du bas vers le haut), très mauvaise méthode."""
premiers = [2] if n > 2 else []
for i in range(3, n, 2):
# Teste si i est premier, si oui on l'ajoutera
iEstPremier = True
for diviseur in premiers: # Il suffit de tester les diviseurs premiers
if i % diviseur == 0:
iEstPremier = False
break
if iEstPremier:
premiers.append(i)
return premiers
[docs]def comptePremiersPremiers_Opti(k):
r""" Compte le nombre de nombres premiers plus petit que k (en utilisant la méthode du crible)."""
return len(crible(k)) # Environ n/log(n)
# %% Exercice 2 : Ecriture décimale d'un entier
# 1.a)
[docs]def chiffresDecimauxTriche(n):
""" On triche en utilisant les fonctions :py:func:`str` et :py:func:`int`."""
return [int(c) for c in reversed(str(n))]
[docs]def chiffresDecimaux(n, reversed=False):
r""" Renvoie la liste des chiffres de l'écriture décimale de l'entier n, en temps et mémoire :math:`O(\log(n))`."""
n_init = n
chiffres = []
# Cette boucle termine toujours car n décroit strictement à chaque itération
while n > 0:
# Invariant de boucle :
# Le nombre n qui reste et les chiffres de la liste représentent toujours le nombre n initial
assert n_init == (n * 10**(len(chiffres))) + sum(10**(i) * chiffres[i] for i in range(len(chiffres))), "Mauvais invariant de boucle pour n = {}, chiffres = {}".format(n, chiffres)
# Et hop, un chiffre de plus !
chiffres.append(n % 10)
n //= 10 # n' = n // 10 donc n' < n
if reversed:
chiffres.reverse() # Si on veut le bit de poids fort en premier
# Selon qu'on veuille les chiffres en commençant par celui des unités ou non
return chiffres
print("Chiffres decimaux de 2015 :", chiffresDecimaux(2015)) # [2, 0, 1, 5]
[docs]def chiffresBasek(n, base=10, reversed=False):
""" Généralise :py:func:`chiffresDecimaux` pour fontionner en base quelconque (``base``)."""
chiffres = []
while n > 0:
chiffres.append(n % base)
n //= base # n = n // base # revient au même
if reversed:
chiffres.reverse() # Si on veut le bit de poids fort en premier
return chiffres
chiffresBinaires = lambda n: chiffresBasek(n, base=2)
print("Chiffres de 31 pour son ecriture binaire :", chiffresBinaires(31)) # [1, 1, 1, 1, 1]
print("Chiffres de 32 pour son ecriture binaire :", chiffresBinaires(32)) # [1, 0, 0, 0, 0, 0]
# %% Exercice 3 : La moyenne des autres
# a)
[docs]def moyenneAutres(t, i):
""" Calcul la moyenne des n-1 autres valeurs du tableau t d'indices différents de i, en temps :math:`O(n)`."""
# On vérifie que les arguments t et i soient corrects.
assert len(t) >= 2, "Tableau trop petit !"
assert 0 <= i < len(t), "Mauvais argument i : i < 0 ou i >= len(t)."
# return sum(t[j] for j in range(len(t)) if i != j) / (len(t) - 1)
return (sum(t) - t[i]) / (len(t) - 1) # Shorter!
t = [0, 1, 2, 3, 4, 5, 6]
print("Exemples de moyenneAutres avec le tableau t =", t)
for i in range(len(t)):
print("moyenneAutres pour i =", i, "vaut", moyenneAutres(t, i))
# b)
[docs]def testMoyAutres(t):
""" Teste si un des éléments du tableau vaut la moyenne des autres, naïvement en temps :math:`O(n^2)`."""
for i in range(len(t)): # n exécution de boucles
if t[i] == moyenneAutres(t, i): # O(n) pour chaque test
# Oups, on utilise == avec des nombres flottants !
# On ne devrait pas ! Les calculs flottants entraînent souvent des erreurs !
# On peut faire abs(t[i] - moyenneAutres(t, i)) < epsilon à la place (e.g. epsilon = 1e-10)
return True
return False
t = [0, 1, 2, 3, 4, 5, 6]
print("testMoyAutres(t) vaut", testMoyAutres(t))
print("En effet, moyenneAutres(t, 3) =", moyenneAutres(t, 3))
# c)
[docs]def testMoyAutres_Opti(t):
""" Teste si un des éléments du tableau vaut la moyenne des autres, de façon maline en temps :math:`O(n)`.
Si sommeDesValeurs est la somme des valeurs du tableau t (sommeDesValeurs = sum(t)),
on peut utiliser la relation suivante (par définition) :
sommeDesValeurs - t[i] = moyenneAutres(t, i) * (n-1)
donc on teste si un t[i] vaut (sommeDesValeurs - t[i]) / (n-1)
"""
n = len(t)
assert n >= 2, "Tableau trop petit !"
sommeDesValeurs = sum(t) # Ce calcul en O(n) n'est fait qu'une fois !
for i in range(n): # n exécution de boucles
if t[i] == (sommeDesValeurs - t[i]) / (n-1): # O(1) pour chaque test (parce qu'on est malin)
# Oups, on utilise == avec des nombres flottants !
return True
return False
# %% Exercice 4 : Recherche dichotomique
[docs]def rechercheDicho(t, x):
""" On suppose que t est trié de façon croissante, et la fonction est en O(log(n))."""
g = 0
d = len(t) - 1
while g <= d:
m = (g+d) // 2
if t[m] == x:
return m
elif x > t[m]:
g = m+1 # On fouille dans la partie droite [m+1:] = [g:d+1]
else:
d = m-1 # On fouille dans la partie gauche [:m-1] = [g:d+1]
return -1 # Pas trouvé !
print("rechercheDicho([1, 2, 4], 1)) donne", rechercheDicho([1, 2, 4], 1)) # 0
print("rechercheDicho([1, 2, 4], 3)) donne", rechercheDicho([1, 2, 4], 3)) # -1
print("rechercheDicho([1, 2, 4], 5)) donne", rechercheDicho([1, 2, 4], 5)) # -1
print("rechercheDicho([1, 2, 3, 4], 4)) donne", rechercheDicho([1, 2, 3, 4], 4)) # 3
# Une seconde implémentation récursive
[docs]def rechercheDichoRec(t, i, gauche=0, droite=None):
""" On suppose que t est trié de façon croissante, et la fonction est en :math:`O(log(n))`."""
if droite == None:
droite = len(t)-1
if gauche > droite: # On a pas trouvé !
return -1
middle = (gauche + droite) // 2
if t[middle] == i:
# i est au milieu !
return middle
elif i < t[middle]:
# i ne peut que se trouver dans la moitié gauche
return rechercheDichoRec(t, i, gauche=gauche, droite=middle-1)
else:
# i ne peut que se trouver dans la moitié droite
return rechercheDichoRec(t, i, gauche=middle+1, droite=droite)
print("rechercheDichoRec([1, 2, 4], 1)) donne", rechercheDichoRec([1, 2, 4], 1)) # 0
print("rechercheDichoRec([1, 2, 4], 3)) donne", rechercheDichoRec([1, 2, 4], 3)) # -1
print("rechercheDichoRec([1, 2, 4], 5)) donne", rechercheDichoRec([1, 2, 4], 5)) # -1
print("rechercheDichoRec([1, 2, 3, 4], 4)) donne", rechercheDichoRec([1, 2, 3, 4], 4)) # 3
# %% Exercice 5 : Calcul des effectifs dans une série de valeurs
# a)
[docs]def effectifs(t, m):
""" Calcul des effectifs dans une liste de valeurs, en temps et mémoire :math:`O(n)`."""
# On vérifie, juste au cas où
assert all(0 <= i <= m for i in t), "Une valeur du tableau t n'est pas comprise entre 0 et m (not (0 <= i <= m))."
e = [0] * (m+1)
for i in t:
e[i] += 1
return e
t = [1, 2, 1, 4, 1]
print("Pour t = {}, ses effectifs sont : {}.".format(t, effectifs(t, 4)))
import random
t = [random.randrange(1, 11) for _ in range(1000)]
print("Pour un tableau aleatoire, ses effectifs sont", effectifs(t, 10))
# Un petit graphique en passant :
# if __name__ == '__main__':
# import matplotlib.pyplot as plt
# x = list(range(11)) # On prend 0 pour bien voir
# y = effectifs(t, 10)
# plt.title("Effectifs d'un tableau aléatoire de 1000 entiers tirés entre 1 et 10.")
# plt.xlabel("Valeurs entre 1 et 10")
# plt.xticks(list(range(1,11)))
# plt.ylabel("Nombres de 1, de 2, .., de 10")
# plt.plot(x, y, 'ro', markersize=12)
# plt.plot(x, [100 for i in x], 'b-')
# plt.savefig("TP2__Exemple_Effectifs.png")
# plt.show()
# b)
# La méthode naïve est en O(n^2)
[docs]def effectifsCumules(t, m):
""" Calcul des effectifs cumulés dans une liste de valeurs, en temps :math:`O(n^2)` et mémoire :math:`O(n)`."""
# On vérifie
assert all(0 <= i <= m for i in t), "Une valeur du tableau t n'est pas comprise entre 0 et m (not (0 <= i <= m))."
e = [0] * (m+1)
for i in range(m+1):
for valeur in t:
# On compte le nombre de valeurs plus petites que i, dans e[i]
if valeur <= i:
e[i] += 1
return e
print("Pour ce tableau aleatoire, ses effectifs cumules sont", effectifsCumules(t, 10))
# Meilleure méthode !
def cumSum(t):
""" Calcule la somme cumulées des valeurs de t, en :math:`O(n)` en temps et espace."""
n = len(t)
u = t[:] # Une copie fraiche, astuce. On peut aussi utiliser list(t).
for i in range(1, n):
u[i] = u[i-1] + t[i] # On accumule les valeurs
return u
[docs]def effectifsCumulesOpti(t, m):
""" Calcul des effectifs cumulés dans une liste de valeurs, qui ne sont autres que les sommes cumulées des effectifs, en temps et mémoire :math:`O(n)`."""
return cumSum(effectifs(t, m))
print("Pour ce tableau aleatoire, ses effectifs cumules sont", effectifsCumulesOpti(t, 10))
# Un petit graphique en passant :
# if __name__ == '__main__':
# import matplotlib.pyplot as plt
# x = list(range(11)) # On prend 0 pour bien voir
# y = effectifsCumules(t, 10)
# plt.title("Effectifs cumulés d'un tableau aléatoire de 1000 entiers tirés entre 1 et 10.")
# plt.plot(x, y, 'ro', markersize=12)
# plt.plot(x, [100*i for i in x], 'b-')
# plt.xlabel("Valeurs entre 1 et 10")
# plt.xticks(list(range(1,11)))
# plt.ylabel("Nombres de 1, de valeurs de 1 à 2, .., de valeurs 1 à 10")
# plt.yticks(list(range(0,1001,100)))
# plt.savefig("TP2__Exemple_Effectifs_cumulés.png")
# plt.show()
# %% Exercice 6 : Manipulation de tableaux à deux dimensions
# 6.1) Mise en bouche
[docs]def ligneMin(a):
""" Prend un tableau 2d de nombres entiers et qui renvoie l'indice de la ligne de somme minimale."""
n = len(a) # nombre de lignes
m = len(a[0]) # nombre de colonnes
sommes = [sum(a[i][j] for j in range(m)) for i in range(n)]
return sommes.index(min(sommes)) # i = argmin(sommes)
# Un exemple :
a = [[3, 2, 6], [4, 1, 4], [0, 5, 2]]
print("Pour a =", a)
print("La liste des sommes de ses lignes est :", [sum(a[i][j] for j in range(len(a[0]))) for i in range(len(a))])
print("Et donc l'indice de la ligne de somme minimale est :", ligneMin(a)) # 2
# 6.2) La chasse au trésor
# 6.2.a)
# Un chemin est un choix de n directions "bas" et "droite"
# C'est une liste de 2(n-1) valeurs valant n-1 fois "bas" et n-1 fois "droite", ordonnée
# Il s'agit donc de choisir i1, .. i_{n-1} les n-1 positions (parmis 1..2(n-1))
# des déplacements "bas" pour fixer le chemin (les déplacements "droits" sont les indices non choisis)
# Donc le nombre de chemins est exactement C(n-1, 2(n-1)) = (2(n-1))! / (n-1)!(n-1)!
# On va s'en servir après
[docs]def cumSum(t):
""" Calcule la somme cumulées des valeurs de t, en :math:`O(n)` en temps et espace."""
n = len(t)
u = t[:] # Une copie fraiche, astuce. On peut aussi utiliser list(t).
for i in range(1, n):
u[i] = u[i-1] + t[i] # On accumule les valeurs
return u
# 6.2.b)
[docs]def calculePieces(terrain):
""" Calcule le tableau auxiliaire pieces de même format que terrain, de telle sorte que pieces[i][j] soit égal au nombre maximal de pièces que l’explorateur peut récolter en se déplaçant de la case (0, 0) à la case (i, j).
- :math:`O(n^2)` en mémoire et en temps.
"""
n = len(terrain) # nombre de lignes
m = len(terrain[0]) # nombre de colonnes
pieces = [[0]*m for i in range(n)]
pieces[0] = cumSum(terrain[0]) # La première ligne se calcule facilement
# Et maintenant on commence à descendre
for i in range(0, n-1):
# On calcule la nouvelle ligne pieces[i+1][j+1] en fonction de pieces[i][j] et pieces[i+1][j-1] :
# Pour cette case là (la plus à gauche, première de sa ligne), on ne peut venir que du haut
pieces[i+1][0] = pieces[i][0] + terrain[i+1][0]
for j in range(0, m-1):
pieces[i+1][j+1] = max( # Ici on pourrait retenir le choix du max afin de construire le chemin
pieces[i][j+1], # On vient du haut (choix "bas")
pieces[i+1][j] # Ou de la gauche (choix "droite")
) + terrain[i+1][j+1] # Et on récolte la case (i+1,j+1)
return pieces
terrain = [[3, 2, 6], [4, 1, 4], [0, 5, 2]]
print("Pour l'exemple du TP, terrain =", terrain)
print("Qui donne pieces =", calculePieces(terrain))
[docs]def butinMax(terrain):
""" Implémentation naïve du calcul de butin maximum, en suivant le sujet."""
pieces = calculePieces(terrain)
return pieces[-1][-1] # astuce pour prendre la case en bas à droite
# return pieces[len(a)-1][len(a[0])-1] # marche aussi
print("Pour l'exemple du TP, butinMax(terrain) =", butinMax(terrain))
# 6.2.c)
# L'algorithme de calcul du tableau pieces et en O(nm) = O(n^2)
# et est un exemple très classique de programmation dynamique
# (très similaire au problème de plus longue sous séquence commune)
# 6.2.d)
# Une façon est de modifier la fonction calculePieces pour enregistrer quel choix est fait à chaque appel à max
# Une autre façon est de lire le tableau pieces par la fin du chemin
[docs]def butinMax2(terrain):
""" Calcule le butin optimal et *un* chemin y menant, en :math:`O(n)` en temps et espace en plus du calcul du tableau pieces (donc en :math:`O(n^2)` au total)."""
pieces = calculePieces(terrain)
n, m = len(terrain), len(terrain[0]) # nombre de lignes, colonnes
y, x = n-1, m-1
chemin = []
while x > 0 and y > 0:
gauche = pieces[y][x-1] # attention les indices sont inversés
haut = pieces[y-1][x] # dans cette convention
if gauche > haut: # On est venu par le choix "droite"
x -= 1
chemin.append("droite")
else: # ou bien par le choix "bas"
y -= 1
chemin.append("bas")
if x > 0: # On avait commencé par x fois "droite"
chemin += ["droite"] * x
elif y > 0: # Ou bien y fois "bas"
chemin += ["bas"] * y
# On a empilé les choix dans l'ordre inverse, on corrige ça
chemin.reverse()
return(pieces, chemin)
print("Pour l'exemple du TP, butinMax2(terrain) =", butinMax2(terrain))