Commissariat Régional de l’Education de Monastir
Section : Sciences de l’Informatique
Devoir de synthèse n°3
Epreuve : Algorithmique & Programmation
Niveau : 4ème année Date : Mardi 06/05/2025. Durée : 3 heures
Nom & Prénom : ………………………… Classe : ………….. Note : ………/20
- Le sujet comporte 5 pages numérotées de 1/5 à 5/5.
- Le candidat est appelé à répondre sur la première feuille du devoir qui sera remise
à la fin de l’épreuve.
Exercice 1 : (3 points)
Soit la fonction quoi suivante :
Fonction quoi (x : ………….….) : ……………….
Début
yx, a0, bx
Tant que (abs(y*y-x)>=0.0001) faire
Si y*y > x+0.0001 alors
by
Sinon
ay
Finsi
y(a+b)/2
Fin tantque
retourner y
Fin
Travail demandé :
1. Effectuer le tournage à la main de la fonction quoi pour chacun des cas suivants :
a. x=256
y
a
b
b. x=25
y
a
b
2. Déduire le rôle de la fonction quoi.
…………………………………………………………………………………………
……………………………………………………….…………………………………
1|5
Exercice N°2 : (4 points)
Tout entier naturel positif N peut s’écrire de façon unique sous la forme :
N=a1*1 ! + a2*2 ! + a3*3 ! +…………..+ ad*d ! où a1, a2, a3, ……..ad sont des
entiers positifs.
Exemples :
• 23=3*3! + 2*2! + 1*1!
• 19=1*5! + 1*3! + 1*2! + 1*1!
• 350=2*5! + 4*4! + 2*3! + 2*1!
Travail demandé :
1. Ecrire un algorithme d’une fonction récursive Fact permettant de calculer la
factorielle d’un entier naturel N. on rappelle que la factorielle de N est
N ! =1* 2* ……....* N.
2. Utiliser la fonction Fact pour écrire l’algorithme d’un module permettant de
retourner la décomposition d’un entier positif en une somme de factoriels.
Exercice n°3 : (5 points)
On veut remplir une matrice binaire (contenant uniquement des 0 et des 1) à partir
d’un fichier Texte "sequence_matrice.txt" selon le principe suivant :
• Le nombre de lignes correspond au nombre total de lignes du fichier.
• Le nombre de colonnes est calculé automatiquement selon la règle suivante :
Pour chaque ligne, on additionne tous les entiers et on y ajoute le nombre de tirets
(-) présents dans la ligne.
Le plus grand résultat obtenu sur l'ensemble des lignes détermine le nombre de
colonnes de la matrice.
1. La taille des lignes (NL) correspond au nombre total de lignes du fichier.
2. Le nombre de colonnes (NC) est calculé automatiquement selon la règle
suivante :
a. Pour chaque ligne, on additionne tous les entiers et on y ajoute le
nombre de tirets (-) présents dans la ligne.
b. Le plus grand résultat obtenu sur l'ensemble des lignes détermine le
nombre de colonnes de la matrice.
3. Chaque entier indique le nombre de 1 consécutifs à insérer.
4. Entre deux groupes de 1, un 0 est automatiquement inséré.
5. Le remplissage se fait de gauche à droite.
2|5
Exemples :
Contenu du fichier sequence_matrice.txt : Matrice M obtenue :
3-2-1
2-3 1 1 1 0 1 1 0 1
1-1-2 1 1 0 1 1 1 0 0
Calculs intermédiaires : 1 0 1 0 1 1 0 0
• Ligne 1 : 3+2+1 = 6 + 2 tirets → 8
• Ligne 2 : 2+3 = 5 + 1 tiret → 6
• Ligne 3 : 1+1+2 = 4 + 2 tirets → 6
→ Le nombre de colonnes est donc : 8
Travail demandé :
Proposer une solution modulaire qui permet de remplir et d’afficher une matrice M à
partir du fichier texte "sequence_matrice.txt" en respectant les règles suivantes :
• Le fichier texte est déjà remplit et enregistré sous la racine c :/
• Chaque suite d'entiers de la ligne du fichier construit une ligne de la matrice.
• Chaque groupe de x1 est inséré successivement, séparé par un 0, tant que la fin
de ligne n'est pas atteinte.
• Les cases restantes de la ligne (si la séquence ne remplit pas toute la ligne) sont
complétées par des 0.
Exercice N°4 : (8 points)
Pour évaluer l’état d’une grille dans des jeux, il faut
trouver tous les alignements de N éléments dans une
matrice M de dimension NL lignes*NC colonnes.
Dans la suite, nous décidons de rechercher les
alignements de 1 dans une matrice M de dimension NL lignes*NC colonnes déjà
remplie par des 0 et des 1.
I- Recherche d’alignements horizontaux :
Rechercher un alignement horizontal dans un tableau revient à rechercher un
alignement dans chacune de ses lignes.
Question :
Ecrire un algorithme d’une procédure trouve_suite (M, NC, L, N, T, K) permettant
de remplir le tableau T par K indice de début de chaque liste des éléments recherchés
formant une suite des 1 de longueur N dans une ligne L.
Exemple : soit N=3, NL=7, NC=6
3|5
M=
1. Utiliser la procédure précédente pour écrire un algorithme de la procédure
trouve_align_H (M, NL, NC, N, TH, H) permettant de remplir un tableau
d’enregistrement TH par H enregistrements où chaque enregistrement comporte
2 champs :
• Num_L : Numéro du ligne comportant la suite des 1 de longueur N.
• IDD : indice de début de la liste des éléments recherchés formant une
suite des 1 de longueur N dans la ligne.
II- Recherche d’alignements verticaux :
Rechercher un alignement dans la direction verticale revient à rechercher un
alignement horizontal dans son transposé.
M= Matrice transposée M1=
Question :
1. Ecrire une procédure transpose (M, NL, NC, M1) permettant de construire la
matrice transposé M1 de la matrice M.
III- Recherche d’alignement diagonaux
Rechercher un alignement dans une direction diagonale revient à rechercher un
alignement vertical dans une matrice dont les lignes sont décalées.
4|5
Décalage gauche
RQ : on combe les extrémités des lignes avec des zéros.
1. Ecrire un algorithme d’une procédure decale_gauche(M,NL,NC, M1,NC1)
permettant de décaler chaque ligne vers la gauche d’autant de colonnes que son
rang dans la matrice M dans une matrice M1 de NC1 colonnes.
2. Ecrire un algorithme d’une procédure decale_droite(M,NL,NC, M1,NC1)
permettant de décaler chaque ligne vers la droite d’autant de colonnes que son
rang dans la matrice M dans une matrice M1 de NC1 colonnes.
IV- Assemblage :
1. En utilisant les modules précédents définies, écrire un algorithme de la
procédure affiche (M, NL, NC, N) permettant d’afficher tous les alignements
de N éléments dans une Matrice M de NL et NC entiers.
➢ NB :
M est une matrice de type Mat déjà remplie par NL*NC entiers entre 0 et 1.
NL, NC et N sont des entiers déjà saisis.
5|5