ENPC - Programmation

ENPC - Programmation - Séance 1

Documentation

Le langage Java repose sur des bibliothèques de classes offertes en standard aux utilisateurs. Ainsi, par exemple, l'instruction System.out.println("Bonjour !") est un appel à la méthode println() avec comme argument la chaîne de caractères "Bonjour !" (de type String), sur le champ out de la classe System. Ces bibliothèques de classes sont organisées en paquets, que l'on appelle API (Application Programming Interface). Les classes System ou String font partie du paquet java.lang dont toutes les classes sont utilisables naturellement par défaut dans un programme. Toutes les API sont documentées dans un format standardisé et ces documentations sont accessibles à l'URL http://cermics.enpc.fr/doc/java/jdk1.4.1/docs/api/index.html

Ouvrez une fenêtre de navigateur (Netscape, par exemple) et parcourez ces documentations. Sauvegardez cet URL dans vos signets (bookmarks).

En partant de la classe System du paquet java.lang, retrouvez la méthode println().

Nomenclature

Par habitude et convention, les identificateurs en Java respectent les règles implicites suivantes:

les noms des paquets commencent par une minuscule;
les noms des classes commencent par une majuscule;
les noms des variables et des méthodes commencent par une minuscule;
les noms de constantes sont en majuscule;
les noms d'identificateurs constitués de plusieurs mots prennent une majuscule au début de chaque mot. Exemples: la classe MonProgramme, la méthode maMethode(), la variable uneNouvelleVariable, la constante MAX_VALUE, etc.

Le langage Java impose deux contraintes sur l'écriture des programmes:

tout code doit nécessairement être écrit à l'intérieur d'une classe. Il est donc nécessaire de créer une classe dès que l'on veut écrire la moindre ligne de code ou la moindre fonction.
le code source d'une classe publique doit nécessairement être écrit dans un fichier qui possède exactement le même nom que la classe, avec l'extension .java. Par exemple, la classe Bonjour est écrite dans le fichier Bonjour.java. Il est nécessaire de respecter la casse (majuscule/minuscule).

Arguments sur la ligne de commande

Dans le profil de la méthode principale public static void main(String[] args), qui doit se trouver dans tout programme destiné à être exécuté, args est le nom du paramètre de cette méthode qui représente les arguments de la ligne de commande. Le type de ce paramètre est String[], qui représente le type des tableaux de String. En effet, lors de l'exécution du programme, la variable args est la référence à un tableau dont les éléments représentent les chaînes de caractères passées après le nom de la classe sur la ligne de commande. Par exemple, si l'appel est le suivant:

% java immersion.Bonjour toto tata titi

