Se qui suit, sont mes corrections des devoirs
d'informatique de MIAS (made in GOWAP).
| UNIVERSITÉ DE TOURS, DEUG MIAS 2ème
année, épreuve d'informatique |
Session : Janvier 1997
Durée : 2 heures |
Documents manuscrits et
listings seuls autorisés.
Les algorithmes devront être écrits en Pascal. Les exercices sont
indépendants. |
Il sera tenu compte de la présentation
et de la clarté des explications.
La compréhension du sujet fait partie de l'épreuve.
Tout ce qui n'est pas précisé dans le texte est laissé au gré du
candidat qui justifiera ses choix.
Le candidat précisera, dans chacune des questions, les paramètres
d'entrée et de sortie nécessaires.
1) Afin d'accélérer la recherche
d'informations sur les employés d'une société, on se propose de
réaliser un fichier informatique du personnel. Chaque employé est
caractérisé par son nom, son prénom, son numéro INSEE composé de 15
chiffres : sexe (1 ou 2) / année de naissance (00-99) / mois de naissance
(01-12) : département de naissance (01-99) / deux blocs de trois chiffres
quelconques / clé de deux chiffres, son adresse, son coefficient (nombre
entier permettant de calculer le salaire brut) et diverses informations
complémentaires que l'on ne considérera pas dans l'exercice.
Question Q1 :
Définir le type Employé en respectant les
caractéristiques d'un employé énoncé précédemment. On prêtera une
attention toute particulière à la définition du numéro INSEE.
Question Q2 :
On désire disposer d'un fichier d'employés indexé
sur leur année de naissance, ce qui signifie que, lors d'une lecture, par
exemple, on parcourt le fichier en débutant par l'employé le plus âgé
et en finissant par le plus jeune. On n'emploiera pas la technique
habituelle consistant à créer un second fichier physique d'index comme
indiqué dans la figure suivante,
|
|
| DUPONT |
1 62 03 18 137 438 11 |
... |
| DURANT |
1 54 04 37 ......... |
... |
| JACQUES |
2 52 09 ..... |
... |
| MARTIN |
1 69 08 ..... |
... |
| LOUIS |
2 43 11 ............ |
... |
| JEAN |
2 41 10 ....... |
... |
| PIERRE |
1 65 01 ...... |
... |
|
|
|
|
mais on se propose d'ajouter directement dans le
fichier des employés le numéro d'enregistrement pour l'index : on
agrège donc le fichier d'index au fichier de données principal, comme
dans la figure ci-après.
|
|
| DUPONT |
1 62 03 18 137 438 11 |
... |
5 |
| DURANT |
1 54 04 37 ......... |
... |
4 |
| JACQUES |
2 52 09 ..... |
... |
2 |
| MARTIN |
1 69 08 ..... |
... |
1 |
| LOUIS |
2 43 11 ............ |
... |
0 |
| JEAN |
2 41 10 ....... |
... |
6 |
| PIERRE |
1 65 01 ...... |
... |
3 |
|
Modifier le type en Q1 en intégrant le numéro
d'enregistrement pour l'index.
Question Q3:
Écrire l'algorithme de lecture et d'affichage de la
liste des employés en ordre décroissant de leur âge.
Question Q4:
La suppression d'un employé consiste simplement à
mettre -1 comme numéro d'enregistrement pour l'index. Par exemple, la
suppression de l'employé JEAN a entraîné la modification dans
l'enregistrement 0 de la valeur d'index, qui est passée de 5 à -1.
Indiquer la modification à apporter à l'algorithme de Q3 afin d'afficher
seulement les enregistrements valides (N.B. : on ne demande pas
d'écrire l'algorithme de modification des index).
2) Écrire une fonction récursive
permettant de calculer la valeur de x^k pour x réel quelconque et k
entier relatif quelconque. On exploitera les propriétés suivantes :
| x^k |
=1
=1/x-^k
=x^(k-1) x
=(x^(k/2))² |
pour k = 0
pour k négatif
pour k positif impair
pour k positif pair |
| On testera cette fonction à l'aide d'un programme principal
permettant à l'utilisateur de fournir les valeurs de x et de k. |
 |
