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)

moyenne : 250.5

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)

moyenne : 250.5

On peut également, si le sujet nous y autorise, utiliser la commande sum:

In [6]:

print("moyenne :", sum(L) / len(L))

moyenne : 250.5

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

Out[7]:

250.5

In [8]:

print("variance :", sum([(L[i] - moy)**2 for i in range(len(L))]) / len(L))

variance : 20833.25

In [9]:

print("variance :", sum([(elt - moy)**2 for elt in L]) / len(L))

variance : 20833.25

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))

Le maximum vaut 0.9990537238643286, et apparaît pour la première fois à l'indice 79.

On peut vérifier notre résultat avec les commandes ad hoc de Python :

In [11]:

max(A)

Out[11]:

0.9990537238643286

In [12]:

M == max(A)

Out[12]:

True

In [13]:

A.index(max(A))

Out[13]:

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)

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026, 354224848179261915075]

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)

Test palindrome : False

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)

Nouvelle chaine sans espace :  esoperesteicietserepose
Test palindrome : True

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")

Out[18]:

'112312'

In [19]:

s = '1'
print(s)
for i in range(9):
    s = lookandsay(s)
    print(s)

1
11
21
1211
111221
312211
13112221
1113213211
31131211131221
13211311123113112211

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)

Out[21]:

1.3076923076923077

In [22]:

cste_conway('1', 45)

Out[22]:

1.302964816988995

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))

Premier terme de la suite : 17 ; approximation obtenue : 1.3057126333376172
Premier terme de la suite : 54 ; approximation obtenue : 1.299567840664732
Premier terme de la suite : 23 ; approximation obtenue : 1.299567840664732
Premier terme de la suite : 30 ; approximation obtenue : 1.3018739456515112
Premier terme de la suite : 64 ; approximation obtenue : 1.299567840664732

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)

Out[25]:

[2, 7, 8, 3, 9, 1, 5, 4, 6, 0]

Deux cas particuliers permettent de vérifier le résultat obtenu :

In [26]:

permutation(0)

Out[26]:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In [27]:

permutation(fact(10) - 1)

Out[27]:

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

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.