Manipulation des tableaux

**kevinjumper** · 06/11/2014, 12h16

Bonjour,
je cherche vivement à terminer un exercice mais je butte sur la suite du programme à écrire:

écrire une fonction public static int[] troisPlusProches(int x, int y, int[] coordonneesHabitations),
qui retourne dans un tableau d’entiers les coordonnées des trois habitations les
plus proches du point de (x,y) donné en argument parmi toutes les habitations
de la commune (passée en argument). La tableau sera ordonné selon les mêmes
conventions que pour la tableau de coordonnées des habitations (cooordonnée en
x puis en y).
Il sera aussi ordonné de la coordonnée la plus proche à la plus distante.

Indication : Pour atteindre ce résultat, vous pouvez copier la tableau des coordonnées
dans un tableau temporaire tmp au moyen de l’instruction
System.arraycopy(coordonneesHabitations, 0, tmp, 0,coordonneesHabitations.length);

puis chercher trois fois le point le plus proche dans tmp. A chaque fois qu’un
point le plus proche aura été déterminé il faudra le remplacer par une point trop
éloigné pour être à nouveau candidat.

Vous prendrez la valeur 1000000 pour chacune de ces coordonnées.

**joel.drigo** · 06/11/2014, 12h21

Salut,

Et donc, sur quoi buttes-tu ? Quel est le code que tu as déjà écrit pour réaliser cette méthode ?

**kevinjumper** · 06/11/2014, 12h55

Envoyé par joel.drigo

Salut,

Et donc, sur quoi buttes-tu ? Quel est le code que tu as déjà écrit pour réaliser cette méthode ?

------------------------------------------------------------------------------------------------------
Salut,
Merci déjà de ton retour c'est sympa et surtout que j'aurai dû effectivement y associer mon bout de code que voici:

//ici il s'agit de calculer la distance entre 2 points du plan

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public static double calculerDistance(int x1, int y1, int x2, int y2)
	{  
		return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
	}
// ici, je retourne la position de l'habitation la plus proche du couple (x,y) donné
	public static int plusProche(int x, int y, int[] coordonneesHabitations)
	{
		int position = 0;	
		double min = Integer.MAX_VALUE;
 
		for(int i = 0; i<coordonneesHabitations.length -1; i++)
		{  
			for (int j = i+1; j<coordonneesHabitations.length -1; j++)
			{		
				if((i!=x)&&(j!=y))
				{
					double distmin = calculerDistance(x,coordonneesHabitations[i],y,coordonneesHabitations[j]);
					if(distmin<min)
					{	min = distmin;				
						position = i;
					}					
				} 
			 }
		   }
	      return position;	
	   }
	// cette partie est celle sur laquelle je butte, car il faut que je copie les données du tableau initiale dans un autre tableau et que je trie ce tableau en recherchant 3 fois le point le couple de point (abscisse et ordonnée) le plus proche du couple (x,y) et retourner le résultat dans un tableau.
Remarque: je n'ai pas terminé le code car je suis à court d'idée.
	   public static int[] troisPlusProches(int x, int y, int[] coordonneesHabitations)
	   {
		    //int position = 0;	
			double min = Integer.MAX_VALUE;
			int[] tmp = new int[0];
			System.arraycopy(coordonneesHabitations, 0, tmp, 0,
					coordonneesHabitations.length);
 
			for(int i = 0; i<tmp.length -1; i++)
			{  
				for (int j = i+1; j<tmp.length -1; j++)
				{		
					if((i!=x)&&(j!=y))
					{
						double distmin = calculerDistance(x,tmp[i],y,tmp[j]);
						if(distmin<min)
						{	min = distmin;				
							//position = i;							
 
						}					
					} 
				 }
			   }
		      return tmp;	
	   }

**joel.drigo** · 06/11/2014, 14h12

Déjà, on te demande de faire une méthode qui détermine les trois habitation les plus proches (classées de la plus proche à la plus éloignée), et on te précise même que le type de retour doit être un tableau de int (dans la signature : ...int[] troisPlusProches(int x, int y...).

Donc déjà commence par créer un tableau de taille 6 (pour 3 couples de coordonnées). Il te faudra un curseur (un index) pour enregistrer les différentes habitations trouvées.

Ensuite, il n'y a pas d'indication dans la façon dont sont stockées les coordonnées dans les tableaux, mais à priori, je pense que chaque couple (x, y) se succède, de cette manière : x0,y0,x1,y1,x2,y2... Donc ta double boucle n'est pas la bonne manière de parcourir les coordonnées : tu dois parcourir les x,y de 2 en 2 avec un :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
for(int index=0; index<coordonneesHabitations.length; index+=2) ) {
   int xhabitation = coordonneesHabitations[index];
   int yhabitation = coordonneesHabitations[index+1];
 
    ...
 
 
}

