L = [k for k in range(1, 501)]
import random as rd
A = [rd.random() for k in range(1000)]
def max(L) :
M = L[0]
for i in range(1, len(L)) :
if L[i] > M :
M = L[i]
return M
def max(L) :
M = L[0]
i_M = 0
for i in range(1, len(L)) :
if L[i] > M :
M = L[i]
i_M = i
return M, i_M
u = 1
v = 1
L = [1, 1]
for i in range(2, 100) :
w = u + v
L.append(w)
u = v
v = w
# print(L)
On rappelle que la moyenne d'une liste $\texttt{L = [}x_1, \ldots, x_n \texttt{]}$ est : $\displaystyle \overline{x}_n = \dfrac{1}{n} \ \sum_{i=1}^{n} x_i$.
def moyenne1(L) :
S = 0
for i in range(len(L)) :
S = S + L[i]
return S/len(L)
moyenne1(L)
9.27372692193079e+18
def moyenne2(L) :
return sum(L)/len(L)
moyenne2(L)
9.27372692193079e+18
On rappelle que la variance empirique d'une liste $\texttt{L = [}x_1, \ldots, x_n \texttt{]}$ est : $\displaystyle s_n^2 = \dfrac{1}{n} \ \sum_{i=1}^{n} (x_i - \overline{x}_n)^2$
def variance_emp(L) :
s2 = [(L[i] - moyenne2(L))**2 for i in range(len(L))]
return sum(s2)/len(L)
variance_emp(L)
1.9442300692781128e+39
def troncature(chaine, k) :
n = len(chaine)
return chaine[0:(n-k)]
troncature('Hello world !', 8)
'Hello'
def est_palindrome(mot) :
n = len(mot)
for i in range(n//2) :
if mot[i] != mot[n-1-i] :
return False
return True
est_palindrome('kayak')
True
On pouvait également coder cette fonction de la manière suivante (moins idiomatique de Python)
def est_palindrome(mot) :
n = len(mot)
i = 0
while mot[i] == mot[n-1-i] and i < n//2 : # on rappelle que a//b permet d'obtenir
# le quotient de la division euclidienne de a par b
i = i + 1
return i == n//2
Enfin, testons si la phrase suivante est un palindrome : Esope reste ici et se repose.
S = 'esope reste ici et se repose'
est_palindrome(S)
False
En fait, il s'agit bien d'un palindrome si l'on ôte les espaces. On peut modifier la fonction $\texttt{est\_palindrome}$ de la façon suivante.
def est_palindrome(mot) :
mot = mot.replace(" ", "")
n = len(mot)
for i in range(n//2) :
if mot[i] != mot[n-1-i] :
return False
return True
est_palindrome(S)
True
def bonjour(nom) :
return 'Bonjour ' + str(nom) + ' !'
bonjour('Arnaud')
'Bonjour Arnaud !'
def affiche_avec_cadre(message) :
n = len(message)
cadre = '*' * (n+4)
return print(cadre + '\n' + '* ' + str(message) + ' *' + '\n' + cadre)
affiche_avec_cadre('Le nombre d étoiles dépend de la longueur !')
*********************************************** * Le nombre d étoiles dépend de la longueur ! * ***********************************************
affiche_avec_cadre( bonjour('Arnaud') )
******************** * Bonjour Arnaud ! * ********************
def conway(seq) :
i = 0
res = ''
while i < len(seq) :
compteur = 1
j = i + 1
while j < len(seq) and seq[i] == seq[j] :
compteur = compteur + 1
j = j + 1
res = res + str(compteur) + seq[i]
i = j
return res
sequence = '1'
print(sequence)
for i in range(9) :
sequence = conway(sequence)
print(sequence)
1 11 21 1211 111221 312211 13112221 1113213211 31131211131221 13211311123113112211
Lors de l'exécution de la fonction $\texttt{conway}$, les deux boucles $\texttt{while}$ permettent de parcourir le mot $\texttt{seq}$ exactement une fois. En notant $m$ le nombre de caractères de $\texttt{seq}$, on en déduit que la complexité de cette fonction $\texttt{conway}$ est en $O(m)$.
def cste_conway_approx(seq, n) :
u = seq
v = conway(seq)
for i in range(n) :
u = v
v = conway(u)
return len(v) / len(u)
cste_conway_approx('1', 10)
1.3076923076923077
cste_conway_approx('1', 45)
1.302964816988995
Pour tester l'impact de la valeur initiale choisie pour la suite de Conway sur la valeur de la constante limite obtenue, on choisit cette valeur initiale de façon aléatoire à l'aide de la fonction $\texttt{rd.randint}$ du module $\texttt{random}$.
import random as rd # si l'importation n'a pas déjà été faite dans l'Exercice 1
for i in range(10):
seq = rd.randint(1, 100)
if seq != 22:
print("Premier terme de la suite : "+ str(seq) + " ; approximation obtenue : " +
str(cste_conway_approx(str(seq), 40)))
Premier terme de la suite : 14 ; approximation obtenue : 1.3057126333376172 Premier terme de la suite : 5 ; approximation obtenue : 1.299567840664732 Premier terme de la suite : 81 ; approximation obtenue : 1.3012102296966568 Premier terme de la suite : 57 ; approximation obtenue : 1.299567840664732 Premier terme de la suite : 10 ; approximation obtenue : 1.3057126333376172 Premier terme de la suite : 19 ; approximation obtenue : 1.3057126333376172 Premier terme de la suite : 53 ; approximation obtenue : 1.299567840664732 Premier terme de la suite : 87 ; approximation obtenue : 1.299567840664732 Premier terme de la suite : 70 ; approximation obtenue : 1.299567840664732 Premier terme de la suite : 85 ; approximation obtenue : 1.299567840664732
Remarque :
On a en fait l'approximation suivante de la constante $\lambda$ de Conway :
$$ \lambda \ \simeq \ 1.303577269\ldots $$
def facto(k):
P = 1
for i in range(1, k + 1):
P = P * i
return P
facto(4)
24
def permutation(n) :
res = [-1]*10
lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(9, -1, -1) :
k = n // facto(i) # indice, dans la liste lst, du 1er chiffre de la n-ème permutation
# des éléments de la liste lst
n = n - k * facto(i) # numéro de la nouvelle permutation à chercher : permutation des
# éléments de la liste lst privée de son k-ème élément (c'est le reste dans la
# division euclidienne de n par facto(i))
res[9-i] = lst.pop(k)
return res
permutation(77777)
[0, 2, 9, 5, 1, 3, 7, 8, 6, 4]
Deux cas particuliers permettent de se conforter dans la validité de notre fonction $\texttt{permutation}$ :
permutation(0)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
permutation(facto(10) - 1)
[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.