Définition ALGORITHME : un algorithme est un ensemble fini (au sens "pas infini") d'instructions précises permettant de résoudre une classe de problèmes. L'algorithme doit être écrit de façon suffisamment clair pour lever toute ambiguïté, et être transposable facilement dans un langage de programmation.
Le mot classe est ici important : on doit pouvoir résoudre un type de problèmes et pas un cas unique. Si l'algorithme ne fonctionne que pour UN cas particulier, on ne parlera pas d'algorithme.
De façon plus précise, un algorithme est un ensemble fini d'instructions précises effectuant des calculs et/ou des modifications sur des entrées pour produire une sortie.
ENTREE(S) → Algorithme → SORTIE
Comme vous pouvez le voir, cela ressemble fort à ce qu'on pourrait définir comme une fonction. Ce n'est pas un hasard, nous le verrons en Terminale.
Gérard Berry parle des algorithmes comme étant des méthodes à appliquer sans réflechir, en suivant machinalement le déroulement et les ordres.
On sépare réflexion et exécution.
La réflexion est utilisée par l'informaticien ou l'informaticienne lors de l'élaboration de l'algorithme.
Lors du déroulement de l'algorithme, l'ordinateur exécute. Point.
En réalité, cette définition est floue. Elle comporte beaucoup de non-dits. Nous verrons une définition plus formelle en Terminale.
(Rappel) B - Algorithmique
L'algorithmique consiste à étudier des problèmes en vue de les résoudre à l'aide d'un algorithme le plus efficace possible.
On cherche donc :
à estimer la rapidité d'exécution de l'algorithme.
Cela revient à connaître le coût de l'algorithme.
à vérifier que la réponse éventuelle soit juste.
Cette vérification se nomme la preuve de correction.
à vérifier qu'il s'arrête bien sur n'importe quelle entrée fournie.
Cette vérification se nomme la preuve de terminaison.
(Rappel) C - Bilan des coûts
Problème facile
Facile en informatique : peut répondre en un temps raisonnable.
Le coût constant
Le coût logarithmique
Le coût linéaire (lié à n)
Le coût quadratique (lié à n2)
Problème difficile
Difficle en informatique : temps de calcul déraisonnable.
Le coût exponentiel (lié à xn) : avec un tel coût, on estime que l'algorithme n'est pas exploitable à grande échelle. Il va mettre trop de temps pour répondre.
Le coût factoriel (lié à la fonction factorielle n!) : encore moins exploitable.
(Rappel) D - Unités courantes : k M G T
Sous-unité
Valeur en décimal
Pourquoi ?
Un kilo (k) représente 103
1 000
Un Méga (M) représente 106
1 000 000
un million, soit 1000 x 1 000
Un Giga (G) représente 109
1 000 000 000
un milliard, soit 1000 x 1 000 000
Un Téra (T) représente 1012
1 000 000 000 000
mille milliards, soit 1000 x 1 000 000 000
On voit donc que chaque sous-unité représente 1000 fois plus que la précédente.
Passons à la nouveauté :
1.1 Algorithme implémenté sous forme de fonction
Implémentation
L'implémentation est le nom qu'on donne au passage de :
l'idée abstraite de l'algorithme (sur papier) à
son exécution concrète à l'aide d'un programme (en machine)
Or, vous connaissez déjà un objet informatique qui accepte des valeurs en entrée et qui renvoie une réponse en sortie : les fonctions.
⇒
algo MAXIMUM
⇒
[5, 10, 50, 0, 20]
50
⇒
fonction maximum()
⇒
[5, 10, 50, 0, 20]
50
Exemple
L'algorithme du MAXIMUM est ainsi déjà implémenté en Python à travers la fonction native max() :
>>> max([5, 10, 50, 0, 20])
50
Conclusion
On implémentera les algorithmes sous forme de fonctions :
Les ENTREES : les paramètres de la fonction
SORTIE : le retour de la fonction
Pourquoi est-il important d'optimiser les algorithmes alors que les machines actuelles sont très puissantes ?
A cause de l'augmentation énorme du volume de données à traiter : un algorithme ne pourra être implémenté en machine que s'il répond en un temps acceptable.
Vous êtes chef de service. On vous propose de choisir entre
Investir dans un équipement informatique Tip Top ou
Investir dans le salaire d'un.e nouvel.le informaticien.ne Tip Top. Quelqu'un qui a pris NSI dès la 1er. Si si.
Alors ? Votre choix ?
Imaginons qu'on veuille identifier quelqu'un dans une base de données comportant n fiches.
Cas 1
INFORMATICIEN NORMAL : l'algorithme créé par l'informaticien a besoin de n3 opérations pour identifier la personne dans la base de données qui comporte n fiches.
ORDINATEUR TIP-TOP : l'ordinateur est capable de faire 200 Giga comparaisons par seconde.
On peut en déduire le temps mis par l'ordinateur pour identifier les personnes en fonction de la taille de la base de données :
t = (n3) / (200.109)
En Python :
t = n**3 / 200E9
01 ✎° Calculer les temps mis pour réaliser cette tâche si la base de données possède
5000 fiches (n = 5.103),
5 millions de fiches (n = 5.106),
5 milliards de fiches (n = 5.109).
...CORRECTION...
Pour n = 5000 fiches :
t = (5E3)**3 / 200E9 = 0,625 s
Pour n = 5 millions de fiches :
t = (5E6)**3 / 200E9 = 625000000 s
t = (5E6)**3 / (200E9*3600*24*365) = 19.8 ans
Pour n = 5 milliards de fiches :
t = (5E9)**3 / 200E9 = 6,25.1017 s
t = (5E9)**3 / (200E9*3600*24*365) = 19 818 619 990 ans !
Cas 2
INFORMATICIEN TIP-TOP : l'algorithme créé par l'informaticien a besoin de n2 comparaisons pour identifier la personne dans la base de données qui comporte n fiches.
ORDINATEUR MEDIOCRE : l'ordinateur est capable de faire 30 Mega comparaisons par seconde...
On peut en déduire le temps mis par l'ordinateur pour identifier les personnes en fonction de la taille de la base de données :
t = (n2) / (30.106)
En Python :
t = n**2 / 30E6
02 ✎° Calculer les temps mis pour réaliser cette tâche si la base de données possède
5000 fiches (5.103),
5 millions de fiches (5.106),
5 milliards de fiches (5.109).
...CORRECTION...
Pour 5000 fiches :
t = (5E3)**2 / 30E6 = 0,83 s
Pour 5 millions de fiches :
t = (5E6)**2 / 30E6 = 833333 s
t = (5E6)**2 / (30E6*3600*24) = 9.6 jours
Pour 5 milliards de fiches :
t = (5E9)**2 / 30E6 = 833333333333 s
t = (5E9)**2 / (30E6*3600*24*365) = 26 424 ans !
Un ordinateur ultra performant n'a en réalité aucun chance face à un ordinateur moins performant muni d'un programme plus efficace.
L'aspect logiciel et algorithmique est finalement plus fondamental que l'aspect matériel.
Comparaison visuelle des deux cas
Voici un script Python permettant de générer les courbes ci-dessus.
# 1 - Importation des modules nécessairesimportmathimportmatplotlib.pyplotasplt# 2 - Constantes# 3 - Déclaration des fonctions# 4 - Programme principal# Création des tableaux de donnéesvaleurs_n=[nforninrange(10000)]# Abscissetemps_1=[n**3/200E9forninvaleurs_n]# Ordonnéetemps_2=[n**2/30E6forninvaleurs_n]# Ordonnéexmax=max(valeurs_n)ymax=max(temps_1)# Création des courbesplt.plot(valeurs_n,temps_1,label="Cas 1",color='orange')plt.plot(valeurs_n,temps_2,label="Cas 2",color="red")plt.xlabel("Nbr de fiches")plt.ylabel("Temps d'exécution (s)")plt.title("Comparaison des temps d'exécution")plt.legend(loc='upper center')plt.axis([0,xmax,0,ymax])plt.grid()plt.show()# Affichage à l'écran des courbes
Et ça date de quand l'algorithmique ? Des années 2000 ? Des années 1940 ?
1.2 Historique rapide
Certains pensent que l'un des algorithmes les plus anciens est l'algorithme d'Euclide. Cet algorithme permet de trouver le plus grand commun diviseur (PGCD) de deux entiers a et b.
Par exemple, pour a = 15 et b = 20, il s'agit de 5.
En effet,
15 peut se décomposer en 3*5 et
20 peut se décomposer en 4*5.
Gravure d'Euclide (depuis https://fr.wikipedia.org/wiki/Euclide#/media/Fichier:Euklid-von-Alexandria_1.jpg) - Domaine Public
Un algorithme efficace permettant de trouver automatiquement ce PGCD date de -300 et se trouve dans les écrits du mathématicien Euclide d'Alexandrie. Il a été découvert de façon autonome en Inde et en Chine quelques siècles plus tard.
Vers 800, Muhammad Ibn Mūsā al-Khuwārizmī dit Al-Khwarizmi, mathématicien, né dans dans l'actuel Ouzbékistan et mort à Badgad, publie de nombreux textes. Les traductions permettront l'introduction de l'algèbre en Europe. Il a notamment répertorié et classifié de nombreux algorithmes (créés par d'autres). Il y montre leurs terminaisons (le fait qu'ils s'arrêtent bien à tous les coups) ou pas.
Timbre Al-Khwarizmi - Domaine Public
Son nom est bien entendu à l'origine d'algorithme.
Depuis, bien des gens ont travaillé et travaillent toujours pour trouver, créer ou améliorer les algorithmes.
L'un des grands noms de l'algorithmique est Donald Knuth, informaticien et mathématicien américain de renom. Il est un des pionniers de l'algorithmique et a fait de nombreuses contributions dans plusieurs branches de l'informatique théorique (fondements logiques et mathématiques de l'informatique). A tel point, qu'on le nomme parfois le père de l'analyse algorithmique.
Nous allons maintenant tenter de réaliser un algorithme qui signale si un élément existe dans un tableau (et renvoie son indice) ou renvoie -1 sinon.
Cette méthode se nomme méthode par balayage ou recherche linéaire.
En anglais, on parle de linear search.
Vous allez comprendre pourquoi en utilisant l'animation suivante : créer un tableau avec l'un des boutons aléatoires, choisir une valeur à chercher et appuyer sur le bouton lançant l'animation.
Valeur cherchée :
Indice i
00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
Case t[i]
60
89
15
56
82
1
86
97
24
86
75
6
14
69
98
31
37
89
91
56
2.1 Principe de la recherche linéaire
Principe général
BUT : trouver la position de la première occurrence de l'élément x recherché dans un tableau t.
PRINCIPE (en 4 étapes) :
On commence par la case d'indice 0
TANT QUE la case est valide ET ne contient pas le contenu cherché, on passe à la case suivante
SI la valeur finale de l'indice est valide : la réponse est bien l'indice. SINON, la réponse est -1 car on a atteint la fin du tableau sans trouver.
On RENVOIE la réponse
Exemples
Prenons t=[13, 18, 89, 1024, 45, -12, 18]
Indice i
0
1
2
3
4
5
6
Case t[i]
13
18
89
1024
45
-12
18
Voici trois exemples de réponses attendues :
Recherche de 89 (présent une fois) :
t=[13, 18, 89, 1024, 45, -12, 18]
⇒
RECHERCHER
⇒
et
2
x=89
Recherche de 18 (présent deux fois) :
t=[13, 18, 89, 1024, 45, -12, 18]
⇒
RECHERCHER
⇒
et
1
x=18
Recherche de 100 (non présent) :
t=[13, 18, 89, 1024, 45, -12, 18]
⇒
RECHERCHER
⇒
et
-1
x=100
2.2 Algorithme de la recherche linéaire
Description des entrées/sortie
NOM : RECHERCHE_LINEAIRE
ENTREES :
t : un tableau contenant n éléments.
x : l'élément qu'on recherche dans le tableau
(optionnelle selon les langages d'implémentation)longueur, le nombre d'éléments dans le tableau t
SORTIE : un entier valant
soit l'indice où se trouve la première (et peut-être) seule occurrence de l'élément cherché.
une réponse voulant dire que l'élément x n'est présent dans le tableau. VIDE ou -1
Description de l'algorithme
Ci-dessous, on fait le choix de répondre -1 en cas de valeur non trouvée.
i ← 0
TANT QUEi < longueurET que t[i] est différent de x
i ← i + 1
Fin TANT QUE
SIi < longueur
reponse ← i
SINON
reponse ← -1
Fin Si
Renvoyerreponse
03° Utiliser les instructions suivantes pour revoir comment fonctionne un tableau :
defrechercher(t,x):"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent :: param t(list) :: un tableau contenant le même type d'éléments que le paramètre x :: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau :: return (int) :: l'indice de la case ou -1 :: exemples :: >>> test = [10,20,30,40,50] >>> rechercher(test, 20) 1 >>> rechercher(test, 60) -1 """passtab_test=[13, 18, 89, 1024, 45, -12, 18]a=rechercher(tab_test,18)b=rechercher(tab_test,1024)c=rechercher(tab_test,1025)
Comme vous pouvez le voir, sous la fonction à réaliser, on a rajouté des instructions pour créer un tableau et mémoriser quelques appels dans des variables. Vous pourrez visualiser le résultat pour voir si votre fonction répond correctement.
defrechercher(t,x):"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent :: param t(list) :: un tableau contenant le même type d'éléments que le paramètre x :: param x(au choix) :: l'élément qu'on cherche à trouver dans le tableau :: return (int) :: l'indice de la case ou -1 :: exemples :: >>> test = [10,20,30,40,50] >>> rechercher(test, 20) 1 >>> rechercher(test, 60) -1 """i=0longueur=len(t)whilei<longueurandt[i]!=x:i=i+1ifi<longueur:reponse=ielse:reponse=-1returnreponsetab_test=[13, 18, 89, 1024, 45, -12, 18]a=rechercher(tab_test,18)b=rechercher(tab_test,1024)c=rechercher(tab_test,1025)
10 ✎° Rajouter un commentaire derrière chaque instruction pour traduire en français le rôle de cette ligne.
Si vous êtes en classe, demander le document-réponse de cette question.
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
defrechercher(t:list,x:int) ->int:"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""i=0# On se place sur la première caselongueur=len(t)# On mémorise le nb de caseswhilei<longueurandt[i]!=x:# Tant qu'il reste des cases et que la case actuelle n'est pas la bonnei=i+1# On passe à la case suivanteifi<longueur:# Si i obtenu est une valeur possible pour ce tableaureponse=ielse:# Sinon, c'est qu'on est sorti du tableaureponse=-1returnreponse# Renvoie la réponse
RAPPEL : phase d'initialisation du TANT QUE
Attention à l'une des erreurs typiques lors de l'utilisation d'une boucle non bornée TANT QUE : le fait d'oublier de donner une valeur par défaut permettant de rentrer dans la boucle à la variable qui gère la boucle.
11° Réaliser une modification de rechercher() en utilisant plutôt une boucle for associée à un return : dès qu'on connaît la réponse, on répond. On ne renvoie -1 qu'après avoir effectué toute la boucle : si on arrive à cette ligne, c'est qu'on a pas rencontré l'élément recherché avant.
Le prototype de la fonction reste le même :
1
defrechercher(t:list,x:'Element') -> int:
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
defrechercher(t,x):"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présentforiinrange(len(t)):ift[i]==x:returnireturn-1tab_test=[13, 18, 89, 1024, 45, -12, 18]a=rechercher(tab_test,18)b=rechercher(tab_test,1024)c=rechercher(tab_test,1025)
12° Au niveau algorithmique, quelle est la version la plus rigoureuse : celle avec le while ou celle avec for+return ?
...CORRECTION...
Sur le principe de la recherche, on doit interrompre la recherche dès qu'on trouve le bon élément. Il s'agit donc d'une boucle non bornée.
Donc, le while est le plus adapté.
13° Au niveau programmation, quelle est la version la plus lisible : celle avec le while ou celle avec for+return ?
...CORRECTION...
Cette fois, la version avec le for est plus lisible : pas besoin de noter l'initialisation, l'incrémentation et de tester s'il reste encore une case ou non.
Pour les plus rapides° : fournir une fonction de recherche un peu différent : cette fois, on veut renvoyer l'indice de la dernière occurrence dans le tableau.
Recherche de 18 (présent deux fois) :
t=[13, 18, 89, 1024, 45, -12, 18]
⇒
RECHERCHER
⇒
et
6
x=18
Il faudra vous demander s'il faut utiliser une boucle bornée ou non bornée, comment parvenir à stocker les réponses successives...
La compréhension totale de cette partie va nécessiter de faire le complément Python sur la construction par compréhension (la partie 5 ci-dessous)
14° Utiliser le programme ci-dessous. Il génére un tableau t de n nombres compris entre 10 et 20, génère un nombre x au hasard puis utilise la fonction rechercher(). On affiche le résultat obtenu.
Lancer 5 fois le programme et vérifier qu'il donne la bonne réponse à chaque fois.
importrandomdefrechercher(t:list,x:int) ->int:"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""i=0# On se place sur la première caselongueur=len(t)# On mémorise le nb de caseswhilei<longueurandt[i]!=x:# Tant qu'il reste des cases et que la case actuelle n'est pas la bonnei=i+1# On passe à la case suivanteifi<longueur:# Si i obtenu est une valeur possible pour ce tableaureponse=ielse:# Sinon, c'est qu'on est sorti du tableaureponse=-1returnreponse# Renvoie la réponsen=random.randint(5,10)# nombre de cases entre 5 et 10t=[random.randint(1,20)forxinrange(n)]# le tableau de cases aléatoiresx=random.randint(0,30)# génération du nombre qu'on chercheindice=rechercher(t,x)# récupération de l'indice print(t)print(f"On cherche {x} : réponse {indice}")
Malheureusement, tester (même 1 million de fois) ne permet pas d'être certain que la réponse est bonne.
15° Même si nous savons que vérifier ne veut pas dire démontrer, ce programme va vous permettre de lancer en boucle autant de tests que vous le désirez. Si l'un d'entre eux est faux, le programme doit stopper immédiatement.
Comment aller vous procéder :
Si c'est -1, on vérifie que l'élément n'appartient pas au tableau
Si on récupère un indice valide, il faudra tester deux choses :
l'élément se trouve bien à cette position i et
aucun indice plus petit ne contient cet élément.
Tâches à accomplir :
Placer ce nouveau programme en mémoire
Lire le prototype de la fonction pour comprendre ce que doit faire cette fonction
importrandomdefrechercher(t:list,x:int)->int:"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""i=0# On se place sur la première caselongueur=len(t)# On mémorise le nb de caseswhilei<longueurandt[i]!=x:# Tant qu'il reste des cases et que la case actuelle n'est pas la bonnei=i+1# On passe à la case suivanteifi<longueur:# Si i obtenu est une valeur possible pour ce tableaureponse=ielse:# Sinon, c'est qu'on est sorti du tableaureponse=-1returnreponse# Renvoie la réponsedeftester():forkinrange(1000):n=random.randint(3,10)t=[random.randint(10,20)forxinrange(n)]x=random.randint(8,22)indice=rechercher(t,x)print(f"Test {k+1}")ifindice==...and...in...:# Si on a -1 alors que x est présentprint("ECHEC DU TEST")print(t)print(f"On cherche {x} : réponse {indice}")return...else:foriinrange(0,indice):# Pour chaque indice j inférieur à indiceift[...]==...:# Si on trouve x dans la case jreturn...print("OK AVEC LES 1000 TESTS AUTOMATIQUES")return...# si on arrive ici, c'est que tous les tests sont bonstester()
importrandomdefrechercher(t:list,x:int)->int:"""Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""i=0# On se place sur la première caselongueur=len(t)# On mémorise le nb de caseswhilei<longueurandt[i]!=x:# Tant qu'il reste des cases et que la case actuelle n'est pas la bonnei=i+1# On passe à la case suivanteifi<longueur:# Si i obtenu est une valeur possible pour ce tableaureponse=ielse:# Sinon, c'est qu'on est sorti du tableaureponse=-1returnreponse# Renvoie la réponsedeftester():forkinrange(1000):n=random.randint(3,10)t=[random.randint(10,20)forxinrange(n)]x=random.randint(8,22)indice=rechercher(t,x)print(f"Test {k+1}")ifindice==-1andxint:# Si on a -1 alors que x est présentprint("ECHEC DU TEST")print(t)print(f"On cherche {x} : réponse {indice}")returnFalseelse:foriinrange(0,indice):# Pour chaque indice j inférieur à indiceift[i]==x:# Si on trouve x dans la case jreturnFalseprint("OK AVEC LES 1000 TESTS AUTOMATIQUES")returnTrue# si on arrive ici, c'est que tous les tests sont bonstester()
Nous allons utiliser une nouvelle façon de créer des tableaux.
Jusqu'à présent, vous ne savez créer des tableaux qu'en extension : on fournit directement dans les crochets les valeurs voulues. Pour créer un tableau contenant les entiers de 1 à 3000, ca risque d'être long à taper...
5.1 Création par compréhension à partir d'un autre tableau
A - Principe
La déclaration d'un tableau par compréhension consiste à créer un tableau à l'aide d'une boucle for. Créons un nouveau tableau nt.
nt=[ 0 forelementinbase]
Comme doit-on comprendre cela ? "Pour chaque élément du tableau initial, créé une case contenant 0 dans le nouveau tableau". Voici l'explication :
On déclare un nouveau tableau nt crée par compréhension puisqu'on y voit une boucle :
nt=[... for ...]
"Pour chaque élément du tableau initial" se note :
nt=[...forelementinbase]
"Crée une case contenant 0 dans le nouveau tableau" se note :
nt=[ 0 forelementinbase]
B - Exemple 1 ; tableau de même taille
>>> base = [1, 2, 5]
>>> nt = [100 for valeur in base]
>>> nt
[100, 100, 100]
On peut traduire cela par :
Crée un tableau nt par compréhension où
pour chaque valeur contenue dans base
on crée une case contenant 100 dans nt.
C - Exemple 2 : copie peu profonde
copie=[vforvinb]
On peut traduire cela par :
Crée un tableau dd par compréhension où
pour chaque valeur contenue dans b
on crée une case contenant la même valeur.
>>> b = [1, 2, 5]
>>> copie = [v for v in b]
>>> copie
[1, 2, 5]
D - Exemple 3 : copie peu profonde modifiée
On peut indiquer une expression expliquant ce que doit être le contenu de la nouvelle case.
copie_mod=[v*100forvinb]
On peut traduire cela par :
Crée un tableau dd par compréhension où
pour chaque valeur contenue dans b
on crée une case contenant le double de la case de b.
>>> b = [1, 2, 5]
>>> copie_mod = [v*100 for v in b]
>>> copie_mod
[100, 200, 500]
16° Créer (par compréhension) un tableau qui contient des valeurs 100 fois plus grandes que le tableau suivant :
>>> t1 = [1, 2, 3, 5, 7, 11]
...CORRECTION...
>>> t1 = [1, 2, 3, 5, 7, 11]
>>> dd = [v*100 for v in t1]
>>> dd
[100, 200, 300, 500, 700, 1100]
17° Créer, par compréhension, un tableau longueurs dont les cases contiennent le nombre de lettres des prénoms contenus dans le tableau prenoms :
5.2 Création par compréhension sans tableau initial
A - Principe
On peut créer des tableaux contenant un nombre précis d'élements en utilisant range().
B - Exemple 1
>>> t = [0 for i in range(10)]
>>> t
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
On place 0 dans une case pour chaque indice i (qui vaut 0 puis 1 puis 2 ... jusqu'à 9). Donc 10 cases.
C - Exemple 2
>>> t = [i*10 for i in range(10)]
>>> t
[0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
La variable de boucle i varie de 0 à 9, et on place 10 fois plus dans la case correspondante du nouveau tableau.
D - Exemple 3
>>> import random
>>> tableau = [random.randint(1, 100) for i in range(10)]
>>> tableau
[42, 41, 96, 35, 58, 94, 16, 21, 84, 51]
On crée 10 cases dans lesquelles on place un nombre aléatoire entre 1 et 100.
18° Créer par compréhension un tableau de 100 éléments contenant des nombres aléatoires compris entre 20 et 50.
...CORRECTION...
>>> import random
>>> tableau = [random.randint(2, 50) for x in range(100)]
19° Créer par compréhension un tableau de 500 éléments contenant 0.
...CORRECTION...
>>> tableau = [0 for _ in range(500)]
On peut même faire mieux : on peut inclure une instructions conditionnelles ou même un appel de fonction dans la construction.
5.3 Création par compréhension avec condition
A - Principe
On peut rajouter une expression booléenne à la toute fin de la déclaration.
B - Réaliser un filtrage
On crée un tableau de 50 notes comprises entre 0 et 20. On crée un second tableau à partir du premier : on ne garde que les notes supérieures ou égales à 10.
La fonction détermine la valeur à placer lors de la création par compréhension. Imaginons qu'on dispose de cette fonction en mémoire :
1
2
3
4
5
6
defpas_plus(valeur:int,seuil:int)->int:"""Fonction qui écrête : elle renvoie la valeur ou le seuil si la valeur est supérieure au seuil"""ifvaleur>seuil:returnseuilreturnvaleur
>>> import random
>>> t = [random.randint(1, 20) for _ in range(10)]
>>> t
[14, 19, 7, 14, 11, 1, 13, 12, 20, 1]>>> t2 = [pas_plus(valeur, 15) for valeur in t]
>>> t2
[14, 15, 7, 14, 11, 1, 13, 12, 15, 1]
On obtient bien un tableau de 10 éléments sans qu'aucun élément ne soit plus grand que 15.
20° Créer un tableau p6 dont les cases contiennent les prénoms de 6 caractères ou plus contenus dans le tableau prenoms :
Chercher, c'est courant... Python ne sait pas faire ça tout seul ?
Si, il existe des fonctions ou méthodes de Python qui permettent de le faire. Mais, comment fonctionnent-elles ?
En NSI, nous cherchons à comprendre et construire, pas simplement utiliser.
Maintenant, vous savez comment cela fonctionne, on peut vous montrer comment le faire en quelques lignes.
>>> t = [40, 70, 30, 20, 30]
>>> t.index(40)
0
>>> t.index(30)
2
>>> t.index(80)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
ValueError: 80 is not in list
