Programmations

Janvier 2004

DEVOIR DE SYNTHESE 2° ANNEE - INSA de LYON

Module "PROGRAMMATIONS"

Tous documents autorisés - Durée : 3 heures

Barème indicatif : 7 points sur les exercices, 13 points sur le problème.

NB. La recopie d’extraits des supports de cours sans adaptation au sujet ne donnera pas de points. Présenter correctement avec indentation et commenter les points délicats.

EXERCICES (ne pas recopier les énoncés sur votre copie)

Soit les déclarations suivantes :

Const MaxLignes = 30 ; MaxColonnes = 50 ; {nous prendrons 6 et 8 dans les exemples}

Type t_lignes = 1..MaxLignes ; t_colonnes = 1..MaxColonnes ;

t_val = array[t_lignes,t_colonnes] of integer ;

t_matrice = record nblignes : t_lignes ; nbcolonnes : t_colonnes ;

info : t_val end ;

Si X est de type t_matrice, les valeurs entières utiles pour X.info vont de 1 à X.nblignes pour les indices des lignes et de 1 à X.nbcolonnes pour les indices des colonnes.

Q1 : Donner la déclaration et la réalisation d’une fonction booléenne EXO1 qui à partir d’une matrice fournie A de type t_matrice renvoie dans un booléen vrai si la matrice a au moins N lignes et M colonnes et faux sinon. On considère que N et M sont deux entiers fournis et la fonction EXO1 a donc 3 paramètres.
Function EXO1 (A :t_matrice; N, M : Integer) : Boolean ;
Begin

EXO1 := (A.nblignes >= N) and (A.nbcolonnes >= M)

End ;

Q2 : Donner la déclaration et la réalisation d’une fonction booléenne EXO2 qui à partir de deux matrices A et B fournies de type t_matrice renvoie vrai si les contenus de A et B sont identiques et faux sinon. Rappelons que la comparaison directe d’enregistrements n’est pas utilisable.
Function EXO2 (A,B :t_matrice ; N, M : Integer) : Boolean ;
Var I, J : Integer ; OK : Boolean ;
Begin

OK := (A.nblignes = B.nblignes) and (A.nbcolonnes = B.nbcolonnes) ;

If OK

Then Begin

I := 1;

While (I <= A.nblignes) and OK

Do Begin

J := 1 ;

While (J <= A.nbcolonnes) and OK

Do Begin

OK := OK and (A.info[I,J]=B.info[I,J]) ;

J := J+1

End ;

I := I+1

End

End ;

EXO2 := OK

End ;
Q3 : Donner la déclaration et une réalisation de la procédure EXO3 qui à partir d’une matrice fournie A de type t_matrice renvoie dans B de type t_matrice la sous-matrice carrée de taille N ayant pour coin supérieur gauche A.info[X,Y] où X et Y désignent une position valide dans A (à valeur dans t_lignes et t_colonnes). Un dernier paramètre booléen OK indique si cette extraction a été possible et donc si B a des valeurs significatives (vrai dans ce cas, faux sinon). Ainsi, sur la matrice A représentée ci-dessous à gauche, si l’on demande l’extraction de la sous-matrice carrée de taille N = 3 et de coin supérieur gauche X = 1 et Y = 1, on obtient la matrice B représentée à droite. L’extraction avec X = 4 et Y = 3 n’est pas faisable.

5	6	1	4	9	2	9	5	.	.
		7	2	1	4	9	6	.	.
A		8	3	7	2	1	2	.	.
		4	5	8	3	7	1	.	.
		7	8	3	2	9	4	.	.
		.	.	.	.	.	.	.	.

3	3	1	4	9	.	.	.	.	.
		7	2	1	.	.	.	.	.
B		8	3	7	.	.	.	.	.
		.	.	.	.	.	.	.	.
		.	.	.	.	.	.	.	.
		.	.	.	.	.	.	.	.

Procedure EXO3 (A : t_matrice ; N, X, Y : Integer ;

Var B : t_matrice ; Var OK : Boolean);

Var I, J ,K, L: Integer ;
Begin

OK := ((X+N-1) <= A.nblignes) and ((Y+N-1) <= A.nbcolonnes) ;

If OK

Then Begin

B.nblignes := N ;

B.nbcolonnes := N ;

K := 1 ;

For I := X To X+N-1

Do Begin

L := 1 ;

For J := Y To Y+N-1

Do Begin

B.info[K,L] := A.info[I,J];

L := L+1

End;

K := K+1

End

End

End ;
Q4 : Même question pour une procédure EXO4 qui doit renvoyer la sous-matrice, lorsquelle existe, pour laquelle A.info[X,Y] désigne son coin inférieur droit. Ainsi, si l’on demande l’extraction sur A de la sous-matrice carrée de taille N = 3 et de coin inférieur droit X = 4 et Y = 5, on obtient la même matrice B représentée ci-dessus. L’extraction avec X = 2 et Y = 3 n’est pas faisable.
Procedure EXO4 (A : t_matrice ; N, X, Y : Integer ;

Var B : t_matrice ; Var OK : Boolean);

