Durée : 2 h

1- OBJECTIFS

• Savoir concevoir de façon intuitive de petits algorithmes (hors tableaux)
• Connaître quelques algorithmes élémentaires solutionnant des problèmes classiques
• Savoir programmer en JAva de tels algorithmes
  

• Consignes générales :
• Recommandation : concevoir d'abord les algorithmes en pseudo-langage, en ne s'attachant qu'à la rigueur sémantique, avant de les exprimer en Java
• On s'interdit l'emploi des méthodes des bibliothèques Java qui solutionneraient d'emblée le problème posé !
• Il est attendu des solutions itératives et non récursives
• Il est attendu des solutions sans tableau
• Le travail demandé doit être terminé, en séance ou hors séance
• Le niveau de difficulté de chaque exercice (algorithme ou/et programmation) est spécifié par un nombre d'étoiles :
  
• *  facile
• **  peu difficile
• ***  assez difficile
• ****  difficile ou assez long à réaliser
  

Ecrire en Java une méthode calculant n! pour n entier naturel donné :
• paramètre : un entier naturel n
• valeur de retour : n!
  

L'algorithme de détermination du pgcd (plus grand commun diviseur) de deux entiers naturels est décrit dans les Eléments d'Euclide (300 av J.-C. environ), bien qu'il soit peut-être encore antérieur. Il est basé sur le théorème suivant :

Quel que soir l'entier a positif ou nul :

pgcd(a, 0) = a
pgcd(a, b) = pgcd(b, a modulo b),  quel que soit l'entier positif b

Dérouler l'algorithme sur les exemples suivants : pgcd(26, 12), pgcd(12, 26), pgcd(7, 11).

Ecrire en Java une méthode calculant le plus grand commun diviseur de deux entiers naturels avec la méthode d'Euclide :
• paramètre : deux entiers naturels a et b
  
• valeur de retour :  pgcd(a,b)
  

Ecrire en Java une méthode calculant la racine cubique d'un nombre x sachant que, si alpha est une approximation de la racine cubique de x non nul, alors (2*alpha + x/alpha²)/3 est une approximation meilleure  :

• paramètre : un réel x
  
• valeur de retour : la racine cubique de x
• contrainte de réalisation : arrêter l'algorithme quand l'écart relatif entre deux approximations successives devient négligeable (i.e. inférieur à une constante donnée)
  

Fibonacci fut un grand mathématicien italien des années 1200. Il eut notamment à résoudre un problème à finalité économique : celui de la productivité d'un élevage de lapins. Les données sont les suivantes :

Un couple de lapins devient rapidement adulte et est capable de donner naissance à un nouveau couple de lapins au bout de 2 mois, puis un autre (couple) chaque mois. Chacun des nouveaus couples de lapins suit à son tour cette règle. Combien y aura-t-il de couples de lapins au bout d'un an ?


Trouver la relation de récurrence qui exprime l'effectif de couples au mois n en fonction des effectifs aux mois précédents. Puis écrire en Java une méthode implantant cette récurrence et calculant l'effectif au bout du nombre de mois spécifié par l'utilisateur :

• paramètre : le nombre n de mois
• valeur de retour : fibonacci(n)

Un nombre parfait est un entier naturel strictement supérieur à 1 égal à la somme de ses diviseurs autres que lui-même. Par exemple 6 (=1+2+3), 28, 496 et 8128 sont quatre premiers nombres parfaits (en fait les quatre seuls inférieurs à 10 000 000). A titre culturel :

• on ne connaît que 44 nombres parfaits (donnée 2006) ; les 4 premiers sont connus depuis l'antiquité ; le 44ième est un entier de 77 chiffres
  
• on ne sait pas s'il existe une infinité de nombres parfaits
  
• on conjecture qu'il n'existe aucun nombre parfait impair
  

Ecrire  en Java une méthode déterminant le premier nombre parfait, s'il existe, d'une plage donnée :

• paramètre : deux entiers naturels i et j, i étant supposé au plus égal à j
• valeur de retour : le premier nombre parfait, s'il existe, du segment [i, j], ou 0 sinon

Ecrire en Java une méthode faisant appel à la méthode précédente et affichant tous les nombres parfaits d'une plage donnée :

• paramètre : deux entiers naturels i et j, i étant supposé au plus égal à j
• valeur de retour : aucune
• comportement : affiche tous les nombres parfaits du segment [i, j], s'il y en a.

Ecrire en Java une méthode calculant sin(x) à partir de son développement limité au voisinage de 0 :
sin(x) = x - x³/3! + x⁵/5! + ... + (-1)ⁿx⁽²ⁿ⁺¹⁾/(2n+1)! + ...

• paramètre : un réel x proche de 0
  
• valeur de retour : la valeur de sin(x)
• contraintes de réalisation :
• pas d'utilisation de tableau ! (car inutile !)
• le développement sera calculé jusqu'à ce que la différence relative entre deux termes successifs devienne négligeable (i.e. inférieure à une constante donnée)
• afin de minimier le nombre de multiplications, les termes du développement seront calculés de proche en proche (i.e. le terme de rang n sera calculé à partir du terme de rand n-1)

Ecrire en Java une méthode convertissant un entier naturel octal en décimal :

• paramètre : un entier naturel n codé en octal
• valeur de retour : la valeur décimale de n
• contrainte de réalisation :
  
• pas d'utilisation de tableau ! (car inutile !)
• en supposant que n comporte k chiffres (la détermination de k est inutile ! ), les différents chiffres de n seront déterminés par k divisions successives par 10 et non par k divisions successives par des puissances consécutives de 10
• afin de minimiser le nombre d'opérations, les puissances de 10 nécessaires au calcul de la valeur décimale seront calculées de proche en proche (i.e. 10^k sera calculé à partir de la valeur de 10^k-1 calculée à l'étape précédente)

Cet exercice généralise le précédent.
Ecrire en Java une méthode convertissant un entier naturel d'une base B1 dans une base B2, chaque base étant à valeur dans [2, 10] :

• trois paramètres : un entier naturel n écrit dans une base B1, la valeur de la base B1, la valeur de la base B2
• valeur de retour : la valeur de n dans la base B2
• contrainte de réalisation : même nature de contraintes que dans l'exercice précédent.