Exercice 11 - Webs

Professeur: Mr Baâzaoui. A | |Lycée Secondaire Ibn El Jazzar-Kairouan | | |Classe : 4ème année SI 1 | | | |Matière : Algorithmique et Programmation |
|Correction du Série N°02 | | |
Exercice 11 |[pi|[pic]=Empilement |Dépileme|
|c] | |nt |
|[pi|[pic] |[pic] |
|c] | | |
1°) x=2, n=8 et x =2 et n = 11 |[pi|[pic]=Empilement |Dépileme|
|c] | |nt |
|- |- |- |
|- |- |- |
|- |- |- |
|[pi|[pic] |[pic] |
|c] | | | 2°)
* Analyse
> Résultat : puissance_rapide
> Traitement : la puissance_rapide est obtenue comme suit :
Cas particulier : on a deux cas :
Cas 1 : si (x=0) alors puissance_rapide (
0
Cas 2 : si (n=0) alors puissance_rapide (
1
Cas général : on a deux cas :
- si [pic] est pair le calcul de [pic]se ramène au calcul de [pic]que
l'on multiplie par lui même
- si [pic] est impair[pic], on calcule [pic]que l'on multiplie par lui
même, puis on multiplie le résultat par [pic]
* Algorithme
0) Fonction puissance_rapide (x : réel ; n : entier) : réel
1) Si (x = 0) alors
Puissance_rapide ( 0
Sinon si (n = 0) alors
Puissance_rapide ( 1
Sinon
R ( puissance_rapide (x, n div 2)
Fin si
Fin si
2) Si n mod 2 = 0 alors
Puissance_rapide ( R*R
Sinon
Puissance_rapide ( R*R*x
Fin si
3) Fin puissance_rapide
. Tableau de déclaration des objets locaux
|Objets |Types/Natures|Rôles |
|R |Réel |Sauvegarder le résultat|
| | |de [pic] |
3°) x=2, n =8
|[p|[pic] | |[pic] |
|ic| | | |
|] | | | |
|- |- | |- |
|- |- | |- |
|- |- | |- |
|- |- | |- |
|[p|[pic] | |[pic] |
|ic| | | |
|] | | | |
x=2, n=11
|[p|[pic] | |[pic] |
|ic| | | |
|] | | | |
|[p|[pic] | |[pic] |
|ic| | | |
|] | | | |
Exercice 13 * Analyse
> Résultat : PGCD
> Traitement : le calcul du PGCD par la méthode d'Euclide est obtenu
comme suit :
Cas particulier (condition d'arrêt) : Si (A mod B =
0) alors PGCD ( B
Cas général (appel récursif): Sinon la fonction
appelle elle-même avec les nouvelles valeurs B et
A
mod B. On a donc PGCD ( PGCD (B, A mod B)
* Algorithme
0) Début fonction PGCD (A, B : entier) : entier
1) Si (A mod B = 0) alors
PGCD ( B
Sinon
PGCD ( PGCD (B, A mod B)
Fin si
2) Fin PGCD Exercice 14 * Analyse
> Résultat : PGCD
> Traitement : le calcul du PGCD par la méthode de différence est
obtenu comme suit :
Cas particulier (condition d'arrêt) : Si (A = B)
alors PGCD ( A
Cas général (appel récursif): Sinon on
a deux cas :
Cas1 : Si A(B alors la fonction appelle
elle même avec les nouvelles valeurs A-B et B
C'est-à-dire PGCD (
PGCD (A-B, B)
Cas2 : Si B (A alors la fonction appelle
elle-même avec les nouvelles valeurs A et B-A
C'est-à-dire PGCD ( PGCD (A,
B-A)
* Algorithme
0) Début fonction PGCD (A, B : entier) : entier
1) Si (A= B) alors
PGCD ( A
Sinon Si (A(B) alors
PGCD ( PGCD (A-B, B)
Sinon
PGCD ( PGCD (A, B-A)
Fin si
2) Fin PGCD Exercice 15 * Analyse
> Résultat : PPCM
> Traitement : le calcul du PPCM est obtenu comme suit :
Cas particulier (condition d'arrêt) : Si (A mod B
= 0) alors PPCM ( A
Cas général (appel récursif): Sinon la fonction
appelle elle même avec les nouvelles valeurs
2*A et B puis 3*A et B ensuite 4*A et B etc .... Jusqu'à A mod B = 0. Donc
dans le programme principal il faut sauvegarder la valeur initiale de A
avant d'appeler la fonction PPCM sinon elle sera perdue (i ( A)
Dans le cas général l'appel de la fonction PPCM sera comme suit : PPCM (
PPCM (A+i, B)
* Algorithme
0) Début fonction PPCM (A, B : entier) : entier
1) Si (A mod B =0) Alors
PPCM ( A
Sinon
PPCM ( PPCM (A+i, B)
Fin si
2) Fin PPCM Exercice 16 * Analyse
> Résultat : Fibonacci
> Traitement : le calcul du nième terme de la suite de Fibonacci est
obtenu comme suit :
Cas particulier (condition d'arrêt) : on deux cas
Cas 1 : Si (n=0) alors
Fibonacci ( 0
Cas 2 : Si (n=1) alors
Fibonacci ( 1
Cas général (appel récursif) : sinon la fonction
appelle elle-même 2 fois avec les valeurs n-1 et n-2 d'où l'appel
récursif suivant : Fibonacci ( Fibonacci (n-1) + Fibonacci (n-2)
* Algorithme
0) Début fonction Fibonacci (n : octet) : mot
1) Si (n=0) alors
Fibonacci ( 0
Sinon si (n=1) alors
Fibonacci ( 1
Sinon
Fibonacci ( Fibonacci (n-1) + Fibonacci (n-2)
Fin si
2) Fin Fibonacci
Exécution à la main pour n=4
|n |Appels = empilement |Fibonacci |
| | |(n) |
|4 |Fibonacci(3) + |3 |
|3 |Fibonacci (2) |2 |
|2 |Fibonacci (2) + |1 |
|1 |Fibonacci (1) |1 |
|0 |Fibonacci (1) + |0 |
| |Fibonacci (0) | |
| |- | |
| |- | |
Exercice 17 * Analyse
> Résultat : Combinaison
> Traitement : le calcul de la combinaison de p éléments parmi n
éléments est obtenu comme suit :
Cas particulier (condition d'arrêt) : on a trois
cas :
Cas 1 : Si (p ( n) alors
Combinaison ( 0
Cas 2 : Si (p=n) ou (p=0) alors
Combinaison ( 1
Cas 3 : Si (p=1) alors
Combinaison ( n Cas général (appel récursif): Sinon la fonction
appelle elle même avec les nouvelles valeurs
p et n-1 puis avec p-1 et n-1 Dans le cas général l'appel de la fonction
Combinaison sera comme suit :
Combinaison ( Combinaison
(p, n-1) + combinaison (p-1, n-1)
* Algorithme
0) Début fonction Combinaison (p, n : entier) : entier long
1) Si (p ( n) alors
Combinaison ( 0
Sinon si (p=n) ou (p=0) alors
Combinaison ( 1
Sinon si (p=1) alors
Combinaison ( n
Sinon
Combinaison ( combinaison (p, n-1)
+ combinaison (p-1, n-1)
Fin si
2) Fin combinaison
Exécution à la main pour n=4 et p = 2
|n |p |Appels |Combinaison |
| | | |(n, p) |
|4 |2 |Combinaison (3, 2) + |6 |
|3 |2 |combinaison (3, 1) |3 |
|3 |1 |Combinaison (2, 2) + |3 |
|2 |2 |combinaison (2, 1) |1 |
|2 |1 |Combinaison (2, 1) + |2 |
|2 |0 |combinaison (2, 0) |1 |
|1 |1 |- |1 |
|1 |0 |Combinaison (1, 1) + |1 |
| | |combinaison (1, 0) | |
| | |- | |
| | |- | |
| | |- | |