Var I, J, k, L : Integer ;

Begin

OK := ((X-N) >= 0) and ((Y-N) >= 0) ;

If OK

Then Begin

B.nblignes := N ;

B.nbcolonnes := N ;

K := 1 ;

For I := X-N+1 To X

Do Begin

L := 1 ;

For J := Y-N+1 To Y

Do Begin

B.info[K,L] := A.info[I,J];

L := L+1

End;

K := K+1

End

End

End ;

PROBLEME : Réseaux de transport

Les pouvoirs publics sont très intéressés par l’amélioration de la circulation et la sécurité des usagers des réseaux de transport en commun avec, par exemple, de nouvelles utilisations du robot YARSOZK. Sur un arrêt de bus ou des quais de stations de métro, il peut prendre chaque usager en photo. Le robot YARSOZK coûte très cher et il n’est installé que dans un nombre limité de stations. Une association souhaite proposer aux usagers qui n’aiment pas être pris en photo un programme de calcul d’itinéraires. Il faut essayer, si possible, de relier une station X à une station Y sans jamais monter dans ou descendre d’un moyen de transport dans une station équipée du robot YARSOZK.

Nous allons repérer les stations par des codes entiers. Le petit réseau de transport représenté ci-dessous comporte 4 lignes et 8 stations. Ainsi, on peut aller de la station 3 aux stations 2, 4 et 6. On doit pouvoir travailler avec des nombres très variables de stations par ligne ce qui va justifier le choix d’une structure dynamique. On utilise les concepts de chemin (succession de stations) et de ligne (succession de stations desservies en séquence par un même train ou bus). Une ligne peut être décrite par deux chemins mais les chemins ne servent pas seulement à décrire des lignes : ils sont utilisés aussi dans la construction d’itinéraires. Par exemple, on peut parler du chemin C10 qui emprunte les stations 1, 2, 3 et 6 (par utilisation des lignes L1 et L3).

Ligne L1 : chemins C1/C2 (1-2-3-4/4-3-2-1)

Ligne L2 : chemins C3/C4 (5-6-7/7-6-5)

Ligne L3 : chemins C5/C6 (8-6-3/3-6-8)

Ligne L4 : chemins C7/C8 (1-5-8/8-5-1)

1 2 3 4

5 6 7

8

Nous allons tout d’abord nous intéresser à la gestion des chemins représentés grâce aux types suivants :

Type t_pposte = ^t_poste ;

t_poste = record station : integer ; photo : boolean ;

suite : t_pposte end ;
t_chemin = record nom : string ;

debut : t_pposte ;

fin : t_pposte  end ;

On peut représenter le chemin C10 (1-2-3-6) qui conduit des stations 1 à 6 par :

C10

1 F 2 T 3 F 6 F

Le champ photo dit si la station est équipée du robot YARSOZK (T pour « true ») ou pas (F pour « false »). Ainsi, on note que la station 2 est équipée du robot.

Sur une variable C de type t_chemin, C.debut désigne le premier poste de la liste de stations et C.fin désigne le dernier poste. La succession des valeurs prises par le champ station dans les postes de la liste donne des stations pour aller de C.debut^.station à C.fin^.station.

Q5. Donner une réalisation de la fonction Init_Chemin qui renvoie une valeur de type t_chemin en donnant au nouveau chemin le nom Nom_Chemin.

Function Init_Chemin (Nom_Chemin : string) : t_chemin ;
Function Init_Chemin (Nom_Chemin : string) : t_chemin ;

Var X : t_chemin ;

Begin

X.nom := Nom_Chemin ;

X.debut := Nil ;

X.fin := Nil ;

Init_Chemin := X

End ;
Q6. Donner une réalisation de la procédure Ajout_Station_Chemin qui transforme la valeur de C de type t_chemin en ajoutant toujours en queue de la liste linéaire de tête C.debut un poste pour la station désignée par Num.

Procedure Ajout_Station_Chemin (Var C : t_chemin ; Num : integer) ;
Procedure Ajout_Station_Chemin(Var C : t_chemin ; Num : integer) ;

Var Nouveau : t_poste ;

Begin

// creation du poste et remplissage

New(Nouveau);

Nouveau^.station := Num ;

Nouveau^.photo := false ;

Nouveau^.suite := Nil ;

// Si c’est le premier, on chang le debut, sinon on l’accroche sur //l’ancien dernier

If C.debut = Nil

Then C.debut := Nouveau 

Else C.fin^.suite := Nouveau ;

// et c’est le nouveau dernier

C.fin := Nouveau

