Introduction aux algorithmes
- Fiche de cours
- Quiz
- Profs en ligne
- Videos
- Application mobile
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.
• É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).
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.
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.
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.
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.
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) :
Ainsi qu’une utilisation :
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.
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.
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 0
N »
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.
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.
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 0  NSI 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 0
N »
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 |
|
|
Comment as-tu trouvé ce cours ?
Évalue ce cours !
Vous avez obtenu75%de bonnes réponses !
Recevez l'intégralité des bonnes réponses ainsi que les rappels de cours associés :
Fiches de cours les plus recherchées
Mathématiques
Exploiter la relation y = f(x) d'une fonction- Terminale- Mathématiques
Mathématiques
Fonction logarithme décimal- Terminale- Mathématiques
Mathématiques
CanardMasqué présente : Les systèmes de numération
Mathématiques
Le vocabulaire des probabilités
Mathématiques
Utilisation du tableur pour des tableaux croisés
Mathématiques
Isoler une variable
Mathématiques
Appliquer une formule
Mathématiques
Coefficient directeur de la tangente à une courbe en un point
Mathématiques
Somme des termes d'une suite arithmétique- Terminale- Mathématiques
Mathématiques
Somme des termes d'une suite géométrique- Terminale- Mathématiques
Mathématiques
Fonctions exponentielles de base q
Mathématiques
La fonction inverse- Terminale- Mathématiques
Mathématiques
Ajustement affine
Fermer
Accédez gratuitement à