Ensuite, chaque fois que tu détermines une nouvelle distance minimum, tu stockes effectivement l'index de cette habitation (tu as mis le code en commentaire). Tu pourrais aussi stocker le x et y. Mais en stockant l'index, tu pourras directement appliquer la suggestion qu'on te donne pour éliminer les maisons déjà sélectionnées (en remplaçant leurs coordonnées dans le tableau temporaire par une valeur très grande (1000000)).

A la fin de la boucle, tu stockes les x, y correspond à l'index trouvé donc, dans le tableau à retourner en résultat, à la position curseur , tu écris 1000000 dans ces coordonnées dans le tableau temporaire, et tu incrémente le curseur, pour que la prochaine habitation trouvée puisse être stockée...

Evidemment, dans la boucle qui cherche la distance la plus petite, il faut ajouter un test pour ne pas prendre en compte les coordonnées supérieures ou égales à 1000000...

Il n'y a pas d'information au sujet du moyen d'indiquer le nombre de maisons (s'il est inférieur à 3), où alors j'ai mal lu, mais je suppose que le jeu de données fait qu'il y a toujours au moins 3 maisons dans le tableau paramètres.

**kevinjumper** · 06/11/2014, 14h59

Merci Joel,

mais pour être franc, je sollicite ton aide pour terminer ce code. j'ai déjà tester la fonction plus haut qui me retourne la position de l'habitation la plus proche du point (x,y) avec en données le tableau de coordonnées initial: int[] coordonneesHabitations = {9, 30, 18, 8, 3, 18, 25, 36};
Mais là avec tout ce que tu me dis, bien sûr qui pourrais m'aider à avancer, la méthode à écrire me rend un peu confus.

BR,
kevin.

**Nico02** · 06/11/2014, 15h12

Salut,

Il y a un problème dans l'appel de ta fonction de calcul de distance.

Toi tu écris -> calculerDistance(x,coordonneesHabitations[i],y,coordonneesHabitations[j]) ce qui est équivalent à calculerDistance(x1,x2,y1,y2)Or si on regarde la signature de ta méthode -> public static double calculerDistance(int x1, int y1, int x2, int y2) on voit que tes points ne correspondent pas aux paramètres que tu lui passes.

Pour le reste, je trouve déjà assez étrange de représenter des coordonnées dans un simple tableau d'entier. Un talbeau à 2 dimension serait bien plus adapter mais bon.. passons.

Du-coup je rejoins @joel.drigo sur la manière dont tu dois parcourir ton tableau en prenant les éléments 2 par 2.

