#!/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)
[docs]def print_logEntier(n, base):
p = logEntier(n, base)
print("Le logarithme entier en base {base} de {n} est {p} (car {min} = {base}**{p} <= {n} < {base}**({p}+1) = {max}).".format(n=n, p=p, min=base**p, max=base**(p+1), base=base))
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))