Lycée Secondaire Dar Chaâbane El Fehri Classe : 4ème SI 1

Date : 10/12/2024
DEVOIR DE SYNTHESE N°1 Durée : 3 Heures
Discipline : Informatique
Réalisé par Mme Hami DHAMEN Matière : Algorithmique & programmation
Nom & Prénom :…………………………………
Exercice1 : (2 Points)
Soient les fonctions ci-dessous :

Fonction ( f1 ) Fonction ( f2 )
Fonction f1(a,b :entier) :entier Fonction f2(a,b :entier) :entier
Début Début
Si b=1 alors Si b=1 alors
Retourner a Retourner a
Sinon Sinon
Retourner a * f1(a,b-1) Retourner a + f2(a,b-1)
FinSi FinSi
Fin Fin
Fonction ( f3 ) Fonction ( f4 )
Fonction f3(a,b :entier) :entier Fonction f4(a,b:entier):entier
Début Début
Si a<b alors ch convch(b)
Retourner 0 Si a=0:
Sinon Retourner 0
Retourner 1+ f3(a mod b,b) Sinonsi pos(convch( a mod 10), ch) ≠ -1 alors
FinSi Retourner 1+f4(a div 10,b)
Fin Sinon
Retourner f4(a div 10 ,b)
FinSi
Fin

Sachant que a et b deux entiers naturels non nuls, on vous demande de cocher la case correspondante à
la proposition correcte :

1) Pour calculer le produit de deux entiers a et b, on utilise la fonction :

f1 f2 f3 f4

2) Pour calculer le nombre de chiffres communs entre deux entiers a et b, on utilise la fonction :
f1 f2 f3 f4

3) Pour calculer l’expression ab, on utilise la fonction :

f1 f2 f3 f4

4) Pour calculer le quotient de la division entière de deux entiers a et b, on utilise la fonction :

f1 f2 f3 f4

1
Exercice2 : (3 Points=1+0,5+1,5 )

Soit la fonction Inconnue définie par :

Inconnue(n)= 0 si n=0

Inconnue(n)= 2*n-1 + Inconnue(n-1) sinon

Questions :
1) Déterminer avec détail :
Inconnue(3) Inconnue(4)

2) Donner le rôle de la fonction Inconnue

…………………………………………………………………………………………
3) Ecrire d’une façon récursive l’algorithme de la fonction Inconnue
……………………………………………………..
……………………………………………………..
……………………………………………………..
……………………………………………………..
……………………………………………………..
……………………………………………………..
……………………………………………………..
……………………………………………………..

Exercice3 : (2 Points )
Soit T un tableau déjà rempli par N entiers.
Ecrire d’une manière récursive l’algorithme de la fonction nommée Position qui permet de renvoyer une
chaine de caractères contenant les positions d’occurrence, séparées par un tiret, d’un entier X dans le
tableau T. Si l’entier X ne figure pas dans T la fonction revoie la chaine vide (l’entier X est déjà saisie
auparavant)
Exemple : 0 1 2 3 4
Prenons X =10 , N=5 et T= 10 5 10 50 10

Le résultat renvoyé par la fonction Position sera la chaine ″0-2-4-″

2
Exercice4 : (4 Points )
Etend donnée un fichier binaire nommé ″entier.fch″ déjà rempli par une suite d’entiers distincts. On
veut réorganiser ce fichier de la manière suivante :
Le plus petit nombre, le plus grand nombre, le deuxième plus petit nombre, le deuxième plus grand
nombre, le troisième plus petit nombre, etc
Exemples :
1- Soit le fichier ″entier.fch″ suivant :

30 80 1 26 22 900 24 70 50

Après réorganisation, ce fichier sera :

1 900 22 80 24 70 26 50 30

2- Soit le fichier ″entier.fch″ suivant :

3 1 4 2

Après réorganisation, ce fichier sera :

1 4 2 3

On vous demande d’écrire l’algorithme du module nommé reorganiser() qui permet de réorganiser le
fichier ″entier.fch″ en respectant la méthode décrite auparavant
Exercice5 : (4 Points )
On appelle bigramme une suite de deux lettres identiques
Soit un fichier texte nommé ″texte.txt″ déjà rempli par un texte ne contenant que de lettres minuscules et
de astérisques ″*″.
On veut déterminer tous les bigrammes et leurs occurrences dans le fichier ″texte.txt″
Pour cela on vous demande d’écrire un algorithme de la procédure nommée former(T,n) qui permet de
former, à partir du fichier ″texte.txt″, un tableau d’enregistrements T. Chaque enregistrement est formé
de champs suivants :
• big :bigramme provenant du fichier ″texte.txt″
• Nbocc ; nombre d’occurrences du bigramme big dans le fichier ″texte.txt″
N.B : le tableau T doit être trié dans l’ordre décroissant selon le champ Nbocc
Exemple : aacc**aa*bba
Soit le fichier ″texte.txt″ suivant : b*cddbbbee***oeeee*

Le tableau T avant l’opération du tri : big aa cc bb dd ee

Nbocc 2 1 3 1 4

big ee bb aa cc dd
Le tableau T après l’opération du tri :
Nbocc 4 3 2 1 1

3
Exercice6 : (5 Points )
Soit une matrice M contenant nl*nc lettres majuscules (3≤nl≤20 et 3≤nc≤20)
Soit un vecteur T (tableau à une seule dimension) contenant nc lettres majuscules
On défini, par un taux de ressemblance entre une ligne et le vecteur T, par le nombre de positions
(numéros de colonnes de M) qui ont des valeurs égales aux valeurs du vecteur aux mêmes positions
On veut déterminer la ou les lignes de M ayant le plus élevé taux de ressemblance
Exemple :
M= 1 2 3 4 5 6 T= 1 2 3 4 5 6
1 C B F G J K
A M K J O G
2 A M C J A G
3 T M Z J R L
4 A B K U O G

Les lignes ayant le plus élevé taux de ressemblance sont 2 , 4

(en effet taux de ressemblance de la ligne 1 et T =0
taux de ressemblance de la ligne 2 et T =4
taux de ressemblance de la ligne 3 et T =2
taux de ressemblance de la ligne 4 et T =4)

Pour faciliter cette tâche, on va utiliser un fichier d’enregistrements nommé ″taux.fch″. Chaque
enregistrement est composé de champs suivants :
• Numl : numéro de la ligne de M
• Taux : taux de ressemblance entre la ligne numl et le vecteur T

Travail demandé :
1) Définir les types adéquats pour déclarer la matrice M, le vecteur T et le fichier ″taux.fch″
2) Ecrire l’algorithme de la fonction ressemblance(M,T,l,nc) qui permet de calculer le taux de
ressemblance d’une ligne l de la matrice M et le vecteur T
3) Ecrire l’algorithme de la procédure former(M,T,nl,nc) qui permet de calculer pour chaque ligne
de M, le taux de ressemblance avec T et mettre le résultat dans le fichier ″taux.fch″. Cette
procédure doit appeler la fonction ressemblance déjà définie auparavant
4) Ecrire l’algorithme de la procédure affich() qui permet de déterminer et afficher la ou les lignes
ayant le plus élevé taux de ressemblance

Bon courage
4