P5.1 La boite à outils

Ecrire une fonction qui prend en argument une liste de nombres et renvoi le nombre de multiples de 3 dans cette liste

Exercice de code : Compte les multiples de 3

Ecrire la fonction compterMult3(lst). Une liste lst sera générée pour tester votre code.

Vous devez créer un compte et vous connecter avant de poser une question.

def compterMult3(lst : list) -> int : ''' Entrée : lst une liste de nombres Sortie : n : int : Le nombre de multiples de 3 dans la liste ''' #Votre code ici

Plus d'actions... Réinitialiser code Aide

L'algorithme en pseudo-code

Le pseudo-code est indépendant du langage, c'est une description des opérations a faire pour accomplir une tâche. Il est important de bien distinguer algorithme et code. Lorsque vous écrivez un pseudo-code vous vous libérez des questions de syntaxe pour vous concentrer uniquement sur l'algorithme.

pseudo code de l'algorithme de recherche des multiples de 3 dans une liste :

fonction compterMult3(lst) :
     n ← 0
     pour element dans lst :
          si element%3 =  0 :
                 n ← n+1
          fin de si
     fin de pour
     renvoyer n

Notion de complexité

L'algorithme contient une boucle sur les éléments de la liste lst.

• Avant la boucle on a 1 affection
• La boucle est exécutée N fois (N=longueur de la liste)
• Dans la boucle il y a 1 opération (%), un test, une addition et une affectation. Au total 4 opération élémentaires
• Après la boucle il n'y a rien

On a donc au total, 4N + 1 opérations élémentaires dans ce code. 4N+1 est une fonction linéaire, on dit qu'on a une complexité linéaire et on note C=O(N)

Exemple

Vérifions la complexité de compterMult3()

def compterMult3(lst): n=0 for e in lst : if e%3==0: n+=1 return(n) from time import time # on va mesurer le temps mis pour calculer la moyenne d'une liste de N nombres # avec N=10 puis 100 puis 1000 etc ... jusqu'à 1 million # à chaque fois on multiplie N par 10 et on obtient un temps t # on à par exemple le t100 pour n=100, et le t1000 pour N=100, # et on affichera t1000 / t100 pour voir le rapport entre le deux # pour le 1er calcul on ne peux pas comparer au t précédent, on # le divisera par 1 : tref=1 for N in range(1,6) : lst=[i for i in range(0,10**N)] debut=time() for _ in range(100) : compterMult3(lst) fin=time() print('N=',10**N,'temps=',fin-debut,' ( x ',(fin-debut)/tref,')' ) tref=fin-debut

Vous observez que lorsque le nombre N d'éléments de la liste est multiplié par 10, le temps de calcul est multiplié aussi par un facteur du même ordre de grandeur. Nous observons bien ici une complexité linéaire.

Exercice de code : Calcul de moyenne

Ecrire la fonction somme(lst). Une liste lst sera générée pour exécuter votre code.

Vous devez créer un compte et vous connecter avant de poser une question.

def moyenne(lst) : ''' Entrée : lst : list Sortie : La moyenne des éléments de la liste : float ''' #Votre code ici

Plus d'actions... Réinitialiser code Aide

Ici il n'est pas question de compter, mais de faire la somme. Nous avons déjà vu cet algorithme plusieurs fois.

pseudo code de l'algorithme de la moyenne :

fonction moyenne(lst) :
     somme ← 0
     pour element dans lst :
          somme ← somme + element
     fin de pour
     renvoyer somme/len(lst)

Notion de complexité

L'algorithme contient une boucle sur les éléments de la liste lst.

• Avant la boucle on a 1 affection
• La boucle est exécutée N fois (N=longueur de la liste)
• Dans la boucle il y a une addition et une affectation. Au total 2 opération élémentaires
• Après la boucle il n'y a rien

On a donc au total, 2N + 1 opérations élémentaires dans ce code. 2N+1 est une fonction linéaire, on dit ici aussi qu'on a une complexité linéaire et on note C=O(N)

Exemple

Vérifions la complexité de moyenne()

