Code source de TP2

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