Cours JAVA

Cours Java : introduction aux bases de l'iteration


Télécharger Cours Java : introduction aux bases de l'iteration

★★★★★★★★★★3.5 étoiles sur 5 basé sur 1 votes.
Votez ce document:

Télécharger aussi :


Cours Java : introduction aux bases de l'itération

2.3. ITÉRATIONS

int i;

for(i = 1; i <= n; i++) System.out.println(i);

Ici, on a affichétous les entiers entre 1 et n. Prenons l’exemple de n = 2 et déroulons

les calculs faits par l’ordinateur :

– étape 1 : i vaut 1, il est plus petit que n, on exécute l’instruction

System.out.println(i);

et on incrémente i;

– étape 2 : i vaut 2, il est plus petit que n, on exécute l’instruction

System.out.println(i);

et on incrémente i;

– étape 3 : i vaut 3, il est plus grand que n, on sort de la boucle.

Une forme encore plus courante est celle oùon déclare i dans la boucle :

for(int i = 1; i <= n; i++) System.out.println(i);

Dans ce cas, on n’a pas accès à la variable i en dehors du corps de la boucle. Un autre exemple est le calcul de la somme

n 1

i=1 i

qui se fait par

double s = 0.0;

for(int i = 1; i <= n; i++) s = s + 1/((double)i);

La conversion explicite en double est ici nécessaire, car sinon la ligne plus naturelle : s = s + 1/i;

conduit à évaluer d’abord 1/i comme une opération entière, autrement dit le quotient de 1 par i, i.e., 0. Et la valeur finale de s serait toujours 1.0.

La forme générale est la suivante :

for(Init; C; Inc) I

Dans cette écriture Init est une initialisation (pouvant comporter une déclaration), Inc est une incrémentation, et C un test d’arrêt, ce sont des expressions qui ne se terminent pas par un point virgule. Quant à I, c’est le corps de la boucle constituéd’une seule instruction ou d’une suite d’instructions entre accolades. Init est exécutée

en premier, ensuite la condition C est évaluée si sa valeur est true alors la suite d’instructions I est exécutée suivie de l’instruction d’incrémentation Inc et un nouveau tour de boucle reprend avec l’évaluation de C. Noter que Init (tout comme Inc) peut être composée d’une seule expression ou bien de plusieurs, séparées par des , (virgules).

 CHAPITRE 2. SUITE D’INSTRUCTIONS

Noter que les instructions Init ou Inc de la forme générale (ou même les deux) peuvent être vides. Il n’y a alors pas d’initialisation ou pas d’incrémentation ; l’ini¬tialisation peut, dans ce cas, figurer avant le for et l’incrémentation à l’intérieur de I.

Insistons sur le fait que la boucle

for(int i = 1; i <= n; i++) System.out.println(i);

peut également s’écrire :

for(int i = 1; i <= n; i++) {

System.out.println(i);

}

pour faire ressortir le bloc d’instructions, ou encore :

for(int i = 1; i <= n; i++){ System.out.println(i); }

ce qui fait gagner une ligne...

2.3.2 Itérations tant que

Une telle instruction a la forme suivante :

while(C)

oùC est une condition et I une instruction ou un bloc d’instructions. L’itération évalue C et exécute I si le résultat est true, cette suite est répétée tant que l’évaluation de C donne la valeur true.

Un exemple classique de l’utilisation de while est le calcul du pgcd de deux nombres par l’algorithme d’Euclide. Cet algorithme consiste à remplacer le calcul de pgcd(a, b) par celui de pgcd(b, r) oùr est le reste de la division de a par b et ceci tant que r =~ 0.

while(b != 0){ r = a % b;

a = b;

b = r;

}

Examinons ce qu’il se passe avec a = 28, b = 16.

– étape 1 : b = 16 est non nul, on exécute le corps de la boucle, et on calcule r = 12 ;

– étape 2 : a = 16, b = 12 est non nul, on calcule r = 4;

– étape 3 : a = 12, b = 4, on calcule r = 0 ;

– étape 4 : a = 4, b = 0 et on sort de la boucle.

double s = 0.0;

for(int i = 1; i <= n; i++) s += 1/((double)i);

est

double s = 0.0;

int i = 1;

while(i <= n){

s += 1/((double)i);

i++;

}

mais que la première forme est plus compacte que la seconde. On a tendance à utiliser une boucle for quand on peut prévoir le nombre d’itérations, et while dans les autres cas.

2.3.3 Itérations répéter tant que

