Définition : conteneur regroupant des éléments, ordonnés, repérés par un indice.

exemples : lst = [ 1, 2, 3 ] lst=["a" , "b" , "c" ] lst = [1, [2,3], "abc" ] etc..

Accès ou modifier des éléments :

lst = [1, 2, 3, 4, 5, 6]
lst[0] vaut 1  lst[3] vaut 4
lst[2:4] vaut [2, 3, 4]
lst[:3] vaut [1, 2, 3] 
lst[3:] vaut [4, 5, 6]
pour modifier : lst[2] = 10 -> lst vaut [1, 2, 10, 4, 5, 6]

Parcourir

Parcours sur les éléments :
lst = [1, 2, 3, 4]
for elem in lst :
    print(elem)
affichera :
1
2
3
4

Parcours sur les indices :
lst = [1, 2, 3, 4]
for i in range(len(lst)) :
    print(lst[i])
affichera le même résultat

méthodes

Ajouter un élément :

Avec append :
lst = [1, 2, 3, 4]
lst.append(5) -> lst vaut [1, 2, 3, 4, 5]

Avec insert : 
lst = [1, 2, 3, 4]
lst.insert(0, "A") -> lst vaut ["A", 1, 2, 3, 4]

Avec pop:
lst = [1, 2, 3, 4]
lst.pop() -> renvoie 4 et lst vaut [1, 2, 3]
lst.pop(0) -> renvoie 0 et lst vaut [2, 3, 4]
lst.pop(1) -> renvoie 2 et lst vaut [1, 3, 4]

Avec remove: 
lst = [1, 2, 3, 4]
lst.remove(1) -> lst vaut [2, 3, 4] (erreur si élément non présent)

avec del :
lst = [1, 2, 3, 4]
del lst[1] -> lst vaut  [1, 3, 4] (retire l'élément d'indice 1)

Avec sort():
lst = [6, 2, 7, 4]
lst.sort() -> ne renvoie rien et modifie lst qui vaut [2, 4, 6, 7]


Avec sorted: 
lst = [6, 2, 7, 4]
sorted(lst) renvoie une nouvelle liste contenant : [2, 4, 6, 7]
en général utilisé ainsi :
lst2 = sorted(lst1)

count():
lst = [6, 2, 7, 4, 2, 1, 2]
lst.count(2) -> renvoie 3 (2 est trois fois dans la liste)

