TD 1 – Une introduction en douceur à l’algorithmique avec

TD 1 – Une introduction en douceur à l’algorithmique avec

Guido

1) Présentation de Guido

“Guido Van Robot” est un environnement de programmation d’un petit robot utilisant un microlangage,

en fait un sous-ensemble minimum de Python. Bien que ce langage soit extrêmement

rudimentaire, il est très pédagogique.

Guido est un robot évoluant dans un monde en deux dimensions, constitué de rues et d’avenues.

Voici un exemple de situation de départ :

define untour :

do 3:

move

turnlef t

do 2:

move

turnlef t

do 3:

move

turnlef t

do 2:

move

do 2:

move

putbeeper

untour

pickbeeper

do 3:

move

turnof f

Guido est matérialisé par une triangle dont l’orientation indique dans quelle direction il va

avancer. Il se déplace de case en case, les coins des cases étant matérialisés par les points

noirs. Les traits rouges sont des murs, que le Robot ne peut traverser. La barre de statut

indique que le robot transporte un “beeper”, une sonnette en français. Il peut à loisir prendre

des sonnettes présentes sur le terrain ou en déposer s’il en a dans son sac à sonnettes.

Pour diriger Guido, on écrit un code, en utilisant les commandes connues par Guido, ou

celles que l’on définit soi-même. Guido peut ainsi avancer, tourner sur lui-même, tester son

environnement (présence ou absence de murs, de sonnettes...). On peut lire ci-dessus un

exemple d’un tel code. Le plus simple est que vous constatiez de vous-même ce que ce programme

fait effectuer au robot.

Les 12 premières lignes ne sont pas exécutées, elles constituent une définition de fonction

permettant de découper la tâche à effectuer en sous-tâches plus simples à appréhender. La

première commande exécutée par le robot est une boucle do 2, qui lui demande de répéter

deux fois les instructions suivant la ligne do qui sont indentées. Ensuite, il dépose sa sonnette

(putbeeper), exécute l’ensemble des instructions définissant la fonction untour, ramasse sa

sonnette (pickbeeper), avance encore de trois pas, et s’éteint.

Pour bien comprendre ce qui se passe, le plus simple est que vous essayiez de modifier une ligne

ou deux, pour voir ce qui se passe. Et s’il se passe quelque chose qui n’est pas prévu, tentez de

comprendre en suivant pas-à-pas le déroulement des instructions.

1

2) Les commandes de Guido

Les commandes permettant de contrôler Guido sont de 3 types :

 les commandes primitives :

– move : avancer d’une case vers l’avant,

– turnleft : tourner de 90 vers la gauche,

– pickbeeper : ramasser une sonnette,

– putbeeper : déposer une sonnette,

– turnoff : s’éteindre ;

 les tests :

– front_is_clear : vrai si il n’y a pas de mur devant,

– front_is_blocked : vrai si il y a un mur devant,

– left_is_clear : vrai si il n’y a pas de mur à gauche,

– left_is_blocked : vrai si il y a un mur à gauche,

– right_is_clear : vrai si il n’y a pas de mur à droite,

– right_is_blocked : vrai si il y a un mur à droite,

– next_to_a_beeper : vrai si la case comporte une sonnette,

– not_next_to_a_beeper : vrai si la case ne comporte pas de sonnette,

– any_beepers_in_beeper_bag : vrai si Guido transporte au moins une sonnette,

– no_beepers_in_beeper_bag : vrai si Guido ne transporte aucune sonnette,

– facing_north : vrai si Guido regarde vers le nord,

– not_facing_north : vrai si Guido ne regarde pas vers le nord,

– facing_south : vrai si Guido regarde vers le sud,

– not_facing_south : vrai si Guido ne regarde pas vers le sud,

– facing_east : vrai si Guido regarde vers l’est,

– not_facing_east : vrai si Guido ne regarde pas vers l’est,

– facing_west : vrai si Guido regarde vers l’ouest,

– not_facing_west : vrai si Guido ne regarde pas vers l’ouest ;

 les structure :

– la conditionnelle : “if <condition>: <actions>” qui exécute les actions si la condition

est vraie, et rien sinon,

– la boucle itérative : “do <nombre>: <actions>” qui exécute les actions le nombre de

fois indiqué,

...