Correction du TD n°1

Exercice 1

L'algorithme était:

001 action main(args)
002 Données args : tableau de Chaine
003 Locales k, i, j : entier
004 k := -4
005 i := 0
006 tantque k < 0 faire
007 pour j de 1 à -k pas 2 faire
008 i := i + k * j
009 fait
010 k := k + 1
011 fait
012 ecrire(i)
013 fin action

trace de l'exécution de cet algorithme est donnée ci-dessous.

La première colonne indique le numéro de la ligne dans l'algorithme. Les trois autres indiquent les valeurs des variables k, i et j après exécution de cette ligne.

La ligne en grisée est la ligne où le contenu de la variable i est écrit à l'écran

- | Ligne | k | i | j
1 | 5 | -4 | 0 | -
2 | 6 | -4 | 0 | -
3 | 7 | -4 | 0 | 1
4 | 8 | -4 | -4 | 1
5 | 9 | -4 | -4 | 1
6 | 7 | -4 | -4 | 3
7 | 8 | -4 | -16 | 3
8 | 9 | -4 | -16 | 3
9 | 7 | -4 | -16 | 5
10 | 10 | -3 | -16 | 5
11 | 11 | -3 | -16 | 5
12 | 6 | -3 | -16 | 5
13 | 7 | -3 | -16 | 1
14 | 8 | -3 | -19 | 1
15 | 9 | -3 | -19 | 1
16 | 7 | -3 | -19 | 3
17 | 8 | -3 | -28 | 3
18 | 9 | -3 | -28 | 3
19 | 7 | -3 | -28 | 3
20 | 10 | -2 | -28 | 3
21 | 11 | -2 | -28 | 3
22 | 6 | -2 | -28 | 3
23 | 7 | -2 | -28 | 1
24 | 8 | -2 | -30 | 1
25 | 9 | -2 | -30 | 1
26 | 7 | -2 | -30 | 3
27 | 10 | -1 | -30 | 3
28 | 11 | -1 | -30 | 3
29 | 6 | -1 | -30 | 3
30 | 7 | -1 | -30 | 1
31 | 8 | -1 | -31 | 1
32 | 9 | -1 | -31 | 1
33 | 7 | -1 | -31 | 3
34 | 10 | 0 | -31 | 3
35 | 11 | 0 | -31 | 3
36 | 6 | 0 | -31 | 3
37 | 12 | 0 | -31 | 3
38 | 13 | 0 | -31 | 3

Exercice 2

001 action parcourt(coteCarre, largeurDamier)
002 Données coteCarre, largeurDamier : entier
003 Locales x, y : entier { Coordonnees du robot }
004 i : entier { Indice de boucle pour }
005 x := lire()
006 y := lire()
007 si x >= 1 et x <= largeurDamier et
008 y >= 1 et y <= largeurDamier et
009 x+coteCarre <= largeurDamier et
010 y-coteCarre >= 1 alors
011 pour i de 1 à coteCarre faire
012 x := x+1
013 ecrire(x,",",y)
014 fait
015 pour i de 1 à coteCarre faire
016 y := y-1
017 ecrire(x,",",y)
018 fait
019 pour i de 1 à coteCarre faire
020 x := x-1
021 ecrire(x,",",y)
022 fait
023 pour i de 1 à coteCarre faire
024 y := y+1
025 ecrire(x,",",y)
026 fait
027 sinon
028 ecrire("erreur")
029 fsi
030 fin action

Le pas des structures "pour" étant égal à 1, il peut ne pas être spécifié explicitement.

Autre solution

001 action parcourt(coteCarre, largeurDamier)
002 Données coteCarre, largeurDamier : entier
003 Locales x, y : entier { Coordonnees du robot }
004 i : entier { Indice de boucle pour }
005 xinc, yinc : entier { Increments elementaires en x et en y }
006 x := lire()
007 y := lire()
008 xinc := 1
009 yinc := 0
010 si x >= 1 et x <= largeurDamier et
011 y >= 1 et y <= largeurDamier et
012 x+coteCarre <= largeurDamier et
013 y-coteCarre >= 1 alors
014 pour i de 1 à 4*coteCarre faire
015 x := x+xinc
016 y := y+yinc
017 ecrire(x,",",y)
018 si i = coteCarre alors
019 xinc := 0
020 yinc := -1
021 fsi
022 si i = coteCarre*2 alors
023 xinc := -1
024 yinc := 0
025 fsi
026 si i = coteCarre*3 alors
027 xinc := 0
028 yinc := 1
029 fsi
030 fait
031 sinon
032 ecrire("erreur")
033 fsi
034 fin action

Dans cette seconde solution, on est parti du principe que, pour parcourir un carré de 4 cellules de coté, il faut réaliser 4x4 déplacements successifs avec un incrément de déplacement en x et un incrément de déplacement en y et que, arrivé à certaines étapes du déplacement, les valeurs d'incrément en x et en y doivent changer.

Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr