Discussion :

[Khalfe]

Bonjour;
Je cherche à transcrire unt algorithme en java

J'ai commencé l'interprétation mais je me demande à quoi correspond X.clé en java?
J'ai du mal à comprendre aussi element(E,i), correspond à une methode ou une class?
Aussi, à la fin j'ai un retour NIL que je comprends pas car la methode est sensé retourner je crois la valeur cherché ou la position?

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
 
public class Chercher {
 
	int E[] = { 1, 3, 7, 8, 4, 9, 18, 22, 23, 25, 20, 11, 26, 27, 31, 34, 36, 13 };
	int i0, i, X;
	int N = E.length;
	int d,R ;
 
	public int Chercher (int []E, int V) {
 
	  i0 = Math.round(N*V/R) ; 
	  i = i0 ; 
	  X = element(E,i);   //(N est la taille de E, R=36 est le nombre de clés possibles)
 
	  if(X < V) { d = 1;}
	  else { d = -1;}
 
	  while( i+d != i0 ){           // parcours tout E   ***** Ligne de comparaison  *****
 
	      if(X== V) return X;
	      i =  Math.floorMod(( i + d ), N) ;      // parcours tout E
	      X = element(E,i);
 
	  return (Integer) null;
	  }
	return V;
	}
 
	public int element(int[] E, int i) {
 
		return E[i];
	}
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
 
	}
 
}

[choukie12]

Bonjour,

Déjà pour commencer, tu n'as pas un enoncé? Car ce que tu donnes, n'est pas un algorithme pour moi, c'est déjà du code par endroit...
De plus, on ne sait pas ce que représente V... est ce l'élément à retrouver?

le X.clé n'a pas de sens, ca serait plutôt valeur...

A la base cette algorithm ne serait pas pour objective C ou autre?


Et au passage :

Code :

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

return (Integer) null;

Ca ne sert à rien de caster null.

Jérémy.

[Khalfe]

Bonjour,

Déjà pour commencer, tu n'as pas un enoncé? Car ce que tu donnes, n'est pas un algorithme pour moi, c'est déjà du code par endroit...
De plus, on ne sait pas ce que représente V... est ce l'élément à retrouver?

le X.clé n'a pas de sens, ca serait plutôt valeur...

A la base cette algorithm ne serait pas pour objective C ou autre?


Et au passage :

Code :

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

return (Integer) null;

Ca ne sert à rien de caster null.

Jérémy.

Merci Jérémy

En fait c'est un exercice dont voici l'énoncé, je voudrais le transcrire en code java,pour verifier les différente étapes d'exécution et le nombre de comparaison.
Soit l'algorithme de recherche séquentielle suivant:

[Drowan]

Comme indiqué par choukie, on ne comprend pas vraiment ce que représente tes variables. Essaye de leur donner des noms significatif. Même toi ça t'aidera à comprendre ce que tu fais.
Par exemple au lieu d'appeler ton array E appelle le elements et au lieu d'appeler leur nombre N = E.length appelle le numberOfElments = elements.lengthÇa t'éviteras aussi d'avoir à "sur"commenter ton code avec des choses comme //n représente le nombre de .... Si tes variables ont des noms clairs u te simplifieras la vie (ou au moins le développement).

Ensuite, qu'est sensé faire X = élément(E, i) dans ton algorithme ?
Si c'est retourner l’élément i du tableau E, pas besoin de créer une fonction pour ça. fais juste E[i]Et enfin, tu n'explique pas ce qu'est censé faire ton code. C'est sensé retourner quoi chercher(E, V) ? la position de V dans E ? C'est quoi V ?

[choukie12]

Hello,

Je crois que ca te donnerait quelque chose de ce genre la :

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
 
private static int chercher(int[] elements, int valATrouver){
        int nbrValeurs = elements.length;     // C'est le fameux N
        int i0 = Math.round((nbrValeurs*valATrouver)/36);   //
        int i = i0;
        int elementAtIndexI = elements[i];  // c'est le fameux X, et i-1, parce que le tableau commence à 1 dans l'algo mais en java c'est 0
        int d;
        if(elementAtIndexI < valATrouver) {
            d = 1;
        }else{
            d = -1;
        }
 
        while(i+d != i0){
            if(elementAtIndexI == valATrouver){
                return elementAtIndexI;
            }else {
                i = (i + d) % nbrValeurs;
                elementAtIndexI = elements[i];
            }
        }
        return 0;
    }

Et pour le nombre de boucles faites, tu peux ajouter un compteur dans ton while de ce style :

Code :

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

1
2
3
4
 
        int cpt = 1;
        ton while
        System.out.println(cpt++ + " fois");

Attention, le code n'est pas optimisé. De plus les variables sont assez dures à nommer correctement car l'algorithme est pas vraiment parlant...

Ensuite dans l’énoncé : notez que les positions commencent à 1, c'est pas pratique pour le java dont l'index de départ est toujours 0;


Jérémy

[Khalfe]

Merci Jeremy, j'ai essayé de l'executer mais , j'ai un resultat bizare, il ne trouve pas les valeurs 1, 22,23,20,13

Code :

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

1
2
3
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
	at Tri.Chercher.chercher(Chercher.java:25)
	at Tri.Chercher.main(Chercher.java:45)

et les nombres d’exécution(la valeur de cpt) me paraissent bizarre par ce que: chercher(E,3) cpt=3, chercher(E,7) cpt=2 chercher(E,9) cpt=4 ; chercher(E,11) cpt=9 ; chercher(E,26) cpt =2 fois; chercher(E,36) cpt=18. Sachant que le tableau E est le suivant:

Code :

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

int [] E = { 1,3,7,8,4,9,18,22,23,25,20,11,26,27,31,34,36,13};

Voici le code

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
 
package Tri;
public class Chercher {
	//int cpt = 1;
	 static int cpt = 1;
	private static int chercher(int[] elements, int valATrouver){
        int nbrValeurs = elements.length;     // C'est le fameux N
        int i0 = Math.round((nbrValeurs*valATrouver)/36);   //
        int i = i0;
        int elementAtIndexI = elements[i-1];  // c'est le fameux X, et i-1, parce que le tableau commence à 1 dans l'algo mais en java c'est 0
        int d;
 
        if(elementAtIndexI < valATrouver) {
            d = 1;
        }else{
            d = -1;
        }
 
        while(i+d != i0){
        	cpt++;
            if(elementAtIndexI == valATrouver){
                return elementAtIndexI;
            }else {
                i = (i + d) % nbrValeurs;
                elementAtIndexI = elements[i-1];
            }
        }
        return 0;
    }
 
	public int element(int[] E, int i) {
 
		return E[i];
	}
 
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		 int [] E = { 1,3,7,8,4,9,18,22,23,25,20,11,26,27,31,34,36,13};
		Chercher c=new Chercher();
 
		System.out.println(c.chercher(E,7));
		 System.out.println(cpt++ + " fois");
 
	}
 
}

Merci d"avance.

[choukie12]

Hello,

Alors écoute je pense qu'il y a un souci dans l'énoncé à ce niveau la :

notez que les positions commencent à 1

remplace les i-1 par de i, et ca fonctionne.
Car tu as 18 chiffres dans le tableau, donc ca veut dire que tes index du tableau vont de 0 à 17. Donc si tu fais i-1, quand ton expression : (i + d) % nbrValeurs; te renvoie 0, (quand i = 17 et que d = 1). ben tu vas essayer de récupérer l'élément en position -1, ce qui est pas possible d'ou l'exception que tu as :

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at Tri.Chercher.chercher(Chercher.java:25)
at Tri.Chercher.main(Chercher.java:45)

Donc il faut bien récupérer l'élément i, et non i-1;

PS : j'ai mis à jour le code dans mon commentaire juste avant.

Jérémy