ExErcicEs dE révision – suitE –
Exercice 1
On se propose d’écrire un algorithme permettant de saisir deux entiers N (20≤N≤50) et M (N
<=M<=100) puis d’afficher tous les nombres compris entre N et M qui sont autonombres. Un
autonombre X est un entier positif qui ne peut pas s’écrire sous la forme d’un entier Y ajouté à
la somme des chiffres de Y.
Exemples :
- 24 n’est pas un autonombre puisqu’il est égal à l’entier 21 ajouté à la somme de ses chiffres
(24 = 21 + (2 + 1)).
- 53 est un autonombre puisqu’il ne peut pas s’écrire à partir d’un autre nombre ajouté à la
somme de ses chiffres
Procédure saisir(@x :entier, a,b :entier
Début
Répéter
LIRE(x)
Jusqu’à a<= x <= b
fin
Fonction som_chif(n : entier):entier
Début
S0
tantque n 0 faire:
s s+nMOD10
nn DIV10
retourner s
fonction autonombre(x : entier): booléen
debut
y x-1
s y + som_chif(y)
tantque s x te y >=x DIV 2:
y y-1
s y+som_chif(y)
retourner s x
procédure affiche( N,M : entier)
début
pour i de N à M faire
si autonombre (i) alors
ecrire (i)
finsi
finpr
fin
FATEN BEN ALI
1
Exercice 2
La suite de Héron Alexandrie est une suite permettant de trouver une valeur approchée de la
racine carrée d'un réel positif x. Elle est définie par :
𝑈0 = 𝑝 p est le plus grand entier qui vérifie 𝑝2 ≤ x
{ 1 𝑥
𝑈𝑛 = (𝑈𝑛−1 + ) 𝑛>0
2 𝑈𝑛−1
Le dernier terme 𝑼𝒏 qui vérifie |𝑼𝒏 − 𝑼𝒏−𝟏| ≤ 𝒆𝒑𝒔𝒊𝒍𝒐𝒏 est une estimation à epsilon près de
√𝒙
Exemple : Si x = 29 alors p = 5, car le plus grand entier vérifiant p²= x est 5 (5² = 25 ≤ 29).
Selon la définition de la suite U, le calcul de la valeur approchée de √29 à 10-5 près est présenté
dans le Tableau suivant:
n=1 n=2 n=3 n=4
𝑼𝒏−𝟏 5 5,4 5,385185185185185 5,385161807173060
𝑼𝒏 5,4 5,385185185185185 5,385161807173060 5,385164807134505
|𝑼𝒏 − 𝑼𝒏−𝟏 | 0,4 0,014814814814815 0,000020378012124 0,000000000038555
D'où, pour x = 29. la valeur approchée de √𝑥 est égale 5,385164807134505.
On se propose d’écrire un algorithme permettant de créer et de remplir un tableau
d'enregistrements nommé RC par une valeur approchée à 10-5 près de la racine carrée des n (0<
n <=100) entiers contenu dans un tableau X
Chaque enregistrement est formé par les champs suivants
• Ent : entier
• Racine :Une valeur approchée de la racine carrée de Ent à 10-5 près.
1- chercher la racine carrée d’un entier x
1-1 chercher U0
Fonction u_init ( x : réel ) : entier
Début
P0
Tantque P*P <= x faire
PP+1
Fin Tq
Retourner P – 1
Fin
1-2 calculer Un
FATEN BEN ALI
2
Fonction suite ( x :réel ) : réel
Début
Uanc u-init(x)
Uact (Uanc + x / Uanc)/2
Tantque abs(Uact -Uanc)> 0.00001 Faire
Uanc Uact
Uact (Uanc + x / Uanc)/2
finTQ
retourner Uact
2- remplir un tableau X par n entiers
2-1 saisir n (0< n <=100)
Procedure saisir(@n :entier)
début
répéter
lire(n)
jusqu’à 0< n <=100
fin
2-2 remplir X
Procedure remplir ( @X :TAB , n :entier)
Début
Pour i de 0 à n-1 faire
Répéter
Lire (X[i])
Jusqu’à X[i] > 0
Finpr
fin
3- remplir un tableau RC d’enregistrement ( Ent, Racine)
Suite_carrée = enregistrement
Ent : réel
Racine : réel
finEregistrement
TAB = tableau de 100 réels
RAC = tableau de 100 Suite_carrée
Procedure remplir_RC ( @RC : RAC, X : TAB , n :entier)
début
Pour i de 0 à n-1 faire
RC[i].Ent X[i]
RC[i].Racine suite(X[i])
FinPr
Fin
FATEN BEN ALI
3
Exercice 3
Pour déterminer le PGCD de plusieurs nombres, il suffit d'écrire leurs décompositions en
facteurs premiers, puis calculer le produit de tous les facteurs premiers communs à ces nombres
où chacun d'eux n'est pris qu'une seule fois avec son exposant le plus petit.
La décomposition d'un entier en produit de facteurs premiers, consiste à écrire cet entier sous
la forme d'un produit de ces diviseurs premiers.
Par exemple, la décomposition en facteurs premiers des trois entiers N1=924, N2=560 et N3 =
1400 donne :
N1 = 924 = 2x2x3x7x11=2²x3x7x11
N2 = 560 =2×2x2x2x5x7 = 24x5x7
N3 = 1400=2x2x2x5x5x7=23x5²x7
Donc le PGCD de N1, N2 et N3 est égal à 2² x 7 = 28
En effet, Les facteurs premiers communs sont : 2 et 7
L'exposant le plus petit pour le facteur premier 2 est 2 (2², 24 et 23) .
L'exposant le plus petit pour le facteur premier 7 est 1
Pour un nombre N, on dispose d'une procédure K_facteurs(N, T, K) qui permet de générer un
tableau T de K enregistrements représentant les K facteurs premiers du nombre N où chaque
enregistrement est composé des deux champs suivants :
• Fact : Un facteur premier de N.
• Expo: L'exposant du facteur premier.
Exemple :
Pour N = 1400, la décomposition en facteurs premiers de N est 23× 5² x 71
Donc le tableau T contiendra les enregistrements suivants :
K_facteurs ( 1400,T,K)
0 1 2
2 3 5 2 7 1
Travail demandé :
1) Déclarer un type pour le tableau T ainsi que tous les types nécessaires à sa déclaration,
sachant que K est inférieur ou égal à 50.
facteurs = enregistrement
Fact :entier
Expo : entier
FinEnregistrement
TAB = tableau de 50 facteurs
2) En utilisant la procédure K_facteurs, écrire un algorithme d'une fonction PGCD(N1, N2,
N3) qui permet de calculer le PGCD des trois entiers N1, N2 et N3.
NB : on n'est pas appelé à développer la procédure K _facteurs.
FATEN BEN ALI
4
1- décomposer les facteurs premiers de N1
2- décomposer les facteurs premiers de N2
3- décomposer les facteurs premiers de N3
4- les facteurs communs (avec leurs exposants) entre N1, N2, N3
5- chercher le plus petit exposant d’un facteur premier en commun
6- caluler le PGCD
Fonction existe (x : entier, T : TAB, n :entier)
Début
i0
tantque i < n et x T[i].Fact faire
ii
finTq
retourner i < n
fin
procedure commun (A : TAB, na : entier, B : TAB, nb :entier, @ C : TAB, @nc :entier)
Début
nc 0
Pour i de 0 à na faire
Si existe(A[i].Fact, B,nb) alors
C[nc].Fact A[i].Fact
C[nc].Expo min(A[i].Expo,B[i].Expo)
FINSI
finPr
Fin
Fonction PGCD (N1,N2,N3 : entier ) : entier
Début
K _facteurs(N1,T1,K1)
K _facteurs(N2,T2,K2)
K _facteurs(N3,T3,K3)
commun (T1,K1, T2,K2,C,nc)
commun (C,nc, T3,K3,Res,nr)
S0
Pour i de 0 à nr faire
S S + puissance(Res[i].Fact,Res[i].Expo)
FinPr
Retourner S
fin
les fonctions min et puissance sont à définir
FATEN BEN ALI
5
