.. _interrorapide20minutes201410rst: ============================================================== 1A.e - Correction de l’interrogation écrite du 10 octobre 2014 ============================================================== .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/exams/interro_rapide_20_minutes_2014_10.ipynb|*` dictionnaire et coût algorithmique .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: Enoncé 1 ~~~~~~~~ Q1 ^^ Ecrire une fonction qui prend une chaîne de caractères en argument et la retourne sans ses voyelles. .. code:: ipython3 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") .. parsed-literal:: ('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" ...``. Q2 ^^ 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). .. code:: ipython3 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 .. parsed-literal:: {(0, 1): 1, (1, 2): 1} Pour cette question, le code écrit fonction doit fonctionner pour n’importe quelle matrice. Q3 ^^ Calculer :math:`\sum_{i=1}^{10} \frac{1}{i}` .. code:: ipython3 sum ( 1/i for i in range(1,11) ) .. parsed-literal:: 2.9289682539682538 Q4 ^^ Quel le coût du programme suivant en :math:`O(N)` ? .. code:: ipython3 from math import log s = 0 N = 100 while N > 1 : for i in range(1, N): s += log(i) N //= 2 print(s) .. parsed-literal:: 581.4676254832484 La première boucle s’exécute pour les valeurs :math:`N`, :math:`N/2`, :math:`N/4`, … jusqu’à ce que :math:`N \leqslant 1`. La boucle imbriquée fait la somme des :math:`log` de 1 à :math:`N`. Le nombre des opérations est en :math:`O(N + N/2 + N/4 + ...)`, soit quelque chose comme :math:`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. .. code:: ipython3 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 ) .. parsed-literal:: 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 Enoncé 2 ~~~~~~~~ Q1 ^^ On considère un mot ``abcdef``, puis on construit un autre mot selon le schéma : - 1ère lettre, dernière lettre, 2ème lettre, avant-dernière lettre, 3ème lettre, … - Exemple 1 : ``abcdef`` :math:`\rightarrow` ``afbecd`` - Exemple 2 : ``kayak`` :math:`\rightarrow` ``kkaay`` .. code:: ipython3 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") .. parsed-literal:: ('afbecd', 'kkaay') Q2 ^^ 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). .. code:: ipython3 dictionnaire_depart = { "cle1":"valeur1", "cle2":"valeur2" } dictionnaire_retourne = { } for k,v in dictionnaire_depart.items(): dictionnaire_retourne[v] = k dictionnaire_retourne .. parsed-literal:: {'valeur2': 'cle2', 'valeur1': 'cle1'} La méthode `items `__ retourne un `itérateur `__ et non une liste. Un itéreur n’est pas un ensemble mais une façon de parcourir tous les éléments d’un ensemble. .. code:: ipython3 dictionnaire_depart = { "cle1":"valeur1", "cle2":"valeur2" } print ( dictionnaire_depart.items() ) print ( list ( dictionnaire_depart.items() ) ) .. parsed-literal:: 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 : .. code:: ipython3 dictionnaire_depart.items() [0] :: --------------------------------------------------------------------------- TypeError Traceback (most recent call last) in () ----> 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 `__. .. code:: ipython3 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) ) .. parsed-literal:: [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 : .. code:: ipython3 iterateur(0,10) [0] :: --------------------------------------------------------------------------- TypeError Traceback (most recent call last) in () ----> 1 iterateur(0,10) [0] TypeError: 'generator' object is not subscriptable Mais on peut parcourir les éléments générés : .. code:: ipython3 for x in iterateur(0,10): print(x) .. parsed-literal:: 0 1 2 3 4 5 6 7 8 9 Q3 ^^ Calculer :math:`\frac{1}{1000} \sum_{i=1}^{1000} e^{ \frac{i}{1000} }`. .. code:: ipython3 from math import exp 1/1000 * sum ( exp ( i / 1000 ) for i in range(1,1001) ) .. parsed-literal:: 1.7191411125634257 Q4 ^^ Quel le coût du programme suivant en :math:`O(N)` ? .. code:: ipython3 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) .. parsed-literal:: 317.3177321667311 A chaque itération :math:`i`, on calcule :math:`2^i` logarithmes. On fait :math:`N` itérations soit :math:`1 + 2 + 4 + ... + 2^N` calculs, c’est-à-dire environ :math:`O(1 + 2^1 + 2^2 + 2^3 + ... + 2^N) = O(2^{N+1}) = O(2^N)` (c’est une somme géométrique). .. code:: ipython3 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) .. parsed-literal:: 1013 1024 2036 2048 4083 4096 8178 8192 16369 16384 32752 32768 65519 65536 131054 131072 262125 262144 524268 524288