Algorithmique et programmationCours

Un programme informatique est une suite d'instructions que l'on va faire exécuter par une machine. On peut rédiger cette suite d'instructions en français, mais pour que la machine la comprenne, on passe par un langage informatique avec un format défini de façon précise.

Il existe plusieurs langages informatiques, mais ici on utilisera le langage « Python ». On verra au fur et à mesure comment utiliser ce langage.

I

Instructions de base

Voyons d'abord quelques instructions de base en Python, de sorte que l'on puisse construire nos premiers programmes.

A

Calculs

Comme avec une calculatrice, on peut faire les opérations de base :

            \verb!5+3!
renvoie
            \verb!8!

On a le tableau d'opérations suivantes en Python :

 Symboles  Opérations
\verb! + ! addition
\verb! - ! soustraction
\verb! * ! multiplication
\verb! / ! division
\verb! ** !

puissance

On peut aussi faire des divisions euclidiennes, avec un quotient et un reste :

  • \verb! a//b ! renvoie le quotient de la division euclidienne de a par b.
  • \verb! a\%b ! renvoie le reste de la division euclidienne de a par b.
  • \verb! 9//4 ! renvoie \verb! 2 !.
  • \verb! 9\%4 ! renvoie \verb! 1 !.
B

Commentaires

Souvent, lorsqu'on écrit un programme, on a besoin d'y ajouter des commentaires pour expliquer ce que l'on fait, surtout si on est plusieurs à développer ou à utiliser un même code.

Il ne faut pas que la machine lise ces commentaires, il faut donc lui indiquer quel est le texte à ignorer. En Python, cela se fait en plaçant le symbole # au début du texte à ignorer.

          \verb! 5+3 #ici un commentaire !
          \verb! #ici un autre commentaire !

La machine effectue 5+3 en ignorant les commentaires.

C

Entrées et sorties

En plus des calculs de base, Python contient un certain nombre de fonctions prédéfinies, qui permettent en particulier :

  • d'afficher un texte, avec la fonction \verb! print ! ;
  • de demander quelque chose à l'utilisateur et d'enregistrer son entrée, avec la commande \verb! input !.
1

Entrée

Pour récupérer la donnée saisie par l'utilisateur, on utilisera la fonction \verb! input !.

L'instruction

\verb!input("Entrez un texte")!

affiche : « Entrez un texte »

puis récupère l'entrée de l'utilisateur.

\verb! input ! récupère également l'entrée de l'utilisateur, mais sans afficher de texte.

Par contre, si on ne peut pas enregistrer cette entrée en mémoire, ça n'a pas beaucoup d'intérêt, car on ne peut alors pas l'utiliser. 

2

Sortie

Pour l'affichage, on utilisera en Python la fonction \verb! print ! en mettant entre parenthèses ce que l'on veut afficher.

L'instruction

 \verb! print("Bonjour")!

affiche : Bonjour

L'instruction

\verb! print(5) !

affiche : 5

II

Variables

A

Définition

Variable

Une variable est une « boîte » virtuelle qui correspond à une case mémoire de la machine, dans laquelle on peut stocker un nombre, un caractère, un texte, etc.

Sur cette boîte, on met une étiquette, pour que le programme s'y retrouve : ce sera le nom de la variable.

On ne peut pas choisir n'importe quel nom de variable, certaines instructions de base, comme celles que nous verrons ensuite, ont un nom protégé. Par exemple, il est interdit d'appeler une variable « \verb!if! ».

B

Affectation et utilisation

Affecte

Quand on attribue une valeur à une variable, on dit qu'on affecte une valeur à la variable.

En langage naturel :

L'instruction :

\verb!mon_nombre ← 5!

veut dire qu'on affecte la valeur 5 à la variable « \verb!mon_nombre! », c'est-à-dire qu'on met la valeur 5 dans la case mémoire qui porte l'étiquette « \verb!mon_nombre! ».

En Python :

En Python, on utilise le signe = pour affecter une valeur à une variable :

\verb!mon_nombre = 5!

Pour utiliser une variable, il suffit d'écrire son nom, et, au moment de l'exécution, le programme ira chercher sa valeur.

