Transcrire mon algorithme en Java et analyse de l'exécution de mon algorithme

Version imprimable

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:

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
 
	}
 
}

21/11/2018, 08h55
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:

return (Integer) null;

Ca ne sert à rien de caster null.

Jérémy.
21/11/2018, 16h22
Khalfe

Citation:

Envoyé par 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:

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:
21/11/2018, 16h24
Drowan

:salut:

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 ?

Hello,

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

Code:

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:

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

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:

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:

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

Voici le code

Code:

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.

21/11/2018, 21h53
choukie12

Hello,

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

Citation:

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 :

Citation:

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
22/11/2018, 16h38
Khalfe

Citation:

Envoyé par choukie12

Hello,

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

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 :

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

Merci beaucoup, finalement ça marche.