Exercice 2.1
On considère la fonction suivante :
fonction test (ref n:entier;val i:entier):vide; debut tant que i > 0 faire n = n + i; i = i-1; fintantque finQue valent
var n,i:entier test(3,5)
var n,i:entier n = 4 test(n,5)
var n,i:entier n = 4 i = 5 test(n,i);
Exercice 2.2
Ecrire les fonctions puissance
, Modulo
,
QuotientEntier
, PGCD
à partir des algorithmes décrit dans le TD1.
Exercice 2.3
Pour multiplier deux entiers X et Y, on détermine la suite :
Le produit XY est égal à la somme desa- Appliquer l'algorithme au produitpour lesquels
est impair.
Produit
appliquant cet
algorithme. Quel est le paramètre pertinent pour évaluer le temps
d'exécution ?
Exercice 2.4
Quelle est la plus petite valeur strictement positive de pour
laquelle un algorithme
dont le temps d'exécution est
s'exécute plus vite qu'un
algorithme pour lequel le temps d'exécution est
sur la même
machine ?
Soit (resp.
) la valeur maximum de
pour laquelle
on peut exécuter un certain algorithme réalisant
(resp.
) opérations en un temps
. De combien augmente
l'image de la fonction
(resp.
) lorsque l'on passe de
à
?
Exercice 2.5
Écrire une fonction qui teste si un entier est premier ou non.
Exercice 2.6
Écrire une fonction utilisant les précédentes permettant d'afficher le énième nombre premier.