SECTION 

SECTION : SCIENCES DE L’INFORMATIQUE

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

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 
partie : (10 points)

Exercice n°1 
n°1 : (4 points)
1) Résultat de la fonction
b n Résultat
2 13 1101 (0,75 point)
16 163 A3 (0,75 point)

2) Le type de la fonction inconnue est : Chaîne de caractères / Chaîne / String (0,5 point)
Tableau de déclaration d’objets  :
Objet (0.25 point x 3) Type/Nature (0.25 point x 2)
Ch, S Chaîne de caractères / Chaîne / String
Entier / Integer / Mot / Word / Octet / Byte / Entier long / Longint /
R
Entier court / Shortint

3) La fonction retourne le résultat de la conversion d’un entier n dans la base b. (0,25 point x 3)

Exercice n°2 
n°2 : (3 points)
On n’acceptera pas une analyse à la place de l’algorithme.
1) Algorithme de la fonction récursive U
0/ DEF FN U (n : Entier) : Entier Long (Entier /Réel) (0.25pt)
1/ Si (n = 0) Alors U  0 (0.25pt + 0.25pt)
Sinon Si (n = 1) Alors U  -9 (0.25pt + 0.25pt)
Sinon U  6 * FN U(n-1) – 9 * FN U(n-2) (0.25pt + 0.5pt)
FinSi
2/ FIN U
2) L’ordre de récurrence de la fonction est égal à 2 car le terme Un est défini à partir des termes Un-1 et Un-2
(0.5 + 0.5 = 1 pt)
Solutions équivalentes possibles :
 car le terme Un est défini à partir des deux termes précédents.
 car le terme Un est défini à partir de deux termes.

Page 1 / 7
Exercice n°3 
n°3 : (3 points)
Analyse de la fonction Div_huit
DEF FN Div_huit (Ch : chaîne) : Booléen (0.25 pt)
5/ Résultat = Div_huit  (Cas1 OU Cas2) (0.25 pt)
4/ (Cas1, Cas2) = [Cas1  Faux, Cas2  Faux]
Si (c MOD 2 = 0) ET ((d*10 + u) MOD 8 = 0) Alors (0.75 pt)
Cas1  Vrai
Sinon
Si (c MOD 2 = 1) ET ((d*10 + u - 4) MOD 8 = 0) Alors
Cas2  Vrai (0.75 pt)
FinSi
FinSi
1/ c = Val (ch[Long(ch)-2],c,e) (3*0.25 = 0.75 pt)
2/ d = Val(ch[Long(ch)-1],d,e)
3/ u = Val(ch[Long(ch)],u,e)
6/ FIN Div_huit
TDO (0.25 pt)
Objet Nature / Type Rôle
Cas1, Cas2 Booléen (ou Logique) Variable intermédiaire
c entier Chiffre des centaines
d entier Chiffre des dizaines
u entier Chiffre des unités
e entier Variable intermédiaire
NB :
 La numérotation des séquences n’est pas obligatoire.
 Si le candidat utilise directement DIV et MOD dans l’extraction, il aura 0 sur cette partie.

Partie 2 : (10 points)

Analyse du programme principal

DEBUT Zone_Accumulation
4/ Résultat = PROC Afficher_NbZones (Nb_Zones, Recap, Nb_Recap, Deg_Min)
3/ (Recap, Nb_Recap, Nb_Zones) = Proc Déterminer_Zones (Espace, N, Recap, Nb_Recap, Nb_Zones,
Deg_Min, DN)
1/ (Espace, N) = Proc Remplir_Matrice (Espace, N)
2/ (Deg_Min, DN) = Proc Valider (Deg_Min, DN)
5/ FIN Zone_Accumulation

Tableau des nouveaux types

Type
Tab_Mat = Tableau de 100x100 d’entiers
Enreg = enregistrement
Lig : entier
Col : entier
Nb_Uns : entier
FIN Enreg
Tab_Recap = Tableau de 100x100 d'enreg (récapitulatif des subdivisions de la matrice)
Tableau des objets globaux
Objet Type Rôle

Page 2 / 7
 Recap Tab_Recap Tableau des zones de concentration
Nb_Recap, Entier Contient le nombre d’éléments du tableau
Nb_zones Entier Contient le nombre de zones de concentration
Espace Tab_Mat Matrice carrée contenant des 0 et des 1
N Entier Contient l’ordre de la matrice Espace
DN Entier Contient le nombre de zones
Deg_Min Entier Degré minimum de concentration
Afficher_NbZones Procédure Permet d’afficher les zones de concentration min
Déterminer_Zones Procédure Permet de déterminer les zones et leur concentration
Remplir_Matrice Procédure Permet de remplir la matrice Espace
Valider Procédure Permet de valider la valeur de Deg_Min et DN

Analyse de la procédure Remplir_Matrice

DEF PROC Remplir_Matrice (Var Espace : Tab_Mat ; Var N : entier)
Résultat = (Espace, N)
1/ (Espace , N) = [] Répéter
N = Donnée (Introduire N : )
Jusqu'à (N dans [1..100])
Pour l de 1 à N faire
Pour c de 1 à N faire
Espace [l, c]  hasard(2)
FIN pour
FIN Pour
2/ FIN Remplir_Matrice
Tableau des objets locaux
Objet Nature / Type Rôle
L Entier Compteur
C Entier Compteur

Analyse de la procédure Valider

DEF PROC Valider (VAR Deg_Min , DN : entier)
Résultat = (Deg_Min , DN)
2/ Deg_Min = [] Répéter
Deg_Min = Donnée
Jusqu'à (Deg_Min DANS [1..DN*DN])
1/ DN = [] Répéter
DN = Donnée
Jusqu'à (N MOD DN = 0) ET (DN > 0)
3/ FIN Valider
Analyse de la procédure Afficher_NbZones
DEF PROC Afficher_NbZones (Recap : Tab_Recap ; Nb_Recap, Nb_Zones, Deg_Min : entier)
Résultat = Tab-Affiché
1/ Tab-Affiché = [ Ecrire (« Le nombre de zones de concentration est : » , Nb_Zones) ]
Pour i de 1 à Nb_Recap faire
Si recap[i]. Nb_uns >= Deg_Min alors
écrire (" Zone n° :" ,i, " : ligne : ", recap[i].lig , " , colonne : ", recap[i].col , " . Le nombre de 1
dans cette zone est : ", recap[i].nb_uns, ". ")
FinSi
FinPour
2/ FIN Afficher_NbZones
Tableau des objets locaux
Objet Nature / Type rôle

Page 3 / 7
 i Variable / Entier Compteur

Analyse de la procédure Déterminer_Zones

DEF PROC Determiner_Zones (Espace : tab_Mat ; N : entier ; VAR Recap : Tab_Recap ; VAR Nb_Recap,
Nb_Zones : entier ; Deg_Min, DN : entier)
Résultat = (Recap , Nb_Recap, Nb_Zones)
1/ (Recap, Nb_Recap , Nb_Zones) =
[cpt 0, Nb_Zones  0]
Pour cptlig de 1 à (N/DN)² faire (* Division horizontale de ESPACE en DN
Pour cptcol de 1 à (N/DN)² faire bandes, et division verticale de caque bande en
Nbun  0 DN subdivisions*)
Cpt  cpt + 1
Recap[cpt].lig  DN * cptlig – DN + 1 (*Sauvegarde des coordonnées
Recap[cpt].col  DN * cptcol – DN + 1 de la 1ère cellule *)
Parcours horizontal Pour lig de (DN * cptlig – DN + 1) à (DN * cptlig) faire
des DN lignes d’une Pour col de (DN * cptcol – DN + 1) à (DN * cptcol) faire
subdivision Si (Espace [lig, col] = 1) alors (*Détermination du
Parcours vertical des
Nbun  Nbun+1 nombre de « 1 » *)
DN colonnes de la FinSi
subdivision FinPour
FinPour
Recap[cpt].nb_uns  nbun
Si nb_uns ≥ Deg_min alors (*Détermination du nombre
nb_zones  nb_zones +1 de zones de concentration *)
FinSi
FinPour
FinPour
Nb_Recap  cpt
2/ FIN Determiner-Zones
Tableau des objets locaux
Objet Nature / Type rôle
Cptlig , cptcol , nbun , cpt , col , lig Variable / Entier Compteurs

Algorithme programme principal

DEBUT Zone_Accumulation
1/ Proc Remplir_Matrice (Espace, N)
2/ Proc Valider (Deg_Min, DN)
3/ Proc Déterminer_Zones (Espace, N, Recap, Nb_Recap, Nb_Zones, Deg_Min, DN)
4/ Proc Afficher_NbZones (Nb_Zones, Recap, Nb_Recap, Deg_Min)
5/ FIN Zone_Accumulation

Algorithme de la procédure Remplir_Matrice

0/ DEF PROC Remplir_Matrice (Var Espace : Tab_Mat ; Var N : entier)
1/ Répéter
Lire(N)
Jusqu'à (N dans [1..100])
Pour l de 1 à N faire
Pour c de 1 à N faire
Espace [l, c]  hasard(2)
FIN pour
FIN Pour

Page 4 / 7
2/ FIN Remplir_Matrice

Algorithme de la procédure Valider

0/ DEF PROC Valider (VAR Deg_Min : entier ; DN : entier)
1/ Répéter
DN = Donnée
Jusqu'à (N MOD DN = 0) ET (DN > 0)
2/ Répéter
Lire(Deg_Min)
Jusqu'à (Deg_Min DANS [1..DN*DN])
3/ FIN Valider

Algorithme de la procédure Afficher_NbZones

0/ DEF PROC Afficher_NbZones (Recap :Tab_Recap ; Nb_Recap, Nb_Zones, Deg_Min : entier)
1/ Ecrire (« Le nombre de zones de concentration est : » , Nb_Zones)
Pour i de 1 à Nb-Recap faire
Si recap[i]. Nb_uns >= Deg_Min alors
Ecrire (" Zone n° :" ,i, " : ligne : ", recap[i].lig , " , colonne : ", recap[i].col , " . Le nombre de 1
dans cette zone est : ", recap[i].nb_uns, ". ")
FinSi
FinPour
3/ FIN Afficher_NbZones

Algorithme de la procédure Déterminer_Zones

0/ DEF PROC Determiner_Zones (Espace : tab_Mat ; D : entier ; VAR Recap : Tab_Recap ; VAR Nb_Recap,
Nb_Zones : entier ; Deg_Min, DN : entier)
1/ cpt 0 Nb_Zones  0
Pour cptlig de 1 à carré(N/DN) faire
Pour cptcol de 1 à carré(N/DN) faire
Nbun  0
Cpt  cpt + 1
Recap[cpt].lig  DN * cptlig – DN + 1
Recap[cpt].col  DN * cptcol – DN + 1
Pour lig de (DN * cptlig – DN + 1) à (DN * cptlig) faire
Pour col de (DN * cptcol – DN + 1) à (DN * cptcol) faire
Si (Espace [lig, col] = 1) alors
NbunNbun+1
FinSi
FinPour
FinPour
Recap[cpt].nb_uns  nbun
Si nb_uns >= Deg_min alors
nb_zones  nb_zones +1
FinSi
FinPour
FinPour
Nb_Recap  cpt
2/ FIN Determiner-Zones

Barème de la Partie II

Page 5 / 7
 Action Points
Programme principal (Décomposition + cohérence) 1
TDNT 0.5
TDO 0.5
Saisie de N et validation 0.5
Remplissage Espace et validation 0.75
Saisie de DN et validation 0.5
Saisie de Deg_Min et validation 0.5
Détermination et affichage du nombre de zones de concentration: 2.25 =
 Division horizontale de Espace en DN bandes et division verticale de
chaque bande en DN subdivisions 0.5
 Sauvegarde des coordonnées de la 1ère cellule 0.5
 Détermination du nombre de 1 0.5
 Détermination du nombre de zones de concentration 0.5
 Affichage du nombre de zones de concentration 0.25
Affichage des caractéristiques des subdivisions 0.5
Algorithmes (à répartir entre les modules envisagés) 3

Page 6 / 7
Page 7 / 7