def moyenne(lst): somme=0 for e in lst : somme+=e return(somme/len(lst)) from time import time # on va mesurer le temps mis pour calculer la moyenne d'une liste de N nombres # avec N=10 puis 100 puis 1000 etc ... jusqu'à 1 million # à chaque fois on multiplie N par 10 et on obtient un temps t # on à par exemple le t100 pour n=100, et le t1000 pour N=100, # et on affichera t1000 / t100 pour voir le rapport entre le deux # pour le 1er calcul on ne peux pas comparer au t précédent, on # le divisera par 1 : tref=1 for N in range(1,6) : lst=[i for i in range(0,10**N)] debut=time() for _ in range(100) : moyenne(lst) fin=time() print('N=',10**N,'temps=',fin-debut,' ( x ',(fin-debut)/tref,')' ) tref=fin-debut

Vous observez là encore que lorsque le nombre N d'éléments de la liste est multiplié 10, le temps de calcul est multiplié aussi par un facteur du même ordre de grandeur. Nous observons donc encore bien ici une complexité linéaire.

Exercice de code : Indice du maximum

Ecrire la fonction idxMax(lst). Une liste lst sera générée pour exécuter votre code.

Vous devez créer un compte et vous connecter avant de poser une question.

def idxMax(lst) : ''' Entrée : une liste de nombre (list) Sortie : L'indice du plus grand élément de la liste (int) ''' #Votre code ici

Plus d'actions... Réinitialiser code Aide

Ici il n'est pas question de compter ou de sommer, mais de mémoriser la dernière position du max parmi les éléments déjà parcourus.

pseudo code de l'algorithme de recherche de l'indice du max des éléments d'une liste :

fonction idxMax(lst) :
     idxMax ← 0
     pour i allant de 1 à len(lst)-1 :
         si lst[i] > lst[idxMax] :
               idxMax ← i
         fin de si
     fin de pour
     renvoyer n

La boucle va de 1 à len(lst) -1 si les indices vont de 0 à len(lst)-1 comme en python. on écrit i in range( 1,len(lst) )

remarque : Dans d'autres langages les indices vont de 1 à len(lst), dans ce cas la boucle ira de 2 à len(lst).

Notion de complexité

L'algorithme contient une boucle sur les éléments de la liste lst (en partant du 2ème)

• Avant la boucle on a 1 affection
• La boucle est exécutée N-1 fois (N=longueur de la liste)
• Dans la boucle il y a une comparaison et une affectation. Au total 2 opération élémentaires
• Après la boucle il n'y a rien

On a donc au total, 2N + 1 opérations élémentaires dans ce code. On a de nouveau une complexité linéaire et on note C=O(N)

Exemple

Vérifions la complexité de idxMax()

def idxMax(lst): idxMax=0 for i in range(1,len(lst)) : if lst[i]>lst[idxMax]: idxMax=i return idxMax from time import time tref=1 for N in range(1,6) : lst=[i for i in range(0,10**N)] debut=time() for _ in range(100) : idxMax(lst) fin=time() print('N=',10**N,'temps=',fin-debut,' ( x ',(fin-debut)/tref,')' ) tref=fin-debut

Vous observez là encore que lorsque le nombre N d'éléments de la liste est multiplié 10, le temps de calcul est multiplié aussi par un facteur du même ordre de grandeur. Nous observons donc encore bien ici une complexité linéaire.

Variante

