#! /usr/bin/env python3 # -*- coding: utf-8; mode: python -*- """ TP1 au Lycée Lakanal (sujet rédigé par Arnaud Basson). - *Date :* jeudi 17-09 et vendredi 18-10 (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 : Sommes doubles def s1(n): r""" :math:`s1(n) = \sum_{1 <= i < j <= n} ij` """ resultat = 0 for i in range(1, n): # 1 <= i < n for j in range(i+1, n+1): # i < j <= n resultat += i * j return resultat print("Pour n = 10, s1(n) = s1(10) = {}".format(s1(10))) def s2(n): r""" :math:`s2(n) = \sum_{0 <= p + q <= n} p / (q + 1)` """ resultat = 0.0 for p in range(0, n+1): # 0 <= p <= n for q in range(0, n-p+1): # 0 <= q <= n - p # assert 0 <= p + q <= n resultat += p / (q + 1) return resultat print("Pour n = 10, s2(n) = s2(10) = {}".format(s2(10))) # %% Exercice 2 : Suites récurrentes def v(n): """ Calcul le énième terme de la suite récurrente :math:`v_n` définie par :math:`v_0 = 1, v_1 = 2, et v_{n+2} = v_{n+1} + 3 * v_n`.""" assert n >= 0, "n doit être positif." v0, v1 = 1, 2 if n == 0: return v0 elif n == 1: return v1 else: vn, vnext = v0, v1 # n = 0 for _ in range(0, n): # On peut changer ici l'équation de la récurrence vn, vnext = vnext, vnext + 3*vn return vn print("Pour n = 10, v(10) = v_10 = {}".format(v(10))) def seuil(p): """ Trouve par recherche exhaustive le plus petit entier n tel que :math:`v(n) < p`. Attention, cette fonction n'est *pas du tout* optimisée.""" if p <= 1: return 0 n = 0 while v(n) < p: n += 1 return n print("Pour p = 3841, le seuil trouve vaut {}.".format(seuil(3841))) print("Pour p = 3842, le seuil trouve vaut {}.".format(seuil(3842))) print("Pour p = 3843, le seuil trouve vaut {}.".format(seuil(3843))) def catalan(n): """ Calcule de façon naïve le nième nombre de Catalan. La complexité spatiale est en :math:`O(n)`, et temporelle en :math:`O(n^2)`.""" c = [1] for i in range(0, n): # Boucle en O(n) # Calcule la nouvelle valeur c_i = c[i] grâce à toutes celles calculées avant # Somme en O(i) c.append(sum(c[k] * c[i - k] for k in range(0, i+1))) return c[n] for i in range(10): print("Pour i = {}, le ieme nombre de Catalan est {}.".format(i, catalan(i))) # %% Exercice 3 : Sous-maximum def sousMaximum(t): """ Calcule le deuxième plus grand élément d’un tableau de nombres t dont les éléments sont supposés deux à deux distincts. On effectue un seul parcours du tableau, donc l'algorithme est en :math:`O(n)` (pire cas, meilleur cas, moyenne, bref toutes les complexités).""" n = len(t) assert n >= 2, "sousMaximum(t) exige au moins deux éléments." plusGrand, secondPlusGrand = max(t[0], t[1]), min(t[0], t[1]) for i in range(2, n): if t[i] > plusGrand: plusGrand, secondPlusGrand = t[i], plusGrand elif plusGrand > t[i] > secondPlusGrand: secondPlusGrand = t[i] return secondPlusGrand # Exemple from random import shuffle for i in range(2, 10): t = list(range(i)) shuffle(t) print("Pour i = {}, t = {}, sousMaximum(t) = {}.".format(i, t, sousMaximum(t))) # %% Exercice 4 : Échange des voisins def echangeVoisins1(t): """ Renvoit un nouveau tableau.""" n = len(t) nouveau_t = t assert n % 2 == 0 for i in range(0, int(n / 2)): nouveau_t[2*i], nouveau_t[2*i + 1] = nouveau_t[2*i + 1], nouveau_t[2*i] return nouveau_t # Exemple t = [1, 2, 3, 4] print(t) u = echangeVoisins1(t) print(u) def echangeVoisins2(t): """ Calcul en place.""" n = len(t) assert n % 2 == 0 for i in range(0, int(n / 2)): t[2*i], t[2*i + 1] = t[2*i + 1], t[2*i] # Exemple t = [1, 2, 3, 4] print(t) echangeVoisins2(t) print(t) # %% Exercice 5 : produit interactif def estNombre(ch): """ Teste si la chaîne ch est un nombre entier positif ou non (naïvement).""" # Mauvaise façon : # try: # int(ch) # return True # except: # return False # Bonne façon : for c in ch: if c not in '0123456789': return False return True def double(): n = int(input("Choisissez un entier n : ")) print("Le double de {} est {}.".format(n, 2*n)) def produit(): prod = 1 s = input("Choisissez un entier n : ") while s: prod *= int(s) print("Le produit vaut actuellement {}.".format(prod)) s = input("Choisissez autre un entier n : ") print("Le produit entier vaut {}.".format(prod)) # %% Exercice 6 : Recherche de sous-chaînes de caractères def sousChaineConstante(texte): """ En O(n).""" longueur_max = 1 n = len(texte) for i in range(0, n): caractere = texte[i] # print("Recherche d'un morceau compose du caractere {} (d'indice {}).".format(caractere, i)) longueur_morceau = 1 while i + longueur_morceau < n and texte[i + longueur_morceau] == caractere: longueur_morceau += 1 # print("La longueur du morceau vaut actuellement {}.".format(longueur_morceau)) # print("La longueur du morceau vaut finalement {}.".format(longueur_morceau)) longueur_max = max(longueur_max, longueur_morceau) return longueur_max print(sousChaineConstante("aabaaacca")) # "aaa" def sousChaineRepetee(texte): """ Au pire des cas, en :math:`O(n^3)`.""" n = len(texte) maxi = 0 sousChaineMaxi = "" for i in range(0, n): for j in range(i+1, n): long = longueur(texte, i, j) if long > maxi: maxi = long sousChaineMaxi = texte[i : i+long] return sousChaineMaxi def longueur(texte, i, j): r""" On suppose :math:`0 \leq i < j < len(texte)`. Cette fonction est au pire en :math:`O(j-i)` (soit :math:`O(n)` dans le pire des cas).""" k = 0 while k < j-i and k < len(texte)-j and texte[i+k] == texte[j+k]: k += 1 return k print("Pour 'roucouler', la plus grand sous-chaine repetee est", sousChaineRepetee("roucouler")) print("Pour 'tralala', la plus grand sous-chaine repetee est", sousChaineRepetee("tralala")) print("Pour 'l'ouie de l'oie de Louis', la plus grand sous-chaine repetee est", sousChaineRepetee("l'ouïe de l'oie de Louis"))