#!/usr/bin/env python
# coding: utf-8
#
#
TP 3 (structures linéaires de données) : éléments de correction
#
# Exercice 1
#
# In[1]:
L = [i for i in range(1, 501)]
# In[2]:
import random as rd
A = [rd.random() for i in range(1000)]
# In[3]:
S = "esope reste ici et se repose"
#
# Exercice 2 : Moyenne et variance
#
# Si on n'autorise pas la fonction ```sum``` de Python (les sujets de concours le font parfois), on calcule la somme à la main :
# In[4]:
moy = 0
n = len(L)
for i in range(n):
moy = moy + L[i] # ou moy += L[i]
moy = moy / n
print("moyenne :", moy)
# ou la variante suivante :
# In[5]:
moy = 0
for elt in L:
moy = moy + elt # ou moy += elt
moy = moy / len(L)
print("moyenne :", moy)
# On peut également, si le sujet nous y autorise, utiliser la commande ```sum```:
# In[6]:
print("moyenne :", sum(L) / len(L))
# Pour la variance, on utilise le calcul de la moyenne, que l'on a stocké au préalable dans la variable ```moy```:
# In[7]:
moy
# In[8]:
print("variance :", sum([(L[i] - moy)**2 for i in range(len(L))]) / len(L))
# In[9]:
print("variance :", sum([(elt - moy)**2 for elt in L]) / len(L))
# > L'utilisation d'une liste définie par compréhension facilite grandement l'écriture (et la lecture) des scripts précédents. Il faut bien comprendre ce mécanisme !
#
#
#
À retenir :
#
# - On peut utiliser une liste définie par compréhension quand on connaît explicitement la forme du $i^{\textrm{ème}}$ élément de la liste
# - On peut alors également très facilement calculer la somme de cette liste avec la commande
sum.
#
#
# Exercice 3 : Recherche du maximum dans une liste
#
# In[10]:
M = A[0] # initialisation du maximum
p = 0 # initialisation de la position du maximum
for i in range(1, len(A)): # on parcourt la liste
if A[i] > M:
M = A[i] # mise à jour du maximum
p = i # mise à jour de sa position
print("Le maximum vaut {0}, et apparaît pour la première fois à l'indice {1}.".format(M, p))
# On peut vérifier notre résultat avec les commandes *ad hoc* de Python :
# In[11]:
max(A)
# In[12]:
M == max(A)
# In[13]:
A.index(max(A))
# > Là encore, la recherche du maximum (ou du minimum) dans une liste de nombres est un classique à maîtriser : c'est une question fréquente lorsque l'on traite des données expérimentales par exemple (et c'est également une question fréquente des écrits de concours...)
#
# Exercice 4 : Suite de Fibonacci
#
# L'idée est d'adapter ce que l'on a déjà vu pour calculer le $n^{\textrm{ème}}$ terme de la suite de Fibonacci lors de précédents TP :
# In[14]:
u, v = 1, 1 # on a besoin de stocker 2 variables pour f_n et f_(n+1)
L = [1, 1] # initialisation de la liste des valeurs
for i in range(2, 100): # attention aux bornes !
u, v = v, u + v # mise à jour des termes de la suite
L.append(v) # ajout à la liste L du nouveau terme calculé
print(L)
#
# Exercice 5 : Palindrome
#
# Pour tester si une chaîne est un palindrome, on peut calculer le booléen suivant (attention aux bornes !) :
# In[15]:
n = len(S)
palin = True
i = 0
while i <= n / 2 and palin:
palin = (S[i] == S[n - 1 - i])
i += 1
print("Test palindrome :", palin)
# En fait, il s'agit bien d'un palindrome, si l'on néglige les espaces :
# In[16]:
S = S.replace(" ", "") # enleve les espaces dans la chaîne de caractères
print("Nouvelle chaine sans espace : ", S)
n = len(S)
palin = True
i = 0
while i <= n // 2 and palin:
palin = (S[i] == S[n - 1 - i])
i += 1
print("Test palindrome :", palin)
#
# Exercice 6 : Suite de Conway
#
# In[17]:
def lookandsay(s):
i = 0
t = ''
while i < len(s):
k = 1
j = i + 1
while j < len(s) and s[j] == s[i]:
k += 1
j += 1
t = t + str(k) + s[i]
i = j
return t
# In[18]:
lookandsay("1332")
# In[19]:
s = '1'
print(s)
for i in range(9):
s = lookandsay(s)
print(s)
# Une approximation de la constante de Conway est donnée par le calcul d'un rapport $\frac{u_{n+1}}{u_n}$ pour un $n$ assez grand :
# In[20]:
def cste_conway(s, n):
u, v = s, lookandsay(s)
for _ in range(n):
u, v = v, lookandsay(v)
return len(v) / len(u)
# In[21]:
cste_conway('1', 10)
# In[22]:
cste_conway('1', 45)
# On peut vérifier expérimentalement l'indépendance de la constante de Conway vis-à-vis du premier terme de la suite :
# In[23]:
# import random as rd # l'import a déjà été fait plus haut
for i in range(5):
s = rd.randint(1, 100)
if s != 22:
print("Premier terme de la suite :", s, "; approximation obtenue :",
cste_conway(str(s), 40))
# **Remarque :**
# >On a en fait l'approximation suivante de la constante $\lambda$ de Conway :
# >
# >$$ \lambda \simeq 1.303577269\dots$$
#
# Exercice 7 : Permutations
#
# In[24]:
def fact(n):
s = 1
for k in range(1, n + 1):
s *= k
return s
def permutation(n):
sol = []
lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(9, -1, -1):
k = n // fact(i)
n -= k * fact(i)
sol.append(lst.pop(k))
return sol
# In[25]:
permutation(999999)
# Deux cas particuliers permettent de vérifier le résultat obtenu :
# In[26]:
permutation(0)
# In[27]:
permutation(fact(10) - 1)
# **Remarque :**
# > On peut se poser la question de la complexité de notre algorithme. Par exemple, on recalcule toutes les factorielles à chaque étape, alors que l'on pourrait les pré-calculer toutes de manière itérative et les stocker dans une liste. Ce genre de considérations n'est pas la priorité pour l'instant, mais le deviendra plus tard dans l'année.