Université Bordeaux 1 Licence Informatique 2006/2007

Initiation à l'algorithmique
 
TD 1

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 $a^n$ pour un nombre réel $a$ et un entier positif $n$.
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 $a$ et/ou de $n$ le nombre de tour de boucle nécessaire pour calculer $a^n$ avec chacun de vos algorithmes.

On veut maintenant calculer $\sum\limits_{i=0}^{i=n} a^i$.
c- Ecrire un algorithme somme_puissances qui utilise l'algorithme puissance. Evaluez en fonction de $a$ et/ou de $n$ le nombre de tour de boucle nécessaire pour calculer $\sum\limits_{i=0}^{i=n} a^i$.
d- Ecrire une deuxième version de l'algorithme permettant de calculer $\sum\limits_{i=0}^{i=n} a^i$ en cherchant cette fois-ci à optimiser le nombre de tour de boucle.

Exercice 1.2

Division euclidienne

Soient $a$ un entier positif et $b$ un entier strictement positif. Effectuer la division euclidienne (division entière) de $a$ par $b$, c'est déterminer l'unique couple $(q,r)$ de deux entiers (appelés quotient et reste) tel que $a=b*q+r$ avec $0 \leq r < b$.

a- Ecrire un algorithme qui, étant donnés deux entiers $a \geq 0$ et $b > 0$, calcule le quotient et le reste de la division entière de $a$ par $b$ par soustractions successives. Faire tourner votre algorithme en prenant comme paramètres les couples $a=13$, $b=3$ et $a=2$, $b=7$.
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

Calcul du Plus Grand Commun Diviseur (PGCD) de deux entiers strictement positifs

a- par l'algorithme d'Euclide :

Le PGCD de $a$ et $b$ est égal à $b$ si ce dernier divise $a$, sinon le PGCD de $a$ et $b$ est égal au PGCD de $b$ et de $r$ (où $r$ représente le reste de la division euclidienne de $a$ par $b$).

Ecrire l'algorithme PGCD en utilisant l'algorithme Modulo. Que se passe-t-il si $a < b$ ?

b- par soustraction :

Si $a=b$, alors PGCD := $a$, sinon on recommence avec le couple formé par la différence entre le plus grand et le plus petit, et le plus petit.

Ecrire l'algorithme correspondant en utilisant une boucle tant que. Donner une majoration du nombre de tests de comparaison.

Exercice 1.4
On rappelle que la somme des $n$ premiers impairs est égale au carré de $n$.
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.