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