L'algorithme tombé à l'épreuve de remplacement du BAC S 2013 en Antilles-Guyane reprend le contexte de notre
concours de programmation actuel, avec un robot qui tente de traverser un pont en effectuant des déplacements aléatoires. A la différence qu'ici il ne sera pas demandé d'améliorer le robot mais simplement de l'étudier. Voici le sujet:
Question A)1):L'algorithme s'articule autour d'une boucle 'tant que' dont la condition de poursuite est
"y≥-1 et y≤1 et x≤9".
Toute sortie de l'algorithme implique donc la réalisation du contraire de cette condition, c'est-à-dire ici
"y<-1 ou y>1 ou x>9".
Ce sont en effet trois façons pour le robot de sortir du pont; par en bas, par en haut ou par la droite.
Il est impossible que l'algorithme se termine avec x=-1 et y=1. En effet, dans les déplacements du robot codés par l'algorithmes, la variable x est initialisée à 0 et est incrémentée de 1 à chaque passage dans la boucle. Elle ne peut donc jamais devenir négative.
Il est possible que l'algorithme se termine avec x=10 et y=0. Cela correspond à une sortie du pont par la droite et donc ici à une réussite de la traversée. Les positions précédentes possibles x=9 et y=0 ou y=-1 ou y=1 sont bien sur le pont.
Il est impossible que l'algorithme se termine avec x=2 et y=4. En effet, les positions précédentes possible x=1 et y=5 ou y=4 ou y=3 sont déjà toutes en dehors du pont
(trop hautes) et l'algorithme aurait donc déjà dû s'arrêter.
Il est possible que l'algorithme se termine avec x=10 et y=2. En effet, il y a bien une position précédente possible sur le pont: x=9 et y=1. Mais cela veut aussi dire en réalité que le robot est tombé du pont par le haut dès le début de ce dernier déplacement
(en dépassant y=1) et n'a donc pas réussi la traversée.
Question A)2):On doit donc ici trouver un critère permettant de dire si le robot a traversé le pont ou est tombé au cours de ses déplacements.
On pourrait traduire la fait d'atteindre l'autre rive par x=10 ou encore x≥10, mais le dernier exemple de la question précédente montre que ce n'est pas suffisant et qu'il faut donc considérer y.
On obtient donc:
"x≥10 et y≥-1 et y≤1".
La condition sur x est d'ailleurs totalement inutile ici puisqu'il n'y a pas d'autre façon de sortir du pont avec une valeur de y dans cet intervalle que par la droite.
On en arrive ainsi à:
"y≥-1 et y≤1".
Voici donc l'algorithme modifié:
- Code: Select all
x,y,n sont des entiers
Affecter à x la valeur 0
Affecter à y la valeur 0
Tant que y≥-1 et y≤1 et x≤9
Affecter à n une valeur choisie au hasard entre -1, 0 et 1
Affecter à y la valeur y+n
Affecter à x la valeur x+1
Fin tant que
Si y≥-1 et y≤1 alors
Afficher "Tom a réussi la traversée"
sinon
Afficher "Tom est tombé"
FinSi
Téléchargement:BAC S 2014 - sujets inédites toutes matières & toutes zones 2013-2014 + corrigés
by 
