République Tunisienne Section : Sciences de l’informatique
Ministère de l’éducation
Commissariat Régional de Nabeul Matière : Algorithmique et programmation
Niveau : 4ème Année Date : Jeudi 11 Mai 2017 Durée : 3 Heures
Bac blanc
Nom & Prénom : ………………………………… Classe : ………… Note : ………………… /20
N.B : Cette feuille est à remettre à la fin de l’épreuve
Exercice 1 (2,5 points)
1) Soit l’algorithme de la fonction "Inconnue" suivant :
1) DEF FN Inconnue (Var F : fich) : Booléen
2) Ouvrir(F)
3) Inconnue Finfichier(F)
4) Fin Inconnue
Après exécution de cet algorithme, et pour chacune des propositions suivantes,
mettre dans chaque case la lettre V si la proposition est correcte ou la lettre F dans le
cas contraire.
Le fichier F est un fichier Texte
Le fichier F est vide
3) Soient les différents algorithmes de la procédure "Afficher" ci-dessous (avec N un
entier strictement supérieur à 1) :
N° de l’algorithme L’algorithme
1) Def Proc Afficher (N:entier)
2) Si N=1 Alors Ecrire (N)
Sinon Proc Afficher (N-1)
1 Ecrire(N)
Fin Si
3) Fin Afficher
1) Def Proc Afficher (N:entier)
2) Si N=1 Alors Ecrire (N)
Sinon Ecrire(N)
2 Proc Afficher (N-1)
Fin Si
3) Fin Afficher
1) Def Proc Afficher (N:entier)
2) Si N=1 Alors Ecrire (N)
3 Sinon Proc Afficher (N-1)
Fin Si
3) Fin Afficher
Pour chacun des résultats ci-dessous, mettre dans chaque case le numéro de
l’algorithme de la procédure "Afficher" qui correspond à l’affichage de ces résultats :
1 de 1 à N de N à 1
Exercice 2 (4 points)
On se propose d’effectuer une opération d’addition entre deux nombres dans une base de
numération B (avec 2 < B < 16).
Exemple :
Pour additionner les nombres (FA) 16 et (A1E) 16 nous procédons comme suit :
① ①
0 F A
+A 1 E
= B 1 8
A+E 10 + 14 = 24 24 > 16 donc (24 – 16 = 8) et on retient 1
1+F+1 1 + 15 + 1 = 17 17 > 16 donc (17 – 16 = 1) et on retient 1
1+0+A 1 + 0 + 10 = 11 11 < 16 donc B dans la base 16
Ainsi, (FA + A1E) 16 = (B18)16
Travail demandé :
Ecrire l’algorithme d’un module permettant de déterminer le résultat de l’addition de
deux nombres N1 et N2 dans une base B (avec N1, N2 et B sont passés en paramètres) et
ce, sans convertir les nombres N1 et N2 dans la base décimale.
Dresser le ou les tableaux de déclaration des objets envisagés, sous la forme suivante :
Objet Type/Nature Rôle
Exercice 3 (4 points)
Pour trier un tableau T de N nombres distincts, en utilisant le tri PRAM, on procède de la
manière suivante :
Les valeurs du tableau à trier seront placées sur la première ligne d'une grille ainsi
que sur la première colonne, comme le montre l’exemple ci-dessous.
Une case d’indices (i, j), avec i ≠ 1 et j ≠ 1, sera remplie par :
1 si la valeur de la case d’indices (1, j) est inférieure à la valeur de la case
d’indices (i, 1),
0 sinon.
En parcourant la grille : Au niveau de chaque ligne, on compte le nombre de 1 (nb1).
La valeur correspondante sera placée dans la position (nb1+1) du nouveau tableau
trié.
Exemple :
Soit le tableau T à trier suivant : 2 8 3 7
La grille obtenue est la suivante :
2 8 3 7
2 0 0 0 0
8 1 0 1 1
3 1 0 0 0
7 1 0 1 0
En parcourant la grille, ligne par ligne, nous obtenons les sommes suivantes :
0
3
1
2
Le tableau trié sera donc : 2 3 7 8
Travail demandé :
Ecrire l’algorithme d’un module qui permet de trier un tableau T contenant N entiers
distincts en utilisant la méthode énoncé ci-haut, tout en dressant le ou les tableaux de
déclaration des objets envisagés sous la forme suivante :
Objet Type/Nature Rôle
NB : T et N sont passés en paramètres.
Problème (9,5 points)
On se propose de simuler le jeu suivant :
Deux joueurs, disposant chacun de six dominos. Chaque domino porte un mot de quatre
lettres, tiré d’un lexique. Un joueur est désigné au hasard pour commencer le jeu.
A chaque fois, un joueur pose un domino tout en juxtaposant ce dernier avec le précédent,
de façon à ce que les deux dernières lettres du premier domino concaténées avec les deux
premières lettres du second domino forment un mot de quatre lettres, se trouvant dans le
lexique.
Le jeu est terminé quand l’un des joueurs a utilisé tous ses dominos, il sera déclaré
"gagnant". Le jeu se termine aussi quand il n’y a plus aucune possibilité de former un mot
se trouvant dans le lexique fixé à l’avance. Dans ce dernier cas, le joueur qui a moins de
dominos restants sera déclaré "gagnant".
Exemple :
1- A partir du lexique suivant, formé de 13 mots :
TELE TETE MELE MARE CURE CUBE SEVE SETE LESE LEVE MISE MITE MILE VELO
2- Le 1er joueur dispose des six dominos suivants :
BETE SEME VECU LESE TELE LOUP
3- Le 2ème joueur dispose des six dominos suivants :
FETA SEVE RECU LEVA TETE SEMA
4- Le jeu peut procéder comme suit :
LESE TETE TELE SEVE LOUP
5- Le jeu s’arrête à ce niveau car le 2ème joueur ne trouve pas un domino contenant un mot
commençant par les deux lettres "UP"
6- Le 1er joueur est déclaré "gagnant" car il lui reste 3 dominos uniquement or le 2 ème joueur en lui
reste 4.
On se propose d’écrire un programme permettant de simuler le jeu décrit ci-dessus et ce :
En remplissant un fichier texte intitulé "Lexique.txt" par N mots formé chacun par
quatre lettres majuscules (avec N > 10).
En simulant le jeu précédemment décrit.
En affichant un message déclarant le joueur gagnant.
Travail demandé :
1- Ecrire une analyse du programme principal en décomposant le problème en modules.
2- Ecrire les algorithmes des modules envisagés tout en dressant les tableaux de
déclaration des objets sous la forme suivante :
Objet Type/Nature Rôle
