Université Bordeaux 1 Licence Informatique 2006/2007
Dans tous les exercices qui suivent on demande d'écrire des algorithmes en utilisant le langage EXALGO défini en cours.
Exercice 1.1
On veut calculer pour un nombre réel
et un entier
positif
.
a- Ecrire deux versions de cet algorithme, la
première version utilisera une boucle tant que, la
deuxième utilisera une boucle pour.
b- Evaluez en fonction de et/ou de
le nombre de tour
de boucle nécessaire pour calculer
avec chacun de vos algorithmes.
On veut maintenant calculer
.
c- Ecrire un algorithme somme_puissances
qui utilise
l'algorithme puissance
. Evaluez en fonction de et/ou de
le
nombre de tour de boucle nécessaire pour calculer
.
d- Ecrire une deuxième version de l'algorithme permettant de calculer
en cherchant cette fois-ci à optimiser le nombre de tour de boucle.
Exercice 1.2
Soientun entier positif et
un entier strictement positif. Effectuer la division euclidienne (division entière) de
par
, c'est déterminer l'unique couple
de deux entiers (appelés quotient et reste) tel que
avec
.
a- Ecrire un algorithme qui, étant donnés deux entiers
et
, calcule le quotient et le reste de la division entière
de
par
par soustractions successives. Faire tourner votre
algorithme en prenant comme paramètres
les couples
,
et
,
.
b- Quel le nombre de tours de boucle effectués ?
Dans le pire des cas, par quelle valeur est-il borné ?
c- Réécrire l'algorithme à l'aide d'une boucle répéter jusqu'à
.
Est-il toujours valide pour tout couple
de données ?
d- Déduire de ce programme deux algorithmes Modulo
et
QuotientEntier
qui calculent respectivement le reste et le
quotient de la division entière de 2 entiers.
Exercice 1.3
a- par l'algorithme d'Euclide :
Le PGCD deEcrire l'algorithme PGCD en utilisant l'algorithme Modulo. Que se passe-t-il siet
est égal à
si ce dernier divise
, sinon le PGCD de
et
est égal au PGCD de
et de
(où
représente le reste de la division euclidienne de
par
).
b- par soustraction :
SiEcrire l'algorithme correspondant en utilisant une boucle, alors PGCD :=
, sinon on recommence avec le couple formé par la différence entre le plus grand et le plus petit, et le plus petit.
tant que
. Donner
une majoration du nombre de tests de comparaison.
Exercice 1.4
On rappelle que la somme des premiers impairs est égale au
carré
de
.
Ecrire à l'aide d'une boucle tant que
et exclusivement de
l'opération d'addition une fonction calculant la racine carrée
entière par défaut d'un nombre entier positif donné;
calculer le nombre d'additions et de comparaisons à effectuer.
Même question avec une boucle répéter...jusqu'à
.
Comparer les deux versions.