|
Algorithmique et programmation : Immersion Java |
Ces deux séances d'immersion Java, programmées dans le cadre de la semaine logicielle, sont les deux premières séances du module Algorithmique et programmation, consacrées à la pratique de l'environnement de programmation en Java sous Linux et aux premiers éléments de programmation dans le style impératif. À la fin de la seconde séance, un test sera réalisé afin de déterminer des groupes de niveau pour la suite du module.
Le développement d'applications Java se fait sous Linux ; les machines dans les salles de cours disposent déjà des logiciels nécessaires, mais vous devez organiser un espace de travail dans votre répertoire personnel :
| linux% tar xf java.tar |
Vous disposez maintenant d'un répertoire java, et sous celui-ci, de deux répertoires src et classes
La première application consiste à afficher "Bonjour Java" à l'écran. Le programme de cette application se compose d'une classe Bonjour, faisant partie du paquet immersion.
|
Dans le répertoire java/src, créez le sous-répertoire immersion.
Ouvrez une fenêtre Emacs.
Sous Emacs, ouvrez un fichier ~/java/src/immersion/Bonjour.java.
|
Le squelette d'un programme Java apparaît sous Emacs. Remplacez les deux "?????" par immersion (nom du paquet) et par Bonjour (nom de la classe). C'est le programme Java minimal.
|
Compilez ce programme par la commande suivante, exécutée dans le répertoire où se trouve le fichier Bonjour.java :
| linux% javac -d ~/java/classes Bonjour.java |
L'exécution de cette commande (si aucune erreur n'est détectée) a pour effet de créer un fichier de classe, dont le nom est Bonjour.class, et de placer ce fichier dans le répertoire ~/java/classes/immersion.
Lancez cette application par la commande suivante :
| linux% java immersion.Bonjour |
Cette commande n'a aucun effet, ce qui est normal, puisque la fonction main ne comporte aucune instruction.
L'écriture d'un programme comporte généralement des erreurs, que le compilateur détecte en émettant des messages d'erreurs. Dans ce cas, la compilation ne produit pas de fichier de classe, il faut corriger les erreurs et recompiler tant qu'il y a des erreurs.
Ajoutez volontairement des erreurs au programme précédent, par exemple :
Des messages d'erreurs sont affichés par le compilateur et indiquent la position dans le programme où l'erreur a été détectée. Il est plus commode d'obtenir les messages d'erreurs sous Emacs. Au lieu de compiler dans un fenêtre terminal, il suffit de compiler sous Emacs, en sélectionnant l'item Compile ... du menu Tools d'Emacs, ou bien en tapant control-c control-c sous Emacs. La fenêtre qui contenait le programme est alors divisée en deux ; le programme reste affiché dans l'une alors que le résultat de la compilation, avec les messages d'erreurs éventuels, apparaissent dans l'autre. On peut alors se positionner dans le texte du programme, en tapant control-c control-n, sur la première erreur, puis sur les erreurs suivantes. On remonte aux erreurs précédentes en tapant en tapant control-c control-p ("n" pour next, "p" pour previous). Corrigez vos erreurs.
Le dialogue entre l'application et l'utilisateur, au moyen du clavier ou de l'écran, se fait toujours à l'aide de chaînes de caractères. Ajoutez une instruction d'impression d'une chaîne de caractères dans la fonction main :
public static void main(String[] args) {
System.out.println("Bonjour, Java");
}
|
Compilez à nouveau ce programme (commande javac) et exécutez à nouveau l'application (commande java) ; on peut rappeler des commandes précédemment exécutées avec la touche "flèche vers le haut" du clavier. On observe la sortie du programme : Bonjour, Java.
Inversement, l'utilisateur de l'application peut entrer une ou plusieurs chaînes de caractères lors du lancement, par exemple :
| linux% java immersion.Bonjour Salut Java |
public static void main(String[] args) {
String message = args[0] + ", " + args[1] + " !";
System.out.println( ... );
}
|
On observe maintenant la sortie du programme : Salut, Java !.
|
On notera que les chaînes de caractères ne sont pas des noms de variable.
Problème : Calculer la somme des n premiers entiers 1, 2, ..., n.
Ce problème dépend d'un paramètre, n. La résolution de ce problème, par un programme, se fait à l'aide d'une fonction, qui à n associe n*(n+1)/2.
Ouvrez sous Emacs, toujours dans le répertoire ~/java/src/immersion, un nouveau fichier Sommes.java et écrivez le programme suivant :
package immersion;
class Sommes {
static int sommerEntiers(int n) {
return n*(n+1)/2;
}
public static void main(String[] args) {
}
}
|
Compilez ce programme et exécutez l'application immersion.Sommes. Cette exécution n'a aucun effet, ce qui est normal, puisque sa fonction main ne comporte pour le moment aucune instruction.
Java dispose d'opérateurs arithmétiques : +, -, *, /. Ces opérateurs permettent de construire des expressions arithmétiques, par exemple n*(n+1)/2, à partir de constantes et de variables.
|
Une définition de fonction comporte :
|
Une fois définie, une fonction peut être utilisée plusieurs fois, en l'invoquant avec des arguments.
Problème : Calculer la somme des entiers de p à q.
On peut résoudre ce problème en utilisant la fonction sommerEntiers. Ajoutez, dans la classe Sommes, après sommerEntiers, la fonction suivante sommerEntiersDeÀ, qui prend en paramètres deux int, p et q :
static int sommerEntiersDeÀ(int p, int q) {
...
}
public static void main(String[] args) {
int s = Sommes.sommerEntiersDeÀ(3, 28);
System.out.println(s);
}
|
Une invocation de fonction comporte :
|
À l'intérieur d'une même classe, le nom de la classe et le "." ne sont pas nécessaires. Simplifiez la définition précédente.
Dans la fonction précédente, il serait plus correct de retourner 0 si p>q, ce qu'on teste au moyen d'une instruction conditionnelle :
L'instruction conditionnelle if se compose :
|
Complétez les fonctions suivantes :
static int sommerEntiersDeÀ(int p, int q) {
if (p <= q) {
return ...;
} else {
return ...;
}
}
public static void main(String[] args) {
...
}
|
|
L'utilisateur de l'application peut entrer une ou plusieurs valeurs numériques lors de son lancement, nécessairement sous forme de chaînes de caractères, par exemple :
| linux% java immersion.Sommes 123 456 |
public static void main(String[] args) {
int a = Integer.parseInt(args[0]);
int b = Integer.parseInt(args[1]);
int s = Sommes.sommerEntiersDeÀ( ... );
System.out.println("La sommes des entiers de " +
a + " à " + b + " est " + s);
}
|
Si l'utilisateur de l'application représente les entiers dans une base différente de 10, il faut préciser cette base dans l'expression de conversion. Par exemple, Integer.parseInt("100", 2) a pour valeur l'entier 4.
|
Si les chaînes de caractères entrées par l'utilisateur ne correspondent pas à des nombres entiers, un message d'erreur est affiché, et le programme est aussitôt terminé. Testez par exemple :
| linux% java immersion.Sommes 123.0 |
Enfin, si la fonction main utilise la variable args[0] et qu'aucune donnée n'est spécifiée au lancement de l'application, un autre message d'erreur est affiché, et le programme est aussitôt terminé. Testez :
| linux% java immersion.Sommes |
Problème : Calculer la somme des puissances k des n premiers entiers.
Ce problème doit être résolu par une fonction à deux paramètres, k et n. Alors que, pour chaque k, il existe une expression arithmétique dépendant de n qui fournit la solution du problème, il n'existe pas d'expression arithmétique dépendant de k et de n qui résolve le problème.
Il n'existe pas non plus d'opérateur d'exponentiation en Java.
On recourt à une instruction d'itération pour résoudre le problème posé et pour calculer une puissance.
Complétez la fonction suivante :
static int sommerPuissances(int k, int n) {
int somme = 0;
for (int i=1; i<=n; i++) {
somme = ... ;
}
return somme ;
}
static int puissance(int p, int k) {
int r = ...;
for (int i=1; i<=k; i++) {
r = ... ;
}
return ... ;
}
public static void main(String[] args) {
int a = ... ;
int b = ... ;
int s = Sommes.sommerPuissances( ... );
System.out.println("La sommes des puissanes " + a +
" des " + b + " premiers entiers est " + s);
}
}
|
L'instruction d'itération for se compose :
Le corps est exécuté un certain nombre de fois, chaque exécution étant appelée une itération. Le corps n'est exécuté que si la valeur de la condition d'exécution est true. À la fin de chaque itération, la transformation est exécutée. Si cette valeur de la condition est false, la boucle est terminée. |
Problème : Le nombre entier n est-il premier ?
Ce problème doit être résolu par une fonction à un paramètre entier, n et retournant un boolean. Appelons cette fonction estPremier. Une méthode simple consiste à calculer le reste de la division euclidienne de n par chacun des entiers de 2 à n ; dès qu'un reste nul est obtenu, la fonction doit retourner false ; sinon, elle doit retourner true.
L'opérateur calculant le reste de la division euclidienne est %.
Complétez la fonction suivante, dans un fichier premiers, toujours dans le répertoire ~/java/src/immersion :
package immersion;
class Premiers {
static boolean estPremier( ... ) {
...
}
}
|
|
|
Parmi les nombres suivants, lesquels ne sont pas premiers : 863 869 877 871 881 883 887 ?
Problème : Calculer la probabilité pour que deux individus d'un groupe de k personnes aient leur anniversaire un même jour (en supposant les dates de naissances réparties de façon uniforme).
Ce problème doit être résolu par une fonction à deux paramètres, k et n (le nombre de jours dans l'année terrestre, généralement 365) ; cette fonction doit retourner un nombre réel entre 0 et 1, représenté en mémoire comme un nombre flottant de type double.
Grâce à l'hypothèse de répartition uniforme, la probabilité qu'il n'y ait pas de coincidence de date est le quotient du nombre de fonctions injectives de [1, k] dans [1, n] sur le nombre total de fonctions : n(n-1)...(n-k+1)/nk.
|
Compte tenu de ces règles, complétez la fonction suivante :
package immersion;
class Anniversaires {
... ... probabilitéCoincidence( ... ) {
...
}
|
Problème : Calculer l'effectif minimal d'un groupe d'individus pour que la probabilité que deux individus aient leur anniversaire un même jour soit supérieure à p.
La solution de ce problème utilise la fonction précédente. Il faut ici calculer la probabilité de coincidence pour des valeurs croissantes de l'effectif, tant que cette probabilité est inférieure à p. On utilise l'instruction d'itération while.
| linux% java immersion.Anniversaires 0.5 365 |
Complétez la fonction suivante :
package immersion;
class Anniversaires {
// ...
... ... effectifMinimal( ... ) {
...
}
public static void main(String[] args) {
double p = Double.parseDouble(args[0]);
int jours = ...;
int effectif = Anniversaires.effectifMinimal(p, jours);
System.out.println( ... );
}
}
|
L'instruction d'itération while se compose :
|
Problème : Calculer le nombre minimum de jours que devrait avoir une année pour que la probabilité que deux individus parmi n aient leur anniversaire un même jour soit inférieure à p (par exemple, p = 0.01).
Complétez la fonction suivante :
package immersion;
class Anniversaires {
static ... annéeMinimaleSansCoincidence( ... ) {
...
}
}
|
Problème : Calculer une approximation de la racine carrée de x, pour x>0, grâce à la suite récurrente suivante :
y0 = 1 yn+1 = 1/2 (yn + x/yn)
Ce problème doit être résolu par une fonction, à un paramètre, x de type double, dont le type de retour est un double.
On utilisera comme condition d'arrêt de l'itération Math.abs(y*y-x) > 1e-15*x.
Programmez la solution de ce problème.
URL:
<http://cermics.enpc.fr/cours/AP/immersion.html>