Code source de exos_algo2

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
TD2 au Lycée Lakanal (sujet rédigé par Arnaud Basson).

- *Date :* jeudi 08 octobre 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 : Logarithme entier en base 2

[docs]def logEntier(n, base=2): """ Calcule le logarithme entier du nombre entier positif n, en temps O(log(n)) et memoire O(1).""" p = 0 assert n > 0 valeur = 1 while valeur <= n: # Cette boucle termine en O(log(n)) executions p += 1 valeur *= base # On evite le base**p a chaque fois p -= 1 assert base**p <= n < base**(p+1) # Juste pour verifier... return p
[docs]def logEntier2(n): return logEntier(n, base=2)
print_logEntier(12345, 2) print_logEntier(1234567890, 10) ## Exercice 2 : Tableau qui monte et qui descend
[docs]def testeFenetre(t): n = len(t) assert n > 0 and n < 4 and isinstance(n, int) if n == 1: return True, t[0] elif n == 2: return True, max(t[0], t[1]) elif n == 3: if t[0] < t[1] and t[2] < t[1]: return True, t[1] elif t[0] < t[1] < t[2]: return False, "Partie croissante" elif t[2] < t[1] < t[0]: return False, "Partie decroissante" return False, "FAILURE"
[docs]def maximumTableauMD(t): # assert estMD(t) # Il suffit de trouver un element t[k] tel que t[k-1] < t[k] et t[k+1] < t[k] n = len(t) pivot = int(n / 2) print("Entree dans le tableau {t} de taille {n} : pivot = {pivot} (t[pivot] = {tpivot}).".format(t=t, n=n, pivot=pivot, tpivot=t[pivot])) reponse, v = testeFenetre(t[max(0, pivot-1) : pivot+2]) if reponse: return v elif v == "Partie croissante": return maximumTableauMD(t[pivot:]) elif v == "Partie decroissante": return maximumTableauMD(t[:pivot])
[docs]def estMD(t): maxt = max(t) # maximumTableauMD ne marche pas si t n'est pas MD ! k = t.index(maxt) # On trouve l'indice du maximum for i in range(len(t)): if i < k: # Partie decroissante if not (t[k-1] < t[k]): return False # Oups, pas decroissant elif i == k: if not (t[k-1] < t[k] and t[k+1] < t[k]): return False # Oups, t[k] n'est pas un bon pivot ! elif i > k: # Partie decroissante if not (t[k-1] > t[k]): return False # Oups, pas decroissant return True
## Exercice 3 : Triangle de Pascal
[docs]def trianglePascal(n): """ O(n**2) en temps et en espace pour un resultat renvoye de taille n+1.""" t = [[0]*(n+1) for i in range(n+1)] # Colonne de gauche et diagonale for i in range(n+1): t[i][0] = 1 t[i][i] = 1 # Iteration for m in range(n): for p in range(m): t[m+1][p+1] = t[m][p+1] + t[m][p] return [t[-1][p] for p in range(n+1)]
for n in range(10): print("Pour n = {}, trianglePascal(n) = {}.".format(n, trianglePascal(n)))
[docs]def trianglePascal2(n): """ O(n**2) en temps et O(n) en espace pour un resultat renvoye de taille n+1.""" t = [1] + [0]*n # Iteration for m in range(1, n+1): t[1:m+1] = [t[p] + t[p-1] for p in range(1, m+1)] return t
for n in range(10): print("Pour n = {}, trianglePascal2(n) = {}.".format(n, trianglePascal2(n)))
[docs]def coefficientBinomial(m, p): """ Calcule un seul coefficient en temps O(m**2) et en espace O(m) (vraiment inutile).""" if p > m: return 0 else: return trianglePascal2(m)[p]
[docs]def coefficientBinomial2(m, p): """ Calcule un seul coefficient en temps O(min(p, m-p)) et en espace O(1).""" if p < 0 or p > m: return 0 else: b = 1 p = min(p, m - p) # (m p) = (m m-p) for i in range(1, p+1): b = (b * (m - i + 1)) // i return b
## Exercice 4 : Rendre la monnaie pieces = [1, 2, 5, 10, 20, 50]
[docs]def faconsDePayer(montant, montantPieces=pieces, verbose=False): """ Mal ecrite, mais ca marche.""" facons = 0 for i6 in range(0, 1+montant, montantPieces[5]): for i5 in range(0, 1+montant-i6, montantPieces[4]): for i4 in range(0, 1+montant-i6-i5, montantPieces[3]): for i3 in range(0, 1+montant-i6-i5-i4, montantPieces[2]): for i2 in range(0, 1+montant-i6-i5-i4-i3, montantPieces[1]): for i1 in range(0, 1+montant-i6-i5-i4-i3-i2, montantPieces[0]): if i1+i2+i3+i4+i5+i6 == montant: facons += 1 if verbose: print("Une autre facon est : " + str((i1, i2, i3, i4, i5, i6))) return facons
print("Il y a {} facons de payer 8 centimes avec les pieces {}.".format(faconsDePayer(8, pieces), pieces)) print("Il y a {} facons de payer 1 euros avec les pieces {}.".format(faconsDePayer(100, pieces), pieces)) # Le dernier exemple est long (plusieurs minutes) # Et repond : # print("Il y a {} facons de payer 10 euros avec les pieces {}.".format(faconsDePayer(1000, pieces), pieces))