Algorithmes et PYTHON
Ce cours vous donne les bases suffisantes pour comprendre les algorithmes informatiques proposés en terminale.Il est conseillé de s'entraîner à refaire les exemples sur feuille.
Si vous maîtrisez ce cours, il faut alors savoir l'appliquer en écrivant des programmes, en particulier dans le langage PYTHON expliqué dans ce cours de PYTHON en Première Spécialité Maths.
Le dernier exemple du cours consiste à traduire dans le langage PYTHON la plupart des algorithmes proposés.
Algorithmes et programmes
Un algorithme informatique est une suite d'instructions permettant d'écrire un programme informatique.
En terminale, les algorithmes proposés sont écrits en langage courant. Par contre, l'écriture d'un programme se fait toujours dans un langage donné (par exemple en PYTHON).
Dans tout ce qui suit, le programme dont il est question est celui qui serait associé à l'algorithme proposé.
Les variables: l'affectation
En informatique, on manipule des variables.
Il faut imaginer une variable comme un "tiroir", auquel on a donné un nom. Le nom est parfois réduit à sa plus simple expression, à savoir une lettre.
Le programme passe son temps à remplir ces "tiroirs", en général avec des nombres, ou des textes, ou des listes (de nombres et/ou de textes).
On dit alors qu'on affecte des valeurs à des variables.
Exemple
Affecter à A la valeur 8
Ici, A est le nom d'une variable.Quand le programme lit cette instruction, il remplit le "tiroir" A avec la valeur 8.
Cette instruction est équivalente à la suivante:
A prend la valeur 8
Cette instruction est aussi équivalente à la suivante:A ← 8
Les variables: comment les utiliser?
Le contenu des variables peut évidemment être manipulé par le programme.
Cette fois-ci, le programme va regarder la valeur que contient un "tiroir", et il va s'en servir!
Quand il utilise la valeur en question, le contenu de la variable initiale reste inchangé, sauf si le programme affecte une nouvelle valeur à cette variable!
Exemple
A ← 8
B ← A
Après cette seconde instruction, la variable A contient toujours la valeur 8. La variable B contient également la valeur 8.
Exemple
A ← 8
B ← 2
A ← A+B
Après la seconde instruction, la variable B contient la valeur 2.
Dans la troisième instruction, le programme manipule le contenu de la variable A et le modifie.
Après la troisième instruction, la variable A contient la valeur 10. La variable B contient toujours la valeur 2.
L'affichage (ou l'écriture)
Le programme peut afficher à l'écran (ou écrire sur l'écran) le contenu des variables. Il peut aussi afficher (ou écrire) de simples textes (mis entre guillemets), ou le résultat d'un calcul.
On utilise le mot "écriture" car le programme écrit quelque chose sur l'écran.
Exemple
A ← 8
Afficher A
Exemple
A ← 8
Afficher "le double de A vaut "
Afficher $2×A$
Dans la troisième instruction, le programme affiche à l'écran le résultat de son opération, c'est à dire 16.
Finalement, le programme aura affiché: "le double de A vaut 16".
La lecture
Le programme peut demander à l'utilisateur de lui donner une valeur, qu'il affectera alors à une variable. Ce processus s'appelle la lecture.
On utilise ce mot car le programme lit ce que l'utilisateur écrit à l'aide de son clavier.
Exemple
Lire A
Afficher A
Supposons, par exemple, que l'utilisateur tape 37, le programme va alors affecter à A la valeur 37.
Dans la seconde instruction, le programme affiche à l'écran le contenu de la variable A. Dans notre exemple, il s'affichera donc 37.
Remarque: l'instruction Lire A est équivalente à l'instruction Saisir A
Exemple
Ecrire l'algorithme d'un programme qui demande la valeur de 2 nombres, puis qui affiche leur produit.
Solution...Corrigé
Une possibilité:
Lire A
Lire B
Afficher A+B
Lire A
Lire B
C ← A+B
Afficher C
Lire A
Lire B
A ← A+B
Afficher A
Rappel: on peut remplacer l'instruction Lire A par l'instruction Saisir A
Les conditions
Le programme peut vérifier si une certaine condition est vérifiée. Dans ce cas, il effectuera alors certaines instructions.
Cela s'exprime en utilisant les mots: Si...Alors...Fin du Si.
Le programme peut vérifier si une certaine condition est vérifiée. Dans ce cas, il effectuera alors certaines instructions, sinon il effectuera d'autres instructions.
Cela s'exprime en utilisant les mots: Si...Alors...Sinon...Fin du Si.
Exemple
Lire A
Si A est pair
Alors Afficher "Oui! "
Afficher A
Afficher " est pair. "
Fin du Si
Afficher "Fin du programme"
Supposons, par exemple, que l'utilisateur tape 12. Le programme va alors affecter à A la valeur 12.
A la seconde instruction, il va tester si A est pair. Et comme c'est le cas, il va effectuer la troisième instruction, et afficher: "Oui! ".
Puis il continue, et affiche la valeur de A, c'est à dire 12. Et il affiche ensuite " est pair. ".
Il arrive alors à la Fin du Si.
Il passe alors à la dernière instruction du programme, et affiche "Fin du programme".
Finalement, dans cet exemple, il a affiché: "Oui! 12 est pair. Fin du programme"
Mais supposons, par exemple, que l'utilisateur tape 11. Dans ce cas, la condition n'étant pas vérifiée, les instructions entre le Alors et la Fin du Si ne sont pas effectuées, et le programme passe à la dernière instruction. Il s'affiche donc uniquement: "Fin du programme".
Exemple
Ecrire l'algorithme d'un programme qui demande la valeur d'un nombre, puis qui affiche "Pair", si le nombre est pair, et "Impair", si le nombre est impair.
Solution...Corrigé
Lire A
Si A est pair
Alors Afficher "Pair"
Sinon Afficher "Impair"
Fin du Si
Les boucles
Le programme peut répéter un certain nombre de fois certaines instructions. Ces instructions constituent une boucle.
Boucle Pour
Si l'on connait le nombre de boucles à répéter, on utilise souvent les mots: Pour...allant de...à...Fin du Pour.
Boucle Tant que
Si l'on ne connait pas le nombre de boucles à répéter, on ne peut pas utiliser de boucle Pour. On utilise alors souvent les mots: Tant que...Fin du Tant que.
Il existe d'autres boucles, mais elles sont hors programme.
Exemple
Pour I allant de 1 à 5
Afficher I
Afficher " "
Fin du Pour
Afficher "Fin du programme"
Il va ensuite effectuer les deux instructions situées dans la boucle, et il va les répéter tant que I ne dépasse pas 5.
Et à la fin de chaque boucle, il va automatiquement augmenter I de 1 (on dit incrémenter I de 1).
Ainsi, il va afficher 1 2 3 4 5 .
Vous noterez les espaces entre chaque nombre.
Dès qu'il aura affiché 5, puis l'espace " ", il arrivera à la fin de la cinquième boucle, et incrémentera automatiquement I de 1, qui vaudra alors 6.
Par conséquent, il ne commencera pas de sixième boucle. Il arrêtera ses boucles, et il passera à l'instruction suivante. Il affichera alors "Fin du programme".
Finalement, ce programme aura affiché: "1 2 3 4 5 Fin du programme".
Exemple
Ecrire l'algorithme d'un programme similaire au précédent, mais avec une boucle Tant que.
Solution...Corrigé
I ← 1
Tant que $I≤5$
Afficher I
Afficher " "
I ← I+1
Fin du Tant que
Afficher "Fin du programme"
Il faut absolument ajouter la première ligne: I ← 1,
ainsi que la cinquième: I ← I+1.
Cette cinquième ligne peut aussi s'écrire: augmenter I de 1, ou affecter à I la valeur I+1.
Exemple
Ecrire l'algorithme d'un programme qui affiche la somme les entiers de 1 à 100.
Solution...Corrigé
Comme le nombre de boucles est connu, il est préférable d'utiliser une boucle Pour
Affecter à S la valeur 0
Pour I allant de 1 à 100
S ← S+I
Fin du Pour
Afficher S
Exemple
Ecrire l'algorithme d'un programme qui somme les entiers naturels à partir de 1 et qui s'arrête dès que la somme dépasse 1000. Le programme affiche alors le dernier entier sommé.
Solution...Corrigé
Comme le nombre de boucles est inconnu, et qu'il est limité par une condition, on utilise une boucle Tant que
S ← 0
I ← 0
Tant que $S≤1000$
I ← I+1
S ← S+I
Fin du Tant que
Afficher I
Les Fonctions
Une fonction est un bloc d'instructions destiné à être utilisé ultérieurement. Ce bloc d'instruction dépend d'un ou de plusieurs paramètres.
On utilise alors souvent les mots: Fonction... Valeur retournée...Fin de la fonction.
Exemple
Ecrire l'algorithme d'un programme qui affiche les nombres de 0 à 5 et leurs images par la fonction $f(x)=x^2-5x+1$. Votre algorithme utilisera une fonction et une boucle.
Solution...Corrigé
On commence par définir la fonction f(x).Puis, comme le nombre de boucles est connu, on utilise une boucle Pour
Fonction f(x)
y ← x²-5x+1
valeur retournée y
Fin de la fonction
Pour I allant de 0 à 5
Afficher I et f(I)
Fin du Pour
Exemple de synthèse
Traduire en PYTHON tous les algorithmes qui suivent.
PROGRAMME 1
A ← 8
B ← 2
A ← A+B
PROGRAMME 2
A ← 8
Afficher "le double de A vaut "
Afficher $2×A$
PROGRAMME 3
Lire A
Lire B
A ← A+B
Afficher A
PROGRAMME 4
Lire A
Si A est pair
Alors Afficher "Pair"
Sinon Afficher "Impair"
Fin du Si
PROGRAMME 5
Pour I allant de 1 à 5
Afficher I
Afficher " "
Fin du Pour
Afficher "Fin du programme"
PROGRAMME 6
I ← 1
Tant que $I≤5$
Afficher I
Afficher " "
I ← I+1
Fin du Tant que
Afficher "Fin du programme"
PROGRAMME 7
S ← 0
I ← 0
Tant que $S≤1000$
I ← I+1
S ← S+I
Fin du Tant que
Afficher I
PROGRAMME 8
Fonction f(x)
y ← x²-5x+1
valeur retournée y
Fin de la fonction
Pour I allant de 0 à 5
Afficher I et f(I)
Fin du Pour
Corrigé
Les textes qui suivent un dièse sont des commentaires. Ils sont ignorés par le compilateur PYTHON.
Après exécution de ce programme, la variable A contient le nombre 10. Mais l'utilisateur ne s'en rend pas compte car il ne s'affiche rien dans la console.
Après exécution de ce programme, la variable A contient le nombre 8. Il s'affiche dans la console les deux lignes suivantes.
le double de A vaut
16
Quand l'utilisateur exécute ce programme, il s'affiche une première fenêtre dans laquelle l'utilisateur va rentrer par exemple 5. Puis il s'affiche une première fenêtre dans laquelle l'utilisateur va rentrer par exemple 7.
Mais, pour le compilateur Python, 5 et 7 ne sont pas des nombres, mais des textes. L'instruction A=A+B ne va donc pas les sommer, mais elle va les concaténer (les mettres bout à bout).
La variable A va finalement contenir le texte 57.
Dans notre exemple, il s'affiche dans la console le texte 57
Le programme est similaire au précédent, mais chacun aura noté le mot int avant le input. Les textes saisis sont ainsi 'transformés' en entiers par PYTHON.
Donc, cette fois-ci, si l'utilisateur entre 5, puis 7, alors l'instruction A=A+B va les sommer, et la variable A va finalement contenir l'entier 12.
Dans notre exemple, il s'affiche dans la console l'entier 12
Le programme est encore similaire au précédent, mais chacun aura noté le mot float avant le input. Les textes saisis sont ainsi 'transformés' en nombre à écriture à virgule par PYTHON.
Donc, par exemple, si l'utilisateur entre 5.2, puis 7.4, alors l'instruction A=A+B va les sommer, et la variable A va finalement contenir le nombre à virgule 12,6
Dans notre exemple, il s'affiche dans la console le nombre à virgule 12.6
Le programme est encore similaire au précédent, mais chacun aura noté les textes entre quotes à l'intérieur des parenthèses associées aux input. Ces textes sont indicatifs et ils apparaissent dans les fenêtres de saisie.
Cela rend le programme plus ergonomique car l'utilisateur sait ce qu'il doit faire.
De même, le texte dans le print rend l'affichage final plus explicite.
Après exécution, si l'utilisateur a rentré par exemple 5.2 et 7.4, il s'affiche dans la console
la somme vaut 12.6
Quand l'utilisateur exécute ce programme, il s'affiche une fenêtre dans laquelle il est écrit A=
L'utilisateur va alors entrer un nombre (entier sinon le programme bugue) qui sera affecté à la variable A.
Le calcul A%2 donne alors le reste de la division euclidienne de A par 2.
Le double égal qui suit est un test; ici, il permet de savoir si ce reste est nul (et donc si le nombre A est pair).
Admettons que l'utilisateur entre 5, alors il va s'afficher le texte 'impair' dans la console.
Admettons que l'utilisateur entre 6, alors il va s'afficher le texte 'pair' dans la console.
Chacun aura noté les deux points après le test qui suit le if, ou après le else.
Toutes les instructions associées au if ou au else sont indentées (décalées vers la droite), ce qui permet à PYTHON de les repérer.
range(1,6) contient les entiers de 1 à 6-1=5.
Lors de la boucle for, la variable I prendra donc successivement les valeurs 1, 2, 3, 4 et 5.
Les nombres de 1 à 5 vont s'afficher dans la console, séparés par une ligne vide.
Puis il s'affiche le texte 'Fin du programme'
Le résultat est le même que pour le programme précédent.
Chacun aura noté que I est initialisé par l'instruction I=1. De plus, comme la valeur de I ne change pas automatiquement, l'instruction I=I+1 est indispensable.
Après exécution, il s'affiche dans la console la valeur de I, ici 45.
Cela signifie que 1+2+3+...+45 est strictement supérieur à 1000, alors que 1+2+3+..+44 était inférieur ou égal à 1000.
Pour les sceptiques:
1+2+3+...+44=(44+45)/2=990
1+2+3+...+45=990+45=1035.
Après exécution, il s'affiche dans la console :
f( 0 )= 1
f( 1 )= -3
f( 2 )= -5
f( 3 )= -5
f( 4)= -3
f( 5 )= 1