#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
TD4 au Lycée Lakanal (sujet rédigé par Arnaud Basson).
- *Date :* jeudi 12 novembre 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 : Moyenne arithmético-géométrique
print("\n\nExercice 1 : Moyenne arithmetico-geometrique")
from math import sqrt
[docs]def moyArithGeom(a, b, n):
r""" Calcule les énièmes termes des deux suites adjacentes :math:`u_n, v_n`, définies selon :
.. math:: u_0 = a,\;\; v_0 = b
.. math:: u_{n+1}=\frac{u_n+v_n}{2}, v_{n+1}=\sqrt{u_n v_n}
"""
u, v = a, b
for _ in range(n):
u, v = (u + v) / 2, sqrt(u * v)
return (u, v)
print("Exemples de moyenne arithmetico-geometrique :")
for (a, b) in [(10, 500), (2, 6000), (19, 93)]:
print("\nPour a =", a, "et b =", b)
for n in range(12):
u, v = moyArithGeom(a, b, n)
print("\tPour n =", n, "u_n =", u, "et v_n =", v)
if u == v:
print("\tLa suite a converge !")
# %% Exercice 2 : Calcul récursif du pgcd
print("Exercice 2 : Calcul recursif du pgcd")
[docs]def pgcdRec(a, b):
r""" Calcule le PGCD de a et b récursivement.
- *Note :* elle a un temps logarithmique mais une pile d'appels logarithmique aussi (la version itérative est meilleure, car sans pile d'appel).
- Complexité temporelle en :math:`O(\log(\min(a,b)))`.
- Voir dans le `TP4 <../TPs/solutions/TP4.html#pgcd_rec>`_ pour plus d'exemples de fonctions récursives.
"""
if b == 0:
return a
if b > a:
return pgcdRec(b, a)
r = a % b
return pgcdRec(b, r)
print("\nQuelques essais de pgcdRec(a, b) :")
for a in [10, 20, 30, 200, 400, 10000, 94749651, 789465179864519465]:
for b in [0, 1, 2, 5, 10, 37, 69, 117, 673, 7894651, 74147894651]:
d = pgcdRec(a, b)
print("pgcdRec de", a, "et", b, "=", d)
[docs]def pgcdBinaire(a, b):
r""" Autre algorithme de calcul du PGCD de a et b, plus lent.
- Termine bien en considérant l'ordre lexicographique sur le nombre de bits de a et de b.
- Complexité temporelle en :math:`O(\log(a) + \log(b))`.
- Complexité mémoire en :math:`O(1)`.
"""
if b == 0:
return a
if a == 0:
return b
if b < 0 or a < 0:
return pgcdBinaire(abs(a), abs(b))
if a % 2 == 0:
if b % 2 == 0:
return 2 * pgcdBinaire(a//2, b//2)
else:
return pgcdBinaire(a//2, b)
else:
if b % 2 == 0:
return pgcdBinaire(a, b//2)
elif a >= b:
return pgcdBinaire((a-b)//2, b)
else:
return pgcdBinaire(b, a)
print("\nQuelques essais de pgcdBinaire(a, b) :")
for a in [10, 20, 30, 200, 400, 10000, 94749651, 789465179864519465]:
for b in [0, 1, 2, 5, 10, 37, 69, 117, 673, 7894651, 74147894651]:
d = pgcdBinaire(a, b)
print("pgcdBinaire de", a, "et", b, "=", d)
assert d == pgcdRec(a, b)
# %% Exercice 3 : fonction mystère
print("Exercice 3 : fonction mystere")
[docs]def f(x, n):
r""" *"Fonction mystère"* de l'exercise 3.
a. Termine toujours car n est strictement décroissant et minoré par 1.
b. Ohoh, apparemment :math:`f(x,n) = x^n` (mais avec la convention :math:`x^0 = x` et pas 1). Invariant : x**(n-i) == a à chaque boucle (vrai au début i = n, a = 1, reste vrai en considérant les deux cas sur le bit suivant de n, et à la fin ça donne x**(n-1) == a donc x**n == a*x = f(x,n) prouve la correction).
c. En fait, c'est **l'écriture itérative des appels récursifs successifs (dépliés) de l'exponentiation rapide**.
d. Le nombre de multiplication concernant a est le nombre de bit à 1 dans n et le nombre d'exponentiation concernant x est exactement le nombre de bit de n, donc le tout est bien en :math:`O(\log(n))`.
"""
a = 1
while n > 1:
if n % 2 == 1:
a = a * x
x = x**2
n = n // 2
return a*x
print("Testons cette fonction mystère sur quelques valeurs :")
for x in [0, 1, 2, 3, 10, -1, -2]:
print("Pour x =", x)
for n in [1, 2, 3, 4, 5, 100]:
print("\tPour n =", n)
print("\tf(x, n) =", f(x, n))
assert f(x, n) == x**n
# %% Exercice 4 : Manipulation récursive de l’écriture décimale d’un entier
print("Exercice 4 : Manipulation recursive de l'ecriture decimale d'un entier")
# 4.1
[docs]def sommeChiffres(n):
""" Calcule récursivement la somme des chiffres d'un entier n."""
if n < 0:
return - sommeChiffres(-n)
elif n == 0:
return 0
else:
return n % 10 + sommeChiffres(n//10)
print("Exemple de somme des chiffres d'un entier :")
for n in [7, 1658, 749861, 7948978546, 79849788974659786547894, 100000000000000000000000, 10000000000000000000000000000001]:
print("Pour n =", n, "on a sommeChiffres(n) =", sommeChiffres(n))
# 4.2
[docs]def contient9(n):
r""" Teste si l'écriture décimale de n contient un n.
a. Meilleur des cas : pas d'appel récursif si n termine par un 9 (:math:`O(1)`),
b. Pire des cas : obligé de lire tout les chiffres jusqu'au dernier, donc :math:`O(\log_{10}(n))`.
c. En moyenne : C est comme une loi géométrique tronquée, de paramètre :math:`p = 1/10` (chaque chiffre est uniformément réparti) : on pioche un chiffre, on s'arrête si = 9, on continue sinon. Le paramètre k est la taille (décimale) du nombre entier n. (TODO better explanations !)
"""
if n < 0:
return contient9(-n)
elif n == 0:
return False
elif n % 10 == 9:
return True
else:
return contient9(n // 10)
print("Exemple de chiffres qui contiennent ou ne contiennent pas 9 :")
for n in [7, 1658, 749861, 7948978546, 79849788974659786547894, 100000000000000000000000, 10000000000009000000000000000001]:
print("Pour n =", n, "on a contient9(n) =", contient9(n))