SECTION 

SECTION : SCIENCES DE L’INFORMATIQUE

EPREUVE THEORIQUE 
THEORIQUE : ALGORITHMIQUE ET PROGRAMMATION
SESSION DE JUIN 2011
CORRECTION DE L’EPREUVE –SESSION DE CONTROLE

NB :
 -0.25 par type d’erreur et l’erreur ne sera pénalisée qu’une seule fois
 On acceptera toute solution équivalente

Première partie : (10 points)

Exercice 
Exercice n°1 
n°1 : (3 points = 0.25 * 12)
1- Dans la version n°1, quelle(s) est (sont) la (les) valeur(s) de la variable X qui permet(tent)
l’exécution de la boucle Tant Que?
V 0

V 3

F 4

F 5

2- Dans la version n°1, quelle(s) est (sont) la(les) valeur(s) de la variable X qui permet(tent) de
saisir exactement 10 chiffres d’affaires (CA)?

V -6

F
-4

F 6

F 10
3- Dans la version n°2, que contiendra la variable SOMME à la fin de l’exécution de cet
algorithme si l’utilisateur saisit les valeurs 0, 10, 20 puis 30 ?

F 0

F 30

F 40

V 60
NB : On acceptera aussi Vrai / Faux, Oui / Non et O / N.
Page n°1 / 9
Exercice n°2 : (3,5 points)
On n’acceptera pas une analyse à la place de l’algorithme.

1. Calcul du nième terme de U

Solution itérative
0/ DEFFN Calc_Suite (n , m: entier) : réel (0.5 pt)
1/ s  1 + 1/m (0.5 pt)
Pour i de 1 à n faire (0.5pt)
s 1 + 1/s (0.5 pt)
FinPour
2/ Calc_Suite  s (0.5 pt)
3/ FIN Calc_Suite

Solution récursive
0/ DEFFN Calc_Suite (n , m: entier) : réel (0.5 pt)
1/ Si n = 0 Alors Calc_Suite  1 + 1/m (0.5 pt+0.5pt)
Sinon Calc_Suite  1+ 1/ FN Calc_Suite(n-1,m) (0.5 pt+0.5pt)
Finsi
2/ FIN Calc_Suite

2. L’ordre de récurrence de la fonction est égal à 1 car le terme Un est défini à partir du terme Un-1.
(0.5pt + 0.5pt)
NB : On acceptera les réponses suivantes :
- car le terme Un est défini à partir du terme précédent.
- car le terme Un est défini à partir d’un seul terme.

Exercice n°3 : (3,5 points)

On n’acceptera pas un algorithme à la place de l’analyse.

Analyse de la fonction Nb_Lig_Sym permettant de déterminer le nombre de lignes

symétriques de la matrice Mat :
DEFFN Nb_Lig_Sym (Mat : matrice; m, n : entier) : entier (0,5 pt)
Résultat = Nb_Lig_Sym  nb (0.25pt)
nb = [nb  0] (0.25pt)
Pour L de 1 à m Faire (0.25pt)
Si FN Sym (Mat,L,n) (0.25pt)
Alors nb  nb+1 (0.25pt)
FinSi
FinPour
Fin Nb_Lig_Sym

TDO Locaux (0.5 pt)

Objet Type/Nature Rôle
nb Entier Nombre de lignes symétriques
L Entier Compteur
Sym Fonction/Booléen Fonction permettant de vérifier la symétrie d’une ligne

Page n°2 / 9
 DEFFN Sym (Mat : matrice ; lig, n : entier) : Booléen
Résultat = Sym  valid
Valid = [i  1, valid  (Mat[lig,i]=Mat[lig,n])] (0.5 pt)
Tant que (i<=n Div 2) Et valid Faire (0.25pt)
i  i+1 (0.25pt)
valid  (Mat[lig,i]=Mat[lig,n-i+1]) (0.25pt)
FinTant que
Fin Sym
TDO Locaux
Objet Type/Nature
i Entier
valid Booléen/logique

Deuxième partie : (10 points)

