LOGO
c'est pas que
pour les enfants !!!
|
Alain BOIS |
Jean-Louis Guillot |
LOGO
c'est pas que
pour les enfants !!!
|
Alain BOIS |
Jean-Louis Guillot |
IREM des PAYS de la LOIRE
LOGO
Géométrie Tortue, Arithmétique, Fractales et autres algorithmes ...
Formation de Formateurs IREM - 12/2002 et colloque EMF de Tozeur - 12/2003
Souvenirs ...
Les micro-mondes
Comment communiquer ?
Des mots et des phrases pour le faire
Un peu de grammaire LOGO
Entrer les données et contrôler les procédures
Simulation du comportement animal
Comment simuler l'odorat d'un prédateur
Courbes de poursuite
Calcul du PGCD et du PPCM
Recherche des nombres premiers
Les nombres parfaits
Les congruences: Calcul de la clé RIB d'un compte chèque
Calcul des éléments de la suite de Fibonacci
Egalité de Bezout et récursivité non terminale
Barycentre et théorème de Guldin
Il n'y a pas si longtemps, la tortue se promenait sur le sol de la classe ...
Puis elle est venue dans l'ordinateur, petit triangle bleu dans son aquarium ...
C'est bien facile de la faire se déplacer ... elle parle presque le même langage que nous.
Elle parle en LOGO. Elle connaît les mots avancer, reculer, tourner à droite, à gauche, lever le crayon, baisser le crayon, vider l'écran ... Elle sait où elle est, où elle va, elle mémorise ce qu'on lui demande de garder, elle peut nous donner les renseignements qu'elle connaît.
Elle se comporte presque comme nous :
AV (avance) le nombre de pas,
RE (recule),
TG (tourne à gauche) le nombre de degrés,
TD (tourne à droite),
LC (lève crayon),
BC (baisse crayon),
VE (vide écran),
MT (montre tortue),
CT (cache tortue),
POUR (apprends ... jusqu'au mot FIN)
ME (mixte écran) fixe le nombres de lignes de texte, sous l'espace tortue.
...
La tortue et sa géométrie n'est pas seule dans le monde LOGO.
Elle peut vivre avec d'autres robots différents (autres tortues, chariots élévateurs, bras articulé, tables traçantes, tours, ... ).
Il y a aussi le monde des nombres, le monde des mots et des listes, celui de la musique, ... et bien d'autres mondes aussi.
En bref, tous ceux que vous aurez envie d'inventer, des micro-mondes, à l'intérieur et à l'extérieur de l'ordinateur. En parlant LOGO.
Vous avez deux possibilités, lorsque vous travaillez avec l'ordinateur et la console jLogo (on retrouve ces principes dans la plupart des environnements LOGO) :
Si vous avez réussi, vous devez obtenir le dessin suivant :
Des mots et des phrases pour le faire
Au chargement LOGO connaît un certain nombre de mots. Ce sont les procédures primitives. En raccourci, les primitives.
EC CONTENU permet d'obtenir la liste des primitives disponibles.
EC COMPTE CONTENU donne le nombre des primitives.
Programmer en LOGO, c'est construire de nouveaux mots, les procédures, qui viennent s'ajouter aux primitives, et vous organisez tous ces mots ensemble selon votre projet. Vous apprenez des mots nouveaux au système.
Si vous avez gardé dans l'éditeur la phrase - la liste d'instruction - qui permet d'obtenir le dessin précédent, il vous suffit de la compléter sous la forme du paragraphe suivant pour construire une nouvelle procédure nommée TRUC
POUR TRUC <- le titre de la procédure seul en ligne 1
AV 100 TD 90 AV 100 TD 90 AV 50 TD 90 AV 50 TD 90 AV 100 TD 90 AV 25 TD 90 AV 25 TD 90 AV 50
FIN <- seul en dernière ligne (fin d'apprentissage)
Sortez de l'éditeur un validant et vous obtenez un nouveau mot qui fonctionne exactement comme les autres. Tapez successivement en mode direct :
VE
TRUC
VE TRUC TG 90 AV 125 TD 90 AV 25 TD 90
VE REPETE 4 [TRUC]
VE REPETE 20 [TRUC TD 10 AV 50]
VE REPETE 20 [TRUC TG 45 AV 100]
Avec jLogo, vous pourrez utiliser les onglets :
La partie graphique peut être diminuée en relevant la barre qui la sépare du texte du "journal" en utilisant la souris.
Vous pouvez également utiliser la procédure ME.
ME 5
réservera 5 lignes de texte afficher le "journal" des commandes et des réponses.
CARRE et TRIANGLE (équilatéral) ne figurent pas parmi les primitives ... vous devrez donc les apprendre à LOGO, comme vous avez fait pour TRUC.
Nous décrivons ici seulement les éléments qui vont nous servir dans la suite. De nombreux objets LOGO sont disponibles ou peuvent être créés.
Les objets LOGO pour lire et écrire sont les mots et les listes. Les mots sont écrits avec les caractères usuels et séparés par les espaces. Les nombres sont des mots particuliers ne comportant que des chiffres et s'il y a lieu la virgule ou le point pour séparer la partie décimale.
Les noms des primitives et des procédures (les "exécutables") sont des mots comme AV, REPETE, TRUC ....
Si un mot doit être pris comme une constante non exécutable, comme une donnée ou un identificateur (nom de variable) on le fait précéder d'un guillemet double sauf si c'est un nombre et sauf s'il est un élément d'une liste.
|
"CANARD
125 1357,89 [CANARD 125 1357,89] [maison "5" CANARD "125 [1 a 3]] |
<- un mot
<- un mot qui est un nombre entier <- un mot qui est un nombre décimal <- la liste des trois mots ci-dessus <- une liste de trois éléments |
Une liste est une suite de mots ou de listes.
Vous devrez l'écrire entre crochets, mais LOGO vous la reproduira en supprimant les crochets de début et de fin.
| EC [maison "5" CANARD "125 [1 a 3]] maison "5" CANARD "125 [ 1 a 3 ] EC "CANARD CANARD |
<- vous demandez à LOGO d'écrire |
Les opérations (ou fonctions) produisent un résultat (un objet utilisable) et les commandes réalisent une action sur l'environnement.
| EC 2 + 3 EC SOMME 2 3 |
<- opération addition "infixée" <- opération addition "préfixée" |
Les deux instructions produisent 5 comme résultat. La commande EC écrit le nombre 5. Si vous oubliez de taper EC, LOGO dira :
Que faire de 5 ?
C'est comme ça que vous ferez des phrases compliquées.
AV SOMME PROD 2 10 RESTE 24 5
AV SOMME PROD RESTE 24 5 2 10 c'est différent !
Vous pouvez construire des procédures qui sont des commandes, d'autres qui sont des opérations (ou fonctions), d'autres qui sont les deux à la fois.
Certaines fonctions n'ont aucune entrée (argument, paramètre):
POSITION rend la liste des coordonnées de la tortue
CAP rend le cap de la tortue
Certaines fonctions ont une seule entrée :
PREM liste rend le premier élément de la liste ou le premier caractère du mot
RC nombre rend la racine carrée de nombre
Certaines fonctions ont deux entrées :
MOT "car "table rend le mot "cartable
Si on dispose de plusieurs objets en entrées, on peut s'organiser (ne tapez pas le point d'interrogation):
? EC PH PH PH PH MOT MOT "4 "+ "3 [est la somme de] "4 "et "3
4+3 est la somme de 4 et 3
En plus des fonctions mathématiques, et de celles qui opèrent avec les mots et les listes et qui rendent des nombres, des mots ou des listes, LOGO fournit des prédicats.
Un prédicat est une fonction comme celles que nous venons de décrire, mais elle rend comme résultat le mot "VRAI ou le mot "FAUX. Les opérations booléennes sont des prédicats qui ont aussi comme entrée les valeurs booléennes "VRAI ou "FAUX.
C'est très commode à utiliser pour écrire les conditions des tests.
EC ET PLG? RC 2 1,41 PLP? RC 2 1,42
VRAI
Il est bien vrai que racine de 2 est plus grand que 1,41 et plus petit que 1,42
ET est une opération booléenne préfixée ayant deux entrées booléennes.
PLG? et PLP? sont deux prédicats ayant chacun deux nombres comme entrée.
C'est facile à comprendre lorsque vous n'avez pas d'entrée (pas de paramètres) à entrer par exemple, si vous voulez obtenir l'abscisse de la position de la tortue vous définirez la fonction XCOR. Le mot magique est RENDS qui produit un objet directement utilisable dans vos phrases comme EC SOMME 15 XCOR.
POUR XCOR
RENDS PREMIER POSITION
FIN
L'entrée des données sera détaillée au paragraphe suivant. Vous pourrez alors créer avec le mot magique RENDS la procédure DIFFERENCE inconnue en LOGO pour l'utiliser comme SOMME, PROD, RESTE ... avec ses deux entrées.
Entrer les données et contrôler les procédures
Étudions maintenant l'affectation des variables, les tests, la répétition, la récursivité et la récursivité non terminale.
Il y a bien des primitives comme LISCAR (qui prend le caractère tapé au clavier) ou LISLISTE (qui prend toute la phrase tapée au clavier jusqu'au retour de chariot), qui ressemblent un peu au get ou à l'input ou bien au readln ou read que certains connaissent. De toute façon, il faut bien ranger quelque part une donnée qui vient du clavier, ou l'utiliser tout de suite dans une fonction ou une commande pour en faire quelque chose.
La plupart du temps, en LOGO, vous êtes directement dans l'espace de travail, aux commandes de tout l'environnement. Vous allez tout de suite agir avec les primitives ou les procédures qui vous sont nécessaires, et vous leur donnez directement les données (arguments?) dont elles ont besoin. Admettons par exemple que vous ayez besoin de faire des carrés de différentes tailles. Vous écrirez la procédure :
POUR CARRE :COTE
REPETE 4 [AV :COTE TD 90]
FIN
Puis une fois qu'elle sera validée, vous commanderez en mode direct, suivant ce qu'il vous plaira :
CARRE 10
CARRE 50
etc...
Tout se passe comme vous procédiez chaque fois à une affectation de variable, mais c'est fait directement à l'appel de la procédure (sans "input", "read" ...).
En fait, vous avez créé la variable dont le nom est le mot "COTE et dont le contenu est désigné par :COTE (valant successivement 10, puis 50, puis ...). Cette variable a été crée dans le titre de la procédure; c'est une entrée de la procédure CARRE.
Vous pouvez l'utiliser dans le corps de la procédure comme bon vous semble. Par exemple, insérez l'instruction suivante, puis testez la nouvelle procédure.
EC PH PH [Je viens de faire le carré de] :COTE [pas de côté.]
Une variable peut également être définie dans le corps d'une procédure ou directement au niveau supérieur, sans avoir lancé de procédures.
On utilise les commandes DONNE ou SOIT. Tapez en mode direct les deux commandes et vous retrouvez dans votre tirelire ce que vous y aurez mis.
? DONNE "tirelire "20€
? EC :tirelire
20€
De façon analogue essayez :
? SOIT "X 12,5
? EC :X
12,5
Le contenu de la tirelire est le mot 20€ et celui de X est le nombre 12,5
Contrairement à l'apparence, ces deux affectations de variables fonctionnent différemment.
La commande "DONNE produit une variable globale, c'est-à-dire connue de toutes les procédures qui l'appelleront ou de vous-même, au niveau supérieur.
Par contre, la commande "SOIT produit une variable locale, qui n'est connue que par les niveaux d'appels inférieurs à celui où elle a été créée.
Comme vous avez fait "X au niveau supérieur, tout le monde verra son contenu, comme si c'était une variable globale. Par contre la variable "COTE créée par la procédure CARRE n'est pas accessible au niveau supérieur, c'est une variable locale. Tout se passe comme si vous l'aviez définie en utilisant la commande SOIT à l'intérieur de la procédure CARRE.
? EC :COTE
Pas de chose donnée à COTE
Comme structure itérative, LOGO utilise le mot REPETE et la récursivité.
Répétition :
REPETE le nombre de fois indiqué la liste d'instructions qui est écrite.
Récusivité :
Une procédure récursive est une procédure qui s'appelle elle même. Pensez plutôt que des procédures "clones" s'appellent successivement :
La première appelle la deuxième qui appelle la troisième qui appelle ...
en espérant qu'un évènement arrêtera cette chaîne infernale.
POUR CARRE :COTE
REPETE 4 [AV :COTE TD 90]
CARRE :COTE + 10
FIN
Plutôt que d'attendre que la tortue se cogne contre les murs, ou que l'ordinateur fonde, vous préfèrerez prévoir un test d'arrêt lorsque vous entreprendrez une récursivité.
Condition simple si ... alors :
si condition
alors action
suitePOUR CARRE :COTE
REPETE 4 [AV :COTE TD 90]
SI PLP? :COTE 100 [CARRE :COTE + 10]
FIN
N'oubliez pas de mettre sur la même ligne d'instructions le SI, la condition (prédicat) et la liste d'instructions (entre crochets). Lorsque la condition n'est pas réalisée, on passe à la suite, (ligne du dessous) qui peut être le mot FIN
Dans l'exemple ci-dessus vous avez en fait reconstitué une structure du type
faire action
jusqu'à condition
suite
En changeant la place du test, il est facile de réaliser la structure
tant que condition
faire action
suite
Vous reconstituez de la sorte les structures itératives élémentaires des autres langages de programmation avec récursivité et condition simple.
Condition alternative si ... alors .. sinon :
si condition
alors action 1
sinon action 2
suite
POUR CARRE :COTE
REPETE 4 [AV :COTE TD 90]
SI PLP? :COTE 100 [CARRE :COTE + 10][AV :COTE TD 30 REPETE 3 [AV :COTE TD 120]]
FIN
Comme précédemment, n'oubliez pas de mettre sur la même ligne d'instructions le SI, la condition (prédicat), et la liste d'instructions (entre crochets) à faire lorsque la condition est vraie, puis la liste d'instructions (entre crochets) à faire lorsque la condition est fausse. Après l'exécution de l'une de ces deux listes, on passe à la suite.
Si vous tapez CARRE 60 vous obtiendrez la figure suivante :
Imaginez bien les procédures qui s'appellent successivement (ce sont les acteurs, les ouvriers qui s'activent dès que vous avez passé votre commande):
CARRE 60
action 1 (dessin du carré de 60)
test VRAI
CARRE 50action 1 (dessin du carré de 60)
test VRAI
....
CARRE 100action 1 (dessin du carré de 60)
test FAUX
action 2 (déplacement puis triangle)
FIN
Le travail est fini. Le travail semble fini ...
Regardons d'un peu plus près.
Récursivité non terminale :
Modifiez la procédure précédente pour obtenir :
POUR CARRE :COTE
REPETE 4 [AV :COTE TD 90]
SI PLP? :COTE 100 [CARRE :COTE + 10][AV :COTE TD 30]
REPETE 3 [AV :COTE TD 120]
FIN
Essayez votre nouvelle procédure :
CARRE 60
Vous obtenez ceci :
Étonnant, non ? ... et ce n'est pas une erreur de LOGO !
En effet, lorsque les appels successifs sont terminés, le dernier ouvrier qui intervient, CARRE 100 exécute dans son test AV 100 TD 30, puis passe à la ligne suivante pour faire son triangle de 100.
Mais il n'a pas fini contrairement à ce que vous auriez pu croire ...
Par contre, il dit à CARRE 90 qui lui avait passé la commande que son travail est fini. Mais CARRE 90 remarque qu'il n'avait pas fini sa propre liste de commandes: il avait encore une instruction à faire après avoir fait travaillé son collègue. Il fait donc son triangle de 90 ... ensuite, il doit "rendre la main" à celui qui l'avait commandé, lui aussi a des comptes à rendre ! Et ils se repassent la main... Jusqu'à ce que CARRE 60 termine sa liste et vous rende la main à vous le véritable chef : tous les travailleurs ont terminé votre commande.
Pensez aussi à tous ces documents que vous empilez; pour revenir au premier, il faut bien refaire tout le chemin à l'envers, tout dépiler. Ici on dit souvent descendre la récursivité, puis la remonter.
Sommez une liste et faites la moyenne d'une liste de nombres :
POUR TOTAL :L
SI VIDE? :L [RENDS 0] [RENDS SOMME PREM :L TOTAL SP :L]
FIN
Faites la moyenne d'une liste de nombres :
POUR MOYENNE :L
RENDS DIV TOTAL :L COMPTE :L
FIN
Attention : DIV donne le quotient alors que QUOT donne le quotient entier.
? EC MOYENNE [12 16 18 14,5 13]
14,7
Mettez les mots à l'envers :
POUR ENVERS :M
SI VIDE? :M [RENDS "][RENDS MOT DER :M ENVERS SD :M]
FIN
DER pour dernier, et SD pour sauf dernier, agissent ici sur mots et caractères.
? ENVERS "LAPIN
Que faire de NIPAL ?
Comment simuler l'odorat d'un prédateur
Nous allons situer sur l'écran une proie dont la position va être définie par l'utilisateur et l'emplacement initial du prédateur (dans notre cas la tortue écran). Pour cela nous écrivons une procédure d'initialisation comme suit:
POUR INITIALISATION
EC [TAPEZ LA POSITION EN X ET Y DU PREDATEUR]
DONNE "POSPREDATEUR LL
EC [TAPEZ LA POSITION EN X ET Y DE LA NOURRITURE]
DONNE "POSNOURRITURE LL
LC FPOS :POSNOURRITURE
BC CROIX
LC FPOS :POSPREDATEUR
DONNE "ANGLE_ALEATOIRE HASARD 60
FIN
POUR CROIX
AV 2 RE 4 AV 2 TD 90 AV 2 RE 4
FIN
Ça va c'est pas trop dur !!!
Maintenant venons à la simulation simple de l'odorat, on considère que la tortue est sur le bon chemin lorsque la distance à la proie se raccourcit - dans ce cas elle continue à avancer - sinon on décide aléatoirement de la faire tourner de 1 degré vers la droite.
On va écrire une procédure-prédicat qui va signaler à la tortue que son odorat faiblit:
POUR SENTE_MOINS_BONNE?
RENDS PLG? DISTANCE POS :POS_NOURRITURE :DERNIERE_DISTANCE
FIN
Il nous faut initialiser la variable :DERNIERE_DISTANCE dans la procédure qui va lancer la recherche de nourriture.
POUR CHERCHER_NOURRITURE
DONNE "DERNIERE_DISTANCE DISTANCE POS :POS_NOURRITURE
AV 1
SI SENTE_MOINS_BONNE? [TD :ANGLE_ALEATOIRE]
TROUVER_NOURRITURE
FIN
Il nous reste à tester cette procédure pour voir l'effet produit :
Voici deux copies d'écran avec un angle de 10 degrés pour la première et un angle de 20 degrés pour la deuxième.
Il est possible de prévoir de l'aléatoire dans les marches de la tortue quand elle se rapproche de la proie ou jouer sur de l'aléatoire dans les angles de rotation.
Supposons que nous ayons deux animaux dont on veut modéliser le comportement, l'un part du centre de l'écran (le lièvre), l'autre part d'un point fixé à l'avance et peut se promener sur une droite ou un cercle fixé à l'avance (la tortue). C'est là que la possibilité d'avoir plusieurs tortues à l'écran est intéressante.
Vous allez commencer par initialiser la situation.
POUR INIT
VE
FTORTUE 1 vous allez donner les ordres qui suivent à la tortue 1, la tortue
LC FPOS [100 100]
DONNE "A 1
FTORTUE 0
CT
FTORTUE 2 vous allez donner les ordres qui suivent à la tortue 2, le lièvre
ORIGINE
FIN
POUR TOUT_VOIR
FTORTUE 1
FPOS PH DIFF PREM POS :A DER POS
DONNE "POS_TORTUE POS
FTORTUE 2
FCAP VERS : POS_TORTUE AV 1
SI PLP ? DISTANCE POS :POS_TORTUE 2 [STOP]
TOUT_VOIR
FIN
TAPEZ INIT puis TOUT_VOIR
Et vous allez en voir de toutes les couleurs, votre stratégie va changer si vous décidez de donner à la tortue une trajectoire sur un cercle. Voici quelques courbes obtenues :
C'est quoi au juste un flocon de Koch. Ça dépend du niveau de récursivité !! Au niveau 0, c'est juste un triangle équilatéral dont les côtés comme tous les côtés sont des simples traits.
Puis les traits se divisent eux-mêmes en 4 traits comme ceci:
Et ainsi de suite:
Et donc un flocon devient l'assemblage de ces nouveaux traits :
Voici comment on programme en Logo tout cela:
POUR COTE :TAILLE :NIVEAU
SI EGAL? :NIVEAU 0 [AV :TAILLE STOP]
COTE :TAILLE / 3 DIFF :NIVEAU 1
TG 60
COTE :TAILLE / 3 DIFF :NIVEAU 1
TD 120
COTE :TAILLE / 3 DIFF :NIVEAU 1
TG 60
COTE :TAILLE / 3 DIFF :NIVEAU 1
FIN
Expliquons un peu: si le niveau de récursivité est 0, la procédure va s'arrêter grâce au STOP après avoir tracé un trait simple "AV :TAILLE" mais si le niveau de récursivité est seulement 1, ça se complique: on croit naïvement quand on ne s'est pas encore attaqué à une récursivité non terminale que la procédure retourne sur elle-même et qu'elle va donc faire dessiner à l'objet "Tortue" un trait 3 fois plus petit "COTE :TAILLE / 3" et que la procédure va s'arrêter. Et non!!! elle va continuer sur TG 60 et COTE :TAILLE / 3 DIFF :NIVEAU 1 donc faire le deuxième côté mais TAILLE et NIVEAU sont les variables de la procédure appelante donc ne changent pas de valeurs et ainsi de suite jusqu'à ce que le mot FIN de la procédure appelante soit détecté. Oh les belles cascades !!!
Pour le plaisir des yeux voici ce qu'on obtient si on tape tout bêtement:
REPETE 6 [FLOCON 100 3 TD 60]
Avouez que c'est pas mal !!!!
L'IREM de Nantes a publié une brochure en 1990: "Les courbes de Von Koch et de Sierpinski comme paradigmes de fractals" par A. Robert, professeur à l'université de Neufchâtel. Il y a des exercices sur les centres de gravité ou autres qui peuvent être traîtés élégamment avec l'aide de Logo.
Sans commentaires mais avec les procédures et les images-écrans, voici la courbe appelée C.
POUR C :TAILLE :NIVEAU
SI :NIVEAU = 0 [AV :TAILLE STOP]
C :TAILLE DIFF :NIVEAU 1
TD 90
C :TAILLE :NIVEAU - 1
TG 90
FIN
Vous voyez pourquoi on l'appelle courbe "C". Selon le niveau de la récursivité il y a des études intéressantes à mener sur l'emplacement de l'axe de symétrie.
Nous terminerons cette étude par la modélisation d'un arbre sur lequel on n'a pas placé des fruits, mais ça pourrait être un bon exercice à faire à la maison !!!
Et le bonzaï
BRANCHEG 10 10 10 0.8
Rien ne vous empêche de dessiner une forêt ou des arbres couchés par le vent etc...
Allez, on vous donne les procédures, à vous de les tester, de les modifier.
POUR BRANCHEG :LON :ANG :NIVEAU :COEF
AV :LON * :COEF
NOEUD :LON :ANG :NIVEAU :COEF
RE :LON * :COEF
FIN
POUR NOEUD :LON :ANG :NIVEAU :COEF
SI EGAL? :NIVEAU 0 [STOP]
TG :ANG
BRANCHEG :LON :ANG DIFF :NIVEAU 1 :COEF
TD 2 * :ANG
BRANCHED :LON :ANG + 2 DIFF :NIVEAU 1 :COEF
TG :ANG
FIN
POUR BRANCHED :LON :ANG :NIVEAU :COEF
AV :LON
NOEUD :LON :ANG :NIVEAU :COEF
RE :LON
FIN
Vous commencez par BRANCHEG ou BRANCHED ça fera la même chose.
Nous allons utiliser l'algorithme d'Euclide :
Tant que a <> b
faire
si a > b
a <-- a - b
b <-- a
sinon
a <-- b - a
b <-- a
fin si
fin Tant que
Ce qui donne en Logo:
POUR PGCD :A :B
SI EGAL? :A :B [RENDS :A ]
SI PLG? :A :B [RENDS PGCD :B :A - :B]
RENDS PGCD :B - :A :A
FIN
Si vous voulez obtenir le PGCD par la méthode des divisions successives, vous pourrez vous contenter d'écrire :
POUR PGCD :A :B
SI EGAL? 0 RESTE :A :B [RENDS :B ][RENDS PGCD :B RESTE :A :B]
FIN
... ce qui dit exactement : pour avoir le PGCD de A et de B, si B divise A, c'est B, sinon, ce sera le PGCD de B et du reste de la division précédente. Vous êtes en train de faire les fameuses divisions en cascade ... élégant? non ?
Vous pouvez tester ces procédures et naturellement écrire des "choses" comme cela :
EC PGCD 24 36 mais aussi AV PGCD 360 144
et comme nous le verrons plus loin rien ne nous empêche à condition d'avoir défini FIBO d'écrire
PGCD FIBO 15 FIB 30 ou FIBO PGCD 15 30
Il est donc possible d'écrire une procédure pour calculer le PPCM de 2 nombres de la façon suivante :
POUR PPCM :A :B
RENDS QUOT PROD :A :B PGCD :A :B
FIN
Pendant qu'on y est pourquoi s'arrêter au PPCM de deux nombres, on peut écrire le PPCM de n nombres pris dans une liste de la façon suivante :
POUR PPCMS :LISTE
SI EGAL? COMPTE :LISTE 2 [RENDS PPCM PREM :LISTE DER :LISTE]
RENDS PPCMS PH PPCM ITEM 1 :LISTE ITEM 2 LISTE SP SP :LISTE
FIN
Essayez PPCMS [24 36 48] par exemple ou encore PPCMS [15 25 36 42].
Autre idée bien commode, (utilisée parfois pour trouver un dénominateur commun à deux fractions) : vous prenez le plus grand des deux nombres, vous regardez si c'est un multiple du petit, sinon vous prenez son double, vous regardez ... puis les multiples successifs jusqu'à ce que vous ayez un multiple commun.
Ce qui donne en LOGO
Tant que vous n'avez pas ce multiple, vous faites tourner la moulinette PPMC1 :
POUR PPMC :A :B
SOIT "N 1
RENDS PPMC1 :A :B :N
FIN
POUR PPMC1 :A :B :N
SI EGAL? 0 RESTE :N * :A :B [RENDS :N * :A]
RENDS PPMC1 :A :B :N + 1
FIN
POUR LISTE_DIVISEURS :NOMBRE
SI EGAL? :NOMBRE 1 [RENDS 1]
RENDS DIVISEURS :NOMBRE 1
FIN
POUR DIVISEURS :NOMBRE :DEBUT
SI EGAL? :DEBUT RC :NOMBRE [RENDS :DEBUT]
SI PLG? :DEBUT RC :NOMBRE [RENDS "]
SI EGAL? RESTE :NOMBRE :DEBUT 0 [RENDS PH :DEBUT PH DIVISEURS :NOMBRE :DEBUT + 1 :NOMBRE / :DEBUT]
RENDS DIVISEURS :NOMBRE :DEBUT + 1
FIN
Deux remarques :
Il faut s'habituer à l'écriture préfixée des prédicats SI EGAL? ou SI PLG?
l'écriture de la récursivité est originale :
RENDS PH :DEBUT PH DIVISEURS :NOMBRE :DEBUT + 1 :NOMBRE / :DEBUT
On remplit la procédure-objet par les deux bouts : au début le diviseur trouvé, à la fin le nombre divisé par ce diviseur et au milieu la suite des autres diviseurs.
Et donc pour savoir si un nombre est premier, il suffit d'écrire la procédure suivante.
POUR PREMIER? :A
RENDS EGAL? COMPTE LISTE_DIVISEURS :A 2
FIN
Ça marche, mais c'est un peu lourd. Voyons quelque chose de plus élégant.
En calquant notre démarche sur le crible d'Ératosthène, voici ce que nous pourrions écrire en LOGO :
Commençons par le plus simple, savoir si un nombre est premier en donnant comme liste de début [2 3]. Cette procédure ne marche que pour les nombres supérieurs à 3.
Comme vous avez pu déjà le voir, il y a aussi en Logo des procédures-objets -prédicats qui rendent une valeur de vérité.
POUR PREMIER? :A :B
SI VIDE? :B [RENDS "VRAI]
SI EGAL? RESTE :A PREM :B 0 [RENDS "FAUX]
RENDS PREMIER? :A SP :B
FIN
Je vous dois quelques explications :
- la procédure va tester si A est premier en se servant de la liste B qui va être initialisée à [2 3 5 7 ] par exemple,
- si le reste de A par le premier élément de B est nul c'est pas la peine d'aller plus loin, on a trouvé un diviseur donc on peut rendre Faux, sinon on recommence mais avec une liste de diviseurs moins longue, c'est le principe du crible. Essayez PREMIER? 20 [2 3 5] ça marche mais si vous essayez PREMIER? 49 [2 3 5], l'ordinateur vous répond VRAI, CE QUI EST FAUX!!!
Il faut donc agrandir le crible, ce que l'on va faire dans cette deuxième mouture :
POUR LISTE_PREMIERS :A :B
SI PLG? DER :A :B [RENDS "]
DONNE "NBRE SOMME DER :A 2
SI PREMIER? :NBRE :A [RENDS PH :NBRE LISTE_PREMIERS PH :A :NBRE :B]
RENDS LISTE_PREMIERS PH :A :NBRE :B
FIN
Dès que l'on trouve un nombre premier on l'ajoute à la variable B, alors on ne divise plus par 2 et 3 seulement mais par la liste des nombres premiers qui s'allonge au fur et à mesure que l'on en trouve un.
L'inconvénient c'est que 2 et 3 sont oubliés, je n'ai pas trouvé de solution plus élégante que de les rajouter dans la procédure suivante qui va donner sous forme de liste les nombres premiers jusqu'à 200.
POUR CRIBLE_ERATOSTHENE
RENDS PH [2 3] LISTE_PREMIERS [2 3] 200
FIN
POUR PREM? :N
SI OU EGAL? :N 0 EGAL? :N 1 [RENDS "FAUX]
SI OU EGAL? :N 2 EGAL? :N 3 [RENDS "VRAI]
SI EGAL? 0 RESTE :N 2 [RENDS "FAUX]
RENDS NON DIV? 3
FIN
POUR DIV? :D
SI EGAL? :D * :D :N [RENDS "VRAI]
SI PLG? :D * :D :N [RENDS "FAUX]
SI EGAL? RESTE :N :D 0 [RENDS "VRAI]
RENDS DIV? :D + 2
FIN
La procédure PREM? est un prédicat (elle dit si le nombre est premier) qui utilise le prédicat DIV? (est-il divisible par ... ?) qui tourne éventuellement jusqu'à la racine carrée.
Comme précédemment, on retrouve facilement la liste des nombres premiers jusqu'à un nombre donné, en utilisant un compteur qu'on fait tourner à partir de 1, jusqu'à ce nombre final (la "moulinette LISTPREM1) et en rangeant les nombres premiers trouvés au fur et à mesure.
POUR LISTEPREM :F
DONNE "LP []
SOIT "K 1
SI OU EGAL? :F 0 EGAL? :F 1 [RENDS :LP] [RENDS LISTEPREM1 :K]
FIN
POUR LISTEPREM1 :K
SI PLG? :K :F [RENDS :LP]
SI PREM? :K [DONNE "LP PH :LP :K]
RENDS LISTEPREM1 :K + 1
FIN
En utilisant la procédure LISTE_DIVISEURS, on peut savoir si un nombre est parfait, il suffit d'écrire une procédure qui va donner la somme des éléments d'une liste :
POUR SOMME_LISTE :LISTE
SI VIDE? :LISTE [RENDS 0]
RENDS SOMME PREM :LISTE SOMME_LISTE SP :LISTE
FIN
Je pense qu'elle se comprend sans explication supplémentaire, voir le lexique pour les primitives.
Et donc pour savoir si un nombre est parfait:
POUR PARFAIT? :NOMBRE
RENDS EGAL? SOMME_LISTE SD LISTE_DIVISEURS :NOMBRE :NOMBRE
FIN
Cette procédure est loin d'être parfaite ( sic) pour trouver les nombres parfaits, elle est très lente et je n'ai pu trouver par cette technique que les 4 premiers.
On trouve sur le Net, la méthode pour vérifier la clé Rib d'un compte chèque. Le travail est intéressant parce que si on se tourne vers un bon vieux tableur, il reste en rade parce que le numéro de CC dépasse les limites de calcul et vous renvoie donc un nombre en écriture avec exposant. D'où l'intérêt d'utiliser les congruences. Je m'aperçois que je ne vous ai pas donné la méthode, oh elle est simple (?!), il suffit de multiplier votre numéro de CC par 100, de diviser ce nombre par 97, de vous occuper seulement du reste et de chercher son complément à 97. Il fallait y penser. Donc si on applique cela dans un tableur, ça peut donner cela :
Mais bon, je ne suis pas là pour faire de la pub à Bilou, donc voyons comment avec Logo on peut résoudre cela:
Tout d'abord il faut écrire une procédure qui va nous donner la congruence modulo 97 d'une centaine, d'un millier etc... ça c'est facile :
POUR CONGRU :A
SI EGAL? :A 1 [RENDS 1]
RENDS RESTE PROD 10 CONGRU DIFF :A 1 97
FIN
Essayez CONGRU 3, ça donne 3, bien !!! CONGRU 4 ça donne 30 parfait. Vous avez les congruences dans le tableau Excel.
Bon, maintenant il suffit de mettre en face l'un de l'autre, une liste constituée de votre numéro de compte chèque (séparez les chiffres par un espace et n'oubliez pas les deux zéros à la fin) et de faire un produit terme à terme puis d'additionner. Pour que cela se fasse tout seul il suffit de créer la procédure SOM_PROD.
POUR SOM_PROD :A :B
SI VIDE? :A [ RENDS 0 ]
RENDS SOMME PROD PREM :A PREM :B SOM_PROD SPREM :A SPREM :B
FIN
Mais il nous faut aussi une procédure qui fabrique la liste des congruences à l'envers.
POUR LISTE_CONG :B :C
SI PLG? :B :C [RENDS "]
RENDS PH LISTE_CONG :B + 1 :C CONGRU :B
FIN
Regardez encore comment est écrite cette procédure, elle renvoie la liste des congruences en partant de la plus haute vers la plus basse.
On a presque tout pour travailler. Il suffit de ranger cela dans des variables:
DONNE "B [ 1 6 7 0 7 0 0 0 6 5 1 6 5 1 9 0 3 2 3 4 3 0 0]
DONNE "A LISTE_CONG 1 COMPTE :B
EC 97 - RESTE SOMPROD :A :B 97
Et ça devrait vous afficher 32 comme sur la feuille d'Excel.
On peut reprendre la définition de la suite et écrire une procédure brutale:
POUR FIBO1 :A
SI MEMBRE? :A [1 2] [RENDS 1]
RENDS SOMME FIBO1 :A - 1 FIBO1 :A - 2
FIN
Tapez FIBO1 10 et laborieusement Logo vous affiche 55. Les récursivités sont longues à remonter et les calculs sont très lents, c'est pourquoi je vous conseille cette solution dont l'explication est donnée en annexe.
POUR FIB :I :A :B
SI :I = 1 [RENDS :B]
RENDS FIB :I - 1 :B :A + :B
FIN
POUR FIBO :I
RENDS FIB :I 0 1
FIN
Vous pouvez vous permettre d'afficher FIBO 30, c'est pas mal. Et si vous voulez la liste des nombres de Fibo, il suffit d'écrire cette récursivité non terminale:
POUR LISTE_FIBO :N
SI EGAL? :N 0 [STOP]
LISTE_FIBO :N - 1
EC FIBO :N
FIN
Maintenant que nous avons la procédure FIBO efficace, il nous est possible de vérifier la convergence de un+1 /un.
POUR CONV :D :F
SI EGAL? :D :F [STOP]
EC DIV FIBO :D +1 FIBO :D
CONV :D + 1 :F
FIN
Tapez CONV 1 25 et vous voyez que ça converge vers f .
De même vous pouvez vérifier que un+3 x un - un+2 x un+1. Essayez pour différents nombres. Il serait facile de transformer FIBO en LUCAS.
Et enfin pour terminer ce chapitre sur l'arithmétique et Logo, une propriété que j'ai trouvée dans "Turtle Geometry" , puis au paragraphe suivant une idée pour trouver ces fameux nombres de Bezout (ou résoudre des équations diophantiennes).
FIBO PGCD :A :B = PGCD FIBO :A FIBO :B. Vous pouvez la vérifier sur quelques nombres. La démonstration est parait-il "hard".
Reprenons l'algorithme d'Euclide vu au début de ce chapitre d'arithmétique en le suivant sur un exemple avec les nombres 64 et 36.
"Descendons" l'algorithme à partir de 64 et 36 pour trouver leur PGCD 4 (par soustractions successives), puis essayons de "le remonter" pour trouver deux nombres p et q tels que :
p*64+q*36= 4.
Nous aurons ainsi trouvé une «égalité » de Bezout.
Vous verrez qu'il n'y a pas unicité du couple trouvé (p,q) à partir des deux nombres 64 et 36 (nommés R et N ci dessous).
| R | N | p |
q
|
pR+qN=d |
| 64 | 36 | -5 | 9 | -5*54 + 9*36 = 4 |
| I | ||||
| 64 - 36 | 36 | |||
| 28 | 36 | -5 | 4 | -5*28 + 4*36 = 4 |
| I | ||||
| 28 | 36 - 28 | |||
| 28 | 8 | -1 | 4 | -1*28 + 4*8 = 4 |
| I | ||||
| 28-8 | 8 | |||
| 20 | 8 | -1 | 3 | -1*120 + 3*8 = 4 |
| I | ||||
| 20-8 | 8 | |||
| 12 | 8 | -1 | 2 | -1*12 + 2*8 = 4 |
| I | ||||
| 12 - 8 | 8 | |||
| 4 | 8 | -1 | 1 | -1*4 + 1*8 = 4 |
| I | ||||
| 4 | 8 - 4 | |||
| 4 | 4 | 0 | 1 | 0*4 + 1*4 = 4 |
Quand vous avez fini de "descendre l'algorithme", vous obtenez deux valeurs égales pour R et N. Elles sont le PGCD de tous les couples (R;N) rencontrés.
Pour "faire la première égalité de Bezout", à la dernière ligne de la descente, vous pourrez affecter par exemple p et q à 0 et 1.
0 * 4 + 1 *4 = 4
Vous pourriez faire d'autres choix que le couple (0;1) pour (p;q).
Puis vous "remontez l'algorithme" ligne à ligne, en vous souvenant des changements effectués dans la descente. Par exemple, si en descendant du niveau n au niveau n+1, vous avez remplacé R par R - N en gardant N, en remontant du niveau n + 1 au niveau n, vous garderez p et changerez q en q - p.
| R | N | p | q - p | pR + (q-p)N = d | <- niveau n |
| R - N | N | p | q | p(R - N) + qN = d | <- niveau n + 1 |
Par contre, pour le changement de N en N-R en descente avec R conservé, en remontant,vous garderez q et vous changerez p en p - q .
| R | N | p - q | q | (p - q)R + qN = d | <- niveau n |
| R | N - R | p | q | pR + q(N - R) = d | <- niveau n + 1 |
Pour faire tout ça, il vous suffira de modifier EUCLIDE de la sorte :
POUR EUCLIDE :N :R
SI EGAL? :R :N [DONNE "P 0 DONNE "Q 1 DONNE "PGCD :N STOP]
SI PLG? :N :R [ EUCLIDE :N - :R :R DONNE "Q :Q - :P] [EUCLIDE :N :R - :N DONNE "P :P - :Q]
EC PH PH PH PH PH PH PH PH :P "* :N "+ :Q "* :R "= :PGCD
FIN
Avec la magie de la récursivité non terminale, c'est le dernier "clône" EUCLIDE (vous pouvez le nommer "EUCLIDE 4 4") qui se charge de dire que P vaut O, que Q vaut 1, et que le PGCD est le nombre N, de valeur 4, que lui a passé son collègue précédent (nommé "EUCLIDE 4 8").
EUCLIDE 4 4 écrit les trois nombres dans trois variables globales.
Quand EUCLIDE 4 8 reçoit le message qui remonte, il regarde ce qu'il lui restait à faire lorsqu'il avait appelé EUCLIDE 4 4, juste après qu'il ait fait son test.
Il s'était dit :
"4 est-il plus grand que 8 ? non donc j'appelle EUCLIDE 4 4"
Maintenant qu'EUCLIDE 4 4 lui a rendu le résultat de son travail, il reste à faire à EUCLIDE 4 8 la fin du test (le "sinon"). Il met dans "P le résultat de :P - :Q soit 0 - 1 (ce qui fait -1). Il ne modifie pas la variable "Q, qui vaut donc toujours 1, ni "PGCD qui est 4.
Puis il écrit, en utilisant ses variables locales "N et "R qui valent 4 et 8 :
-1*4+1*8 = 4
Cette fois EUCLIDE 4 8 a bien fini ... au tour de EUCLIDE 12 8 de faire son travail ... Regardez, ils ont tout fait !
? EUCLIDE 64 36
-1 * 4 + 1 * 8 = 4
-1 * 12 + 2 * 8 = 4
-1 * 20 + 3 * 8 = 4
-1 * 28 + 4 * 8 = 4
-5 * 28 + 4 * 36 = 4
-5 * 64 + 9 * 36 = 4
Fabuleux ? non ?
Vous pourrez améliorer votre équipe de travailleurs en leur apprenant à utiliser les divisions successives à la place des soustractions successives. Vous pouvez également souhaiter qu'ils vous rendent la liste [:P :Q] sans écrire ... Proposer un démarrage du premier couple (p,q) avec un choix aléatoire de l'un des deux ...
Petit rappel: pour une surface de révolution, son aire est égale à la longueur de la ligne qui engendre la surface par la longueur du cercle engendré par le centre de gravité de la ligne. C'est le théorème de Guldin2 . Ce qui donne pour la sphère ci-dessous:
Aire = demi-périmètre du cercle x périmètre du cercle décrit par le centre de gravité du demi-cercle.
Voyons comment la tortue peut vérifier ce théorème.
Nous allons tout d'abord faire décrire à la tortue un demi-cercle. Rien de plus facile:
POUR CERCL
DONNE "C [[0 0]]
TD 1
REPETE 90 [AV 5 TD 2 DONNE "C PH :C LISTE POS "]
FIN
Lancez la procédure CERCL, Logo s'occupe de dessiner et va placer dans une liste de listes (variable C) les coordonnées des différents points sur lesquels elle passe. Si vous demandez l'écriture de C, ça devrait vous donner à peu près cela:
[0 0] [0,08726203218640194 4,999238475781965] [0,34894181340109753 9,992386149554818] [0,7847205271393705 14,973359640013541] ...
Une liste de 91 listes.
Il nous faut maintenant écrire les procédures pour trouver le centre de gravité de cette ligne, c'est à peu près l'isobarycentre de ces 91 points.
POUR ISOBARYCENTRE :A
RENDS PH DIV SOM X :A COMPTE :A DIV SOM Y :A COMPTE :A
FIN
Pour obtenir l'abscisse du centre de gravité, il suffit de sommer les abscisses des différents points rencontrés par la tortue, il nous faut donc écrire deux procédures, l'une qui récupère la liste des abscisses, l'autre qui somme les nombres d'une liste
La liste des abscisses sera écrite de la façon suivante:
POUR X :A
SI VIDE? :A [RENDS "]
RENDS PH PREM PREM :A X SP :A
FIN
Idem pour la liste des y mais on prend dans chaque élément de la liste le dernier.
POUR Y :A
SI VIDE? :A [RENDS "]
RENDS PH DER PREM :A Y SP :A
FIN
Il suffit décrire une procédure qui additionne les nombres d'une liste:
POUR SOM :A
SI VIDE? :A [RENDS 0]
RENDS SOMME PREM :A SOM SP :A
FIN
Comme nous voulons seulement vérifier la validité du théorème de Guldin, nous allons procéder de la façon suivante. Comme on sait déjà que l'aire est égale à 4&Mac185;R2. Le quotient du diamètre du cercle par le rayon du cercle engendré par le centre de gravité doit être égal à P . Il nous suffit donc de demander à Logo de faire ce calcul en tapant:
VE
CERCL
EC DIV PREM POS DER ISOBARYCENTRE :C
Allez-y et vous verrez c'est pas si mal.
Naturellement, cette pratique sera plus intéressante à utiliser lorsque la figure engendrée sera plus complexe.
Il est aussi possible d'étudier la procédure BARYCENTRE dans un cadre plus géométrique, dans ce cas on écrirait la procédure barycentre de la façon suivante:
POUR BARYCENTRE :A :B
SI EGAL? COMPTE :A 2 [RENDS BARY :A :B]
DONNE "BARY_PROVISOIRE
BARYCENTRE LISTE PREM :A PREM SP :A LISTE PREM :B PREM SP :B
RENDS BARYCENTRE MP :BARY SP SP :A MP SOMME PREM :B PREM SP :B SP SP :B
FIN
MP item1 item2 est une primitive Logo qui place en première place item1 d'une liste item2. Donc si je lis bien du Logo, ça signifie qu'on recommence la procédure BARYCENTRE avec une nouvelle liste dans laquelle les coordonnées du barycentre des deux premiers points remplacent celles des deux premiers points (les deux premiers points sont supprimés SP SP :A) et dans la liste des coefficients, les deux premiers coefficients sont remplacés par leur somme.
Il suffit d'écrire la procédure BARY :A :B qui va rendre les coordonnées du barycentre de deux points affectés des coefficients placés dans la liste B.
L'intérêt de travailler de cette façon-là c'est qu'on généralise la procédure BARYCENTRE mais aussi que l'on peut visualiser le chemin engendré par les différents centres de gravité transitoires. Voir à cet effet la brochure IREM : LOGO et géométrie - Alain Bois et Jacques Delgoulet 1986.
