Algorithmes sur les nombres

Ce stage permet de présenter les éléments d'algorithmiques présents dans
les programmes de lycée :
- dans les constructions géométriques et les feuilles de calcul présentes
dès la seconde
- dans les programmes de Terminale L pour des algorithmes qui ne sont pas
nécessairement numériques.
- dans les programmes de Première S où les notions de boucles et de tests
sont au programme. - dans les premières STG (logique Algorithmique). - dans les programmes des Terminales STI. Ils peuvent prendre plusieurs formes :
- sur calculatrice pour les élèves et/ou sur calculatrice rétroprojectables
ou simulateurs pour l'enseignant
- pour atténuer la différence entre calculatrice, il peut être fait le
choix de travailler sur un logiciel permettant de travailler
l'algorithmique. Le logiciel Execalgo (gratuit, source :
http://ldif.education.gouv.fr/wws/d_read/eduscol.maths-
l/Document%20accompagnement/ ) permet de le faire avec une syntaxe en
français, un logiciel numérique comme Scilab (gratuit, en français :
http://www.scilab.org/download/) permet de pratiquer l'algorithmique à
égalité entre les élèves. Ce logiciel possède l'avantage d'être un traceur
de courbes et d'avoir un langage semblable à celui employé sur TI et Casio.
- les constructions géométriques nécessitent parfois de pratiquer des
notions d'algorithmique (répétition de construction) et ce, dès la seconde.
- les connaissances sur les tests se révèlent parfois nécessaires sur la
constitution de feuilles calcul sur un tableur (simulation en seconde,
feuilles de calcul en Première L, Epreuve pratique en TS) L'utilisation du
copier/coller permet de pratiquer une répétition, les tableurs sont
également capables d'itérations (boucles). Enfin, le tableur permet de
visualiser ou non des résultats ou des constructions : ces affichages
conditionnels sont pensés dans la construction des instructions ou bien
dans le cadre de mises en forme conditionnelles. Après une première partie de présentation des éléments d'algorithmique,
nous pratiquerons cette notion sur des exemples simples qui résument les
différents cas que l'on peut rencontrer. Les algorithmes sont
essentiellement de deux formes, soit numériques soit permettant la
répétition d'un mécanisme (recette de cuisine) ou d'une construction.
Nous reviendrons sur la programmation sur calculatrice même si ce n'est pas
le but de ce stage. La traduction en tel ou tel langage n'est pas le but.
Nous verrons ensuite comment pratiquer la programmation sur un tableur,
comme celui d'OpenOffice (nous pourrons visualiser également sur Excel la
démarche).
Enfin, nous terminerons par la pratique de l'algorithmique sur une
construction géométrique. Ecriture des algorithmes
Un algorithme est une suite d'actions à effectuer pour obtenir, à partir de
données initiales, la solution d'un problème. Comme il existe souvent
plusieurs manières de résoudre un problème, on peut imaginer plusieurs
algorithmes plus ou moins différents. Il doit pouvoir être effectué
exactement, et dans un temps fini, par un homme utilisant des moyens
manuels. Dans l'expression d'un algorithme, il n'est pas nécessaire de faire appel à
un langage de programmation, le langage courant suffit.
Ex : Détermination de la parité d'un nombre entier
- Demander à l'utilisateur de taper un nombre entier
- Lire ce nombre
- S'il est pair, afficher "Nombre Pair" sinon afficher "Nombre
Impair".
Un organigramme constitue une expression graphique d'un algorithme. On y
distingue trois types d'éléments :
- Les suites d'instructions, dites séquentielles, représentées par des
rectangles.
- Les conditions ou test portant sur des expressions qui orientent la
marche du programme, représentées par des losanges.
- L'ordre dans lequel le programme avance de l'un des éléments
précédents à un autre est indiqué par une flèche. [pic] Les variables
Ces données ainsi que les résultats des calculs intermédiaires ou finaux,
sont rangés dans des "cases-mémoires" appelées variables que l'on repère
par des identificateurs (que l'on choisira autant que possible
significatifs).
Les contenus des variables sont de nature diverse, évoluent pendant
l'exécution des algorithmes, mais une variable ne peut contenir au cours du
traitement que des données de même nature : Le type d'une variable est l'ensemble des valeurs possibles de son contenu.
Le type définit la nature et le champ des valeurs successives de la
variable, On précise ainsi l'intervalle ou l'ensemble de définition. On
distingue : Les types élémentaires :
- les types numériques : ENTIER et REEL. Distinction entre ces types
car l'ordinateur ne réserve pas de la même place mémoire et vu la
limitation de la mémoire, il ne les considère pas de la même manière :
approximation pour les réels ( 0.99999999999 pour 1, même si à l'affichage,
il indique 1) et valeurs exactes pour les entiers
- le type BOOLEEN (deux valeurs possibles : "vrai", "faux")
- le type CHAÎNE (ou chaîne de caractère)
Les types structurés :
- le type TABLEAU ou MATRICE (à une ou plusieurs dimensions)
- le type ENREGISTREMENT (ou type composé)
Dès le début du traitement, on indique (par exemple, dans un tableau), la
liste des variables qui seront utilisées en précisant pour chacune d'elles
le nom, le type ainsi que le rôle de cette variable dans l'algorithme.
Les instructions
Les instructions élémentaires
- La lecture au clavier du contenu d'une ou plusieurs variables :
LIRE(variable) ; LIRE(A,B,C)
Remarques : la lecture au clavier s'achève dès que l'on presse la touche
"entrée" (ou "retour chariot"). La donnée tapée doit être du même type que
la variable qui la reçoit.
- L'affichage à l'écran (ou l'édition sur imprimante) d'un objet (nombre,
chaîne, ...) du contenu d'une ou plusieurs variables, d'une expression, ...
ECRIRE('Prix de revient = ',P_Achat + Frais)
- L'affectation (donner une valeur au contenu d'une variable) :
Nom de Variable ( Expression (la flèche ( peut se lire reçoit)
ex : P_Vente ( P_Achat + Frais + Bénéfices - L'appel d'une fonction (algorithme défini par ailleurs) Les instructions composées
- Un bloc d'instructions est une suite d'instructions (élémentaires ou
non) séparées par des points-virgules et encadrées des deux mots DEBUT et
FIN. Dans la suite, "instruction" désignera soit une instruction
élémentaire soit un bloc.
- Les instructions conditionnelles :
L'alternative : On effectue un test pour choisir entre deux instructions
possibles :
SI ALORS instruction_1
SINON instruction_2;
La conditionnelle simple : même structure mais la deuxième instruction
est vide :
SI ALORS instruction_1; La conditionnelle multiple :
SELON NomVar
Cas_1 : Instruction_1;
Cas_2 : Instruction_2;
...
Cas_n : Instruction_n;
FIN; - Les instructions répétitives (ou boucles): une même séquence est
répétée un certain nombre de fois.
La boucle POUR : on connaît exactement le nombre de répétitions à
effectuer. On utilise un compteur de boucles :
POUR i VARIANT DE a A b EFFECTUER Instruction; La boucle TANT_QUE : elle fonctionne comme la précédente, sauf que le
test d'entrée dans la boucle est effectué avant l'exécution de
l'instruction, on ne connaît pas toujours le nombre de répétition à
effectuer :
TANT_QUE EFFECTUER instruction; Remarque : Cette dernière boucle est la plus générale. Si la condition
d'entrée est fausse dès le début, l'instruction n'est jamais effectuée,
alors qu'elle est exécutée au moins une fois dans la boucle REPETER. La boucle REPETER : elle est un peu moins générale que la précédente. Si
la condition d'entrée est fausse dès le début, l'instruction est exécutée
au moins une fois dans la boucle REPETER alors qu'elle n'est jamais
effectuée, dans la boucle TANT QUE.
REPETER instruction EFFECTUER ;
Utilisations de la calculatrice Exercice 1 1) Calculer, en utilisant la calculatrice (préciser le modèle de
calculatrice utilisé)
A = 123 456² - 123 455 ( 123 457
B = 456 789² - 456 785 ( 456 793
C = 123 456 789² - 123 456 787 ( 123 456 791
2) Donner les résultats exacts. Pour cela, dans chaque expression :
- appeler x le premier nombre élevé au carré
- exprimer les deux autres en fonction de x
- écrire plus simplement l'expression en fonction de x, en développant
3) Calculer D = 123 456 789 010² - 123 456 789 009 ( 123 456 789 011
Exercice 2 Calculer, en utilisant la calculatrice a - b avec a = 1234567891234567892
et b = 123456789132456788(123456789123456790.
Ce résultat vous semble-t-il juste ?
Exercice 3 Les décimales cachées
1) Afficher le nombre sur votre calculatrice.
Soustraire 3 et multiplier par 10.
Soustraire 1 et multiplier par 10.
Et ainsi de suite : soustraire la partie entière et multiplier par 10,
plusieurs fois.
Finalement, combien votre calculatrice connaît-elle de décimales de ?
Combien en affiche-t-elle ?
2) a) Faire afficher à votre calculatrice.
Grâce à la méthode précédente, faire afficher les décimales cachées de
votre calculatrice.
b) Faire afficher le quotient et ses décimales cachées.
A combien près cette fraction est-elle une valeur approchée de ?
Comment peut-on être sûr de l'exactitude d'une certaine décimale ? Exercices : Savoir exécuter un algorithme numérique élémentaire I. Dans cet algorithme a, b, c désignent des variables numériques
début
a(5;
b(12;
c(2*a-b;
b(2*b-c*3;
a(b-a*4+c*5;
écrire('A=',a,' B=',b,' C=',c);
fin.
1) Exécuter cet algorithme
2) Le ré