|
Rappel :
| Fichier : |
Regroupement de données (sous
formes diverses) sur une mémoire de masse. Dans la plupart des cas, un
fichier représente un tableau d'élément définit : ARRAY [0.. EOF
] of Elmt. Un fichier peut contenir 65535 éléments. |
Nous pouvons représenter un fichier avec ses éléments,
soit horizontalement, soit verticalement, mais toujours dans le sens de la
lecture.
| Index : |
numérotation d'un élément ou
pointeur sur un élément. L'index est utilisé dans les tableaux (les
fichiers sont aussi des tableaux) |
| Nous dessinons à gauche d'une
représentation de fichier, une flèche pour désigner l'élément
actuellement pointé : c'est la zone de travail (lecture /
écriture). |
--> |
|
Assignation
(nom logique) |
après avoir déclaré une
variable fichier et son type, nous devons indiquer au programme le nom
physique du fichier sur lequel nous désirons travailler. Ceci fait, nous
pouvons soit le créer (effacer, RAZ), soit l'ouvrir pour y lire des
données. |
Instruction sur les fichiers : « Fich » est
une variable de nom de fichier logique.
| Append(Fich) |
Ouvre un fichier texte, et
place le pointeur à la fin. On l'utilise lorsque l'on désire ajouter des
éléments à un fichier. C'est équivalent à : Reset(Fich) + Seek(FileSize(Fich)) |
| Assign(Fich,St) |
Où St est le nom physique d'un
fichier — st est une chaîne ou une variable string.
Attribut à une variable (nom logique) un nom physique. |
| Reset (Fich) |
Ouverture d'un fichier
existant. |
| ReWrite (Fich) |
Création d'un nouveau fichier
(ou RAZ). |
| Close (Fich) |
Fermeture d'un fichier :
attention, vous devez absolument fermer vos fichiers, car le nombre de
fichiers ouvert est limité. |
| EOF (Fich) |
End of File. Retourne un
booléen qui est vrai (true) lorsque l'on a atteint (le pointeur) la fin
du fichier |
| Seek(Fich,Pos) |
Déplace le pointeur fichier
(Index) en position « Pos ». |
| Truncate (Fich) |
Coupe le fichier à la position
du pointeur (élément pointé aussi). Les éléments coupés sont perdus
(effacé du disque). |
| FilePos (Fich) |
Renvoie la position du pointeur
(Index). |
| FileSize (Fich) |
Retourne le nombre d'éléments
contenu dans le fichier. |
| Read(Fich,elmt) |
Lecture d'un élément dans un
fichier. ReadLn est utilisé dans les fichiers textes. |
| Write(fich,elmt) |
Écriture d'un élément dans
un fichier. |
Exercice 1 :
Q1 : dans cette question, on
nous demande de définir le type Employé, en utilisant les informations du
texte. Pour le numéro d'insée, nous n'avons aucune obligation (même
d'ordre) : le texte ne spécifie rien sur la définition de insée, à part
qu'il contient des données connues. Voilà donc plusieurs
façons de définir insée :
Type
T_Insee1 = String[15] ;
_ _ _T_Insee2
= Array [0..14] of char ;
_ _ _T_Insee3
= Record
_ _ _ _ _ _ _ _
_Sexe, Annee, Mois, Dep,
Cle : Byte ;
_ _ _ _ _ _ _ _
_B1,B2 : Word ;
_ _ _ _ _ _ _ _
End ;
_ _ _T_Insee4
= Record
_ _ _
_ _ _ _ _ _Sexe :
1..2 ;
_ _ _ _ _ _ _ _
_Annee : 0..99 ;
_ _ _ _ _ _ _ _
_Mois : 1..12 ;
_ _ _ _ _ _ _ _
_Dep : 1..99 ;
_ _ _ _ _ _ _ _
_B1,B2 : 0..999 ;
_ _ _ _ _ _ _ _
_Cle : 0..99 ;
_ _ _ _ _ _ _ _
End ; |
La plus simple des définitions est T_Insee2, car elle est
réellement de 15 caractères. T_Insee3 est la définition la plus stable :
il n'y a aucune obligation de valeur, même pour « sexe » . S'il y
avait un écrasement de données (en mémoire ou sur disque), le caractère ou
la variable « sexe » pourrait avoir des valeurs erronées ; il
faudra vérifier son contenu. Exemple : vous voulez lire un numéro d'insée
dans un fichier quelconque ; vous pouvez obtenir, sexe = 'A' ou 65, et là,
vous n'aurez pas les valeurs attendues. S'il n'y a pas de test, vous risquez
d'effectuer des opérations impossibles, et planter votre programme… T_Insee1
est la définition la plus courte et rapide à écrire.
Pour la définition d'employé, nous pouvons aussi mettre un
peu n'importe quoi, et dans l'ordre désiré, car rien n'est stipulé.
Type
EMPLOYE = Record
_ _ _ _ _ _ _ _
Nom, Prenom, Adresse : String;
_ _ _ _ _ _ _ _
INSEE : T_Insee;_
_ _ _{celui que vous voulez}
_ _ _ _ _ _ _ _
coef : integer;
_ _ _ _ _ _ _ _
.. .. {bla
bla, les divers informations complémentaires)
_ _ _ _ _ _ _ _End ; |
Comme le coefficient est un nombre entier, sans aucune
précision, je peux le définir dans le format entier de mon choix, signé ou
non. J'ai mis "integer", car c'est la forme signée la plus
couramment utilisée.
Q2 : le texte de Q2 n'est
franchement pas très clair. Certes, je l'ai compris dans ma première lecture,
mais beaucoup de mes camarades n'ont pas eu cette chance. Certains, n'ont même
rien compris. Voyons pourquoi : la phrase « fichier d'employés
indexé sur leur année de naissance » ne signifie pas que le fichier
d'employés est ordonné, mais que chacun de ces éléments sont indexés par un
autre fichier, qui est lui, ordonné.
Nous avons donc un fichier qui ne contient que des index sur le fichier
employé. Le premier index (élément) de ce fichier désigne le plus vieil
employé contenu dans le fichier d'employés. Nous avons une représentation
horizontale des contenus des fichiers : le fichier d'employé est à
gauche, et le fichier d'index à droite. Comprenons ce schéma en effectuant
manuellement une lecture : pour avoir le plus vieux des employés, je vais
effectuer les taches suivantes :
Lecture dans le fichier d'index du premier élément :
élément 0, j'obtiens l'index 5.
Lecture de l'élément d'index 5 dans le fichier d'employés : j'obtiens
JEAN.
Effectivement, Jean est le plus vieux. Puis, nous obtenons le
suivant en effectuant :
Lecture du 2ème élément du fichier d'index :
élément 1 --> 4
Lecture de l'élément d'index 4 dans le fichier d'employé : Louis
Effectivement, Louis est le 2ème plus vieux. De même, nous
lirons 2, 1, 0, 6 et 3 qui sont respectivement Jacques, Durant, Dupont, Pierre
et Martin.
On ne désire pas avoir deux fichiers pour stocker les employés et les
indexer : nous allons donc les fusionner d'une façon à respecter le même
algorithme de lecture précédent : le premier élément (0) contient
l'index sur (désignant) le plus vieux, et le dernier élément, l'index sur le
plus jeune (§ Tableau de l'énoncé).
Ce fichier obtenu ressemble énormément au fichier d'employés, avec un index
en plus. Pour y accéder, nous devons modifier notre type EMPLOYE.
Type
EMPLOYE = Record
_ _ _ _ _ _ _ _
Nom, Prenom, Adresse : String;
_ _ _ _ _ _ _ _
INSEE : T_Insee;_
_ _ _{celui que vous voulez}
_ _ _ _ _ _ _ _
coef : integer;
_ _ _ _ _ _ _ _
... {bla
bla, les divers informations complémentaires)
_ _ _ _ _ _ _ _ Index :
Integer;
_ _ _ _ _ _ _ _End ; |
Certes, dans la représentation du fichier, nous avons le
prénom suivi du numéro d'insée, ce qui ne correspond pas à notre
déclaration, mais la représentation est simplifiée pour améliorer la
compréhension. Bien qu'un fichier puisse contenir 65535 éléments, je définis
« Index » avec Integer ; j'aurai pu mettre Word ou bien LongInt ;
si je voulais être sûr de mon programme, je le déclarerai comme LongInt, car
il pourrait effectivement atteindre les 65535 éléments, et de plus, je peux
utiliser des valeurs de codage (effacé, § Q4).
Q3 : ici, nous devons travailler
sur le nouveau fichier défini dans Q2. Lire dans l'ordre décroissant des
âges, c'est lire dans l'ordre croissant des années de naissance : ce qui
est l'ordre de notre fichier. Les algorithmes doivent être écrit en pascal. Je
vais définir une procédure répondant à Q3. Nous devons travailler sur un
fichier, donc accéder à une variable logique. Il ne nous est pas demandé
d'ouvrir ou de fermer ce fichier. Nous admettrons que le fichier est déjà
ouvert, et que la variable logique est déclarée globalement. — Pour passer
un fichier dans un sous-programme, ce n'est pas possible d'écrire « Var
Fich :File of EMPLOYE » dans la déclaration d'en-tête. Il nous
faudrait avoir préalablement défini un type de fichier « Type TF =
File of Employe ; Var Fich : TF ; », est ainsi, passer la
variable fichier du type TF.
Aucune information n'est donnée sur les éléments à afficher à l'écran. Je
me contenterai d'afficher les noms.
Procedure
listage;_ _ _ _
_ {on considère que le fichier existe, ouvert}
Var t : Word;_
_ _ _ _ _ _ _ _ _ {mot, 2 octets, valeur de 0 à
65535}
_ _ Elmt :
Employe;
Begin
_ For
t :=0 To FileSize(Fich)-1_
_ _ {Le 1er élémt est le n° zéro}
_ Do
Begin_
_ _ _ _ _ _ _ _ _ _ _ _{le dernier est le nb d'élémt
-1}
_ _ _ Seek(Fich,
t); _
_
_
_
_
_
_{placement
du pointeur fichier}
_ _ _ Read(Fich,
Elmt);
_ _ _ Seek(Fich,
Elmt.Index);
_ _ _ Read(Fich,
Elmt);
_ _ _ WriteLn(Elmt.Nom);
_ _ _End;
End; |
Comme FileSize retourne le nombre d'éléments, je
peux utiliser une boucle FOR. Il est vrai que FileSize
est appelé à chaque boucle pour tester la valeur de « t », ce qui
ralentit le programme. Mais ici, c'est l'idée qui nous intéresse, pas
l'optimisation.
Q4 : ici, on voit bien qu'il a été prudent
d'utiliser précédemment le type Integer pour déclarer les index. Je pense que
l'énoncé n'est franchement pas honnête ; utiliser -1, pour indiquer la
suppression d'élément, sous-entend que nous avons des index signés : or,
aucune information à ce sujet n'a été donnée dans la question Q2. Pour que
notre procédure fonctionne d'une façon correcte, nous devons tester la valeur
de l'index lue au début de la boucle.
Procedure
listage;
Var t : Word;
_ _ Elmt :
Employe;
Begin
_For
t :=0 To FileSize(Fich)-1
_Do
Begin
_ _ _Seek(Fich,
t);
_ _ _Read(Fich,
Elmt);
_ _ _If
Elmt.Index>-1
_ _ _Then
Begin
_ _ _ _ _ _Seek(Fich,
Elmt.Index);
_ _ _ _ _ _Read(Fich,
Elmt);
_ _ _ _ _ _WriteLn(Elmt.Nom);
_ _ _ _ _ End;
_ _ End;
End; |
Exercice 2 :
Odd (entier), renvoie True si l'entier est impair.
Équivalant à l'expression (entier AND 1)=1, et aussi (entier mod 2)=1.
Sqr( expression), renvoie le carré d'une expression.
Function
X_puissance_K (x : Real ; k :Integer) :Real;
Begin
_If
k=0
_Then
X_puissance_K :=1
_Else
_If
k<0
_Then
X_puissance_K :=1/ X_puissance_K(x, -k)
_Else
_If
Odd(k)
_Then
X_puissance_K := X_puissance_K(x, k-1) * x
_Else
X_puissance_K :=Sqr(X_puissance_K(x, k div 2));
End ; |
Ce n'est pas tout à fait la présentation que l'on trouve
habituellement dans des programmes en pascal : ici, nous enchaînons des
tests conditionnels, donc les suivants dépendent des précédents.
Pour le programme principal, on pourra avoir :
Var
x : Real;
_ _ k :
Integer;
Begin
_WriteLn('Calcul
de x^k, où x est un réel, et k un entier signé');
_Write('entrez
la valeur de x : ') ; ReadLn(x);
_Write('entrez
la valeur de k : ') ; ReadLn(k);
_WriteLn('Résultat :
', X_puisance_K(x, k));
End. |
|
Dernière mise à jour : dimanche 06 janvier 2008 |
|