dictionnaire et coût algorithmique
from jyquickhelper import add_notebook_menu
add_notebook_menu()
Ecrire une fonction qui prend une chaîne de caractères en argument et la retourne sans ses voyelles.
def pas_de_voyelle(mot):
s = ""
for c in mot :
if c not in "aeiouy" :
s += c
return s
pas_de_voyelle("bonjour"), pas_de_voyelle("au revoir")
('bnjr', ' rvr')
Cette réponse n'est qu'une réponse parmi d'autres. Certains utilisaient la méthode replace, d'autres un test c == "a" or c == "e" ...
.
Transformer une matrice représentée sous forme de double liste (exemple : [[0,1,0],[0,0,1]]
) en un dictionnaire dont les clés sont les coordonnées et les valeurs les coefficients (soit autant d'éléments que de valeurs non nulles).
mat = [[0,1,0],[0,0,1]]
mat_dict = { }
for i,line in enumerate(mat) :
for j,c in enumerate(line) :
if c != 0 :
mat_dict[i,j] = c
mat_dict
{(0, 1): 1, (1, 2): 1}
Pour cette question, le code écrit fonction doit fonctionner pour n'importe quelle matrice.
Calculer $\sum_{i=1}^{10} \frac{1}{i}$
sum ( 1/i for i in range(1,11) )
2.9289682539682538
Quel le coût du programme suivant en $O(N)$ ?
from math import log
s = 0
N = 100
while N > 1 :
for i in range(1, N):
s += log(i)
N //= 2
print(s)
581.4676254832484
La première boucle s'exécute pour les valeurs $N$, $N/2$, $N/4$, ... jusqu'à ce que $N \leqslant 1$. La boucle imbriquée fait la somme des $log$ de 1 à $N$. Le nombre des opérations est en $O(N + N/2 + N/4 + ...)$, soit quelque chose comme $N \sum_{i=1}^{\ln_2 N} \frac{1}{2^i} \leqslant N \sum_{i=1}^{\infty} \frac{1}{2^i} \leqslant 2N$ (c'est une somme géométrique). On vérifie avec le code suivant qui compte le nombre de fois où on ajoute un logarithme.
def calcul(N):
s = 0
c = 0
while N > 1 :
for i in range(1, N):
s += log(i)
c += 1
N //= 2
return c
for i in range(10000,100000, 10000) :
print( i, calcul(i), i * 2 )
10000 19981 20000 20000 39980 40000 30000 59978 60000 40000 79979 80000 50000 99978 100000 60000 119977 120000 70000 139977 140000 80000 159978 160000 90000 179974 180000
On considère un mot abcdef
, puis on construit un autre mot selon le schéma :
abcdef
$\rightarrow$ afbecd
kayak
$\rightarrow$ kkaay
def strange(mot):
s = ""
for i in range(len(mot)//2) :
s += mot[i] + mot[-i-1]
if len(mot)%2 == 1 :
s += mot[len(mot)//2]
return s
strange("abcdef"), strange("kayak")
('afbecd', 'kkaay')
Retourner un dictionnaire : les clés deviennent les valeurs et les valeurs deviennent les clés (on suppose que les clés et valeurs sont uniques).
dictionnaire_depart = { "cle1":"valeur1", "cle2":"valeur2" }
dictionnaire_retourne = { }
for k,v in dictionnaire_depart.items():
dictionnaire_retourne[v] = k
dictionnaire_retourne
{'valeur2': 'cle2', 'valeur1': 'cle1'}
dictionnaire_depart = { "cle1":"valeur1", "cle2":"valeur2" }
print ( dictionnaire_depart.items() )
print ( list ( dictionnaire_depart.items() ) )
dict_items([('cle1', 'valeur1'), ('cle2', 'valeur2')]) [('cle1', 'valeur1'), ('cle2', 'valeur2')]
Le python est un langage paresseux car très lent. Il faut lui demander de façon explicite de construire un ensemble ou de copier un ensemble. Par défaut, il ne copie jamais un dictionnaire ou une liste et il préfère retourner un itérateur plutôt qu'une copie d'un ensemble. La plupart du temps, on ne s'en aperçoit pas à moins de vouloir accéder à un élément précis de l'ensemble :
dictionnaire_depart.items() [0]
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-24-68beadeaff45> in <module>() ----> 1 dictionnaire_depart.items() [0] TypeError: 'dict_items' object does not support indexing
La fonction ensemble
suivante retourne une liste d'éléments, la fonction iterateur
retourne une façon de parcourir un ensemble. On appelle ce type ce fonction un générateur.
def ensemble(a,b):
res = [ ]
while a < b :
res.append ( a )
a += 1
return res
def iterateur(a,b):
while a < b :
yield a
a += 1
print( iterateur(0,10) )
print( ensemble(0,10) )
<generator object iterateur at 0x0000000006F305E8> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
On ne peut accéder aux éléments d'un générateur car cela n'a pas de sens :
iterateur(0,10) [0]
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-26-86215c660090> in <module>() ----> 1 iterateur(0,10) [0] TypeError: 'generator' object is not subscriptable
Mais on peut parcourir les éléments générés :
for x in iterateur(0,10):
print(x)
0 1 2 3 4 5 6 7 8 9
Calculer $\frac{1}{1000} \sum_{i=1}^{1000} e^{ \frac{i}{1000} }$.
from math import exp
1/1000 * sum ( exp ( i / 1000 ) for i in range(1,1001) )
1.7191411125634257
Quel le coût du programme suivant en $O(N)$ ?
from math import log
s = 0
ii = 1
N = 7
for i in range(1,N):
ii *= 2
for k in range(1,ii):
s += log(k)
print(s)
317.3177321667311
A chaque itération $i$, on calcule $2^i$ logarithmes. On fait $N$ itérations soit $1 + 2 + 4 + ... + 2^N$ calculs, c'est-à-dire environ $O(1 + 2^1 + 2^2 + 2^3 + ... + 2^N) = O(2^{N+1}) = O(2^N)$ (c'est une somme géométrique).
from math import log
def calcul(N):
s = 0
ii = 1
c = 0
for i in range(1,N):
ii *= 2
for k in range(1,ii):
s += log(k)
c += 1
return c
for N in range(10,20):
print(calcul(N), 2**N)
1013 1024 2036 2048 4083 4096 8178 8192 16369 16384 32752 32768 65519 65536 131054 131072 262125 262144 524268 524288