1A.e - Correction de l’interrogation écrite du 26 septembre 2014¶
chaîne de caractères, tri, fonction
Enoncé 1¶
Q1¶
Ecrire une fonction qui retourne 1 si \(n\) est un multiple de 2014.
[2]:
def mul2014(n):
return 1 if n % 2014 == 0 else 0
print(mul2014(2014), mul2014(2015))
1 0
Pour cette question, quelques élèves ont vérifié que n
était plus petit que 2014 d’abord. Ce n’est pas vraiment la peine.
Q2¶
Calculer le minimum des cosinus des entiers de 1 à 10.
[3]:
import math
min(math.cos(i) for i in range(1, 11))
[3]:
-0.9899924966004454
range(0,10)
va de 0 à 10 exclu.
[4]:
list(range(0, 10))
[4]:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Q3¶
Ecire une fonction qui vérifie qu’une chaîne de caractères est symétrique (ex: kayak
).
[5]:
def symetrie(s):
i = 0
j = len(s) - 1
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
print(symetrie("kayak"), symetrie("kakaks"))
True False
Sur cette question, on fait régulièrement deux erreurs lorsqu’on commence à programmer :
Le dernier indice est
len(s)-1
et nonlen(s)
. Le premier indice est 0.Il ne sert à rien que
i
aille de 0 àlen(s)-1
, aller de 0 àlen(s)//2
suffit.
Enoncé 2¶
Q1¶
Ecrire une fonction qui retourne 1 si une chaîne de caractères contient un A, 0 sinon.
[6]:
def contient_A(s):
return 1 if "A" in s else 0
print(contient_A("e"))
0
Utiliser une boucle n’était pas nécessaire, un simple test suffit.
Q2¶
Calculer \(\sum_{i=1}^{10} \frac{x^{2i}}{\sin i}\).
[7]:
import math
x = 0.3
sum(x ** (2 * i) / math.sin(i) for i in range(1, 11))
[7]:
0.12093467645909634
Q3¶
Ecrire qu’une fonction qui vérifie si un tableau est trié.
[8]:
def est_trie(tab):
for i in range(1, len(tab)):
if tab[i - 1] > tab[i]:
return False
return True
est_trie([1]), est_trie([1, 2, 3]), est_trie([1, 2, 3, 0])
[8]:
(True, True, False)
Quelques élèves ont écrit quelque chose comme :
[9]:
def est_trie(tab):
res = tab.copy()
res.sort()
return res == tab
Bien que ceci soit tout-à-fait correct, le fait de trier une copie du tableau nécessite des calculs inutiles. Le coût d’un tri est en \(O(n \ln n)\) alors que tester si le tableau est trié est au pire de \(O(n)\) puisqu’il suffit de le parcourir une fois. J’ajoute une dernière remarque : sans copie la fonction est_trie
retourne toujours vrai.
[10]:
def est_trie_nocopy(tab):
res = tab
res.sort()
return res == tab
t = [0, 1, 2]
print(est_trie(t), est_trie_nocopy(t))
t = [0, 1, 2, 0]
print(est_trie(t), est_trie_nocopy(t))
True True
False True
La raison est l’instruction res = tab
crée une autre variable res
mais l’instruction n’implique pas la copie de la liste. Elle ne fait que donner un autre nom à la même liste. Ainsi :
[11]:
t = [0, 1, 2]
t2 = t
t2[0] = 1000000000
t, t2
[11]:
([1000000000, 1, 2], [1000000000, 1, 2])
Modifier la liste t
revient à modifier la liste t2
puisque ce sont les mêmes. Cela est dû au fait que le langage Python ne copie les listes, les dictionnaires ou les instances de classes que si ces copies sont demandées explicitement. Par défaut, le langage évite toute copie.
[12]: