La réussite scolaire pour tous !

Cours de mathématiques Terminale S - Introduction aux algorithmes


Note par nos Maxinautes :  
Objectif(s)
• Écrire une formule permettant un calcul.
• Écrire un programme calculant et donnant la valeur d’une fonction.
• Écrire les instructions d’entrées et sorties nécessaires au traitement.
Remarque
Les algorithmes de ce cours seront traduits en programmes pour les calculatrices TI-Stats (TI-83 et TI-84 identiques), Casio Graph35+ (ou équivalente), TI-Nspire Cas (qui acceptera quelques programmes spécifiques car c’est une calculatrice formelle).
1. Introduction
a. Algorithme, algorithmique
Au collège, on découvre l’algorithme d’Euclide pour calculer le PGCD de deux nombres, depuis la classe de 3e rechercher quelques valeurs d’une fonction c’est faire de l’algorithmique. Utiliser un tableur, construire des formules reliant le contenu de certaines cellules pour obtenir un résultat, c’est aussi faire de l’algorithmique. Les exemples de pratiques sont nombreux.

Qu’est-ce que l’algorithmique ? L’algorithmique c’est créer des algorithmes.
Un algorithme est un processus (procédé) fini permettant d’obtenir un résultat.
Un algorithme consiste à écrire une suite d’instructions logiques qui doivent permettre d’obtenir le résultat d’un problème que l’on se pose.
Un algorithme est normalement traduit en instructions comprises par une machine, ordinateur, calculatrice, pour effectuer les calculs nécessaires à l’obtention du résultat espéré. C’est programmer l’algorithme.
b. Mise en garde
L’algorithmique demande de la rigueur, de la réflexion, de la patience ainsi qu’un certain apprentissage pour arriver à réaliser bien peu de choses au départ.
Il faut traduire l’algorithme sur une machine, une calculatrice, pour en voir les effets (sauf de petits algorithmes, exemples que l’on pourra faire « tourner à la main »).
Il faut alors bien connaître sa calculatrice pour trouver la liste des instructions à utiliser.
Il ne faut pas de suite vouloir absolument résoudre des problèmes difficiles et compliqués sans prendre le temps de dominer la partie réflexion et apprentissage.
2. Un petit exemple commenté
Le problème : un nombre donné est-il pair ?

Poser la question : "23 461 963 487 (il faut le dire vingt trois milliards quatre cent soixante et un millions…) est-il pair ?" a pour nous une réponse immédiate.
Non, car il ne se termine pas par 0 ou 2 ou un multiple de 2.

Si l’on suppose que ce problème est posé à une machine, par exemple dans une ferme avicole où chaque jours sont produits plusieurs milliers d’œufs, où il faut les regrouper en nombres pairs pour les mettre dans des boites, comment demander cela à la machine trieuse ?
Ce sera très dur, car par exemple sur une calculatrice, il n’y a pas d’instruction qui donne directement le dernier chiffre d’un nombre (c’est envisageable, c’est compliqué, surtout pour un premier exemple).
Il faut connaître une autre méthode ou « ruser » pour obtenir ce que l’on cherche.

Comment reconnaître un nombre pair ? C’est un multiple de 2, c’est la raison qui fait qu’il se termine obligatoirement par 0, 2, 4…

Réflexion
Si je divise un nombre entier par 2 et que le nombre trouvé est entier, c’est que le nombre de départ est pair.
Est-ce qu’une calculatrice sait ce qu’est un entier ? Pas tout à fait, elle sait qu’un nombre est constitué d’une partie entière et d’une partie décimale.

Le principe de résolution du problème : si la partie entière de (nombre/2) est (nombre/2) cela veut dire qu’il n’a pas de partie décimale.

Remarque
Il serait plus simple (apparemment) de regarder si la partie décimale est nulle… nous verrons que cela pose problème, cela sera traité ultérieurement.

On écrit l’algorithme correspondant en langage raisonné, selon des règles strictes. Il faut indiquer les variables utilisées, indiquer ce qui sera entré dans la machine, ce qui en sortira, et les traitements réalisés. (Cela sera indiqué à partir de la fiche suivante.)

Nombre pair ou impair (positif) Version 1 Commentaires
Variables
               N entier
Entrées
               Lire N
Traitement
Afficher le titre de l’algorithme
Afficher « Entrer un nombre entier positif »
Entrer N
SI partie entière (N/2)=N/2 ALORS
                 Afficher « N est pair »
SINON
                 Afficher « N est impair »
FIN SI
Sorties
                 Affichages du traitement
Il est conseillé de toujours donner un titre, un mode d’emploi au début du programme que l’on prépare, car il est toujours difficile de "revenir" sur un programme après un certain temps d’oubli.

Cet algorithme est simple, faisons le tourner à la main :
Il faut entrer un nombre entier positif, par exemple 101.
• Si la partie entière de 101/2 (c’est 50) vaut 101/2 = 50,5 (ce qui n’est pas vrai) alors afficher que "101 est pair" (ce ne sera donc pas affiché).
• Sinon (c’est le cas) afficher que "101 est impair".
 





















Une traduction sur calculatrice est réalisée (les instructions sont présentées à la suite les unes des autres, alors qu’elles occupent souvent plusieurs écrans) :

TI- 84
TI-82 Stat TI-83
Casio Graph 35+
TI-Nspire CAS

Ainsi qu’une utilisation :

TI- 84
TI-82 Stat TI-83
Casio Graph 35+ TI-Nspire CAS

Remarques
• Si dans ce programme je choisis 102,56, j’aurai l’indication que 102,56 est impair ce qui est une erreur. Il faut en tenir compte et essayer d’empêcher les erreurs dues à des entrées non autorisées.
• 102,24 se termine par 4, pourtant ce n’est pas un nombre pair, ni d’ailleurs un nombre impair, il faut un entier, pourtant le programme dit que ce nombre est impair.

• De même on considèrera que -12 n’est pas un nombre pair, il faut qu’il soit entier et positif.

Il est très simple de rajouter quelques instructions pour que les erreurs remarquées dans l’exécution du programme soient corrigées.
3. Deuxième algorithme, tentative de correction des erreurs
On a remarqué que si le nombre n’est pas entier, la réponse (fausse) est toujours « Nombre impair ».
Pour corriger cette erreur « prévisible », il suffit d’utiliser une boucle qui demande d’entrer un nombre jusqu’à ce que ce nombre corresponde aux exigences prévues. Cette boucle sera vue plus précisément dans le prochain cours.

Logique et raisonnement

Il faut que N, un nombre entré au clavier, soit entier et positif (sens large car 0 est bien un nombre pair).

Cela représente deux conditions :
α) nombre entier (ce qui sera testé par PartieEntière(N) = N) ;
β) nombre positif (ce qui sera testé par 0 ≤ N).

La condition doit-elle s’écrire :
a1) « Répéter Lire N Jusqu’à ce que PartieEntière(N) = N) ET 0 ≤ N » ;
a2) « Répéter Lire N Jusqu’à ce que PartieEntière(N) = N) OU 0 ≤ N » ;
a3) « Répéter Lire N Jusqu’à ce que PartieEntière(N) = N) ET N < 0 » ;
a4) « Répéter Lire N Jusqu’à ce que PartieEntière(N) = N) OU N < 0 » ;
a5) « Répéter Lire N Jusqu’à ce que PartieEntière(N) ≠ N) ET 0 ≤ N » ;
a6)
« Répéter Lire N Jusqu’à ce que PartieEntière(N) ≠ N) OU 0 ≤ N » ;
a7) « Répéter Lire N Jusqu’à ce que PartieEntière(N) ≠ N) ET N < 0 » ;
a8) « Répéter Lire N Jusqu’à ce que PartieEntière(N) ≠ N) OU N < 0 ».

Réfléchir à la réponse à donner.

Remarque 
Prendre l’habitude de tester avec la calculatrice n’est pas une bonne solution… Si l’on est en train de mettre au point un logiciel réglant des feux tricolores, on ne peut se permettre de faire des essais jusqu’à ce qu’il n’y ait plus d’accidents.

C’est la proposition a1) qu’il faut utiliser.


Nombre pair ou impair (entier positif) Version 2
Variables
                N entier
Entrées
                Lire N
Traitement
Afficher le titre de l’algorithme
Répéter
                Afficher « Entrer un nombre entier positif »
                Entrer N
Jusqu’à ce que partie entière (N)=N ET 0N
SI partie entière (N/2)=N/2 ALORS
                Afficher « N est pair »
SINON
                Afficher « N est impair »
FIN SI
Sorties
                Affichages du traitement
 





















Remarques

La boucle à utiliser est la boucle "répéter… jusqu’à ce que".
Sur la Graph35+ cette instruction n’existe pas, on utilise alors avec un petit changement la boucle "tant que".
De même, sur la TI-Nspire CAS, cette boucle existe en LUA à partir du logiciel ordinateur. Sur la calculatrice, on utilisera aussi la boucle "tant que".
Ce qui change la façon de tester la condition, il faut initialiser la variable N à une valeur non autorisée, par exemple -1, puis transformer "Jusqu’à ce que partie entière (N) = N ET 0N » en "Tant que N < 0 ou partie entière (N) ≠ N".

La condition doit-elle alors s’écrire :
b1) « Répéter Lire N Jusqu’à ce que PartieEntière(N) = N) ET 0 ≤ N » ;
b2) « Répéter Lire N Jusqu’à ce que PartieEntière(N) = N) OU 0 ≤ N » ;
b3) « Répéter Lire N Jusqu’à ce que PartieEntière(N) = N) ET N < 0 » ;
b4) « Répéter Lire N Jusqu’à ce que PartieEntière(N) = N) OU N < 0 » ;
b5) « Répéter Lire N Jusqu’à ce que PartieEntière(N) ≠ N) ET 0 ≤ N » ;
b6) « Répéter Lire N Jusqu’à ce que PartieEntière(N) ≠ N) OU 0 ≤ N » ;
b7) « Répéter Lire N Jusqu’à ce que PartieEntière(N) ≠ N) ET N < 0 » ;
b8) « Répéter Lire N Jusqu’à ce que PartieEntière(N) ≠ N) OU N < 0 ».

C’est la proposition b8) qu’il faut utiliser.

Nombre pair ou impair (entier positif) Version 2bis
Variables
                N entier
Entrées
                Lire N
Traitement
Afficher « pair ou impair »
Affecter N par -1
                   TantQue PartieEntière (N) ≠ N OU N < 0
                   Afficher « Entrer un nombre entier positif »
                   Entrer N
                   FinTantQue
SI partie entière (N/2)=N/2 ALORS
Afficher « N est pair »
 

Une traduction sur calculatrice est réalisée, les instructions sont présentées à la suite les unes des autres, alors qu’elles occupent souvent plusieurs écrans.
Le programme est renommé en pair02.

TI- 84
TI-82 Stat TI-82
Casio Graph 35+
TI-Nspire CAS

Introduction aux algorithmes 3/5 basé sur 76 votes.
Vous êtes ici :
Accueil > Fiches de cours du CP à la Terminale > cours de Mathématiques > Terminale S > Introduction aux algorithmes
Voir tout le contenu pédagogique relatif à ce sujet
Connexion ou Créer un compte