Il s’agit ici d’effectuer l’instruction I et de ne la répéter que si la condition C est vérifiée. La syntaxe est :

do

while(C)

À titre d’exemple, le problème de Syracuse est le suivant : soit m un entier plus grand que 1. On définit la suite un par u0 = m et

~ =         un ÷ 2 si un est pair,

un+1     3un + 1 sinon.

(la notation n ÷ 2 désigne le quotient de la division euclidienne de n par 2). Il est conjecturé, mais non encore prouvéque pour tout m, la suite prend la valeur 1 au bout d’un temps fini.

Pour vérifier numériquement cette conjecture, on écrit le programme JAVA suivant :

public class Syracuse{

public static void main(String[] args){ int n = Integer.parseInt(args[0]);

do{

if((n % 2) == 0)

n /= 2;

else

n = 3*n+1;

} while(n > 1);

return;

}}

que l’on appelle par :

unix% java Syracuse 101

L’instruction magique Integer.parseInt(args[0]); permet de récupérer la va¬leur de l’entier 101 passésur la ligne de commande.



2.4 Terminaison des programmes

Le programme que nous venons de voir peut être considérécomme étrange, voire dangereux. En effet, si la conjecture est fausse, alors le programme ne va jamais s’arrêter, on dit qu’il ne termine pas. Le problème de la terminaison des programmes est fondamental en programmation. Il faut toujours se demander si le programme qu’on écrit va terminer. D’un point de vue théorique, il est impossible de trouver un algo¬rithme pour faire cela (cf. chapitre 6). D’un point de vue pratique, on doit examiner chaque boucle ou itération et prouver que chacune termine.

Voici quelques erreurs classiques, qui toutes simulent le mouvement perpétuel :

int i = 0; while(true) i++;

ou bien

for(i = 0; i >= 0; i++) ;

On s’attachera à prouver que les algorithmes que nous étudions terminent bien.

2.5 Instructions de rupture de contrôle

Il y a trois telles instructions qui sont return, break et continue. L’instruction return doit être utilisée dans toutes les fonctions qui calculent un résultat (cf. chapitre suivant).

Les deux autres instructions de rupture sont beaucoup moins utilisées et peuvent être omises en première lecture. L’instruction break permet d’interrompre une suite d’instructions dans une boucle pour passer à l’instruction qui suit la boucle dans le texte du programme.

L’instruction continue a un effet similaire à celui de break, mais redonne le contrôle à l’itération suivante de la boucle au lieu d’en sortir.

2.6 Exemples

2.6.1 Méthode de Newton

On rappelle que si f est une fonction suffisamment raisonnable de la variable réelle x, alors la suite

2.6. EXEMPLES

converge vers une racine de f à partir d’un point de départ bien choisi.

Si f(x) = x2 − a avec a > 0, la suite converge vers ~,/a. Dans ce cas particulier, la récurrence s’écrit :

