République Tunisienne Section : Sciences de l’informatique
Ministère de l’éducation
Commissariat Régional de Nabeul Matière : Algorithmiques et programmation
Lycée Grombalia
Classes : 4SI1, 4SI2, 4SI3 Date : 10/12/2024 Durée : 3Heures
Devoir de Synthèse N° 1
Nom & Prénom : ………………………………….…………………… Classe : ……… Note : ………… /20
Le sujet comporte 4 pages, la page n°1 et la page n°2 et la page n°3 et la page n°4 sont à remettre à la
fin de l’épreuve
NB : Tous les exercices doivent être accompagnés par les tableaux de déclarations des objets et
des nouveaux types nécessaires.
Exercice n°1 : (3pts)
Voici le début de la trace d’exécution d’un algorithme de tri :
Etat initial 10 56 4 78 7 98 5
Répétition1 98 56 4 78 7 10 5
Répétition 2 98 78 4 56 7 10 5
…
Q1) De quel algorithme de tri s’agit-il ?
………………………………………………………………………………………………………………
…………………………………………………………………………………………………….…………
Q2) Compléter le tournage à la main de cet algorithme :
Etat initial 10 56 4 78 7 98 5
Répétition1 98 56 4 78 7 10 5
Répétition 2 98 78 4 56 7 10 5
Q3) proposer un algorithme pour cette méthode de tri :
Page 1 sur 4
Exercice n°2: (2pts)
Une matrice d’entiers est dite creuse lorsque elle comporte un nombre de zéros supérieur à la moitié de
nombre des éléments de cette matrice.
Exemple 1 : soit la matrice carré suivante de 4 lignes et 4 colonnes
4 0 0 7
0 0 54 0
8 0 0 6
0 0 3 0
Puisque le nombre de 0 dans la matrice = 10 est supérieur à la moitié de nombre des éléments de cette
matrice (8), donc cette matrice est creuse.
Exemple 2 : soit la matrice carré suivante de 4 lignes et 4 colonnes
8 30 0 7
9 0 54 1
8 2 5 6
0 0 3 0
Puisque le nombre de 0 dans la matrice =5 est inférieur à la moitié de nombre des éléments de cette
matrice (8), donc cette matrice n’est creuse.
Travail demandé:
On disposant d’une matrice carré de N lignes et N colonnes d’entiers et sachant que L représente le
compteur de parcours des lignes et C le compteur de parcours des colonnes.
On vous donne l’algorithme incomplet de la fonction récursive creuse qui permet de vérifier si une
matrice est creuse ou non.
fonction creuse (M : mat, NB, N, L, C :entier) : booleen
Debut
Si (L=N) alors
…………………………….
Sinon
Si (………..…..) alors
retourner creuse (M, NB, N, L+1,0)
Sinon
Si (…………….) alors
retourner creuse (M, NB+1, N, L, C+1)
Sinon
…………………………
Fin si
Fin si
Fin si
Fin
- Compléter l’algorithme de la fonction creuse ci-dessus.
Page 2 sur 4
Exercice n°3 : (7.5pts)
Soit les deux fichiers binaires "Stocks.dat" et "Achat.dat" ayant respectivement la structure suivante :
Le fichier "Stocks.dat" :
- Code-produits: Entier de 4 chiffres
- Qt-Stocks : quantité en stocks.
Le fichier "Achat.dat"
- Code-produits: Entier de 4 chiffres (existe dans le fichier "Stocks.dat"
- Q-Achetée : Quantité Achetée
1. Ecrire l'algorithme d'un module qui permet d'afficher les produits du fichier "Stocks.dat" dont la
quantité en stock est minimale (inferieure à 10).
2. Ecrire l'algorithme d'un module qui permet mettre à jour le fichier "Stocks.dat" en ajoutant la
quantité achetée du fichier "Achat.dat" à la quantité en stock du fichier "Stocks.dat". sachant que
le fichier "Achat.dat" ne contient pas tous les produits).
3. Supposant que le fichier "Stocks.dat" est trié par ordre croissant de Code-produits, Ajouter un
nouveau produit au fichier à sa bonne position, sans trier de nouveau le fichier.
Exercice n°4 : (5.5pts)
Soit ch une chaine de caractères formée uniquement par des chiffres (0..9). Une séquence est dite
équilibrée si elle commence par le caractère "5" et se termine par le caractère "5" et elle contient au
moins un chiffre inferieur à "5" et au moins un chiffre supérieur à "5".
Exemple :
Ch= "12450278569" ch contient une séquence équilibrée de longueur 6. (502785)
Ch ="87541258" ch ne contient pas une séquence équilibré, en effet dans la séquence 54125 ne
contient pas un caractère dont le code ASCII est supérieur au code ASCII de 5.
Travail demandé :
En disposant d’un fichier texte "chaines.txt" déjà remplit par n chaines de caractères. Une chaine par
ligne, et chaque chaine est formée uniquement par des chiffres et comportant deux fois le chiffre 5.
1) A partir du fichier "chaines.txt", écrire l’algorithme d’un module remplir qui permet de remplir
un fichier binaire "equilibres.dat" par les séquences équilibrées. Chaque enregistrement ayant la
structure suivante :
Seq : la séquence équilibré à partir d’une ligne du fichier "chaines.txt" si elle existe.
Long-seq : la longueur de cette séquence équilibrée.
2) Ecrire l’algorithme d’un module afficher qui permet d’afficher la plus longue séquence équilibrée
du fichier "équilibres.dat".
Exemple :
Pour N= 7 et le fichier "chaines.txt" suivant :
4758952 Seq Long-seq
58315470 58315 5
285605339 5605 4
15335 Le fichier "équilibres.dat" sera
5936011945 10
45936011945 514485 6
615144859
3596752
La plus longue séquence équilibrée est : 5936011945
Page 3 sur 4
Exercice n°5 : (12pts)
Un réseau routier peut être représenté par une matrice carré M (NxN) contenant seulement des 0 et
des 1, où N est le nombre des villes. Si M[L,C]= 1, alors la ville numéro L et la ville numéro C sont
reliées par une route principale.
En disposant de la matrice M déjà remplit (vous n’êtes pas appelé à remplir la matrice ni à saisir N) et
pour automatiser ce problème, on vous demande d’écrire un programme qui permet de :
- Remplir le fichier ″ville.dat″ par N villes. chaque enregistrement du fichier ″ville.dat″ est composé
de deux champs :
Numero : entier commençant de 0 et s’incrémente automatiquement.
Nom : chaîne de caractère formée uniquement par des lettres alphabétique et des espaces.
- A partir de la matrice M et du fichier ″ville.dat″, Sauvegarder dans un fichier ″reseau.dat″, le nom
de chaque ville et les noms des villes aux quelles cette ville et liée directement (les noms de chaque
deux villes sont séparés par un tiret). Chaque enregistrement du fichier ″reseau.dat″ comporte deux
champs :
Ville_dep : chaîne de caractère pris à partir du fichier ″ville.dat″
Route : chaîne de caractère contenant les differents noms des villes reliés à Ville_dep
Remarque : la vérification du champ Nom pour qu’il soit formé uniquement par des lettres alphabétique
et des espaces doit se faire par un module récursif.
Exemple :
Si le fichier "villes.dat" contient:
0 Grombalia
1 Soliman
2 Beni khaled
3 Nabeul
4 Menzel Bou Zelfa
……………
Donc, et selon la matrice suivante, la ville de Grombalia est reliée directement par une route
principale à Soliman, Beni khalled et Nabeul
Le contenu du fichier reseau.dat sera
Ville_dep Route
Grombalia Soliman-Beni khaled-Nabeul
Soliman Grombalia-Beni khaled-Mensel bouzelfa
Beni khaled Grombalia-Soliman-Nabeul-Menzel Bou Zelfa
…….
Travail demandé :
1) Ecrire l’algorithme relatif à ce programme en le décomposant en modules.
2) Elaborer l’algorithme de chaque module envisagé dans la question1.
Page 4 sur 4
