Commissariat Régional de l’Éducation de Nabeul

Section : Sciences de l’Informatique

DEVOIR DE SYNTHÈSE N°3 Épreuve : Algorithmique et Programmation

Date : Jeudi 11 Mai 2023 Durée : 3 H
Nom et Prénom : ……………………………………………………………. Classe : …………................ Note : ……………… /20

Le sujet comporte 4 pages numérotées de 1/4 à 4/4. La page 1/4 doit être remise à la fin de l’épreuve.

N.B. : Tout algorithme demandé doit être accompagné par son(ses) tableau(x) de déclaration nécessaire(s).
Exercice N°1 (4 points)
Soit la fonction Inconnu définie par :
Fonction Inconnu (Ch : …………..., Test : …………...) : ……………………….
Début
Si long (ch) ≤ 1 Alors
Retourner Vrai
Sinon Si (ord (ch[long(ch)-1]) > ord (ch[long(ch)-2])) ≠ Test Alors
Retourner Faux
Sinon
Retourner Inconnu (sous_chaine(ch, 0 , long(ch)-1), Test)
FinSi
Fin
1) Compléter l’entête de la fonction Inconnu définie ci-dessus.
2) Pour chacun des appels ci-dessous, compléter le tableau par le résultat retourné par la fonction Inconnu,
sachant que : ord ("0") = 48, ord ("A") = 65 et ord ("a") = 97.
Appel Résultat
Inconnu ("1259", ord("1") < ord("2"))
Inconnu ("ZFBA", ord("Z") < ord("F"))
Inconnu ("1A5a", ord("1") < ord("A"))

3) Déduire le rôle de la fonction Inconnu.

…………………………………………….………………………………………………………..………
4) Soit Mat une matrice de caractères contenant N lignes et M colonnes. En utilisant la fonction Inconnu,
écrire l’algorithme d’un module qui permet d’afficher uniquement les colonnes de cette matrice pour
lesquelles cette fonction retourne vrai.
…………………………………………….………………………………………………………..………
…………………………………………….………………………………………………………..………
…………………………………………….………………………………………………………..………
…………………………………………….………………………………………………………..………
…………………………………………….………………………………………………………..………
…………………………………………….………………………………………………………..………
…………………………………………….………………………………………………………..………
…………………………………………….………………………………………………………..………
…………………………………………….………………………………………………………..………
…………………………………………….………………………………………………………..………
- Page 1 / 4 -
Exercice N°2 (5 points)
Un ingénieur de décoration veut calculer le coût et le temps de réalisation d’un projet qui consiste à décorer la
façade d’un bâtiment par les briques du Jerid (Kaleb). La façade a une longueur de 100 mètres et la hauteur est
calculée en fonction des parties de façades comme indiqué dans le schéma suivant :

Partie de
façade

100 mètres
Il faut noter que :
o La réalisation du projet sera répartie sur N parties de façades ayant des métrages égaux (avec 4 ≤ N ≤15).
o Un mètre carré de façade décorée coûte 57.500 DT.
o Durant une journée, on peut décorer 3 m2.
o L’ingénieur a remarqué que la mesure de la surface en mètre carré (m2) de la façade est équivalente à
l’aire de l’intégrale :

A=

On se propose de calculer les surfaces des parties de façades, en utilisant la méthode des rectangles. Pour cela,
un fichier nommé "detail.dat" sera remplit par les informations de chaque partie de façade.
Une partie de façade est caractérisée par la mesure de la surface à décorer en mètre carré (m2), le coût en dinars
et la durée de réalisation en nombre de jours. Ainsi, chaque enregistrement de ce fichier est caractérisé par :

✓ une surface : réel

✓ un coût : réel
✓ une durée : entier

Ecrire l’algorithme d’un module permettant de remplir le fichier "detail.dat" par les informations de N parties
de façades.

- Page 2 / 4 -
Exercice N°3 (5 points)
Soit la Grille de SuDoKu suivante :

9 8 4 2 3 6 7 1 5 Une grille de SuDoKu est une matrice de taille 9x9 subdivisée en

2 6 5 1 9 7 4 8 3 9 régions (carrés 3x3), telle que chaque ligne, chaque colonne et chaque
1 3 7 8 5 4 6 9 2
région ne doit contenir qu’une seule fois les chiffres de 1 à 9.
7 5 8 4 2 9 1 3 6
4 9 1 6 7 3 2 5 8
3 2 6 5 8 1 9 7 4 Région
8 4 9 7 6 5 3 2 1
6 7 2 3 1 8 5 4 9
5 1 3 9 4 2 8 6 7

Soit M une matrice de type MAT contenant 9x9 chiffres de 1 à 9.

1) Ecrire l’algorithme d’une fonction qui vérifie si une ligne numéro L de la matrice M contient des chiffres
distincts (L donné en paramètres).
2) Ecrire l’algorithme d’une fonction qui vérifie si une colonne numéro C de la matrice M contient des
chiffres distincts (C donné en paramètres).
3) Ecrire l’algorithme d’une fonction qui vérifie si une région commençant de la case d’indices (L, C) de la
matrice M contient des chiffres distincts (L et C sont donnés en paramètres).
4) En utilisant les fonctions définies précédemment, Ecrire l’algorithme d’un module qui vérifie si la matrice
M représente une grille correcte de SuDoKu ou non.

Exercice N°4 (6 points)

Le premier bit d’un nombre signé représente le bit de signe : 0 pour les nombres positifs et 1 pour les nombres
négatifs.
Pour trouver le négatif d’un nombre binaire, il suffit d’inverser tous ses bits en remplaçant le bit 1 par le bit 0
et inversement puis d’ajouter 1 au nombre trouvé.

Exemple :

(+6)10 = (0110)2 0 est le bit de signe qui signifie que le nombre est positif et 110 est la représentation binaire
du nombre 6.
(-6)10 = 1001 + 1 = 1010 on inverse les bits du nombre 6 en binaire en changeant le bit 1 par 0 et inversement
puis on ajoute la valeur 1 au résultat.

On se propose d’écrire un programme qui permet de calculer la différence entre deux nombres binaires signés
donnés en utilisant la somme, sachant qu’en arithmétique A – B = A+(–B).

1) Ecrire l’algorithme d’un module Ajouter1 (A) qui permet d’ajouter la valeur 1 à un nombre binaire A
donné, sachant que :
1+0=1
1 + 1 = 0 et on retient 1
- Page 3 / 4 -
 Exemple :

Retenue 0 0 1 0
1 0 0 1
+
0 0 0 1
= 1 0 1 0

Le calcul se fait de la droite vers la gauche et la valeur initiale de la retenue est 0.

2) Ecrire l’algorithme du module Inverser (B) qui permet d’inverser les bits d’un nombre binaire B donné
en changeant le bit 0 par le bit 1 et le bit 1 par le bit 0 et d’ajouter 1 au résultat trouvé et ce, en utilisant le
module Ajouter1.
3) Ecrire l’algorithme du module Aligner (A, B) qui permet de rendre de même longueur les deux nombres
binaires signés A et B en ajoutant à droite du bit du signe autant de 0 si le bit de signe est 0 et autant de 1
si le bit de signe est 1.
Exemples :
Pour A = 01110 et B = 101, après appel du module Aligner, B devient 11101
Pour A = 011 et B = 11010, après appel du module Aligner, A devient 00011
4) Ecrire l’algorithme du module Différence (A, B) qui permet de calculer la différence de deux nombres
binaires en faisant la somme de A et (-B) comme décrit ci-dessus en utilisant les modules précédemment
définis.
N.B. : La dernière retenue de la somme ne sera pas prise en considération puisque c’est une opération de
soustraction.
Exemple :
Retenue 1 1 1 0 0 0
0 1 1 1 0
+
1 1 1 0 1
= 0 1 0 1 1
1 + 1 + 1 = 1 et on retient 1
1 + 0 + 1 = 0 et on retient 1

- Page 4 / 4 -