index() :
lst.index(2) renvoie 1 (la première occurrence de  2 est à l'indice 1)
index renvoie une erreur si l'élément n'est pas présent

Initialiser et remplir une liste

Exemple : créer une liste contenant les entiers de 1 à 10 :

Avec liste vide et append :
lst = []
for i in range(1, 11) :
    lst.append(i)

Avec une initialisation à la bonne longueur (ici, 10 éléments) :
lst = [0]*10 (créé une liste contenant 10 fois l'entier 0)
for i in range(1, 11) :
    lst[i] = i

Voila un algorithme qui intervient dans de nombreux autres. Vous en connaissez au moins un cas....
Dans ce type d'algorithme on parcourt une liste en conservant l'index correspondant à un critère.

On pourrait sans peine changer un peu le problème en : trouver la dernière valeur paire, trouver le dernier mot commençant par Z etc...

Exercice de code : Maximum

Créez une fonction idxMax() qui prend comme argument une liste d'éléments ordonnables et renvoie l'indice du plus grand.
 
CONTRAINTE : vous ne devez pas utiliser la fonction max de python, le but est de la reprogrammer !
 
Quelle est la complexité de cet algorithme ?

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

def idxMax(lst : list) -> int: ''' Entrée : une liste d'éléments ordonnables : list Sortie : l'indice du plus grand élément : int ''' #Votre code ici

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

Dans l'exercice ci-dessus, on veut l'indice du max.

Il est crucial de ne pas mélanger INDICE et VALEUR, c'est souvent la cause d'erreurs dans les exercices. On lit souvent des choses comme :

def get_idx_min(lst) :
    """ lst liste non vide"""
    min = 0                     # min est le premier INDICE
    for elem in lst :           # parcours sur les VALEURS
        if elem < min:          # on compare 1 VALEURS et un INDICE ! c'est incorrect
                   min = elem   # maintenant min devient une valeur
    return min

La notion de compteur est fondamentale. Dans \"Compter le nombre de <un truc> \" le mot qui importe est compter.

Exercice de code : Un compteur sachant compter doit savoir compter sans compter

Créez une fonction compter(lst) qui renoie le nombre de multiples de 3 dans la liste lst.

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

def compter(lst : list) -> int: ''' Entrée : Sortie : ''' #Votre code ici

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

chaine = "abcdefabcdef"

Portion de chaine :
chaine[0] vaut "a"
chaine[2:4] vaut "cd"
chaine[:3] vaut "abc"
chaine[2:] vaut "cdefabcdef"
chaine[-1] vaut "f"

Fonctions et méthodes :
longueur : len(chaine) vaut 12
a.find('c') renvoie 2   et a.find('z') renvoie -1
a.replace('a','A') renvoie 'AbcdefAbcdef' et a.replace('a','A',1) renvoie 'Abcdefabcdef'
a.upper() renvoie 'ABCDEFABCDEF'   et 'ABCDEF'.lower vaut 'abcdef'
"a et b".split(" ") renvoie ["a","et","b"]
"a et b, sont 2 nombres".split(",") renvoie ["a et b","sont 2 nombres"]

Parcourir :
for lettre in chaine :
    print(lettre)

Définition : conteneur regroupant des éléments, non ordonnés, repérés par une clé (t-uplet nommé).

Les clé jouent le même rôle que les indices des listes

exemples :
dico = { 1: 1, 2:2, 3:3 } # les clé sont des int, la valeurs aussi
dico ={"cle1":2 , "cle2" : 3, "cle3":4 } # les clés sont des str, les valeurs sont int
eleve = { "nom": "Dupond" , "prenom" : "Jean" , "age":15 } # les clés sont str, les valeurs sont de type str ou int

Accès ou modifier des éléments :

eleve = {"nom": "Dupond" , "prenom" : "Jean" , "age":15}
accéder : 
eleve["nom"] vaut "Dupond"
eleve["age"] vaut 15
eleve[0] n'existe pas, il n'y a pas de clé 0 -> KeyError

modifier : 
eleve["nom"] = "Durand" modifie la valeur de la clé nom

méthodes

Ajouter un élément :

Contrairement aux listes, on n'utilise pas une méthode.
On définit simplement une nouvelle clé :
eleve = { "nom": "Dupond" , "prenom" : "Jean" , "age":15 }
Pour ajouter la clé classe :
eleve["classe"] = "TG8"

on utilise del :
eleve = { "nom": "Dupond" , "prenom" : "Jean" , "age":15 }
del eleve["age"] -> eleve vaut {"nom": "Dupond" , "prenom" : "Jean"}

divers

keys():
eleve = { "nom": "Dupond" , "prenom" : "Jean" , "age":15 }
eleve.keys() renvoie ["nom" , "prenom" , "age"]
ça ressemble à une liste, ce n'en est pas tout à fait une mais on peut l'utiliser comme une liste.

values() :
eleve = { "nom": "Dupond" , "prenom" : "Jean" , "age":15 }
eleve.values() renvoie ["Dupond" , "Jean" , 15]

items() :
eleve = { "nom": "Dupond" , "prenom" : "Jean" , "age":15 }
eleve.items() renvoie [("nom","Dupond") , ("prenom","Jean") , ("age",15) ]
c'est une liste de tuples.

Initialiser et remplir un dict

Exemple : créer notre élève :

eleve = {}
eleve["nom"] = "Dupond"
eleve["prenom"] = "Jean"
eleve["age"] = 15

Parcourir

Parcours sur les clés (de loin le plus fréquent):
eleve = {"nom": "Dupond", "prenom" : "Jean", "age":15 }
for cle in eleve.keys() :
     print("la cle est : ", cle," sa valeur est:", eleve[cle])
affichera :
la cle est : nom sa valeur est: Dupond
la cle est : prenom sa valeur est: Jean
la cle est : age sa valeur est: 15

comme le parcours sur les clés est fréquent on peut écrire :
for cle in eleve :
    print("la cle est : ", cle, " sa valeur est:", eleve[cle])
qui fera la même chose.

Parcours sur les valeurs (assez rare et peut poser problème, on ne sait pas retrouver les clés):
for val in eleve.values() :
    print(" la valeur est:", val)

peut être utilisé quelques fois. Exemple :
ventes = {"geoffroy":12 , "arnaud" : 13 , "gilles":16 , "jean" : 5}
def moyenne_ventes(ventes) : 
   total = 0
   for val in ventes.values() : 
       total += val
   return total / len(ventes)

Mais souvent on préfèrera itérer quand même sur les clés :
def moyenne_ventes(ventes) :
    total = 0
    for cle in ventes.keys() :
        total += vente[cle]
    return total / len(ventes)


Parcours sur les items:
for item in eleve.items() :
    print(item)
affichera :
('nom', 'Dupond')
('prenom', 'Jean')
('age', 15)

dico={"NOM":"LOVELACE" , "Prénom" : "Ada"} est un dictionnaire.

• "NOM" et "Prénom" sont les clés
• "LOVELACE" et "Ada" sont les valeurs associées à ces clés.
• ("NOM" : "LOVELACE") est un elément du dictionnaire.

Par exemple :

Application :

dans l'exercice ci-dessous, la structure de donnée dictionnaire est bien adaptée. A vous de jouer !

Exercice de code : Brin d'ADN complémentaire

Créez une fonction comp_inv() qui prend comme argument une séquence d'ADN sous la forme d'une chaîne de caractères, qui renvoie la séquence complémentaire inverse sous la forme d'une autre chaîne de caractères
 
Par exemple, la chaine complémentaire inverse de AACGCT est TTGCGA :

• les A sont changés en T et inversement
• les C en G et inversement.

 
CONTRAINTE : vous devez utiliser un dictionnaire dont les clefs sont les bases ATCG et les valeurs, les bases de remplacement de chaque clef.
Votre code ne doit contenir aucun test.
 
 
Aide 1! Aide 2!

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

def comp_inv(adn : str) -> str: ''' Entrée : un brin d adn: str Sortie : le brin d ADN complémentaire inverse : str Exemple : >>> comp_inv("AATGA") "TTACT" ''' #Votre code ici

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

Dans cet exercice vous allez avoir besoin de random.shuffle(). Voici un exemple de l'utilisation de cette méthode :

En utilisant étudiant l'exemple ci-dessus, pour bien comprendre le fonctionnement de la méthode .shuffle, vous pouvez aborder l'exercice ci-dessous :

Exercice de code : ADN aléatoire contraint

Créez une fonction seq_alea_2() qui prend comme argument 4 entiers représentant respectivement la longueur de la séquence et les pourcentages de chacune des 3 bases A, T et G (le pourcentage de C etant alors déterminé). La fonction générera aléatoirement une séquence d'ADN qui prend en compte les contraintes fournies en arguments et renverra la séquence sous forme d'une liste. Utilisez cette fonction pour générer aléatoirement une séquence d'ADN de 50 bases contenant 10 % de A, 30 % de T, 50 % de G et 10 % de C. Conseil : la fonction random.shuffle() du module random vous sera utile.

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

import random #Cette ligne est requise pour la validation de votre code, ignorez là. random.seed(codeInitRandom) def seq_alea(taille : int) -> list: ''' Entrée : la taille du brin : int puis 3 int donnant les pourcentages de A T et G Sortie : le brin d ADN : list ''' #Votre code ici

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

Ce sont des listes, dont les éléments sont des listes. Les sous listes peuvent contenir des éléments de types quelconques (numériques, string etc...)

lst = [[11,12,13], [21, 22, 23], [31 , 32, 33]]

lst[1] vaut [21, 22, 23]
et donc :
lst[1][0] vaut 21 (l'élément d'indice 0 dans lst[1])

parcourir la liste de liste et afficher les lignes :

lst = [[11,12,13], [21, 22, 23], [31 , 32, 33]]

# parcours sur les indices :
for num_ligne in range(len(lst)) :
    print(lst[num_ligne])

# on aurait put faire un parcours sur les éléments:
for ligne in lst :
    print(ligne)

lst = [ [11,12,13] , [21, 22, 23] , [31 , 32, 33] ]

les colonnes ne correspondent pas à un élément de la liste
mais peuvent être reconstituées en piochant dans les éléments des
sous listes :
colonne1 = [lst[0][1], lst[1][1], lst[2][1]]

ce n'est pas très joli ! on préfère :
colonne[num_col] = [lst[i][col] for col in range(3)]

| X  .  . |
| .  X  . |
| .  .  X |

lst = [[11, 12, 13], [21, 22, 23], [31 , 32, 33]]

diag1 = [lst[i][i]  for i in range(3)]

| .  .  X |
| .  X  . |
| X  .  . |

lst = [[11,12,13], [21, 22, 23], [31 , 32, 33]]

diag2 = [lst[i][2 - i]  for i in range(3)]

plus généralement, pour un tableau carré de taille n :
col = [lst[i][col] for i in range(n)]
diag1 = [lst[i][i] for i in range(n)]
diag2 = [lst[i][n - i] for i in range(n)]

A venir ultérieurement

Pour éviter de vous tromper :

Nommez l'itérateur soigneusement l'iterateur :

• i pour un parcours avec les indices : for i in range( len(lst) ) :
• caractère (ou lettre) pour un parcours sur les caracteres : for caractere in txt :

Ces deux façons de procéder se retrouvent pour tout les itérables. Un itérable est un type de variable contenant des éléments. Par exemple, les chaînes de caractères, et les listes, sont des itérables : on peut itérer sur les lettres d'un mots, sur les éléments d'une liste etc....

Nous retrouveront donc les mêmes parcours pour les listes, et pour bien d'autres structures plus tard.

Nous allons maintenant chercher non plus un caractère unique, mais une sous chaîne dans la chaine. Tout d'abord, voyons la fonction pythn qui sait déjà faire cela :

Mais nous voulons coder une fonction qui fasse cela. Vous aurez besoin d'étudier cet exemple :

Si vous avez bien compris les 2 exemples ci-dessus, vous pouvez maintenant réussir cet exercice :

Exercice de code : coder in

Sans utiliser in tel que montré dans l'exemple précédent, écrire une fonction estDans(s : str,txt:str) -> bool qui renvoie True si la chaine s apparait dans la chaine txt, et False sinon. On se limitera au cas ou chechée, s, est une chaine de 2 caractères seulement.

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

def search(lettre:str,txt:str) -> bool : # votre code ici

La méthode des chaînes replace() en python permet de remplacer une sous chaine par une autre. Etudiez cet exemple :

Par ailleurs, rappelons le principe de la concaténation et au passage de la réplication :

Exercice de code : remplacer

Sans utiliser replace tel que montré dans l'exemple ci-dessus, écrire une fonction remplacers(s1 : str,s2 : str, txt : str) -> str qui renvoie la chaine txt après remplacement de la première occurence de la chaine s1 par la chaine s2. Si la chaine s1 n'est pas trouvée, la fonction renvoie la chaine de départ.

Attention cet exercice est difficile. Inspirez vous de l'exercice précédent (in) et regardez les sorties attendues, comparez avec ce que vous obtenez. Avec patience vous finirez par y arriver !

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

def remplace(s1:str,s2:str,txt:str) -> str: #votre code ici

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)

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)

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

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)

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.

Exercice à choix multiple

Dans sommesPaires vous aurez besoin d'un compteur ?

Votre choix : Sélectionneznonoui

Correct !

Exercice à choix multiple

Dans sommesPaires vous aurez besoin d'un curseur?

Votre choix : Sélectionneznonoui

Correct !

Exercice à choix multiple

Dans sommesPaires vous aurez besoin d'un accumulateur ?

Votre choix : Sélectionnezouinon

Correct !

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

Exercice à choix multiple

Dans moyPaires vous aurez besoin d'un compteur ?

Votre choix : Sélectionnezouinon

Correct !

Exercice à choix multiple

Dans moyPaires vous aurez besoin d'un curseur?

Votre choix : Sélectionnezouinon

Correct !

Exercice à choix multiple

Dans moyPaires vous aurez besoin d'un accumulateur ?

Votre choix : Sélectionnezouinon

Correct !

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

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

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

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().

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.

Nous allons commencer avec un exemple. Vous rappelez-vous de la fonction abs ? Elle prend seulement un argument (un nombre x), et retourne sa valeur absolue (qui devient x quand x ≥ 0 et -x quand x < 0). La façon de définir cette fonction dans Python est :

Nous pourrions coder la même fonction différemment, sans que cela ne fasse aucune différence dans la façon de l'utiliser.

Dans cette seconde version nous introduisons 2 fois l'instruction return. Ne perdez pas de vue que, dès lors qu'une instruction return est exécutée, la fonction s'arrête (et on reprend le programme appelant là ou on l'avait arrêté).

Notez que dans cette version nous n'initialisons pas la variable valeur absolue, c'est inutile, on n'utilise aucune variable, on renvoie simplement un résultat.

Le langage Python est plus aisé pour démarrer la programmation pour la concision des codes écrits et pour la gestion automatique du typage par l'interpréteur. Cependant, le but est que vous puissiez à terme être capable de faire basculer vos compétences acquises en NSI sur Python vers d'autres langages de programmation.

Comme la plupart des langages de programmation nécessitent la spécification du typage des variables, on vous demandera d'écrire en Python, une fonction en précisant le type de chaque entrée et sortie en suivant le même formalisme ci-dessous :

def nomFonction(argument: type) -> typeRetour:
		blocs des instructions
		return résultat
	

La convention PEP8 donne l'habitude de nommer les fonctions (comme les variables) avec des lettres minuscules et des tirets bas (celui du "8") _.

Exemples : lire_fichier, resoudre_equation, creer_grille_vide etc...

Comme pour les noms de variables, il est absolument recommandé de ne pas utiliser de caractères accentués dans les noms des fonctions.

On préfère toutefois parfois (ou souvent suivant les personnes) la convention dite camelCase qui consiste a écrire en minuscules, mais si le nom est constitué de plusieurs mots, on met une majuscules à tous les mots sauf le premier. Exemples : lireFichier, resoudreEquation, creerGrilleVide etc...

Pour clarifier la fonction, il est conseillé d'utiliser un verbe dans son nom (obtenir, donner, get, set, ...).

Il est important de documenter vos fonctions, c'est-à-dire de décrire en quelques phrases le rôle de la fonction, de donner des informations sur la fonction, le lien entre les entrées et la sortie.

Pour cela, juste en dessous de la première ligne définissant la fonction, il suffit de mettre ses informations de préférence entre """ """ ou entre''' ''' et ''' ; c'est ce que l'on appelle en franglais le docstring de la fonction).
Dans la docstring vous indiquerez ce que sont les paramètres et ce que renvoi la fonction, sous cette forme :

L'intérêt de l'auto-documentation d'une fonction par un texte est double :

• Pour vous : le faire vous oblige à réfléchir au contenu de votre fonction avant de la programmer ; c'est un gain d'efficacité,
• Pour les utilisateurs de votre code (ou pour vous longtemps après avoir programmé la fonction) : Quand on saisit dans la console, après l'exécution de la fonction, l'instruction help(nom de la fonction), Python affiche le docstring de la fonction ce qui nous permet d'avoir des informations sur la fonction en cas d'oubli.

Un compteur en action

Ecrire une fonction qui prend en argument une liste de nombres entiers et renvoie 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) : """ :param lst: list : une liste de nombres entiers :returns: int : Le nombre de multiples de 3 dans la liste """ # Votre code ici

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

Déterminer la médiane d'une série statistique

Rappel de l'algorithme de la médiane

Soit lst=[x₁, x₁, ...x_N] une série de nombres (la série contient N éléments) ordonnée dans l'ordre croissant.

• Si N est pair la médiane est la moyenne des valeurs de rang N/2 et N/2 + 1
• Si N est impair, la médiane est la valeur de rang (N+1)/2

Exercice de code : Déterminer la médiane

Ecrire une fonction qui prend en argument une liste de nombre triée en ordre croissant, et renvoie la médiane de la liste. 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 mediane(lst:list) -> float: # Votre code (avec la docstring) ici

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