LYCÉE IBN RACHIK EZZAHRA Niveau : 4ème année

 Section : Sciences de l'informatique

Devoir de contrôle N°4
Matière : Algorithmique et programmation
Date : 21/02/2025 Durée : 1H Classe : 4 SI 1-2-3-4

Nom et Prénom : …………………………………………….. Classe : …………

Exercice 1 : (3 points)
Soient les algorithmes récursifs suivants ainsi que les premiers appels effectués au niveau du
programme principal :
Fonction F1 (a, b : Entier) : Entier Fonction F2 (a, b : Entier) : Entier
Début Début
Si a < b Alors retourner a Si a = b Alors retourner 1
Sinon retourner F1 (a-b, b) Sinon retourner a * F2 (a, b-1)
Fin Fin
Le premier appel se fait par : F1 (a, b) Le premier appel se fait par : F2 (a, b)

Fonction F3 (a, b : Entier) : Entier Fonction F4 (a, b, x : Entier) : Entier

Début Début
Si a < b Alors retourner 0 Si a-b < 0 Alors retourner x
Sinon retourner 1 + F3 (a-b, b) Sinon retourner F4 (a-b, b, a-b)
Fin Fin
Le premier appel se fait par : F3 (a, b) Le premier appel se fait par : F4 (a, b, a)

Fonction F5 (a, b, x : Entier) : Entier Fonction F6 (a, b, x : Entier) : Entier

Début Début
Si x > b Alors retourner 1 Si a-b < 0 Alors retourner x
Sinon retourner a * F5 (a, b, x+1) Sinon retourner F6 (a-b, b, x+1)
Fin Fin
Le premier appel se fait par : F5 (a, b, 1) Le premier appel se fait par : F6 (a, b, 0)

Pour chacune des propositions suivantes mettre une croix (x) devant le nom de la fonction (ou les
noms des fonctions) qui retourne(nt) le résultat demandé :
a. Pour calculer le reste de la division de a par b, on peut faire appel à (aux) la fonction (s) :
F1 F2 F3 F4 F5 F6
b. Pour calculer ab, on peut faire appel à (aux) la fonction (s) :

F1 F2 F3 F4 F5 F6

c. Pour calculer le résultat de a div b, on peut faire appel à (aux) la fonction (s) :

F1 F2 F3 F4 F5 F6

Lycée Ibn Rachik Ezzahra - Devoir de contrôle n° 4 Page 1/2

Exercice 2 : (4 points)
On se propose de calculer le Plus Grand Commun Diviseur (PGCD) de N entiers strictement positifs,
déjà stockés dans la première ligne d'une matrice M. Pour ce faire :
 Remplir les cases des (N-1) autres lignes, de sorte que la valeur d'une case M [L, C] est égale
au pgcd des contenus de M [L-1, C] et M [L-1, C+1].
 La case M [N, 1] contiendra le pgcd des N entiers.
Exemple : Pour N = 4, on aura :
Première ligne déjà remplie
60 48 16 34
12 16 2 PGCD (16, 34)
4 2
2 PGCD (60, 48, 16, 34)

Travail demandé :
Ecrire l’algorithme d’un module qui permet de remplir les cases des N-1 lignes d’une matrice carrée
M d’ordre N en utilisant le principe décrit ci-dessus, puis de retourner le PGCD des N entiers de la
première ligne.
Exercice 3 : (13 points)
Un nombre N est dit nombre de Niven s’il est divisible par la somme S de ses chiffres.
Exemple :
Pour N = 144 ➔ S = 1 + 4 + 4 = 9 ➔ 144 est divisible par 9 alors 144 est un nombre de Niven
On se propose de remplir un fichier intitulé "Niven.dat" par des enregistrements composés chacun
par les deux champs suivants :
 NV : un entier représentant un nombre de Niven de l’intervalle [100,1000]
 NV_Hex: l’équivalent hexadécimal de NV qui contient au moins un caractère alphabétique.
Exemples : Quelques nombres de Niven et leurs équivalents hexadécimaux :
(102, 144, 264, 630, 915) ➔ (66, 90, 108, 276, 393)
Ces nombres de Niven ne seront pas sauvegardés dans le fichier car ils ne contiennent aucun caractère
alphabétique.
(171, 195, 500, 700, 972) ➔ (AB, C3, 1F4, 2BC, 3CC)
Ces nombres de Niven seront sauvegardés dans le fichier car ils contiennent au moins un caractère
alphabétique.
Travail demandé :
1. Ecrire l’algorithme d’un module nommée "convertir (N)" qui permet de convertir un entier
décimal N vers la base 16.
2. Ecrire un algorithme d’une fonction nommée "Niven (N)" qui permet de vérifier si un entier N est
un nombre de Niven ou non.
3. Ecrire un algorithme d’une fonction nommée "verifier (CH)" qui permet de vérifier si une chaîne
de caractères CH contient au moins un caractère alphabétique.
4. Ecrire un algorithme d’une procédure nommée "Remplir (NomF)" qui remplit le fichier
"Niven.dat" par les nombres de Niven de l'intervalle [100, 1000].
5. Ecrire l’algorithme du programme principal ainsi que les tableaux de déclarations des objets
utilisés.
NB : Le paramètre NomF utilisé dans l’entête du module Remplir est une chaîne de caractères
représentant le nom physique du fichier "Niven.dat".
Bon travail
Lycée Ibn Rachik Ezzahra - Devoir de contrôle n° 4 Page 2/2
Classe : 4ème Sciences de l'informatique 1,2, 3 et 4 Lycée Ibn Rachik - Ezzahra