Il existe une variante (qu'on retrouve généralement dans tous les algorithme utilisant un curseur) à l'algorithme que nous venons de voir.

Si, au lieu de l'indice de la valeur maxi, on cherche la valeur elle même, l'algorithme est légèrement différent.
Ecrivez le pseudo-code modifié pour satisfaire cette recherche, puis codez le ici :

Exercice de code

Ecrire la fonction valMax(lst) qui renvoie la valeur max d'une liste
ATTENTION : vous ne pouvez pas utiliser range dans cet exercice !

Vous devez créer un compte et vous connecter avant de poser une question.

def valMax(lst : list) -> float : ''' Renvoie la plus grande valeur de la liste lst ''' # modifier le code ci-dessous qui renvoie l'indice idxMax=0 for i in range(1,len(lst)) : if lst[i]>lst[idxMax]: idxMax=i return idxMax

Plus d'actions... Réinitialiser code Aide

pseudo code de l'algorithme de recherche du max des éléments d'une liste :

fonction valMax(lst) :
     valMax ← lst[0]
     pour i dans lst[1:] :
         si i > valMax :
               valMax ← i
         fin de si
     fin de pour
     renvoyer n

Ecrire l'algorithme d'une fonction sommePaires(lst) qui renvoie la somme des valeurs paires d'une liste.

Ecrire un second algorithme pour moyPaires qui renvoie la moyenne des valeurs paires d'une liste.

N'oubliez pas que vous pouvez visualiser l'exécution de votre code pour vous aider à le mettre au point.

Exercice de code : moyenne coefficientée

Ecrire une fonction moyPondee(notes , coefs) qui renvoie la moyenne coefficientée.

Vous devez créer un compte et vous connecter avant de poser une question.

def moyPonderee(notes : list , coefs : list ) -> list : ''' notes et listes sont 2 listes de même longueur, contenant l'une les notes et l'autre les coeficient (respectifs) des notes d'un élève ''' # a vous ! notes=[12 , 13, 6 , 16] coefs=[1, 4 , 1, 2] print(moyPonderee(notes,coefs))

Plus d'actions... Réinitialiser code Aide

Nous avons déjà traité la question de la recherche d'un caractère dans un texte. Nous allons ici traiter un problème assez similaire mais un peu plus délicat : chercher une chaine dans une autre. Pour plus de clarté, nous appelerons mot la chaine recherchée, et texte la chaine dans laquelle on effectue la recherche.

Commencez par regarder la vidéo ci-dessous pour comprendre le problème.

Ecrivons le pseudo code :

fonction cherchePattern(mot,texte) :
     pos -> -1
     idx -> 0
     tant que idx < len(texte)-len(mot) and pos = -1
          if texte[idx:idx+len(mot)] == mot : pos = idx
          idx = idx + 1
     fin de tant que
     renvoyer pos

Exercice de code : reverse avec pop

Vous devez créer un compte et vous connecter avant de poser une question.

def searchtxt(mot: str , txt : str ) -> int : # votre code ici

Plus d'actions... Réinitialiser code Aide

On veut retourner une liste (c'est à dire ranger ses éléments dans l'ordre inverse) et on va procéder par ajouter successifs (il existe d'autres façons de le faire).
L'algorithme est assez simple :

fonction retourner(lst) :
    lstReverse = [ ]
    tant que lst non vide :
        retirer le dernier elem de lst et l'ajouter à la fin de  lstReverse
    fin de pour
    renvoyer lstReverse

Coder ceci en python ne pose pas de grosse difficulté, mais il faut se souvenir de la méthode pop et de son usage....
Voici un code qui va te servir d'exemple pour l'exercice.

Rappel :
lst = [1,2,3]
a = lst.pop()
-> a=3 et maintenant lst=[1,2]
lst.pop() retire le dernier élément de la liste lst et renvoie sa valeur.

Exercice de code : reverse avec pop

Vous devez créer un compte et vous connecter avant de poser une question.

def reversePOP(lst: list ) -> list : # votre code ici lst=[3,1,6,7,2] print(reversePOP(lst))

Plus d'actions... Réinitialiser code Aide

Au lieu de append, on pourrait aussi utiliser une concaténation de liste : lstR = lstR + [val] donnera le même résultat, essaye les deux façons.
(attention : en réalité ces deux façon de procéder ne sont pas équivalentes. Elle donnent le même résultat et pour cette année nous n'entreront pas dans les détails sr la différence de traitement entre les deux)

On pourrait même ne rien ajouter et ne rien concaténer :

def reversePOP(lst: list ) -> list :
    lstR=[0] * len(lst) # initialise une liste avec len(lst) 0
    idx=0
    while len(lst) > 0:
        e=lst.pop()
        lstR[idx]=e
        idx+=1
    return lstR

Et là encore, le résultat est le même mais les opérations réalisées ne sont pas les même en réalités. Et ici aussi nous n'entreront pas cette année dans les détails.

Toutefois nous aurions put écrire aussi bien cet algorithme :

fonction retourner(lst) :
    lstReverse = [ ]
    tant que lst non vide :
        retirer le premier elem de lst et l'ajouter au début de  lstReverse
    fin de pour
    renvoyer lstReverse

Tu pourra coder ce second algorithme en utilisant lst.pop(0) qui retire l'élément d'indice 0 et lstR.insert(0,val) qui insère val en tête de liste.

On pourrait aussi utiliser une concaténation de liste : lstR = [val] + lstR donnera le même résultat, essaye les deux façons, et surtout remarque bien :

ajouter en tête : lst.insert(0,val) ou lst=[val] + lst
ajouter en queue : lst.append(val) ou lst=lst+[val]

retirer en tête : val = lst.pop(0)
retirer en queue :val = lst.pop()

Rappel :
lst = [1,2,3]
lst.insert(0,7)
-> Maintenant lst vaut [7,1,2,3]

Exercice de code : reverse avec insert

Vous devez créer un compte et vous connecter avant de poser une question.

def reverseInsert(lst: list ) -> list : # votre code ici lst=[3,1,6,7,2] print(reverseInsert(lst))

Plus d'actions... Réinitialiser code Aide

Ou avec l'autre façon, sans rien changer à l'algorithme, mais en remplaçant insert par une concaténation de liste :

Rappel :
lst = [1,2,3]
lst [7]+lst
-> Maintenant lst vaut [7,1,2,3]

Exercice de code : reverse sans pop et sans insert

Vous devez créer un compte et vous connecter avant de poser une question.

def reverseConcat(lst: list ) -> list : # votre code ici lst=[3,1,6,7,2] print(reverseConcat(lst))

Plus d'actions... Réinitialiser code Aide

Complexité

Peut tu estimer la complexité des codes de retournement ? Sont ils tous équivalent ?

Vous aller programmer ici une fonction tri(lst) qui va trier une liste. L'algorithme utilisé, que nous reverrons plus tard dans une autre forme, est le suivant :

fonction triInsertion(lst) :
    listTriee=[]
    Tant que longueur(lst) > 0 :
        rechercher l'indice du min dans lst
        retirer cet élément (avec pop) et l'ajouter (en queue) dans listeTrie
    fin de tant que
    renvoyer listeTriee
(la fonction idxMin(list) est disponible dans cet exercice)

Exercice de code

Vous devez créer un compte et vous connecter avant de poser une question.

def tri(lst: list ) -> list : ''' documentez ''' # votre code ici lst=[3,1,6,7,2] print(tri(lst))

Plus d'actions... Réinitialiser code Aide

Dans ce code, que vous venez de faire, on a pas vraiment de curseurs (il y en a cependant un, caché dans la fnction idxMin que vous avez utilisé), d'accumulateur, ou de compteur. En effet ici on ne compte rien, on ne somme rien, et on ne localise rien.

L'ajout successif d'élément dans une liste est un autre outil indispensable que vous serez souvent amenés à utiliser.

Estimons la complexité de cet algorithme expérimentalement avec time().

Exemple

def tri(lst: list ) -> list : lstTriee=[] while len(lst) > 0: i=idxMin(lst) e=lst.pop(i) lstTriee.append(e) return lstTriee def idxMin(lst : list) -> int: idxMin=0 for i in range(1,len(lst)) : if lst[i] < lst[idxMin]: idxMin=i return idxMin from time import time tref=1 for N in (10,20,40,80,160,320,640,1280,2560) : lst=[i for i in range(N,0,-1)] debut=time() tri(lst) fin=time() print('N=',N,'dt= ',fin-debut,' x ',(fin-debut)/tref) tref=fin-debut

En raison de limitations sur ce site, il n'est pas pssible de travailler sur des listes très grandes. Néanmoins, ici, on a pris une séries de valeurs de N allant de 10 à 2560. A chaque fois on multiplie N par 2. Le temps de calcul évolue d'abord linéairement pour les petites valeurs de N mais rapidement on voit que quand N est multiplié par 2, le temps est multiplié par 4 (2² !)

La complexité semble donc plutot propotionelle à N² dans cet exemple.

Combien de fois est exécutée la boucle while ? Combien d'opération dans cette boucle while ?

La réponse est que la boucle while est exécutée N fois, mais dans la boucle, on appelle idxMin. idxMin a une complexité en O(N), mais comme la liste lst est raccourcie au fur et a mesure, c'est un peu compliqué....

Au premier tour, idxMin cherche dans une liste de longueur N

A second tour dans une liste de longueur N-1

Au troisième tour, dans une liste de longueur N-1

etc... jusqu'au dernier tour, ou il ne reste qu'un élément.

si le temps de idxMin est N, alors le temps de tout les appels est :

1 + 2 + ... + N = N(N+1)/2 = N² /2 + N/2

pour de grandes valeurs de N, N² >> N, la complexité sera proportionnelle à N². On parle ici de complexité quadratique.