Correction du TD n°6

Exercice 1

Implanter une méthode de recherche de l'indice de la valeur minimale d'un intervale d'un tableau d'entiers compris entre les indices deb et fin inclus.

/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class RechercheIndiceMinimum {
static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
/* Fonction d'affichage de tous les entiers contenus */
/* dans un tableau d'entiers */
public static void affichageTableau(int [] t) {
int i;
/* Pour toutes les valeurs d'indice 0 a t.length-1 inclus */
for ( i = 0 ; i < t.length ; i++ )
System.out.println(t[i]);
}
/* Fonction d'initialisation de tous les entiers */
/* contenus dans un tableau d'entiers */
/* avec une valeur tiree au sort entre 0 et max inclus */
public static void initialisationTableau(int [] t,int max) {
int i;
/* Pour toutes les valeurs d'indice 0 a t.length-1 inclus */
for ( i = 0 ; i < t.length ; i++ ) {
/* Initialisation de t[i] avec un entier tire */
/* au hasard entre 0.0 (inclu) et max+1 (exclu) */
t[i] =(int) ((max+1)*Math.random()); }
}
/* Fonction de recherche de l'indice de la valeur */
/* minimum d'un tableau pour les seules valeurs */
/* allant de l'indice deb a l'indice fin inclus */
public static int indiceMinimum(int [] t,int deb,int fin) {
/* Declaration et initialisation a t[deb] de la variable */
/* de stockage de l'indice recherche */
int imin = deb;
int i;
/* Pour toutes les valeurs d'indice 0 a t.length-1 inclus */
for ( i = deb+1 ; i <= fin ; i++ )
/* Si la valeur d'indice i est plus petite que la valeur */
/* d'indice imin */
if ( t[i] < t[imin] )
imin = i;
return(imin);
}
/* Fonction principale */
public static void main(String [] args) throws IOException {
/* Definition et allocation d'un tableau de 10 entiers */
/* tires au sort entre 0 et 5 */
int [] tab = new int[10];
int indice;
int indiceDebut;
int indiceFin;
initialisationTableau(tab,100);
System.out.println("Le tableau contient les valeurs suivantes:");
/* Appel a la fonction d'affichage */
affichageTableau(tab);
System.out.println();
/* Lecture clavier de l'indice de debut de recherche */
System.out.println("Indice de debut de recherche:");
indiceDebut = Integer.valueOf(flux.readLine()).intValue();
/* Lecture clavier de l'indice de fin de recherche */
System.out.println("Indice de fin de recherche:");
indiceFin = Integer.valueOf(flux.readLine()).intValue();
/* Appel a la fonction de recherche */
indice = indiceMinimum(tab,indiceDebut,indiceFin);
System.out.println("L'indice de la valeur minimale est "+indice);
System.out.println("et correspond a la valeur "+tab[indice]);
}
}

RechercheIndiceMinimum.java

Exercice

Implanter la méthode de recherche des nombres premiers par le crible d'Eratosthène.
Le but est de déterminer si chaque nombre entier entre 1 et n est premier ou non.
La méthode développée rendra un tableau de n booléens.

/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class CribleEratosthene {
static BufferedReader flux = new BufferedReader(new InputStreamReader(System.in));
/* Fonction d'affichage de tous les booleens contenus */
/* dans un tableau de booleens */
public static void affichage(boolean [] t) {
int i;
/* Pour toutes les valeurs d'indice 0 a t.length-1 inclus */
for ( i = 0 ; i < t.length ; i++ )
System.out.println(t[i]);
}
/* Fonction d'affichage de tous les entiers codes comme */
/* premiers (true) dans un tableau de booleens */
public static void affichageNombresPremiers(boolean [] t) {
int i;
/* Pour toutes les valeurs d'indice 0 a t.length-1 inclus */
for ( i = 0 ; i < t.length ; i++ )
if ( t[i] )
System.out.println(i+1);
}
/* Fonction d'initialisation a true des booleens */
/* contenus dans un tableau de booleens */
/* sauf la premier a false */
public static void initialisationTableau(boolean [] t) {
int i;
t[0] = false;
/* Pour toutes les valeurs d'indice 1 a t.length-1 inclus */
for ( i = 1 ; i < t.length ; i++ ) {
t[i] = true; }
}
/* Fonction de calcul d'un tableau de booleens */
/* codant les nombres premiers (true pour premier, */
/* false pour non premier) */
public static boolean [] realiseCribreEratosthenet(int n) {
/* Declaration et allocation d'un tableau de n booleens */
boolean [] tab = new boolean[n];
/* Initialisation du tableau tab */
initialisationTableau(tab);
/* Calcul de la valeur limite de criblage */
int limite =(int) Math.sqrt(n);
/* Pour tous les entiers de 2 a limite */
for ( int i = 2 ; i <= limite ; i++ )
/* Si i est un nombre premier */
if ( tab[i-1] )
/* Tous les multiples de i entre 2*i et n inclus ne sont pas */
/* des nombres premiers */
for ( int j = 2*i ; j <= n ; j += i )
tab[j-1] = false;
return(tab);
}
/* Fonction principale */
public static void main(String [] args) throws IOException {
int nb;
boolean [] tableau;
/* Lecture clavier du nombre jusqu'ou realiser le criblage */
System.out.println("Valeur limite jusqu'ou rechercher:");
nb = Integer.valueOf(flux.readLine()).intValue();
/* Realisation du crible */
tableau = realiseCribreEratosthenet(nb);
System.out.println();
System.out.println("Tableau de booleens obtenu");
/* Affichage du tableau de booleens brut */
affichage(tableau);
System.out.println();
System.out.println("Nombres premiers entre 2 et "+nb);
/* Affichage des nombres premiers codes dans un tableau */
/* de booleens */
affichageNombresPremiers(tableau);
}
}

CribleEratosthene.java

Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr