TD 1 : Introduction à l'Algorithmique




Les méthodes des différents exercices doivent être écrites dans les classes fournies en annexe (télécharger ces classes) . Donnez pour chaque méthode son en-tête et sa complexité, et accompagnez chaque itération de son invariant.

EXERCICE 1

 Soient x un réel et n un entier strictement positif. On peut calculer une approximation de sin(x) et de cos(x) en utilisant les formules suivantes : On dit que sin(x) (ou cos(x)) est calculé à l'ordre n si la somme correspondante contient n termes.

En vous limitant aux quatres opérateurs arithmétiques +, -, * et /, donnez le corps des méthodes sin et cos de la classe Trigo telles que, pour tout réel x et pour tout entier n strictement positif, Trigo.sin(x,n) et Trigo.cos(x,n) retournent respectivement les valeurs sin(x) et cos(x) à l'ordre n.

Pour calculer efficacement sin(x) (ou cos(x)) à un ordre n élevé, il ne faut pas recalculer les différentes factorielles, mais plutôt modifier un terme courant.

EXERCICE 2

 Soit n un entier, n > 0. Un entier k, k > 0, est un diviseur de n s'il existe un entier m tel que n = k m. Un entier qui n'admet que 1 et lui-même comme diviseurs est un nombre premier.

Ecrivez la méthode diviseurs de la classe Entier telle que diviseurs(n) affiche à l'écran tous les diviseurs de n. Par exemple, l'évaluation de diviseurs(60) affiche : 

     Les diviseurs de 60 sont : 1 2 3 4 5 6 10 12 15 20 30 60
Soient x et y deux variables de type int. L'expression x / y retourne le reste de la division entière de x par y. Pour calculer les diviseurs de n, on essaie de diviser n par tous les entiers compris entre 1 et n.

EXERCICE 3

 Tout nombre entier n, n > 1, admet une décomposition unique en facteurs premiers. Un algorithme simple pour trouver cette décomposition peut être décrit de la façon suivante : soit p1, p2,..., pk la suite croissante des facteurs premiers de n. Supposons que l'on connaisse les j premiers facteurs premiers de n et le nombre m tel que n = p1 × p2 × ... × pj × m. Pour trouver le (j+1)-ième facteur premier de n, on teste successivement pour tous les entiers d, pj £ d £ m, si d divise m. Le premier entier trouvé est pj+1.

Ecrivez la méthode decomposition telle que decomposition(n) affiche à l'écran la décomposition en facteurs premiers de n. Si n est premier, decomposition n'affiche que n. Par exemple, decomposition(60) affiche : 

     Les facteurs premiers de 60 sont : 2 2 3 5
La suite croissante p1, p2,..., pk des facteurs premiers de n n'est pas strictement croissante car on peut avoir pi = pi+1 pour certains i, 1 £ i < k (par exemple, 60 = 2 × 2 × 3 × 5). Inspirez-vous de l'exercice précédent.

EXERCICE 4

 On dit d'un entier positif ou nul n qu'il est un palindrome si on peut le lire indifféremment de gauche à droite, ou de droite à gauche. Par exemple, 3, 22, 121, 123321 et 4097904 sont des entiers palindromes.

En vous limitant uniquement aux quatres opérateurs arithmétiques +, *, / et %, écrivez la méthode palindrome de la classe Entier telle que palindrome(n) retourne la valeur true si n est un palindrome, false sinon.

Si on appelle C(m) le nombre de chiffres de m et R(m) le ``renversé'' d'un entier m, construisez itérativement deux entiers x et y tels que n = x × 10C(y) + R(y). Au début de l'itération, x = n et y = 0, à la fin de l'itération x = 0 et y = R(n). Eliminez tout de suite les multiples de 10 qui ne peuvent pas être des palindromes.

EXERCICE 5

 On dit d'un entier positif ou nul n qu'il est un mirroir s'il est constitué d'un entier et de son ``renversé'' juxtaposés. Par exemple, 22, 1221 et 67055076 sont des entiers mirroirs, mais 3, 121 et 4097904 n'en sont pas.

En vous limitant uniquement aux quatres opérateurs arithmétiques +, *, / et %, écrivez la méthode mirroir de la classe Entier telle que mirroir(n) retourne la valeur true si n est un mirroir, false sinon.

Inspirez-vous largement de l'exercice précédent, en modifiant le test d'arrêt de la boucle qui calcule x et y, après avoir remarqué que x et y sont successivement tels que x > y, (peut-être) x = y et x < y.

EXERCICE 6

 Voilà une méthode simple pour calculer les n premiers nombres premiers : supposons que l'on connaisse les k premiers nombres premiers, p1, p2,..., pk. Pour trouver le suivant, on teste successivement pour tout les entiers m, m > pk, s'il existe i tel que pi divise m. Si aucun des nombres p1, p2,..., pk ne divise m, alors pk+1 = m. On s'arrête quand k = n.

Expliquez en quoi le fait qu'il existe une infinité de nombres premiers garantit que cet cet algorithme termine. Ecrivez la méthode premiers de la classe Entier telle que premiers(n) affiche à l'écran les n premiers nombres premiers. Par exemple, l'evaluation de premiers(10) affiche : 

     les 10 premiers nombres premiers sont  2 3 5 7 11 13 17 19 23 29
Utilisez un tableau premiers de taille n pour stocker les nombres premiers trouvés. Initialisez la première case du tableau avec la valeur 2 (premiers[0] = 2). Enfin, ne faites pas de calcul inutile en utilisant le fait qu'un nombre pair supérieur à 2 n'est pas premier.

EXERCICE 7

 Une suite finie de n entiers e1, e2,..., en est croissante (respectivement décroissante) si, pour tout i, 1 £ i < n, on a ei £ ei+1 (respectivement ei ³ ei+1).

Ecrivez la méthode croissante de la classe Suite telle que s.croissante() retourne true si la suite s est croissante, false sinon.

Aucune difficulté.

EXERCICE 8

 Une monotonie d'une suite finie S de n entiers e1, e2,..., en est une sous-suite de S monotone de longueur maximale. Par exemple, la suite 1 3 3 2 5 8 9 5 2 3 7 contient les 5 monotonies 1 3 3, 3 3 2, 2 5 8 9, 9 5 2 et 2 3 7.

Quel est le nombre minimum et maximum de monotonies que peut contenir une suite de longueur n ? Ecrivez la méthode monotonies de la classe Suite telle que s.monotonies() retourne le nombre de monotonies contenues dans s.

On peut compter les monotonies en comptant les changemements croissant/décroissant dans la suite.

EXERCICE 9

 Une monotonie croissante d'une suite finie S de n entiers e1, e2,..., en est une sous-suite de S croissante. On s'intéresse à la longueur d'une plus longue monotonie croissante de S. Par exemple, la longueur d'une plus longue monotonie croissante de la suite 1 3 3 2 5 8 9 5 2 3 7 est 4 qui est la longueur de la monotonie croissante 2 5 8 9.

Ecrivez la méthode longueur de la classe Suite telle que s.longueur() retourne la longueur d'une plus longue monotonie croissante de s.

Deux invariants (et donc deux itérations) sont possibles pour résoudre ce problème.

EXERCICE 10

 Deux suites d'entiers sont semblables si elles sont identiques aux répétions consécutives près. Par exemple, les suites 1 1 5 5 5 2 3 3 5 et 1 5 5 2 2 2 3 5 5 sont semblables, alors que les suites 1 5 2 2 3 5 5 et 1 1 5 3 2 2 5 ne le sont pas.

Ecrivez la méthode semblable de la classe Suite telle que s1.semblables(s2) retourne true si les suite s1 et s2 sont semblables, false sinon.

Ecrivez et utilisez la méthode privée suivantDifferent telle que s.suivantDifferent() avance le curseur de s soit en fin de suite, soit sur le premier élément différent de la valeur courante.

This document was translated from LATEX by HEVEA.