(Déclaration de tous les objets locaux :

Analyse du programme principal

DEBUT Cryptage
Résultat = TR
TR = Proc Conv_nbr_txt (TR, MCO, lig, Long_Max)
MCO = Proc Conv_Oct (MCD, lig, Long_Max)
MCD = Proc Remplir (TD, MCD, lig, Long_Max)
TD = Assigner (TD, "C:\txtinit.txt")
lig  FN Nb_ligne (TD)
Long_Max  FN Plus_long (TD)
Fin Cryptage
Tableau de déclaration des nouveaux types
Type
Matrice = Matrice [1..50, 1..50] d’entiers

Tableau de déclaration des objets globaux

Objet Type/Nature Rôle
TD Texte Texte à crypter (supposé déjà saisi)
TR Texte Texte résultat (texte crypté)
MC Matrice Matrice contenant les codes ascii des caractères de T, puis convertis
de la base 10 vers la base 8
Col Octet Nombre de colonnes de MCD (nombre de caractères dans la ligne la
plus longue de T)
Lig Octet Nombre de lignes de MCD (nombre de lignes dans T)
Plus_long Fonction Fonction qui retourne la valeur de Col
Nb_ligne Fonction Fonction qui retourne la valeur de Lig
Conv_Oct Procédure Procédure qui convertit les éléments de MCD en octal
Conv_nbr_txt Procédure Procédure qui remplit le fichier texte TR à partir de MCD
Remplir Procédure Procédure qui remplit la matrice MC à partir du fichier texte T

Page n°3 / 9
 Analyse de la procédure Remplir
DEFPROC Remplir (Var TD : Texte ; Var M : Matrice ; Lig, Long_Max : Octet)
Résultat = M
M = [ L  0, Ouvrir (TD)]
Tant que (Non Fin_fichier(TD)) Faire
LL+1
Lire (TD, ph)
Pour c De 1 à Long_Max Faire
Si (c ≤ Long (ph) Alors M[L, c]  Ord(ph[c])
Sinon M[L,c]  Ord(" ")
FinSi
FinPour
FinTant que
Fin Remplir
Tableau de déclaration des objets locaux
Objet Type/Nat Rôle
L Octet Compteur pour les lignes
c Octet Compteur pour les colonnes
ph Chaîne Variable contenant chaque ligne lue du fichier

Analyse de la procédure Conv_nbr_txt

DEFPROC Conv_nbr_txt ( Var TR : Texte ; MC : Matrice ; lig, Long_Max : Octet)
Résultat = TR
TR = [Assigner (TR, "C:/txtcryp.txt"), Recréer (TR)]
Pour c De 1 à Long_Max Faire
Ph  ""
Pour L De 1 à lig Faire
Convch (MC [L,c], ch)
Ph  ph + ch + " "
Finpour
Ecrire_nl (TR, ph)
Finpour
Fin Conv_nbr_txt
Tableau de déclaration des objets locaux
Objet Type/Nature Rôle
L Octet Compteur pour les lignes
c Octet Compteur pour les colonnes
ph Chaîne Variable contenant chaque ligne lue du fichier
ch Chaîne Variable contenant la conversion d’un élément de la matrice en chaîne

Analyse de la procédure Conv_Oct

DEFPROC Conv_Oct (Var M : Matrice ; Lig, Long_Max : Octet)
Résultat = M
M=[]
Pour L De 1 à lig Faire
Pour c De 1 à Long_Max Faire
M[L,c]  FN Conv10_8 (M[L,c])
FinPour
FinPour
Fin Conv_Oct

Page n°4 / 9
 Tableau de déclaration des objets locaux
Objet Type/Nature Rôle
L Octet Compteur pour les lignes
c Octet Compteur pour les colonnes
Conv10_8 Fonction Fonction qui retourne la conversion d’entier de la base 10 vers la base 8

Analyse de la fonction Conv10_8

Def FN Conv10_8 (d : Entier) : Entier
Résultat = Conv10_8 Res
Res = Valeur (ch, Res, e)
Ch = [Ch ″″]
Répéter
R d MOD 8
Convch (R, Ch1)
d d div 8
Ch  Ch1 + Ch
Jusqu’à (d = 0)
Fin Conv10_8
Tableau de déclaration des objets locaux
Objet Type/Nature Rôle
R Entier Variable pour stocker le reste de la division
Res Entier Variable pour stocker le résultat de la fonction
e Entier Valeur de l’erreur
Ch1 Chaîne Variable pour stocker la conversion de R en chaîne
Ch Chaîne Chaîne résultat de la conversion

Analyse de la fonction Plus_long

DEFFN Plus_long (Var T : Texte) : Octet
Résultat = Plus_long Max
Ouvrir (T ) 
Max = 
 Lire (T , ph )


 Max  Long ( ph ) 
 

Tant que (Non Fin_fichier (T)) Faire

Lire (T, ph)
Si (Long (ph) > Max ) Alors
Max  Long (ph)
Finsi
FinTant que
Fin plus_long

Tableau de déclaration des objets locaux

Objet Type/Nature Rôle
Max Octet Variable temporaire pour stocker le résultat
Ph Chaîne Variable pour stocker chaque ligne lue à partir du texte
Analyse de la fonction Nb_ligne
DEFFN Nb_ligne (Var TD : Texte) : Octet
Résultat = Nb_ligne  N
Page n°5 / 9
N = [N  0, Ouvrir (TD)]
Tant que (Non Fin_fichier (TD)) Faire
Lire_nl (TD)
NN+1
FinTant que
Fin Nb_ligne
Tableau de déclaration des objets locaux
Objet Type/Nature Rôle
N Octet Variable temporaire pour stocker le résultat

NB :
- Le candidat sera évalué en fonction de ses capacités à traduire une analyse en algorithme,
donc les algorithmes sans analyse ne seront pas évalués
- La colonne « Rôle » n’est pas évaluée.

Algorithme du programme principal

0) Début cryptage
1) Assigner (T, "C:\txtinit.txt")
2) Lig  FN Nb_ligne (T)
3) Col  FN Plus_long (T)
4) Proc Remplir (T, MC, lig, col)
Proc Conv_Oct (MC, lig, col)
5) Assigner (TR, "C:/txtcryp.txt"), Recréer (TR)
Proc Conv_nbr_txt (TR, MC, col, lig)
6) Fermer (T), Fermer (TR)
7) Fin cryptage

