Exercices d’algorithmique, 2

2ème TD, quelques exercices d’algorithmique de base.

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).

exos_algo2.logEntier(n, base=2)

Calcule le logarithme entier du nombre entier positif n, en temps O(log(n)) et memoire O(1).

exos_algo2.logEntier2(n)

exos_algo2.print_logEntier(n, base)

exos_algo2.testeFenetre(t)

exos_algo2.maximumTableauMD(t)

exos_algo2.estMD(t)

exos_algo2.trianglePascal(n)

O(n**2) en temps et en espace pour un resultat renvoye de taille n+1.

exos_algo2.trianglePascal2(n)

O(n**2) en temps et O(n) en espace pour un resultat renvoye de taille n+1.

exos_algo2.coefficientBinomial(m, p)

Calcule un seul coefficient en temps O(m**2) et en espace O(m) (vraiment inutile).

exos_algo2.coefficientBinomial2(m, p)

Calcule un seul coefficient en temps O(min(p, m-p)) et en espace O(1).

exos_algo2.faconsDePayer(montant, montantPieces=[1, 2, 5, 10, 20, 50], verbose=False)

Mal ecrite, mais ca marche.

---

Sortie du script

$ python3 exos_algo2.py
Le logarithme entier en base 2 de 12345 est 13 (car 8192 = 2**13 <= 12345 < 2**(13+1) = 16384).
Le logarithme entier en base 10 de 1234567890 est 9 (car 1000000000 = 10**9 <= 1234567890 < 10**(9+1) = 10000000000).
Pour n = 0, trianglePascal(n) = [1].
Pour n = 1, trianglePascal(n) = [1, 1].
Pour n = 2, trianglePascal(n) = [1, 2, 1].
Pour n = 3, trianglePascal(n) = [1, 3, 3, 1].
Pour n = 4, trianglePascal(n) = [1, 4, 6, 4, 1].
Pour n = 5, trianglePascal(n) = [1, 5, 10, 10, 5, 1].
Pour n = 6, trianglePascal(n) = [1, 6, 15, 20, 15, 6, 1].
Pour n = 7, trianglePascal(n) = [1, 7, 21, 35, 35, 21, 7, 1].
Pour n = 8, trianglePascal(n) = [1, 8, 28, 56, 70, 56, 28, 8, 1].
Pour n = 9, trianglePascal(n) = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1].
Pour n = 0, trianglePascal2(n) = [1].
Pour n = 1, trianglePascal2(n) = [1, 1].
Pour n = 2, trianglePascal2(n) = [1, 2, 1].
Pour n = 3, trianglePascal2(n) = [1, 3, 3, 1].
Pour n = 4, trianglePascal2(n) = [1, 4, 6, 4, 1].
Pour n = 5, trianglePascal2(n) = [1, 5, 10, 10, 5, 1].
Pour n = 6, trianglePascal2(n) = [1, 6, 15, 20, 15, 6, 1].
Pour n = 7, trianglePascal2(n) = [1, 7, 21, 35, 35, 21, 7, 1].
Pour n = 8, trianglePascal2(n) = [1, 8, 28, 56, 70, 56, 28, 8, 1].
Pour n = 9, trianglePascal2(n) = [1, 9, 36, 84, 126, 126, 84, 36, 9, 1].
Il y a 7 facons de payer 8 centimes avec les pieces [1, 2, 5, 10, 20, 50].
Il y a 4562 facons de payer 1 euros avec les pieces [1, 2, 5, 10, 20, 50].

Le fichier Python se trouve ici : exos_algo2.py.