Correction du TD n°5
Ecrire une méthode Java qui teste si une chaîne de caractères stockée dans un tableau de caractères est un palindrome.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class TestPalindrome {
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(char [] t) {
int i;
/* Pour toutes les valeurs d'indice 0 a t.length-1 inclus */
for ( i = 0 ; i < t.length ; i++ )
System.out.print(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(char [] t) {
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] =(char) (97+2*Math.random()); }
}
/* Fonction de test si un tableau de caracteres */
/* representant une chaine de caracteres */
/* est un palindrome */
public static boolean testPalindrome(char [] t) {
/* Indice de parcours des couples de caracteres */
int i = 0;
/* Booleen resultat initialise a vrai */
boolean res = true;
/* Tant que tous les couples de catacteres n'ont pas ete */
/* verifies et que l'on a pas conclu trouve de couples */
/* de caracteres differents */
while ( ( i < t.length/2 ) && res ) {
/* Si les caracteres d'indices i et t.length-1-i different, */
/* res passe a faux pour interrompre le tant que */
if ( t[i] != t[t.length-1-i] )
res = false;
/* Increment de i de 1 pour passer au couple */
/* de caracteres suivant */
i++; }
return(res);
}
/* Fonction principale */
public static void main(String [] args) throws IOException {
/* Definition et allocation d'un tableau de 4 caracteres */
/* tires au sort entre 0 et 5 */
char [] tab = new char[4];
initialisationTableau(tab);
System.out.println("Le tableau contient les caracteres suivants:");
/* Appel a la fonction d'affichage */
affichageTableau(tab);
System.out.println();
/* Affichage du resultat de l'appel a la fonction de test */
System.out.println(testPalindrome(tab));
}
}
Exercice 2 - version n°1 
Ecrire une méthode Java qui réorganise un tableau d'entiers de telle manière que tous les nombres pairs soient regroupés au début du tableau et soient suivis les nombres impairs.
Cette version implante une solution non optimisée où 2 tableaux auxiliaires sont
utilisés pour héberger temporairement les valeurs paires pour le premier et les valeurs
impaires pour le second. Ces deux tableaux sont dimensionnés à la valeur maximale
possible : la taille de t.
Une fois qu'ils contiennent toutes les valeurs de t, ces deux tableaux sont fusionnés par
recopie dans le tableau t.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class TriageTableau {
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 reorganisation d'un tableau d'entiers pour */
/* placer toutes les valeurs paires aux petits indices */
/* et les valeurs impaires aux indices superieurs */
public static void triageTableau(int [] t) {
/* Declaration et allocation de deux tableaux d'entiers */
/* auxiliaires destines a recueillir des valeurs paires */
/* et impaires (dimensionnes a la taille de t) */
int [] tpr = new int[t.length];
int [] tmp = new int[t.length];
/* Declaration et initialisation a 0 de deux compteurs */
/* pour les valeurs paires et impaires */
int cptpr = 0;
int cptmp = 0;
int i;
/* Pour toutes les valeurs d'indice 0 a t.length-1 inclus */
for ( i = 0 ; i < t.length ; i++ )
/* Suivant la parite de la valeur d'indice i du tableau t, */
/* copie de cette valeur dans tpr ou tmp et mise a jour */
/* du compteur correspondant */
if ( (t[i]%2) == 0 ) {
tpr[cptpr] = t[i];
cptpr++; }
else {
tmp[cptmp] = t[i];
cptmp++; }
/* Report dans t de l'integralite des valeurs de tpr */
for ( i = 0 ; i < cptpr ; i++ )
t[i] = tpr[i];
/* Report dans t de l'integralite des valeurs de tmp */
/* a la suite des valeurs reportees depuis tpr */
for ( i = 0 ; i < cptmp ; i++ )
t[i+cptpr] = tmp[i];
}
/* 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];
initialisationTableau(tab,5);
System.out.println("Le tableau contient les valeurs suivantes:");
/* Appel a la fonction d'affichage */
affichageTableau(tab);
System.out.println();
/* Reorganisation de tab par appel a triageTableau */
triageTableau(tab);
/* Nouvel affichage de tab (reorganise) par appel */
/* a la fonction d'affichage */
affichageTableau(tab);
}
}
Exercice 2 - version n°2
Ecrire une méthode Java qui réorganise un tableau d'entiers de telle manière que tous les nombres pairs soient regroupés au début du tableau et soient suivis les nombres impairs.
Cette version implante une solution optimisée de la version n°1 où un seul tableau
auxiliaire est utilisé pour héberger temporairement les valeurs paires aux indices bas
et les valeurs impaires aux indices hauts. Ce tableau est dimensionné à la même taille
que t.
Une fois qu'il contient toutes les valeurs de t, ce tableau est recopié dans le tableau
t.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class TriageTableau2 {
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 reorganisation d'un tableau d'entiers pour */
/* placer toutes les valeurs paires aux petits indices */
/* et les valeurs impaires aux indices superieurs */
public static void triageTableau(int [] t) {
/* Declaration et allocation d'un tableaux d'entiers */
/* auxiliaire destine a recueillir des valeurs paires */
/* et impaires (dimensionnes a la taille de t) */
int [] tmp = new int[t.length];
/* Declaration et initialisation d'un compteur entier */
/* donnant l'indice de la premiere place disponible */
/* dans le tableau tmp */
int cpprem = 0;
/* Declaration et initialisation d'un compteur entier */
/* donnant l'indice de la derniere place disponible */
/* dans le tableau tmp */
int cpdern = t.length-1;
int i;
/* Pour toutes les valeurs d'indice 0 a t.length-1 inclus */
for ( i = 0 ; i < t.length ; i++ )
/* Si la valeur d'indice i est paire, elle est copiee */
/* dans tmp a la premiere place disponible et cptpr est */
/* ajuste, sinon elle est copiee a la derniere place */
/* disponible et cptmp est ajuste */
if ( (t[i]%2) == 0 ) {
tmp[cpprem] = t[i];
cpprem++; }
else {
tmp[cpdern] = t[i];
cpdern--; }
/* Report dans t de l'integralite des valeurs de tmp */
for ( i = 0 ; i < t.length ; i++ )
t[i] = tmp[i];
}
/* 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];
initialisationTableau(tab,5);
System.out.println("Le tableau contient les valeurs suivantes:");
/* Appel a la fonction d'affichage */
affichageTableau(tab);
System.out.println();
/* Reorganisation de tab par appel a triageTableau */
triageTableau(tab);
/* Nouvel affichage de tab (reorganise) par appel */
/* a la fonction d'affichage */
affichageTableau(tab);
}
}
Exercice 2 - version n°3
Ecrire une méthode Java qui réorganise un tableau d'entiers de telle manière que tous les nombres pairs soient regroupés au début du tableau et soient suivis les nombres impairs.
Cette version implante une solution sans utilisation d'un tableau auxiliaire.
Elle travaille par double parcours concourants du tableau depuis le debut vers la fin à
la recherche des valeurs impaires et depuis la fin vers le début à la recherche des
valeurs paires avec permutation entre chaque couple de valeurs (impaire, paire) jusqu'à
ce que les deux indices de parcours se soient croisés.
Il faut aussi tenir compte dans le traitement du fait qu'il est possible de ne plus
trouver de valeur impaire ou de valeur paire.
/* Auteur: Nicolas JANEY */
/* nicolas.janey@univ-fcomte.fr */
/* Fevrier 2005 */
import java.io.*;
public class TriageTableau3 {
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 reorganisation d'un tableau d'entiers pour */
/* placer toutes les valeurs paires aux petits indices */
/* et les valeurs impaires aux indices superieurs */
public static void triageTableau(int [] t) {
/* Declaration et initialisation d'une variable entiere */
/* de recherche de l'indice de la premiere valeur impaire */
/* du tableau t */
int ipr = 0;
/* Declaration et initialisation d'une variable entiere */
/* de recherche de l'indice de la derniere valeur */
/* paire du tableau t */
int imp = t.length-1;
/* Variable auxiliaire de permutation */
int aux;
/* Tant qu'une les deux indices ne se sont pas croises */
while ( ipr < imp ) {
/* Recherche par parcours a partir de l'indice donne par ipr */
/* de l'indice de la premiere valeur impaire du tableau t */
while ( ( t[ipr]%2 == 0 ) && ( ipr < t.length ) )
ipr++;
/* Recherche par parcours en arriere a partir de l'indice */
/* donne par imp de l'indice de la premiere valeur paire */
/* du tableau t */
while ( ( t[imp]%2 == 1 ) && ( imp >= 0 ) )
imp--;
/* Si une permutation doit etre realisee */
if ( ipr < imp ) {
aux = t[ipr];
t[ipr] = t[imp];
t[imp] = aux; } }
}
/* 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];
initialisationTableau(tab,5);
System.out.println("Le tableau contient les valeurs suivantes:");
/* Appel a la fonction d'affichage */
affichageTableau(tab);
System.out.println();
/* Reorganisation de tab par appel a triageTableau */
triageTableau(tab);
/* Nouvel affichage de tab (reorganise) par appel */
/* a la fonction d'affichage */
affichageTableau(tab);
}
}
Auteur: Nicolas JANEY
UFR Sciences et Techniques
Université de Besançon
16 Route de Gray, 25030 Besançon
nicolas.janey@univ-fcomte.fr