Correction du devoir de contrôle 4 (Théorique)

Exercice 1 : (3 pts)
a. Pour calculer le reste de la division de a par b, on peut faire appel à (aux) la fonction (s) :
F1 X F2 F3 F4 X F5 F6
b. Pour calculer ab, on peut faire appel à (aux) la fonction (s) :

F1 F2 F3 F4 F5 X F6

c. Pour calculer le résultat de a div b, on peut faire appel à (aux) la fonction (s) :

F1 F2 F3 X F4 F5 F6 X
NB : -0.25 par erreur

Exercice 2 : (4 pts)
Fonction Calculer_Pgcd (M : mat ; n : Entier) : Entier
Début
TDOL
Pour i de 1 à (n-1) Faire O T/N
Pour j de 0 à (n-1-i) Faire i, j Entier
M[i,j]  PGCD (M[i-1,j], M[i-1,j+1]) PGCD Fonction
Fin Pour
Fin Pour
Retourner M[n-1,0]
Fin

Algorithme de la fonction PGCD : Autre algorithme de la fonction PGCD

Fonction PGCD (a, b : Entier) : Entier Fonction PGCD (a, b : Entier) : Entier
Début Début
Si a = b Alors Si (a Mod b) = 0 Alors
Retourner b Retourner b
Sinon Sinon
Si a > b Alors Retourner Pgcd (b, a mod b)
Retourner Pgcd (a - b, b) Fin Si
Sinon Fin
Retourner Pgcd (a, b - a)
Fin si
Fin Si
Fin

Algorithmique et programmation – Correction du devoir de contrôle 4 - 2024/2025 1

Classe : 4ème Sciences de l'informatique 1,2, 3 et 4 Lycée Ibn Rachik - Ezzahra

Exercice 3 : (13 pts)

Algorithme de la fonction convertir
Fonction Convertir (n : Entier) : Chaîne TDOL
Début O T/N
Ch  "" R Entier
Ch Chaîne
Répéter
R  n mod 16
n  n div 16
Si R ≥ 10 Alors
Ch  CHR ( R + 55 ) + Ch
Sinon
Ch  Convch (R) + ch
Fin Si
Jusqu’à n = 0
Retourner Ch
Fin
Algorithme de la fonction Niven
Fonction Niven (n : Entier) : Booléen TDOL
O T/N
Début
S Entier
S0
Répéter
S  S + n mod 10
n  n div 10
Jusqu’à n = 0
Retourner n mod S = 0
Fin
Algorithme de la fonction Verifier Autre algorithme de la fonction Verifier
Fonction Verifier (ch : Chaîne) : Booléen Fonction Verifier (ch : Chaîne) : Booléen
Début Début
c0 Retourner Non Estnum (ch)
i0 Fin
Répéter
Si ch[i] ϵ ['A'..'F'] Alors Autre algorithme de la fonction Verifier
cc+1 Fonction Verifier (ch : Chaîne) : Booléen
Fin Si Début
ii+1 i0
Jusqu’à i = Long (ch) ou c ≠ 0 Répéter
Retourner c ≠ 0 test  ch[i] ϵ ['A'..'F']
TDOL ii+1
Fin
O T/N Jusqu’à i = Long (ch) ou test
c, i Entier Retourner test
Fin

Algorithmique et programmation – Correction du devoir de contrôle 4 - 2024/2025 2

Classe : 4ème Sciences de l'informatique 1,2, 3 et 4 Lycée Ibn Rachik - Ezzahra
Algorithme de la Procédure Remplir
Procédure Remplir (NomF : Chaîne) TDOL
Début O T/N
Ouvrir (NomF, f, "wb") i Entier
Pour i de 100 à 1000 Faire f Fichier_Niven
Si Niven (i) et Verifier (Convertir (i)) Alors e Engt_Niven
e.NV  i Niven Fonction
Verifier Fonction
e.NV_HEX  Convertir (i)
Convertir Fonction
Ecrire (f, e)
Fin Si
Fin Pour
Fermer (f)
Fin
TDNTL
Type
Engt_Niven = Enregistrement
NV : Entier
NV_HEX : Chaîne
Fin
Fichier_Niven = Fichier de Engt_Niven

Algorithme du programme principal : TDOG

Algorithme Nombre_Niven O T/N
Début Remplir Procédure
Remplir ("Niven.dat")
Fin

Algorithmique et programmation – Correction du devoir de contrôle 4 - 2024/2025 3