nbParfait.htm 2A+ (TP_Soutien
16.11.06) & 1A (TDS1_04.2 07.10.2009)
Cr. 20.10.2005
Dernière Màj: 06.10.2009 19:32
/ H. Nguyen-Phu
CORRIGE TYPIQUE DU CALCUL DES NOMBRES PARFAITS
==============================================
Plan:
1.- ANALYSE selon le L.A.O.
3.- Le programme test 'nbParfait_'
4.- Résultats obtenus et conclusion
1.- ANALYSE selon le L.A.O.
Rappel
du problème :
Un nombre est dit parfait s'il est égal à la somme de tous ses diviseurs dans une division entière. Donc, le type de tels nombres doit être un ENTIER.
Exemple: 6 (= 1+2+3) est effectivement un nombre parfait.
Par ailleurs, il est demandé de rechercher tous les nombres parfaits compris entre 1 et un seuil maximal lu sur clavier (et/ou tapée directement via la ligne de commande). Par souci de simplification dans ce qui suit, on ne s’attache pas à expliciter le contenu de la décomposition telle que 1 + 2 + 3 dans l’exemple précédent.
En accord avec le langage algorithmique objet ( L.A.O. cf. Mémento LAO – JAVA ), le schéma bloc détaillé de la classe 'nbParfait' peut être donné par :
_______________________________________________________________________________
nbParfait // Nom de la classe
_______________________________________________________________________________
~ seuilMin : ENTIER // attribut indiquant la limite inférieure
~ seuilMax : ENTIER // attribut indiquant la limite supérieure
_______________________________________________________________________________
// Le constructeur sans arguments n’est pas déclaré ni défini ici !
// Par défaut, ce constructeur sera généré automatiquement par Java
// mais avec des affectations pré-établies qui risquent de ne pas convenir !!
// constructeur à deux arguments :
+ nbParfait(D seuilMin: ENTIER, D max : ENTIER) {
Ceci.seuilMin <-- seuilMin // ‘Ceci’ <=> ‘this’ en Java
seuilMax <-- max }
/* Pas besoin d’accesseurs ni de modificateurs grâce au constructeur ci-dessus
*/
// méthode de traitement avec accès aux attributs privés ci-dessus
+ PROCEDURE rechParfait()
// pour calculer des nombres parfaits de ‘seuilMin’ à 'seuilMax'
_______________________________________________________________________________
L'algorithme de 'rechParfait' est constitué principalement par deux boucles emboîtées:
+ PROCEDURE nbParfait::rechParfait() { // procédure d'instance ici
i, j : ENTIER // indices courants
sommediv : ENTIER // somme des diviseurs
POUR i DE seuilMin A seuilMax FAIRE
sommediv <- 0
POUR j DE 1 A (i-1) FAIRE
//Question: (i-1)
peut-il être remplacé par (i DIV 2) ? Et pourquoi ?
SI ( i MOD j = 0 ) ALORS
sommediv <- sommediv + j
FSI
FPOUR
SI (sommediv = i) ALORS
ECRIRE( i, " est un nombre parfait.")
FSI
FPOUR
}
De même, le programme de test des nombres parfaits est défini dans la classe 'nbParfait_':
______________________________________________________________________________
nbParfait_ // Nom de la classe comportant le module 'main'
______________________________________________________________________________
// Aucun attribut ici !
______________________________________________________________________________
// Par défaut, ce constructeur est généré automatiquement par Java:
+ nbParfait_( ) { }
+ PROCEDURE main(D args : TABLEAU de CHAINES) // procédure de classe 'main'
______________________________________________________________________________
+ PROCEDURE nbParfait_::main(D args : TABLEAU de CHAINES) {
min, max: ENTIER
ECRIRE("nbParfait_ : Test de la classe 'nbParfait' (c) ~/2A env.")
ECRIRE("Usage conseillé: java nbParfait_ unSeuilMin unSeuilMax")
SI (args.Longueur = 2 ) ALORS
// Traitement de la lecture via la ligne de commande:
min <- ENTIER.convENTIER(args[0])
max <- ENTIER.convENTIER(args[1])
SINON
min <- ENTIER.convENTIER(es.LireCh("Seuil minimal = ? : "))
max <- ENTIER.convENTIER(es.LireCh("Seuil maximal = ? : "))
FSI
// Mise en forme des seuils tels que min < max et qu’ils sont positifs :
SI ( min < 1 ) ALORS
min = 1 FSI
SI ( max < min ) ALORS
max = min + 999 // on se limite à trois digits si min = 1!
FSI
ECRIRE("Les seuils retenus (ou lus) sont: Min=", min, " Max= ", max)
// Création d'une instance (i.e. un objet) de la classe 'nbParfait' :
unObj: nbParfait
unObj <- RES nbParfait(min, max)
/* construction d’un objet avec seuilMin = min et seuilMax = max */
// Envoi de message à la méthode de calcul des nombres parfaits entre ces deux seuils:
unObj.rechParfait()
}
2.- La classe 'nbParfait'
import
static java.lang.System.*;
import
static java.lang.Math.*;
/**
* Classe 'nbParfait' : Calcul des nombres entiers dits
PARFAITS
* @author
(c) ~/2A env. H. Nguyen-Phu
* @since
1.0 2005.10.18
* @version 1.1 2006.11.15
19h25
* @see
nbParfait_
*/
public class nbParfait {
/** seuilMin : seuil minimal de la recherche doit être positif */
private int seuilMin;
/** seuilMax : seuil maximal de la recherche doit être positif ;
* Hypo.: seuilMin < seuilMax
*/
private int seuilMax;
/** nbParfait : constructeur à deux arguments
* @param seuilMin: Valeur du seuil minimal de type ENTIER
* @param max: Valeur du seuil maximal de type ENTIER
*/
public nbParfait(int seuilMin, int max ) {// constructeur publique à 2 arguments
this.seuilMin = seuilMin; // emploi obligatoire de 'this' ici !
seuilMax = max; // pas d'emploi de 'this' car 'max' est différent de 'seuilMax'.
}
/** rechParfait( ) : procédure publique d'instance pour calculer les nombres parfaits entre deux seuils
*/
public void rechParfait() {
for (int i= seuilMin;
i<= seuilMax; i++) {
int sommediv=0;
for(int j=1; j<= i/2 ; j++)
// Peut-on mettre: j<= (int) sqrt(i) à l’instar des nombres premiers?
// for(int j=1; j<= (int) sqrt(i); j++)
if (i%j==0)
sommediv
+= j; // affectation composée
if (sommediv==i)
out.println(i+" est un nombre parfait.");
}
}
}
3.- Le programme test 'nbParfait_'
import static java.lang.System.*; // cf. Java 5.0 ou ultérieur ...
/** Classe 'nbParfait_' : pour envoyer un message à la classe 'nbParfait'
* @author (c) ~/2A env. H. Nguyen-Phu
* @since 1.0
2005.10.18
* @version
1.11 2009.10.06
* @see nbParfait
*/
public class nbParfait_ {
/**
* Méthode principale publique de classe 'main(...)'.
* Elle utilise la classe 'es' pour accéder aux méthodes de classe:
* attente() - affichage de l'heure de fin d'exécution,
* LireCh() - lecture récursive d'une chaîne de caractères,
* LireCh(guide) - idem mais un message de guide en lecture.
*
* @param args Tableau de chaînes pour ligne de commande éventuelle
*/
public static void
main(String[] args)
{
int max, min;
// La méthode d'instance 'printf' n'est définie qu' à partir de Java 5.0
// (cf. 'printf' du langage C pour plus détails ... )
out.printf("nbParfait_: Test de la classe 'nbParfait' \n");
out.printf(" (c) ~/2A env. 19h40 06.10.2009\n");
out.printf("Usage : java nbParfait_ unSeuilMinPositif unSeuilMaxPositif\n");
if (args.length == 2 ) {
// Traitement de la lecture via la ligne de commande:
min = Integer.parseInt(args[0]);
max = Integer.parseInt(args[1]);
}
else {
min = Integer.parseInt(es.LireCh("Donner le seuil minimal de la recherche : "));
max = Integer.parseInt(es.LireCh("Donner le seuil maximal de la recherche : "));
}
// Mise en forme des seuils t.q. min < max et qu'ils sont strictement positifs
if ( min < 1 )
min = 1;
if ( max < min
)
max = min + 999;
out.printf("Les seuils retenus (ou lus) sont: seuilMin= %d et seuilMax= %d.\n\n", min, max);
// Création d'une instance (i.e. un objet test) de la classe 'nbParfait' :
nbParfait unObj = new nbParfait(min, max);
// Appel de la méthode de calcul des nombres parfaits de 'min' jusqu'à 'max':
unObj.rechParfait( );
es.attente( );
}
}
4.- Résultats obtenus et conclusion
4.1- Création du fichier
unique de résultats des tests
------------------------------------------------------
La compilation et l’exécution sont effectuées par le script ‘ jc ’ :
jc nbParfait_
Une nouvelle exécution sans re-direction des résultats s’effectue avec :
java nbParfait_
puis avec re-direction des résultats par :
java nbParfait_ 1 100
> nbParfait.res
On peut aussi cumuler (i.e. concaténer) un autre test :
java nbParfait_ 101 10000 >> nbParfait.res
En fin de compte, avec la commande ‘more’ :
more nbParfait.res
on peut lire ainsi le contenu du fichier de sortie ‘nbParfait.res’.
Enfin, la création de fichiers de documentation ‘.html’ est effectuée par:
javadoc -private -author -version
*.java
Il suffit de double-cliquer sur le fichier ‘index.html’ dans le dossier de travail courant pour consulter cette documentation sous Windows.
4.2
Conclusion provisoire
--------------------------
On constate que plus la valeur du seuil maximal est élevé, plus on doit attendre pour voir les résultats... En effet, l’opérateur ‘modulo’ dans «i MOD j = 0» s’exécute en maintes reprises car il est situé à l’intérieur de deux boucles répétitives ‘POUR ... FPOUR’. Cette durée d’exécution sera étudiée lors de l’analyse de la complexité temporelle d’un algorithme.
Il reste aussi l’affichage complet de la décomposition (i.e. 6 = 1+2+3) à faire lors d’une prochaine extension via l’emploi d’un tableau ou d’une liste chaînée par auto-référence monolatère (i.e. unidirectionnelle) d’entiers par exemple (cf. Cours d’info. S2)...
EXERCICE (A TERMINER) :
-
Tracer
le schéma bloc condensé montrant l'envoi de message entre ces deux classes.
-
Adapter
les deux classes ci-dessus en employant des ENTIERS LONGS.
-
Etendre
l’algorithme ‘rechParfait()’
pour expliciter le contenu de la décomposition via l’emploi d’un tableau
approprié en employant aussi une fonction booléenne estParfait(D N: ENTIER).
Indication: cf.
fichiers
nbParfait.java et nbParfait_.java