On considère le programme suivant :

\verb!mon_nombre = 5! 

\verb!mon_nombre + 3!

À la première ligne, ce programme affecte la valeur 5 à la variable \verb!mon_nombre!.

À la deuxième ligne, il remplace « \verb!mon_nombre! » par sa valeur, donc 5, et calcule 5+3=8.

C

Type d'une variable

Les variables peuvent être de différents types. De ce type dépend l'espace utilisé par la variable en mémoire, et aussi l'utilisation que le programme peut en faire.

Le type d'une variable peut être, par exemple :

  • Un nombre entier, positif ou négatif

\verb!0, 1, 35, 427, −6, −12 345!

  • Un nombre à virgule flottante, positif ou négatif. Cela correspond à un nombre réel.

\verb!0.24, 1/3, −1.467789!

  • Un caractère

\verb!'a', ‘b', '1', ';'!

  • Une chaîne de caractères

\verb!« Ceci est une chaîne de caractères »!

  • Une « valeur booléenne », qui ne peut prendre que deux valeurs qui représentent « vrai » ou « faux ».

\verb!True! et \verb!False! sont des booléens.

La notation des types de variables et les types de variables acceptés dépend des langages de programmation. En python, le type « caractère », par exemple, n'est pas défini, mais uniquement le type « chaîne de caractères ».

Tableau des principaux types utilisés en Python :

Français

Anglais

Python

Nombre entier

Integer

\verb!int!

Nombre à virgule flottante

Floating point number

\verb!float!

Chaîne de caractères

Character string

\verb!str!

Valeur booléenne

Boolean

\verb!bool!

Un entier est aussi un réel, donc on pourrait mettre un entier dans une variable de type « float ».

En fait, l'intérêt de séparer les deux est :

  • de mieux gérer la mémoire. En effet, un entier prend moins de place qu'un réel, et donc on prévoit une taille de boite plus petite. Il existe même des types différents selon la taille des entiers, si besoin.
  • de savoir comment arrondir lors d'un calcul. Les entiers seront arrondis à l'unité, alors que avec une variable de type « float », on pourra avoir des chiffres après la virgule.

Il faut faire attention au type des variables dans les instructions, car chaque opération n'accepte que certains types.

Le programme suivant :

\verb!var = 'a'!

\verb!var + 2!

renvoie une erreur, car la variable \verb!var! est un caractère, ce n'est pas un nombre auquel on peut ajouter 2.

D

Déclaration de variables

Dans certains langages, on doit déclarer chaque variable avec son type, avant de commencer le programme.

En langage C :

\verb!int mon_nombre;!

veut dire « réserve une case vide d'étiquette "\verb!mon_nombre!" qui contiendra des nombres entiers, et rien d'autre. »

En Python, l'ordinateur décide tout seul du type de la variable lorsqu'on la crée et il n'y a pas besoin de le déclarer.

Si j'écris en Python :

\verb!mon_nombre = 5!

et que la variable \verb!mon_nombre! n'existe pas déjà, la machine va automatiquement créer cette variable avec le type « \verb!int! » (entier qui correspond à 5).

En Python, la fonction \verb!type()! appliquée à une variable renvoie son type.

L'instruction

            \verb!type(mon_nombre)!

avec la variable précédente, renvoie « \verb!int! ».

Si jamais on a besoin, on peut aussi « forcer le type » de la variable, c'est-à-dire imposer un type donné à la variable.

L'instruction 

\verb!int(nom_de_variable)!

force la machine à considérer \verb!nom_de_variable! comme un entier dans la suite du programme.

Cette instruction peut changer la valeur de la variable :

Le programme suivant

            \verb!var = 5.2!

            \verb!var=int(var)! 

            \verb!print(var)!

affiche 5, et non 5.2, car le programme a arrondi lors du changement de type, pour que ça « rentre » dans une variable de type entier.

Par défaut, le type obtenu avec input() est une chaîne de caractère. 

Du coup, le programme suivant :

\verb!entree=input("Entrez un nombre")!

\verb!entree + 3!

renvoie un message d'erreur si l'utilisateur entre la valeur 5, car la machine l'interprète comme un caractère, et non comme un nombre.

Pour que le programme fonctionne, il faut préciser à Python que l'entrée doit être un entier.

Ainisi, le programme suivant

\verb!entree=int(input("Entrez un nombre"))!

\verb!entree + 3!

va bien renvoyer la valeur 8, si l'utilisateur a saisi la valeur 5, car la variable \verb!entree! est bien considérée comme un nombre entier.

Dans la pratique, il faut donc toujours vérifier ce qu'entre l'utilisateur.

Par exemple pour le programme précédent, il faudrait en fait vérifier que l'utilisateur rentre bien un nombre entier. Si l'utilisateur entre une lettre, le programme va planter car il ne pourra pas mettre la lettre dans une variable de type entier. Pour cela, on va avoir besoin de pouvoir tester des conditions.

III

Instructions conditionnelles

On a parfois besoin de tester une condition et d'exécuter des instructions différentes selon le résultat obtenu.

Demander "Combien font 5+5 ?"
Si l'utilisateur répond 10, renvoyer Vrai.
Sinon, renvoyer Faux.

 

En Python, on utilise pour cela les mots clefs "if" et "else".

\verb!print ("Combien font 5+5 ?")!
\verb!#On met ce que l'utilisateur répond en tant que type float!
\verb!#dans la variable reponse.!
\verb!reponse = float(input())!
\verb!if reponse==10:!
    \verb!print("C'est vrai.")!
\verb!else:!
    \verb!print("C'est faux.")!

La structure en Python est la suivante :

\verb!if < condition> :!
    \verb!groupe d'instructions 1!
\verb!else :!
    \verb!groupe d'instructions 2!

On distingue les groupes d'instructions grâce à l'indentation, c'est-à-dire le retrait devant le texte. La présentation du programme est donc importante.

On peut tout à fait imbriquer plusieurs conditions.

\verb!print ("Combien font 5+5 ?")!
\verb!reponse = float(input())!
\verb!if reponse==10:!
    \verb!print("C'est vrai.")!
\verb!else:!
    \verb!if reponse > 10:!
             \verb!print("C'est trop grand.")!
    \verb!else:!
        \verb!print("C'est trop petit.")!

On veut écrire un programme qui demande un nombre à l'utilisateur, et renvoie sa valeur absolue.

pour tout nombre réel x :

\left| x \right|=\begin{cases} x \ si \ x\gt 0 \cr \cr -x \ si \ x\lt 0 \end{cases}

On va donc tester si le nombre donné est positif ou non, pour calculer et renvoyer sa valeur absolue.

On obtient les programmes suivants.

En Python :

\verb!nombre = float(input(« Entrez un nombre »))!
\verb!if nombre > 0 :!
    \verb!resultat = nombre!
\verb!else :!
    \verb!resultat = (−1) * nombre!
\verb!print(resultat)!

En langage naturel :

Demander un nombre à l'utilisateur
\verb!nombre ← le nombre reçu!
\verb!Si nombre > 0!
\verb!Alors resultat ←  nombre!
\verb!Sinon resultat ←  (−1) * nombre!

\verb!Afficher resultat!

IV

Boucle bornée (for)

Pour répéter des instructions un nombre fixé de fois, on peut utiliser une « boucle for ». On indique le nombre de répétitions à faire, et le groupe d'instructions concernées.

A

En langage naturel

1

Première possibilité

Répéter <nombre de fois> fois 
   < groupe d'instructions >

En langage naturel

\verb!nombre ← 0!
\verb!répéter 4 fois!
    \verb!afficher ("Nombre a pour valeur", nombre)!
    \verb!nombre nombre + 1!
\verb!afficher ("Terminé !")!

Résultat :

Nombre a pour valeur 0
Nombre a pour valeur 1
Nombre a pour valeur 2
Nombre a pour valeur 3
Terminé !

Explication :

Il y a deux instructions dans la boucle, l'affichage, et le fait d'augmenter la valeur de nombre de 1. L'instruction « afficher ("Terminé !") » n'est pas dans la boucle, on ne la fait donc qu'une fois.

Avec l'instruction \verb!nombre nombre + 1!, on augmente la valeur de \verb!nombre!, mais après l'affichage, c'est pourquoi on affiche des valeurs de 0 à 3 et non de 1 à 4.

2

Deuxième possibilité

\verb!Pour compteur de nb_depart à nb_arrivee faire!
    \verb!< groupe d'instructions >!

Ici, « \verb!compteur! » est une variable entière qui sert de compteur de tours. On lui donne bien sûr le nom qu'on veut.

La valeur de cette variable est augmentée de 1 automatiquement à chaque tour : il n'y a pas besoin de faire une instruction supplémentaire pour la modifier.

En langage naturel

\verb!Pour de 1 à 4 faire!
    \verb!afficher ("i a pour valeur", i)!
\verb!afficher ("Terminé !")!

Résultat :

i a pour valeur 1
i a pour valeur 2
i a pour valeur 3
i a pour valeur 4
Terminé !

B

En Python

En Python, on peut utiliser la fonction « \verb!range(n)! » pour exécuter la boucle n fois.

\verb!for compteur in range(<nombre de fois>):!
    \verb!<instructions>!

En Python

\verb!for i in range(4):!
    \verb!print("i a pour valeur", i)!
\verb!print("Fini !")!

Résultat :

i a pour valeur 0
i a pour valeur 1
i a pour valeur 2
i a pour valeur 3
Fini !

Avec \verb!range()!, le compteur part de 0, c'est pourquoi la variable compteur i va ici de 0 à 3 et non de 1 à 4.

C

Application

Dans cet exemple d'application, on veut écrire un programme qui donne la somme des dix premiers entiers, c'est-à-dire la somme 1 + 2 + 3 + 4 + 5 +6 + 7 + 8 + 9 + 10.

On propose l'algorithme suivant :

  • créer une variable « somme » qui est égale à 0 au départ ;
  • lui ajouter 1, puis 2, puis 3, et ainsi de suite jusqu'à 10 ;
  • afficher la valeur finale de « somme ».

 

Programmes obtenus : 

En langage naturel

\verb!somme ← 0!
\verb!Pour compteur de à 10 faire!
    \verb!somme somme + compteur!
\verb!Afficher (somme)!

 

En Python

\verb!somme = 0!
\verb!for compteur in range(10):!
    \verb!somme = somme + compteur + 1!
\verb!print (somme)!

Dans la version en Python, la variable compteur va de 0 à 9, c'est pourquoi on ajoute « \verb!compteur +1! » et non pas « \verb!compteur! » comme dans le premier programme.

V

Boucle non bornée (while)

Parfois, on ne connaît pas à l'avance le nombre de fois que l'on veut exécuter une boucle, mais on sait à quelle condition il faut s'arrêter.

On va alors utiliser l'instruction « \verb!while! », ou en français « tant que ».

En langage naturel, on aura une suite d'instructions de la forme :

\verb!Tant que <condition>!

    \verb!< groupe d'instructions >!

La condition peut être vérifiée ou non, c'est-à-dire qu'elle peut prendre uniquement deux valeurs possibles : vrai ou faux.

En Python, on utilise l'instruction : \verb!while <condition>!.

En langage naturel

\verb!nombre ← 0!
\verb!Tant que nombre <5!
    \verb!afficher ("nombre a pour valeur", nombre)!
    \verb!nombre nombre + 1!
\verb!afficher ("La valeur finale de la variable "nombre" est :", nombre)!

 

En langage Python

\verb!nombre = 0!
\verb!while nombre < 5:!
    \verb!print("nombre a pour valeur", nombre)!
    \verb!nombre=nombre+1!
\verb!print("La valeur finale de la variable "nombre" est :", nombre)!

Résultat :

nombre a pour valeur 0
nombre a pour valeur 1
nombre a pour valeur 2
nombre a pour valeur 3
nombre a pour valeur 4
La valeur finale de la variable "nombre" est : 5

Avec les boucles « \verb!while! », il faut veiller à ce que la boucle finisse par s'arrêter ! Dans l'exemple précédent, par exemple, si on oublie d'augmenter la valeur de la variable \verb!nombre! à chaque boucle, sa valeur reste à 0 et la boucle tourne à l'infini, ce qui bloque le programme et la machine.

VI

Fonction

Pour un programme avec des blocs qui se répètent, ou une suite d'instructions plus complexe, on peut être amené à utiliser la notion de fonction ou « procédure ».

Il s'agit de découper un programme complexe en plus petits blocs que l'on appellera fonctions et que l'on pourra réutiliser.

A

Définition d'une fonction

Pour définir une fonction, il faut préciser :

  • son nom ;
  • les paramètres dont elle a besoin pour fonctionner ;
  • ce qu'elle renvoie.

Une fonction n'est pas censée savoir ce qui se passe dans le programme principal. Elle doit être indépendante.

Par exemple, la façon dont on définit le calcul du carré d'un nombre ne dépend pas du problème dans lequel on l'utilise.

En Python, on utilise la structure suivante :

\verb!def <nom de la fonction>(<liste de paramètres>):!
      \verb!<instructions>!
      \verb!return <ce qu'elle renvoie>!

La fonction suivante calcule l'aire d'un rectangle, dont la longueur et largeur sont indiquées en paramètre.

\verb!def aire_rectangle(longueur, largeur):!
      \verb!resultat = longueur * largeur!
      \verb!return resultat!

Il est possible de ne pas avoir besoin de paramètre, on mettra alors des parenthèses vides.

En Python, la fonction doit forcément retourner quelque chose. Si on ne veut rien retourner, on pourra utiliser le mot-clé « \verb!None! » : \verb!return None!.

B

Utilisation d'une fonction

Dans le reste du programme, on peut faire appel à une fonction en utilisant son nom et en mettant entre parenthèses les paramètres demandés.

Le programme Python suivant affiche l'aire du rectangle de longueur x de largeur y, puis celle du rectangle de longueur 3 et de largeur 2.

En Python :

\verb!#definition de la fonction!
\verb!def aire_rectangle(longueur, largeur):!
    \verb!return longueur*largeur!

\verb!#Programme principal!
\verb!x=10!
\verb!y=5!
\verb!print("Aire 1 : ", aire_rectangle(x,y))!
\verb!print("Aire 2 : ", aire_rectangle(3,2))!

Le programme renvoie :

Aire 1 : 50
Aire 2 : 6

L'ordre des paramètres est important.

On définit une fonction « soustraction » qui soustrait deux nombres et renvoie le résultat, puis on l'utilise.

En Python :

\verb!def soustraction(a, b):!
    \verb!return a-b!
\verb!print("10 − 5 = ", soustraction(10,5))!
\verb!print("5 − 10 = ", soustraction(5,10))!

Le programme renvoie :

10 − 5 = 5
5 − 10 = −5

Le nom des paramètres ne concerne que l'intérieur de la fonction. 

Dans le programme principal, ces paramètres ne doivent pas s'appeler obligatoirement « longueur » et « largeur ». À l'inverse, le programme pourrait contenir des variables nommées « largeur » et « longueur » qui n'ont rien à voir avec les paramètres de la fonction.

Le programme suivant retourne "25" car {5}^{2}=25.

\verb!def carre (x):!
    \verb!return x*x!

\verb!cote = 5!
\verb!x= 3!
\verb!print(carre(cote))!

C'est donc la valeur de « \verb!cote! » que la fonction prend en paramètre, même si il y a une variable nommée \verb!x! dans le programme.

Le « \verb!x! » du bloc fonction fait référence au paramètre, il contient la valeur qu'on a donné à la fonction (ici, 5), et pas à la variable « \verb!x! » du programme.

Les commandes \verb!print()!, \verb!int()! ou \verb!input()! que l'on a utilisées jusqu'à présent sont en fait des fonctions qui sont déjà intégrées à Python, c'est-à-dire qu'elle sont déjà définies sans qu'on ait besoin de le faire, prêtes à être utilisées.