Ensuite pour ce qui est de garder les 3 points les plus proches, je ne vois pas trop de manière élégante de faire dans la situation tel que tu nous la décris (paramètre d'entré, paramètre de sortie).

**kevinjumper** · 06/11/2014, 15h28

Salut Nico,

Merci pour ce retour.... disons en vérité qu'il s'agit d'un exercice que j'essaie de résoudre:

1.1 Introduction
Votre commune cherche le meilleur endroit pour installer sa décharge publique.
Elle souhaite que sa décharge soit la plus éloignée possible des habitations. Les
habitations sont repérées par leur coordonnées x et y sur un plan à deux dimensions.
Comme la commune a déjà une idée de l’endroit où elle aimerait placer
la décharge, elle souhaite vérifier que la distance entre la position souhaitée et la
plus proche des habitations soit raisonnable et la placer de façon optimale près de
l’endroit envisagé.

Il y a toujours un nombre pair d’entrées dans ce tableau. La convention adoptée
est que pour tout i pair correspondant à un indice valide du tableau : tab[i] est
la coordonnée x d’une habitation et tab[i+1] en est la coordonnée y.
Toutes les méthodes que vous définirez dans votre programme devront être
public et static

1.2 Calcul des distances
Dans le fichier fourni, définissez un méthode :
double calculerDistance(int x1, int y1, int x2, int y2)
qui calcule et retourne la distance entre les deux points (x1,y1) et (x2, y2)
passés en arguments.
Pour calculer la distance entre deux points (x1, y1) et (x2, y2), vous utiliserez
la formule suivante :p= (x1-x2)2 + (y1-y2)2
Indication : Pour représenter la distance la plus importante possible entre le point
choisi pour la décharge et un habitation, vous pourrez utiliser la constante Java
Integer.MAX_VALUE.

Voir l’exemple de déroulement plus bas pour des valeurs de test.

1.3 Habitation la plus proche
Complétez votre programme en définissant la méthode :
int plusProche(int x, int y, int[] coordonneesHabitations)
où coordonneesHabitations est un tableau de coordonnées pour les habitations
de la commune, tel que décrit plus haut. La méthode plusProche doit
retourner la position (dans le tableau coordonnesHabitations) de la paire
(xp; yp) de l’habitation la plus proche de point (x, y). Par exemple, si c’est la
deuxième habitation (12, 55) du tableau (33, 12, 12, 55, 12, 12),
la méthode doit retourner 1 (la numérotation commence à 0). Dans le cas où plusieurs
habitations seraient candidates, seule la première dans le tableau sera retenue.
Voir l’exemple de déroulement plus bas pour des valeurs de test.

1.4 Trois habitations les plus proches
Complétez votre programme en définissant une méthode supplémentaire :
int[] troisPlusProches(int x, int y, int[] coordonneesHabitations)

qui retourne dans un tableau d’entiers les coordonnées des trois habitations les
plus proches du point de (x,y) donné en argument parmi toutes les habitations
de la commune (passée en argument). La tableau sera ordonné selon les mêmes
conventions que pour la tableau de coordonnées des habitations (cooordonnée en
x puis en y).
Il sera aussi ordonné de la coordonnée la plus proche à la plus distante.
Indication : Pour atteindre ce résultat, vous pouvez copier la tableau des coordonnées
dans un tableau temporaire tmp au moyen de l’instruction

System.arraycopy(coordonneesHabitations, 0, tmp, 0,coordonneesHabitations.length);

puis chercher trois fois le point le plus proche dans tmp. A chaque fois qu’un
point le plus proche aura été déterminé il faudra le remplacer par une point trop
éloigné pour être à nouveau candidat. Vous prendrez la valeur 1000000 pour
chacune de ces coordonnées (nous supposerons qu’à cette distance on sort de la
commune).

1.5 Place optimale
Terminez enfin votre programme en définissant la fonction
int[] meilleurePlace(int x, int y, int[] coordonneesHabitations)
qui donne le centre de gravité du triangle définit par les trois habitations les plus
proches du point de (x,y).
Le tableau retourné sera donc un tableau à deux entrées dont la première sera la
coordonnée en x et la seconde la coordonnées en y du centre de gravité.
Ce « centre de gravité » représente le meilleur compromis pour les trois habitations
les plus proches. Si (x1,y1), (x2,y2) et (x3,y3) sont les points les plus
proches du point (x,y), les coordonnées (cx,cy) du centre de gravité seront :
cx = (x1 + x2 + x3) / 3
cy = (y1 + y2 + y3) / 3

Exemple de déroulement Cet exemple s’applique au tableau de coordonnées
d’habitations fourni, à savoir : int[] coordonneesHabitations = {9, 30, 18, 8, 3, 18, 25, 36};
Entrez la coordonnee x de la decharge: 10
Entrez le coordonnee y de la decharge: 15
--- Question 1 ---
Coordonnees de l’habitation la plus proche de la decharge :
(3,18) ; distance = 7.616 metres
--- Question 2 ---
Coordonnees des 3 habitations les plus proches de la decharge :
(10,15) est a :
7.616 de (3,18)
10.630 de (18,8)
15.033 de (9,30)
--- Question 3 ---
Coordonnees de la meilleure place pour la decharge :
(10,18)

**joel.drigo** · 06/11/2014, 15h44

On a bien compris l'exercice, surtout qu'on l'a vu dans une autre discussion, il y'a une semaine ou 2). Mais je n'ai pas l'intention de te donner le code tout fait : ce forum n'est pas là pour faire les exercices tout cuit à la place des autres. Il me semble que les indications que je t'ai données sont largement suffisantes pour écrire au moins un algorithme. Et les concepts Java pour l'encoder sont simples. Mais si tu as des questions sur des points en particulier, on pourra te guider.

**kevinjumper** · 07/11/2014, 08h05

Bonjour Joel,

C'est très logique. cependant, j'ai suivi quelque peu tes recommandations; j'ai pu terminer le programme avec succès.
Merci en tout cas pour votre support.

BR,
kevin.

**joel.drigo** · 07/11/2014, 08h32

Donc problème résolu ?

Manipulation des tableaux

Java

Discussions similaires

Partager

Partager