IFT1010 Programmation I

Département d'informatique et de
recherche opérationnelle

Hiver 2002


Accueil

Professeurs et
Démonstrateurs

Horaires et locaux

Notes de cours

Démonstrations
et devoirs

Examens

Liens utiles

Au sujet du
livre de cours

Consultez vos notes

Foire aux questions
(FAQ)

Démonstration 7: Classes et tableaux à une dimension


Pratique | Exercice Noté

Travail pratique (pas noté)

Extension du sujet de TP1

Étendre le sujet du travail pratique numéro 1 en écrivant une méthode qui permet la recherche d'une séquence de chiffres dans la grille et ce, dans n'importe quelle direction (haut, bas, droite, gauche, diagonales, ect).

Cette méthode doit prendre en argument un tableau qui contient la séquence à rechercher. L'appel suivant devrait donc permettre de rechercher dans la grille une occurrence de la séquence 5 7 4 4 7 et d'en indiquer, la (ou les) position(s) dans la grille, ainsi que le sens de lecture:

int [] sequence = {5,7,4,4,7};
chercheSequence(sequence);

Note: L'idée qui sera développée dans le cadre de la démonstration théorique est de passer en revue toutes les positions de départ possibles (le nombre de cases dans la grille), ainsi que toutes les directions (8 en fait).

Exercice noté (1 point)

Crible d'Eratosthène

Il existe un algorithme qui permet de déterminer tous les nombres premiers entre 1 et n; il est connu sous le nom de crible d'Eratosthène. L'idée est de dresser la liste de tous les entiers positifs jusqu'à n et de rayer progressivement tous les multiples.

  1. 1 n'est pas premier (merci :-)
  2. Commencer avec x égal à 2
  3. Rayer tous les multiples de x (pas x lui même)
  4. Sélectionner le prochain nombre non rayé x: il est premier.
    • Si x est supérieur à la racine carrée de n, alors tous les nombres qui restent dans le crible sont premiers;
    • Sinon aller en 3
Écrire une classe Eratosthene qui admet au moins les méthodes suivantes:
  • Un constructeur qui prend en argument l'entier n qui est l'entier au delà duquel nous ne chercherons plus de nombre premier.
  • Un constructeur par défaut (qui ne prend pas d'argument) et qui correspond à un appel implicite du constructeur avec comme entier 1000.
  • Une méthode toString qui affiche la liste des nombres premiers trouvés
  • Une méthode int getNbPremiers() qui retourne le nombre de premiers trouvés par l'application de l'algorithme.
  • Une méthode boolean hasMorePremiers() qui retourne true si un nombre premier n'a pas encore été récupéré par un appel à la méthode qui suit.
  • Une méthode int getNextPremier() qui retourne le prochain nombre premier non encore récupéré. Cette méthode doit traité le cas où l'utilisateur de la classe fait un appel à cette méthode alors que tous les nombres premiers ont déjà été récupérés (un message d'erreur est suffisant)
  • Une méthode void rewind() qui repositionne le premier nombre premier "non consommé" sur le premier nombre non rayé du crible (le prochain nombre premier retourné par int getNextPremier() devrait donc être 2).
Détails d'implémentation: Votre classe devrait contenir un tableau (le crible) dont la taille sera connue au moment de la construction. De manière naturelle, cette table devrait être une table de booléens (rayé ou pas rayé). Le moment idéal pour appliquer l'algorithme du crible est à la construction: définissez une méthode privée qui implémente l'algorithme et que vous appelerez depuis le/les constructeur(s). Voici un exemple de programme qui utilise la classe que vous devez écrire: TestCrible.java.

Pour remettre votre programme: remise ift1010 demo07 Eratosthene.java

On ne vous demande donc pas de remettre TestCrible.java.

Prenez note que chaque exercice noté est à remettre individuellement.



Dernière mise à jour : Mon Mar 18 08:16:56 EST 2002
dift1010@iro.umontreal.ca