Université Mohammed Premier Matière : AAC
ENSA Al Hoceima Filière: GI1
Département de Mathématiques Année Universitaire: 2015/2016
et Informatique Prof: E. W. DADI
Correction TD 1
Exercice 1
Pour chacun des problèmes suivants, élaborer un algorithme itératif et récursif qui le résout :
1. Le nombre de chiffre d’un entier a.
Algorithme Version itérative
Fonction NbChiffres (a :entier) : entier
Var compteur :entier ;
Début
compteur :=1;
Tant que (a>9) Faire
a :=a/10 ;
compteur := compteur +1 ;
FinTQ
Retourner(compteur) ;
Fin
Algorithme Version récursive
Fonction NbChiffres(a :entier) :entier
Début
Si(a<10) alors
Retourner 1;
Sinon
Retourner NbChiffres(a/10)+1 ;
FinSi
Fin
2. La somme des chiffres d’un entier a.
Fonction SChiffres(a :entier) :entier Fonction SChiffres(a :entier) :entier
Var S, t : entier. Var S : entier.
Début Début
S:=0; S:=0;
Tantque(a>9) Faire Tantque(a>9) Faire
t:=(a/10); S :=S+(a%10) ;
S :=S+(a-t*10) ; a:=a/10;
a:=t; FinTq
FinTq Retourner(S+a);
Retourner(S+a)
Algorithme Version récursive Algorithme Version récursive
Fonction SChiffres(a :entier) :entier Fonction SChiffres(a :entier) :entier
Var t :entier ; Début
Début Si(a<10) alors
Si(a<10) alors Retourner a;
Retourner a; Sinon
Sinon Retourner
t :=a/10 ; NbChiffres(a/10)+(a%10) ;
Retourner NbChiffres(t)+(a-t*10) ; FinSi
FinSi Fin
Fin
3. Un algorithme qui test si un nombre a est premier (Comme algorithme de test de
primalité utilisez le suivant : Vérifier si a est divisible par l'un des entiers compris
entre 2 et ).
Algorithme Version itérative
Fonction Primalite (a :entier) : booléen
Var i : entier, test : booléen, r : entier ;
Début
test := vrai;
...Si(a%i=0) alors Retourner (faux) ;
Sinon
i :=3 ;
r := ; // on calcule le racine qu’une seule fois.
TantQue (i<=r ) Faire
Si(a%i=0) alors
Retourner faux ;
FinSi
i=i+ 2;
FinTq
Retourner(test) ;
FinSi
Fin
Algorithme Version récursive
Fonction Primalite (a :entier, i entier) : booléen
Var i :entier, test : booléen;
Début
Si(i<a) alors
Si(a%i=0)
Retourner faux ;
Sinon
Retourner Primalite (a, i+1) ;
FinSi
Sinon
Retourner vrai ;
FinS
Fin
4. Un algorithme qui calcule le PGCD de deux entiers positifs a et b en utilisant
l'algorithme d'Euclide.
Algorithme Version itérative
Fonction PGCD (a ,b :entier) : entier
Var i : entier, r: entier ;
Début
Tantque(r :=(a%b)≠0) Faire
a :=b ;
b :=r ;
FinTq
Retourner(b) ;
Fin
Algorithme Version récursive
Fonction PGCD (a ,b :entier) : entier
Var r: entier ;
Début
r :=a%b ;
Si(r=0)
Retourner b ;
Sinon
Retourner PGCD (b,r) ;
FinSi
Fin
Exercice 2
Fonction MinT(T :tableau, n entier)
Var min, pos : entiers ;
Début
pos :=1 ;
Pour i allant de 2 à n Faire
Si(T[pos]<T[i] ) alors
pos :=i ;
FinSi
FinPour
Retourner (pos) ;
Fin
Fonction Insertion(T : tableau, x entier, pos entier, n entier)
Début
i : = n+1;
Tantque(i>pos) Faire
T[i] := T[i-1];
i-- ;
FinTq
T[i] := x ;
Fin
Fonction Suppression(T : tableau, pos entier, n entier)
Début
i :=n ;
Pour i allant de pos à n faire
T[i] := T[i+1];
FinPour
Fin
Fonction Ex2(T :tableau, x entier, n entier)
Var imin : Entier.
Debut
imin :=MinT(T, n) ;
Insertion(T, x, imin+1, n) ;
Suppression(T, imin+1, n) ;
Fin
Exercice 3
La suite est constante (Un=1/3) donc l’algorithme qui calcule le nieme terme de cette suite doit
être très simple :
Fonction U(n :entier)
Début
Retourner 1/3 ;
Fin
Exercice 4
Fonction Puissance(x réel, n entier) :réel
Var p : réel
Début
i :=n ;
Si (n=0) alors
Retourner 1 ;
Sinon
Si(n%2=0) alors
p=Puissance(x , n/2) ;
Retourner p*p ;
Sinon
Retourner x* Puissance(x, n-1) ;
FinSi
FinSi