End ;
Q7. Donner une réalisation de la procédure Cherche qui, étant donné C de type t_chemin et une station Num, renvoie, lorsqu’un poste correspondant à Num existe dans C, deux pointeurs P et PP de type t_pposte de sorte que P pointe le poste pour lequel station vaut Num alors que PP désigne le poste précédent celui pointé par P dans la structure chaînée. Lorsque la station n’appartient pas au chemin C, ces deux pointeurs doivent valoir NIL et le paramètre OK a la valeur fausse (vraie sinon).

Procedure Cherche (C:t_chemin ; Num :integer ; Var P,PP : t_pposte; Var OK:boolean) ;
Procedure Cherche (C:t_chemin ; Num :integer ;

Var P,PP : t_pposte; Var OK:boolean) ;

Begin

// on positionne les 2 pointeurs, deja l’un derriere l’autre

PP := NIL;

P := C.debut;

OK := FALSE;

// et on les fait avancer jusqu’a fin ou trouve

While (P <> NIL) And (NOT OK) Do Begin

If P^.station = Num

Then OK := TRUE

Else Begin

PP := P;

P := P^.suite;

End;

End;

End ;
Q8. Proposer une réalisation de la procédure Concat qui concatène (met bout à bout) deux chemins C1 et C2 de type t_chemin pour produire un chemin C3 de type t_chemin lorsque la dernière station de C1 est égale à la première station de C2. C3 ne contiendra qu’une occurrence de cette station de liaison. Ainsi, si C1 comporte 1 puis 2 puis 3 et C2 comporte 3 puis 6, alors C3 contiendra 1 puis 2 puis 3 puis 6. Cette condition sur les deux chemins C1 et C2 est supposée vérifiée à l’appel de Concat.

Procedure Concat (C1, C2 : t_chemin ; Var C3 : t_chemin) ;
2 solutions:

- celle du corrige (fiable, dans laquelle tous les postes sont recopiés

- et eventuellement une plus courte, mais moins fiable, en jouant juste sur les pointeurs sans rien recopier. Danger, si on supprime C1, C3 est dans les choux !!!
Procedure Concat (C1, C2 : t_chemin ; Var C3 : t_chemin) ;

Var pc: t_pposte;

Begin

C3 := Init_Chemin (C1.nom + C2.nom);

pc := C1.debut;

While pc <> NIL Do Begin

Ajout_Station_Chemin (C3, pc^.station);

pc := pc^.suite;

End;

pc := C2.debut^.suite;

While pc <> NIL Do Begin

Ajout_Station_Chemin (C3, pc^.station);

pc := pc^.suite;

End;
End;

Q9. Proposer une réalisation de la procédure Detruire qui supprime dans C de type t_chemin la station désignée par Num. On suppose ici que cette station appartient bien à C.

Procedure Detruire (Var C : t_chemin ; Num : integer) ;
Procedure Detruire(Var C : t_chemin ; Num : Integer) ;

Var PP, P : t_pposte ; Trouve : Boolean ;

Begin

Cherche(C,Num,P,PP,Trouve) ;

If Trouve {L’énoncé nous dit que Trouve va prendre la valeur vraie}

Then Begin

PP^.suite := P^.suite ;

Dispose(P)

End

End ;

On construit maintenant une représentation de l’ensemble des lignes (et donc du réseau de transport) en utilisant la structure de données définie ci-dessous. Si R est de type t_reseau, R.val est un tableau d’au plus 100 éléments et R.nb dit combien de chemins sont effectivement stockés. On peut ainsi mémoriser les chemins correspondant à au plus 50 lignes de métro ou de bus. En effet, par convention, si le i-ème élément du tableau R.val donne la succession des postes pour aller du terminus X au terminus Y, on décide que le i+1-ième élément de ce même tableau donne celle qui permet d’aller de Y à X.
Const Max_Lignes = 100 ;

Type t_reseau = record nb : integer ;

val : array [1..Max_Lignes] de t_chemin  end ;
La construction d’un réseau se fait à l’aide de la procédure Construire_Réseau qui ne vous est pas demandée et dont l’entête est :

Procedure Construire_Réseau (Var Reseau : t_reseau ; Var nb_lignes : integer) ;
On suppose que la valeur de nb est toujours inférieure ou égale à Max_Lignes et vaut 0 lorsque la structure est vide.
Q10. En supposant qu’un réseau R de type t_reseau a été créé, proposer une procédure Direct qui renvoie dans son paramètre OK vrai s’il existe un chemin conduisant sans changement de la station X à la station Y (faux sinon). Quand OK vaut vrai, IT de type t_chemin est le chemin direct de longueur minimale (en nombre de stations) pour aller de X à Y. On suppose que X et Y sont des stations différentes. Quand OK vaut faux, la valeur de IT ne sera pas exploitée.

Procedure Direct (R : t_reseau ; X, Y : integer ; Var OK : boolean ; Var IT : t_chemin) ;
NB. On pourra utiliser une fonction Long fournie, qui, étant donné un chemin C de type de t_chemin renvoie le nombre de stations dans ce chemin.

Function Long (C : t_chemin) : integer ;
Procedure Direct (R : t_reseau ; X, Y : integer ;

Var OK : boolean ; Var IT : t_chemin) ;

Var LongMin, LongIeme : Integer;

i : Integer;

Px, PPx, Py, PPy, pc: t_pposte;

Ch : t_chemin;

trouve : Boolean;

Begin

LongMin:= MAXINT;// un grand nombre !

It := Init_Chemin('It');

Ok := FALSE;

// On teste toutes les lignes

For i := 1 To R.nb Do Begin

// On chercle la station de depart

Cherche(R.val[i] ,X, Px, PPx,trouve);

If trouve Then Begin

// et celle d’arrivée, qui doit se trouver apres

Cherche(R.val[i],Y,Py,PPy, trouve);

If trouve And Apres (Py, Px, R.val[i]) Then Begin

// dans ce cas, on construit le chemin

Ch := Init_Chemin ('Solution courante');

pc := Px;

Repeat

Ajout_Station_Chemin(Ch, pc^.station);

pc := pc^.suite;

Until pc = Py;

Ajout_Station_Chemin(Ch, pc^.station);

LongIeme := Long (Ch);

// et on regarde si c’est le meilleur

If LongIeme < LongMin

Then Begin

LongMin := LongIeme;

IT := Ch;

OK := TRUE;

End;

End;

End;

End;

End;
Q11. En supposant qu’un réseau R de type t_reseau a été créé, proposer une procédure Route qui renvoie dans son paramètre OK vrai si il est possible de relier la station X à la station Y avec au plus un changement de ligne (faux sinon). Quand OK vaut vrai, IT de type t_chemin est le chemin de longueur minimale avec au plus un changement de ligne pour aller de X à Y. Quand OK vaut faux, la valeur de IT ne sera pas exploitée. Ainsi, dans le réseau donné en exemple, le plus court chemin avec au plus un changement pour aller de 1 à 7 est celui qui passe par les stations 1, 5, 6 puis 7.

Procedure Route (R : t_reseau ; X, Y : integer ; Var OK : boolean ; Var IT : t_chemin) ;
Procedure Route (R : t_reseau ; X, Y : integer ;

Var OK : boolean ; Var IT : t_chemin) ;

Var ChDirect, ChInd, Ch1, Ch2 : t_chemin;

LongCh, LongInd : integer;

i, j : Integer;

Corres : Integer;

Px, PPx, pc : t_pposte;

possible : Boolean;

Begin

// recherche chemin direct + cout

Direct(R, X, Y, OK, ChDirect);

IT := ChDirect;

If Ok

Then LongCh := Long (ChDirect)

Else LongCh := MAXINT;

// recherche chemin avec une correspondance

For i := 1 To R.nb Do Begin

// départ dans une ligne

Cherche(R.val[i] ,X, Px, PPx,possible);

If possible Then Begin

// on essaie tts les suivantes en correspondance

pc := Px^.Suite;

While pc <> Nil Do Begin

Corres:= pc ^.station;

Direct(R, X, Corres, possible, Ch1);

For j := 1 To R.nb Do Begin

Direct (R, Corres, Y, possible, Ch2);

If possible Then Begin

Concat (Ch1, Ch2, ChInd);

LongInd := Long (ChInd);

If LongInd < LongCh Then Begin

LongCh := LongInd;

IT := ChInd;

OK := TRUE;

End;

End;

End;

pc := pc^.suite;

End;

End;

End;

End;

On peut maintenant s’intéresser aux usagers photophobes.

Q12. On veut traiter le même problème que dans la question précédente avec une procédure Photophobes ayant les mêmes paramètres que Route et calculant, lorsque cela est possible, un chemin de la station X à la station Y sans monter ou descendre à une station équipée du robot. Si X et Y sont équipées du robot, il est clair qu’il n’existe pas de solution et l’on suppose que le cas ne se produit pas.

Procedure Photophobes (R : t_reseau ; X, Y : integer ;

Var OK : boolean ; Var IT : t_chemin) ;

Q12a. Expliquer la réalisation de Photophobes par modification du code de la procédure Route (Question Q11) sans forcément recopier ce qui est inchangé.
Ajouter juste le test quand on a trouve une correspondance

If NOT (pc^ .photo) Then …..
Q12b. Expliquer comment on pourrait réutiliser sans modification la procédure Route (Question Q11) pour faire le travail demandé à Photophobes mais à condition d’avoir modifié la représentation R du réseau.
Supprimer (procédure Detruire) dans le réseau les stations équipées ;