xn+1 = xn − (x2n − a)/(2xn) = 2 (xn + x J

On itère en partant de x0 = a, et on s’arrête quand la différence entre deux valeurs consécutives est plus petite que  > 0 donné. Cette façon de faire est plus stable numériquement (et moins coûteuse) que de tester |x2 n − a| ~ . Si on veut calculer 2 par cette méthode en JAVA, on écrit :

public class Newton{

public static void main(String[] args){ double a = 2.0, x, xold, eps;

x = a;

eps = 1e-10;

do{

// recopie de la valeur ancienne

xold = x;

// calcul de la nouvelle valeur

x = (xold+a/xold)/2;

System.out.println(x);

} while(Math.abs(x-xold) > eps);

System.out.print("Sqrt(a)=");

System.out.println(x);

return;

On peut également vérifier le calcul en comparant avec la fonction Math.sqrt() de JAVA.

Comment prouve-t-on que cet algorithme termine? Ici, il suffit de prouver que la suite |xn+1 − xn| tend vers 0, ce qui est vrai puisque la suite (xn) converge (elle est décroissante, minorée par -,/a).

 xn+1 = xn2 (3 − ax2n).

Écrire une fonction JAVA qui calcule cette suite, et en déduire le calcul de ~'/a. Cette suite converge-t-elle plus ou moins vite que la suite donnée ci-dessus?

 Chapitre 3

Méthodes : théorie et pratique

Nous donnons dans ce chapitre un aperçu général sur l’utilisation des méthodes (fonctions) dans un langage de programmation classique, sans nous occuper de la problématique objet, sur laquelle nous reviendrons dans les chapitres 5 et 9.

3.1 Pourquoi écrire des méthodes

Reprenons l’exemple du chapitre précédent :

public class Newton{

public static void main(String[] args){ double a = 2.0, x, xold, eps;

x = a;

eps = 1e-10;

do{

// recopie de la valeur ancienne

xold = x;

// calcul de la nouvelle valeur

x = (xold+a/xold)/2;

System.out.println(x);

} while(Math.abs(x-xold) > eps);

System.out.print("Sqrt(a)=");

System.out.println(x);

return;

}

}

Nous avons écrit le programme implantant l’algorithme de Newton dans la méthode d’appel (la méthode main). Si nous avons besoin de faire tourner l’algorithme pour plusieurs valeurs de a dans le même temps, nous allons devoir recopier le programme à chaque fois. Le plus simple est donc d’écrire une méthode à part, qui ne fait que les calculs liés à Newton :

 public class Newton2{

public static double sqrtNewton(double a, double eps){ double xold, x = a;

do{

// recopie de la valeur ancienne xold = x;

// calcul de la nouvelle valeur x = (xold+a/xold)/2;

System.out.println(x);

} while(Math.abs(x-xold) > eps); return x;

}

public static void main(String[] args){ double r;

r = sqrtNewton(2, 1e-10); System.out.print("Sqrt(2)="); System.out.println(r); r = sqrtNewton(3, 1e-10); System.out.print("Sqrt(3)="); System.out.println(r);

}}

Remarquons également que nous avons séparéle calcul proprement dit de l’affichage du résultat.

Écrire des méthodes remplit plusieurs rôles : au-delàde la possibilitéde réutilisation des méthodes à différents endroits du programme, le plus important est de clarifier la structure du programme, pour le rendre lisible et compréhensible par d’autres personnes que le programmeur original.

3.2 Comment écrire des méthodes

3.2.1 Syntaxe

Une méthode prend des arguments en paramètres et donne en général un résultat. Elle se déclare par :

public static typeRes nomFonction(type1 nom1, ..., typek nomk)

Dans cette écriture typeRes est le type du résultat.



La signature d’une méthode est constituée de la suite ordonnée des types des pa¬ramètres.

 Le résultat du calcul de la méthode doit être indiquéaprès un return. Il est obligatoire de prévoir une telle instruction dans toutes les branches d’une méthode. L’exécution d’un return a pour effet d’interrompre le calcul de la méthode en rendant le résultat à l’appelant.

On fait appel à une méthode par

nomFonction(var1, var2, ... , vark)

En général cet appel se situe dans une affectation.

En résumé, une syntaxe très courante est la suivante :

public static typeRes nomFonction(type1 nom1, ..., typek nomk){ typeRes r;

r = ...;

return r;

}

...

public static void main(String[] args){

type1 n1;

type2 n2;

...

typek nk;

typeRes s;

...

s = nomFonction(n1, n2, ..., nk); ...

return;

}

3.2.2 Le type spécial void

Le type du résultat peut être void, dans ce cas la méthode ne rend pas de résultat. Elle opère par effet de bord, par exemple en affichant des valeurs à l’écran ou en modi¬fiant des variables globales. Il est déconseilléd’écrire des méthodes qui procèdent par effet de bord, sauf bien entendu pour les affichages.

Un exemple typique est celui de la procédure principale :

// Voici mon premier programme

public class Premier{

public static void main(String[] args){

System.out.println("Bonjour !");

return;

}

}

Notons que le return n’est pas obligatoire dans une méthode de type void, à moins qu’elle ne permette de sortir de la méthode dans un branchement. Nous la mettrons souvent pour marquer l’endroit où on sort de la méthode, et par souci d’homogénéitéde l’écriture.

3.2.3 La surcharge

En JAVA on peut définir plusieurs méthodes qui ont le même nom à condition que leurs signatures soient différentes. On appelle surcharge cette possibilité. Le compilateur doit être à même de déterminer la méthode dont il est question à partir du type des paramètres d’appel. En JAVA, l’opérateur + est surchargé: non seulement il permet de faire des additions, mais il permet de concaténer des chaînes de caractères (voir la section 9.2 pour plus d’information). Par exemple, reprenant le programme de calcul de racine carrée, on aurait pu écrire :

public static void main(String[] args){ double r;

r = sqrtNewton(2, 1e-10);

System.out.println("Sqrt(2)=" + r);

}

3.3 Visibilitédes variables

Les arguments d’une méthode sont passés par valeurs, c’est à dire que leur valeurs sont recopiées lors de l’appel. Après la fin du travail de la méthode les nouvelles valeurs, qui peuvent avoir étéattribuées à ces variables, ne sont plus accessibles.

Ainsi il n’est pas possible d’écrire une méthode qui échange les valeurs de deux variables passées en paramètre, sauf à procéder par des moyens détournés peu recom¬mandés.

Reprenons l’exemple donnéau premier chapitre :

// Calcul de circonférence public class Cercle{

static float pi = (float) Math.PI;

public static float circonference (float r) { return 2. * pi * r; }

public static void main (String[] args){ float c = circonference (1.5);

System.out.print("Circonférence: ");

System.out.println(c);

return;

}}

La variable r présente dans la définition de circonference est instanciée au moment de l’appel de la méthode par la méthode main. Tout se passe comme si le programme réalisait l’affectation r = 1.5 au moment d’entrer dans f.

Dans l’exemple précédent, la variable pi est une variable de classe, ce qui veut dire qu’elle est connue et partagée par toutes les méthodes présentes dans la classe (ainsi que par tous les objets de la classe, voir chapitre 5), ce qui explique qu’on peut l’utiliser dans la méthode circonference.

Pour des raisons de propretédes programmes, on ne souhaite pas qu’il existe beau¬coup de ces variables de classe. L’idéal est que chaque méthode travaille sur ses propres variables, indépendamment des autres méthodes de la classe, autant que cela soit pos¬sible. Regardons ce qui se passe quand on écrit :

public class Essai{

public static int f(int n){ int m = n+1;

return 2*m;

}

public static void main(String[] args){ System.out.print("résultat="); System.out.println(f(4));

return;

}}

La variable m n’est connue (on dit vue) que par la méthode f. En particulier, on ne peut l’utiliser dans la méthode main ou toute autre méthode qui serait dans la classe. Compliquons encore :

public class Essai{

public static int f(int n){ int m = n+1;

return 2*m;

}

public static void main(String[] args){ int m = 3;

System.out.print("résultat="); System.out.print(f(4)); System.out.print(" m="); System.out.println(m); return;

}}

ou

résultat=10 m=3

D’après ce qu’on vient de dire, la variable m de la méthode f n’est connue que de f, donc pas de main et c’est la seconde réponse qui est correcte. On peut imaginer que la variable m de f a comme nom réel m-de-la-méthode-f, alors que l’autre a pour nom m-de-la-méthode-main. Le compilateur et le programme ne peuvent donc pas faire de confusion.

3.4 Quelques conseils pour écrire un programme

Un beau programme est difficile à décrire, à peu près aussi difficile à caractériser qu’un beau tableau, ou une belle preuve. Il existe quand même quelques règles simples. Le premier lecteur d’un programme est soi-même. Si je n’arrive pas à me relire, il est difficile de croire que quelqu’un d’autre le pourra. On peut être amenéà écrire un programme, le laisser dormir pendant quelques mois, puis avoir à le réutiliser. Si le programme est bien écrit, il sera facile à relire.



Grosso modo, la démarche d’écriture de petits ou gros programmes est à peu près la même, à un facteur d’échelle près. On découpe en tranches indépendantes le problème à résoudre, ce qui conduit à isoler des méthodes à écrire. Une fois cette architecture mise en place, il n’y a plus qu’àprogrammer chacune de celles-ci. Même après un découpage a priori du programme en méthodes, il arrive qu’on soit amenéà écrire d’autres méthodes. Quand le décide-t-on ? De façon générale, pour ne pas dupliquer du code. Une autre règle simple est qu’un morceau de code ne doit jamais dépasser une page d’écran. Si cela arrive, on doit couper en deux ou plus. La clartéy gagnera.

La méthode main d’un programme JAVA doit ressembler à une sorte de table des matières de ce qui va suivre. Elle doit se contenter d’appeler les principales méthodes du programme. A priori, elle ne doit pas faire de calculs elle-même.

Les noms de méthode (comme ceux des variables) ne doivent pas se résumer à une lettre. Il est tentant pour un programmeur de succomber à la facilitéet d’imaginer pouvoir programmer toutes les méthodes du monde en réutilisant sans cesse les mêmes noms de variables, de préférence avec un seul caractère par variable. Faire cela conduit rapidement à écrire du code non lisible, à commencer par soi. Ce style de programmation est donc proscrit. Les noms doivent être pertinents. Nous aurions pu écrire le programme concernant les cercles de la façon suivante :

public class D{

static float z = (float)Math.PI;

public static float e(float s){ return 2. * z * s; }

public static void main(String[] args){ float y = e(1.5);

System.out.println(y);

return;

}}

ce qui aurait rendu la chose un peu plus difficile à lire.

Un programme doit être aéré: on écrit une instruction par ligne, on ne mégotte pas sur les lignes blanches. De la même façon, on doit commenter ses programmes. Il ne sert à rien de mettre des commentaires triviaux à toutes les lignes, mais tous les points difficiles du programme doivent avoir en regard quelques commentaires. Un bon début consiste à placer au-dessus de chaque méthode que l’on écrit quelques lignes décrivant le travail de la méthode, les paramètres d’appel, etc. Que dire de plus sur le sujet? Le plus important pour un programmeur est d’adopter rapidement un style de programmation (nombre d’espaces, placement des accolades, etc.) et de s’y tenir.

Finissons avec un programme horrible, qui est le contre-exemple typique à ce qui précède :

public class mystere{public static void main(String[] args){

int

z= Integer.parseInt(args[0]);doif((z%2)==0)

z/=2;

else z=3*z+1;while(z>1);}}

3.5 Quelques exemples de programmes complets 3.5.1 Écriture binaire d’un entier

Tout entier n > 0 peut s’écrire en base 2 sous la forme :

n = nt2t + nt−12t−1 + ••• + n0 =

avec ni valant 0 ou 1, et par convention nt = 1. Le nombre de bits pour écrire n est t + 1.

À partir de n, on peut retrouver ses chiffres en base 2 par division successive par 2 : n0 = n mod 2, n1 = (n ÷ 2) mod 2 (÷ désigne le quotient de n par 2) et ainsi de suite. En JAvA, le quotient se calcule à l’aide de / et le reste avec %. Une méthode affichant à l’écran les chiffres n0, n1, etc. est :

// ENTRÉE: un entier strictement positif n

// SORTIE: aucune

// ACTION: affichage des chiffres binaires de n

public static void binaire(int n){

while(n > 0){

System.out.print(n%2);

Nous avons profitéde cet exemple simple pour montrer jusqu’àquel point les com-mentaires peuvent être utilisés. Le rêve est que les indications suffisent à comprendre ce que fait la méthode, sans avoir besoin de lire le corps de la méthode. En procédant ainsi pour toute méthode d’un gros programme, on dispose gratuitement d’un embryon de la documentation qui doit l’accompagner. Notons qu’en JAVA, il existe un outil javadoc qui permet de faire encore mieux: il fabrique une page web de documentation pour un programme, en allant chercher des commentaires spéciaux dans le code.

3.5.2 Calcul du jour correspondant à une date

Nous terminons ce chapitre par un exemple plus ambitieux. On se donne une date sous forme jour mois année et on souhaite déterminer quel jour de la semaine corres¬pondait à cette date.

Face à n’importe quel problème, il faut établir une sorte de cahier des charges, qu’on appelle spécification du programme. Ici, on rentre la date en chiffres sous la forme agréable jj mm aaaa et on veut en réponse le nom du jour écrit en toutes lettres.

Nous allons d’abord donner la preuve de la formule due au Révérend Zeller et qui résout notre problème.

Théorème 1 Le jour J (un entier entre 0 et 6 avec dimanche codépar 0, etc.) cor-respondant à la date j/m/a est donnépar :

J = (j + 2.6m' − 0.2 + e + e/4 + s/4 − 2s) mod 7

(m' a') = (m − 2, a)           si m > 2,

,              (m + 10,a − 1) si m  2,

et a' = 100s + e, 0  e < 100.

Commençons d’abord par rappeler les propriétés du calendrier grégorien, qui a étémis en place en 1582 par le pape Grégoire XIII : l’année est de 365 jours, sauf quand

elle est bissextile, i.e., divisible par 4, sauf les années séculaires (divisibles par 100), qui ne sont bissextiles que si divisibles par 400.

Si j et m sont fixés, et comme 365 = 7 × 52 + 1, la quantitéJ avance d’1 d’année en année, sauf quand la nouvelle année est bissextile, auquel cas, J progresse de 2. Il faut donc déterminer le nombre d’années bissextiles inférieures à a.

Détermination du nombre d’années bissextiles

Lemme 1 Le nombre d’entiers de [1, N] qui sont divisibles par k est p(N, k) = N/k.

Démonstration : les entiers m de l’intervalle [1, N] divisibles par k sont de la forme m = kr avec 1  kr  N et donc 1/k  r  N/k. Comme r doit être entier, on a en fait 1  r  N/k. a



269