#! /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
[docs]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)))
[docs]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
[docs]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)))
[docs]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)))
[docs]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
[docs]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
[docs]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)
[docs]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
[docs]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
[docs]def double():
n = int(input("Choisissez un entier n : "))
print("Le double de {} est {}.".format(n, 2*n))
[docs]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
[docs]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"
[docs]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
[docs]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"))