e3a Informatique MP 2007

Z12L

e 3 a
CONCOURS ENSAM - ESTP - ARCHIMEDE

Épreuve d'Informatique MP

durée 3 heures

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur 
d'énoncé, d'une
part il le signale au chef de salle, d'autre part il le signale sur sa copie et 
poursuit sa composition
en indiquant les raisons des initiatives qu'il est amené à prendre.

L'usage de la calculatrice est interdit

Indiquer en tête de copie ou de chaque exercice le langage utilisé

Exercice 1

&) Ecrire la fonction

Sym données M : tableau à deux dimensions
n : entier
résultat 56 : boolêen

qui prend en entrée le tableau des coefficients d'une matrice carrée de taille 
n et renvoie la valeur
1 si la matrice est symétrique et 0 sinon.

(9) Ecrire la fonction
Egalite--listes données L : liste
L' : liste
résultat b : booléen

qui prend en entrée deux listes et renvoie la valeur 1 si les deux listes sont 
égales et 0 sinon. Ces
listes contiennent des entiers positifs ou nuls et se terminent par la valeur 
--1.

c) Un tableau d'entiers T est dit trié par ordre croissant si ses entrées sont 
triées par ordre
croissant : si l est la longueur du tableau, Vi,j EUR {1, ..., l},i < j => T[i] 
{ T[j]. Il est dit trié par
ordre décroissant si ses entrées sont triées par ordre décroissant : si l est 
la longueur du tableau,
Vi, j EUR {1, ..., l},i < j => T [2] > T ... Dans les deux cas, il est dit 
trié. Remarquons qu'un tableau
T peut être à la fois trié dans l'ordre croissant et dans l'ordre décroissant, 
s'il vérifie : si l est la
longueur du tableau, Vi, j EUR {1, ..., I}, T [i] = T [3] Il alors est dit 
constant.

Ecrire la fonction

Test--tri données T : tableau d'entiers
l : entier
résultat a: : entier

qui prend en entrée un tableau T de longueur 1 et retourne la valeur 1 si le 
tableau T est trié par
ordre croissant et non constant, --1 si T est trié par ordre décroissant et non 
constant, 0 si T est
constant et 2 si T n'est pas trié.

Ecrire la procédure

Fusion données T : tableau d'entiers
l : entier
U : tableau d'entiers
m : entier
résultat W : tableau d'entiers trié

qui fusionne deux tableaux triés tous deux par ordre croissant (respectivement 
tous deux triés par
ordre décroissant), de longueurs respectives l, m ; le résultat est un tableau 
trié par ordre croissant
(respectivement par ordre décroissant) de longueur 1 + m. Dans le cas où les 
deux tableaux ne
sont pas tous deux triés dans un même ordre, la procédure Fusion renverra un 
tableau vide et un
message d'avertissement.

Exercice 2

a) Que retourne le programme suivant :

S <-- 2007 i <-- 1 tant que (i2 < S) faire i<---- @ + 1 fin tant que afficher(i) b) Que calculent les procédures suivantes : TR(N : entier, T : tableau d'entiers de longueur N, 1 : entier, m : entier) si (1 5 l) et (l 5 m) et (m S N) faire pour (2°: 1) â(i=m--l+l) faireTR[i] <--T[l--1+i] retourner TR fin si Valeur(N : entier, T : tableau d'entiers de longueur N, l : entier) si (1 5 l) et (l 5 N) faire a: <-- T... 9 <-- 0 d +-- N + 1 j <-- 1 tant que (j 5 N) faire si (T... <æ) faire g+--g+1 Ulÿl <-- TÜl si (T... >:13) faire d<--d--1 Uldl *-- TU] fin si j <-- j + 1 fin tant que si (9 < 1 < d) afficher :1: sinon si (1 _<_ 9) faire Valeur(g,TR(N, U, 1,9), !) si (l 2 d) faire Valeur(N ---- d + 1, TR(N, U, d, N),l -- d + 1) fin si sinon retourner "! NON VALIDE" fin si Exercice 3 Soit n un entier naturel. On dit que n est un nombre parfait si 277. est la somme des entiers naturels diviseurs de n. Par exemple, l'entier 6 est un nombre parfait puisque 2 >< 6 = 12 = 6 + 3 + 2 + 1. Ecrire un programme qui détermine la liste des nombres parfaits n tels que n _<_ 9999. Exercice 4 Un entier naturel 77. étant donné, on calcule le produit prod(n) de ses chiffres dans son écriture en base 10, puis le produit des chiffres de prod(n) dans son écriture en base 10, et on recommence ainsi l'application de prod jusqu'à obtenir un chiffre entre 0 et 9. Le nombre minimal de fois où on applique prod pour transformer n en un chiffre entre 0 et 9 est appelé la persistance de n. Par exemple, la persistance de 9 est égale à. O, celle de 97 est égale à 3, car prod(97) = 9 >< 7 = 63,prod(ô3) = 6 >< 3 = 18,prod(18) = 1 >< 8 = 8, et celle de 9575 est égale à 5, car prod(9575) = 1575,pr0d(1575) = 175,prod(175) = 35,prod(35) = 15,prod(15) = 5. Ecrire un programme qui calcule le plus petit entier naturel de persistance 5. Exercice 5 On considère l'alphabet à deux lettres: 2 = {a, à}. Soit n un entier naturel non nul. Un buffer de taille n est modélisé par un automate A,, = (Q... A... 0,Fn) sur l'alphabet E défini par ; 0 Q... l'ensemble des états de A,, est l'ensemble {O, 1, 2, ..., n}. L'état i représente la présence de exactement z' bits dans le buffer. . La lettre & représente l'arrivée d'un bit dans le buffer. La lettre â représente la sortie d'un bit du buffer. . A... est l'ensemble des transitions de An : -- % EUR {O, ...n -- 1}, (i,a,z' + 1), ---- Vz' EUR {1,...,n}, (i,â,z' - 1), o 0 est l'état initial de A... . F,, = {O, ...,n} est l'ensemble des états finaux. On note En le langage reconnu par l'automate A... Dans la suite, 6 désigne le mot vide. 1. Soient m, n des entiers naturels non nuls. Justifier précisément l'équivalence : £...C£n©m b.

Que signifie ceci pour les avions de cette compagnie ?