Algorithme de la procédure Remplir

0) DEFPROC Remplir (Var T : Texte ; Var M : Matrice ; Lig, Col : Octet)
1) L  0, Ouvrir (T)
Tant que (Non Chercher_fin_fichier(T)) Faire
LL+1
Lire (T, ph)
Pour c De 1 à col Faire
Si (c ≤ Long (ph) Alors M[L,c]  Ord(ph[c])
Sinon M[L,c]  Ord(" ")
FinSi
FinPour
FinTant que
2) Fin Remplir

Algorithme de la procédure Conv_nbr_txt

0) DefProc Conv_nbr_txt (Var TR : Texte ; MC : Matrice ; col, lig : Octet)

Page n°6 / 9
 1) Ajouter (TR)
Pour L De 1 à lig Faire
Ph  ""
Pour c De 1 à col Faire
Convch (MC[L,c], ch)
Ph  ph + ch
Finpour
Ecrire_nl (TR, ph)
Finpour
2) Fin Conv_nbr_txt

Algorithme de la procédure Conv_Oct

0) DEFPROC Conv_Oct (Var M : Matrice ; Lig, Col : Octet)
1) Pour L De 1 à lig Faire
Pour c De 1 à col Faire
M[L,c]  FN Conv10_8 (M[L,c])
FinPour
FinPour
2) Fin Conv_Oct

Algorithme de la fonction Conv10_8

0) Def FN Conv10_8 (d : Entier) : Entier
1) Ch ″″
Répéter
R d MOD 8
Convch (R, Ch1)
d d div 8
Ch  Ch1 + Ch
Jusqu’à (d = 0)
2) Valeur (ch, Res, e)
3) Conv10_8  Res
4) Fin Conv10_8
Algorithme de la fonction Nb_ligne
0) Def FN Nb_ligne (Var T : Texte) : Octet
1) N 0, Ouvrir (T)
Tant que (Non Fin_fichier (T)) Faire
Lire_nl (T)
NN+1
FinTant que
2) Nb_ligne  N
3) Fin Nb_ligne

Algorithme de la fonction plus_long

0) Def FN Plus_long (Var T : Texte) : Octet
Page n°7 / 9
 1) Ouvrir (T)
Lire (T, ph)
Max  Long (ph)
Tant que (Non Fin_fichier (T)) Faire
Lire (T, ph)
Si (Long (ph) > Max ) Alors
Max  Long (ph)
Finsi
FinTant que
2) Plus_long  Max
3) Fin plus_long

Barème de la Partie II
Action Points
Analyse Algorithme
Programme principal (Décomposition + cohérence) 0.5+0.5 0.5
TDNT 0.25
TDOG + TDOL 0.5
Transfert du fichier « TxtInit » vers la matrice MC 1.75 = 0.75
- Ouverture du fichier + Parcours du fichier 0.25
- Avancement dans le fichier + Parcours horizontal de MC 0.50
- Parcours vertical de MC 0.50
- Rangement du code Ascii d’un caractère de « TxtInit » dans MC 0.25
- Ajout du code Ascii des espaces 0.25
Détermination de la ligne la plus longue 0.75 0.25
Détermination du nombre de lignes dans « TxtInit » 0.75 0.5
Conversion de la base 10 vers la base 8 1 0.5
Transfert de la matrice MC vers le fichier « TxtCrypt » 1 0.5

NB : La cohérence inclut :

- la concordance des paramètres formels avec les paramètres effectifs
- le mode de passage des paramètres

Page n°8 / 9
Page n°9 / 9