alors args[0] vaut "toto", args[1] vaut "tata" et args[2] vaut "titi". Par ailleurs, la taille de ce tableau (et donc le nombre d'arguments) peut être connu grâce à l'instruction args.length, qui vaudra dans ce cas l'entier 3.

Lecture d'un entier dans une `String`

Comme nous venons de le voir, il est facile de passer un argument à un programme de cette manière. Néanmoins, cet argument ne peut être qu'une chaîne de caractères (String). En effet, même si la ligne de commande est:

% java immersion.Bonjour 12

la seule information dont le programme dispose est que args[0] vaut la chaîne "12" (son type est String).

Si l'on veut récupérer l'entier 12, de type int, à partir de la String "12", on peut utiliser la méthode parseInt() de la classe Integer de la manière suivante:

int i = Integer.parseInt(args[0]);

Mise en jambes

Pour bien commencer, il est souhaitable d'organiser votre répertoire de travail personnel. Sauf indication contraire, les exercices de chaque séance seront placés dans des paquets distincts.

Pour cette séance, vous devez donc créer un répertoire seance1:
```
% mkdir seance1
```
En utilisant l'éditeur de texte emacs, ouvrir un fichier de nom BaseDeux.java, placé dans le sous-répertoire seance1. Pour que la classe BaseDeux correspondante appartienne au paquet seance1, le code source doit avoir la forme suivante:
```
package seance1;
public class BaseDeux {
  public static void main(String[] args) {
    ...
  }
}
```
On souhaite que notre classe affiche la représentation en base 2 d'un nombre entier passé sur la ligne de commande (en base 10). Par exemple:
```
% java seance1.BaseDeux 11
1011
% java seance1.BaseDeux 6
110
```
La fonction Integer.toBinaryString(int i), qui accepte un entier i en argument, retourne la représentation binaire de cet entier sous la forme d'une chaîne de caractères de type String. Écrire le code nécessaire pour la fonction main().
Dans le répertoire père de seance1, compilez le fichier source Java avec la commande:
```
% javac seance1/BaseDeux.java
```
Listez le répertoire seance1 et constatez l'effet de cette commande: un nouveau fichier a été généré, BaseDeux.class, qui contient le bytecode de la classe BaseDeux.
Exécutez ce programme pour le tester.

L'exécution de la commande java suivie du nom d'une classe a pour effet de lancer une Machine Virtuelle Java (JVM) qui interprète le bytecode de cette classe. Pour cela, cette classe doit contenir une méthode main qui possède exactement la signature de celle utilisée dans notre programme.

Exercice 1: factorielle

Donnez la définition récursive de la fonction factorielle.
Écrire, dans une classe Exo1, une méthode fact() qui accepte en argument un entier n, qu'on suppose positif ou nul, et qui retourne sa factorielle (n!).
Dans cette classe, écrire une fonction main() qui appelle la fonction fact() avec l'entier passé sur la ligne de commande. On prendra soin, avant l'appel, de tester si l'entier fourni est bien positif. Dans le cas contraire, on affichera un message d'erreur. Par exemple:
```
% java seance1.Exo1 5
5! vaut 120
% java seance1.Exo1 -2
Factorielle n'est pas définie sur -2
```
Que se passe t-il lors d'un appel à fact(i) si i vaut 3?
L'appel fact(3) teste si 3 est égal à 0. Comme ce n'est pas le cas, elle doit empiler la valeur 3 sur la pile d'appel, qui sera à multiplier avec le résultat de fact(2). Pour connaître cette valeur, il lui faut empiler à nouveau la valeur 2, à multiplier par le résultat de fact(1), etc. jusqu'à fact(0). Dans ce dernier cas, le test (n == 0) est vrai et la valeur de retour est 1. Il ne reste plus qu'à multiplier ce 1 avec la valeur sur le dessus de la pile (1 également). Le résultat est donc 1, à multiplier par la valeur sur le dessus de la pile qui est 2. Le résultat est 2, à multiplier par la valeur sur le dessus de la pile qui est 3. Le résultat final est 6.

Exercice 2: Calcul de a^b

On suppose dans la suite de cet exercice que a et b sont des entiers et que b >= 0.

Une première manière, simple, de calculer a^b est de considérer que:
- a⁰ = 1
- a^b+1 = a * a^b
Déduire de cette définition une fonction récursive expo1() qui déclare deux paramètres entiers a et b, et retourne la valeur de a^b.
Écrire cette fonction Java dans une classe Exo2 et tester son fonctionnement.
Une seconde manière de calculer a^b est de considérer que:
- a⁰ = 1
- a^2k = (a * a)^k
- a^2k+1 = a * (a * a)^k
Comme précédemment, déduire de cette définition une fonction récursive expo2() et l'écrire en Java dans la classe Exo2. Tester cette fonction.
Comparer formellement les deux fonctions en terme de nombre d'appels de fonctions pour calculer a^b étant donnés a et b. Comment faire pour vérifier cette comparaison dans votre programme?

Exercice 3: Affichage d'un triangle

On souhaite écrire un programme qui prend un entier positif sur sa ligne de commande et qui affiche un triangle ayant autant de ligne que l'entier fourni. Voici deux exemples du résultat attendu:

% java seance1.Triangle 3
*
**
***
% java seance1.Triangle 4
*
**
***
****

Écrire, dans une classe Triangle, une méthode afficheTriangle1() qui prend en argument un entier positif n et affiche un triangle de n lignes. En déduire le programme voulu.

Ajouter dans Triangle une fonction afficheTriangle2() permettant d'obtenir le résultat suivant:

% java seance1.Triangle 4
*
**
***
****
***
**
*

Comment faire pour changer arbitrairement le symbole "*"?

Exercice 4: Calcul du triangle de Pascal

On rappelle que les coefficients binomiaux sont données par:

C⁰_n = 1
C^p_n = n!/((n-p)!p!)

Toutes les fonctions qui sont demandées dans cet exercice sont à écrire dans une classe Exo4.

Écrire une fonction C1() récursive, déclarant deux paramètres entiers n et p, et retournant C^p_n.
On souhaite maintenant écrire un programme qui prend un entier x sur sa ligne de commande, et affiche les x premières lignes du triangle de Pascal. Par exemple:
```
% java seance1.Exo4 6
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
```
Ajoutez, dans la classe Exo4, une fonction affichePascal() qui déclare un paramètre entier x et réalise cet affichage. En déduire le programme souhaité.
Jusqu'à quelle valeur le programme fonctionne t-il? Que se passe t-il au-delà?
En fait, le problème vient de l'utilisation de la fonction factorielle, qui requiert la manipulation de valeurs intermédiaires bien plus grandes que le résultat attendu.
Nous nous interdisons donc maintenant le calcul de la factorielle d'un nombre, et voulons réécrire notre programme.
Exprimez C^p+1_n en fonction de C^p_n. Déduisez-en une nouvelle fonction C2() récursive, déclarant deux paramètres entiers n et p, et retournant C^p_n.
Modifier le programme pour qu'il utilise C2() à la place de C1(). Jusqu'à quelles valeurs peut-on utiliser le programme?

Exercice 5: Calcul de racine d'un nombre par la méthode de Newton

La relation de Newton, qui recherche le zéro d'une fonction, utilise la relation suivante:

x_n+1 = x_n - f(x_n) / f'(x_n)

On peut alors prendre une valeur x₀ et calculer successivement les valeurs des x_i suivants.

Pour ce qui concerne la racine carrée d'un nombre a, la fonction qu'on cherche à annuler est f(x) = x² - a, sa dérivée est f'(x) = 2x et la relation de Newton est donc la suivante:

x_n+1 = x_n - (x_n² - a) / 2x_n

Écrire, dans une classe Exo5, une fonction calculRacine() qui accepte en argument un nombre flottant a de type double et un nombre entier n. Cette fonction calcule et retourne l'approximation par n termes de la valeur de la racine carrée de a.

Écrire une fonction main() qui permet de tester cette fonction de sorte qu'elle soit utilisable de la manière suivante:

% java seance1.Exo5 400 6
20.06621767747577 
% java seance1.Exo5 400 9
20.0
% java seance1.Exo5 0.5 9
0.7071067811865475

Comparez les résultats de cette technique en testant l'utilisation de la fonction prédéfinie Math.sqrt() du paquet java.lang.

Exercice 6: Calcul de logarithme par développement limité

Dans cet exercice on souhaite écrire un programme qui calcule le logarithme d'un nombre réel (qu'on supposera positif) en utilisant les développements limités. Le programme prendra deux nombres sur sa ligne de commande:

le premier, un réel positif, est le nombre dont il faut calculer le logarithme;
le second, un entier positif, est le nombre de termes du développement limité.

Le développement limité de ln(1+x) quand x est au voisinage de 0 est:

ln(1+x) = x - x²/2 + x³/3 - x⁴/4 + ...

Le développement limité à l'ordre n ne contient que n termes, plus un terme donnant une approximation du reste, qu'on négligera pour simplifier.

Dans une classe Exo6 écrire une fonction developpementLimiteLog() déclarant un paramètre xde type réel, qu'on supposera proche de 1, et un paramètre n de type entier qu'on supposera positif, qui calcule par itérations successives la valeur du développement limité de ln(x) à l'ordre n et retourne la valeur calculée.

Nous allons maintenant écrire une fonction ln() prenant un argument réel x qu'on supposera positif et retournant ln(x). La fonction ln() pourra utiliser developpementLimiteLog(), mais il faut pour cela se ramener au voisinage de 1.

On rappelle les relations suivantes des logarithmes:

ln(xⁿ) = n * ln(x) avec n: nombre réel positif
ln(x*y) = ln(x) + ln(y)
ln(x/y) = ln(x) - ln(y)

Algorithme pour obtenir calculer ln(x) avec x positif quelconque en se ramenant à des appels recursifs de la forme ln(y) avec y proche de 1

Tout d'abord, si 0<x<1, on utilise la formule ln(x) = -ln(1/x) pour se ramener au cas où le paramètre de ln est supérieur à 1.
Ensuite, si ça n'est pas déjà la cas, on se ramène à des valeurs comprises dans l'intervalle [1,10] en utilisant la formule ln(x*10ⁿ) = ln(x) + n*ln(10).
Ensuite, si ça n'est pas déjà le cas, on se ramène à des valeurs proches de 1 en utilisant la relation ln(x) = ln(Racine(x)²) = 2*ln(Racine(x)). On se ramène ainsi à des valeurs dans l'intervalle 1<=x<A avec A<2 qu'on choisit arbitrairement. On utilisera, dans notre implantation, la fonction Racine de l'exercice précédent.
Finalement, on utilise le développement limité : ln(1+x) = x - x²/2 +x³/3 -x⁴/4 +... pour x proche de zéro.

Tout ça se programme assez facilement !

Écrire une fonction main() qui permet de tester cette fonction de sorte qu'elle soit utilisable de la manière suivante:

% java seance1.Exo6 400 5
5.991581978022303
% java seance1.Exo6 400 8
5.991464545960707
% java seance1.Exo6 0.5 8
-0.6931471802249534

Le dernier nombre donne la précision. Plus il est élevé, plus la précision est grande. On l'utilisera pour fixer le nombre de termes du développement limité, le nombre de termes dans le calcul de la racine, et on fixera la valeur de A dans ce qui précède à A=1/n.

Comparez les résultats de cette technique en testant l'utilisation de la fonction prédéfinie Math.log() du paquet java.lang, qui donne le logarithme naturel (base e) de son argument.

À faire

Envoyer un mail à votre responsable de classe (Nicolas.Bedon[at]univ-mlv.fr ou Etienne.Duris[at]univ-mlv.fr) en indiquant, dans le corps du message, vos nom et prénom.
Écrire et tester les programmes proposés dans cette feuille et envoyer les fichiers source (.java) à la même adresse mail, en tant que fichier attaché. Cette façon de joindre un fichier est bien préférable à un copier - coller dans le corps du message.