TP1 : Remise en forme

Premier TP, remise en forme sur de petites choses.

Documentation

TP1 au Lycée Lakanal (sujet rédigé par Arnaud Basson).

TP1.s1(n)[source]

\(s1(n) = \sum_{1 <= i < j <= n} ij\)

TP1.s2(n)[source]

\(s2(n) = \sum_{0 <= p + q <= n} p / (q + 1)\)

TP1.v(n)[source]

Calcul le énième terme de la suite récurrente \(v_n\) définie par \(v_0 = 1, v_1 = 2, et v_{n+2} = v_{n+1} + 3 * v_n\).

TP1.seuil(p)[source]

Trouve par recherche exhaustive le plus petit entier n tel que \(v(n) < p\).

Attention, cette fonction n’est pas du tout optimisée.

TP1.catalan(n)[source]

Calcule de façon naïve le nième nombre de Catalan.

La complexité spatiale est en \(O(n)\), et temporelle en \(O(n^2)\).

TP1.sousMaximum(t)[source]

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 \(O(n)\) (pire cas, meilleur cas, moyenne, bref toutes les complexités).

TP1.echangeVoisins1(t)[source]

Renvoit un nouveau tableau.

TP1.echangeVoisins2(t)[source]

Calcul en place.

TP1.estNombre(ch)[source]

Teste si la chaîne ch est un nombre entier positif ou non (naïvement).

TP1.double()[source]
TP1.produit()[source]
TP1.sousChaineConstante(texte)[source]

En O(n).

TP1.sousChaineRepetee(texte)[source]

Au pire des cas, en \(O(n^3)\).

TP1.longueur(texte, i, j)[source]

On suppose \(0 \leq i < j < len(texte)\). Cette fonction est au pire en \(O(j-i)\) (soit \(O(n)\) dans le pire des cas).

Sortie du script

$ python TP1.py
Pour n = 10, s1(n) = s1(10) = 1320
Pour n = 10, s2(n) = s2(10) = 90.0
Pour n = 10, v(10) = v_10 = 3842
Pour p = 3841, le seuil trouve vaut 10.
Pour p = 3842, le seuil trouve vaut 10.
Pour p = 3843, le seuil trouve vaut 11.
Pour i = 0, le ieme nombre de Catalan est 1.
Pour i = 1, le ieme nombre de Catalan est 1.
Pour i = 2, le ieme nombre de Catalan est 2.
Pour i = 3, le ieme nombre de Catalan est 5.
Pour i = 4, le ieme nombre de Catalan est 14.
Pour i = 5, le ieme nombre de Catalan est 42.
Pour i = 6, le ieme nombre de Catalan est 132.
Pour i = 7, le ieme nombre de Catalan est 429.
Pour i = 8, le ieme nombre de Catalan est 1430.
Pour i = 9, le ieme nombre de Catalan est 4862.
Pour i = 2, t = [0, 1], sousMaximum(t) = 0.
Pour i = 3, t = [0, 2, 1], sousMaximum(t) = 1.
Pour i = 4, t = [3, 2, 0, 1], sousMaximum(t) = 2.
Pour i = 5, t = [0, 3, 4, 1, 2], sousMaximum(t) = 3.
Pour i = 6, t = [1, 5, 0, 4, 2, 3], sousMaximum(t) = 4.
Pour i = 7, t = [6, 3, 4, 0, 5, 2, 1], sousMaximum(t) = 5.
Pour i = 8, t = [4, 3, 6, 7, 2, 0, 5, 1], sousMaximum(t) = 6.
Pour i = 9, t = [4, 8, 3, 7, 2, 1, 6, 5, 0], sousMaximum(t) = 7.
[1, 2, 3, 4]
[2, 1, 4, 3]
[1, 2, 3, 4]
[2, 1, 4, 3]
3
Pour 'roucouler', la plus grand sous-chaine repetee est ou
Pour 'tralala', la plus grand sous-chaine repetee est al
Pour 'l'ouie de l'oie de Louis', la plus grand sous-chaine repetee est e de

Le fichier Python se trouve ici : TP1.py.