6 réponses
garion28
Messages postés
1543
Date d'inscription
mardi 16 juin 2009
Statut
Membre
Dernière intervention
3 avril 2011
395
29 juin 2009 à 13:46
29 juin 2009 à 13:46
c'est quoi exactement une occurence ?
KX
Messages postés
16668
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mars 2023
3 004
29 juin 2009 à 14:08
29 juin 2009 à 14:08
Une occurrence c'est le nombre d'apparition, ici il s'agit en fait de calculer le nombre de cellules qu'il y a entre la première fois où une valeur apparait, et la deuxième fois où celle-ci apparait.
Une question cependant : avec quel langage ?
Une question cependant : avec quel langage ?
je vous remercie de m'avoir répondu. Il ne s'agit pas d'un langage en particulier. Il s'agit des structures de données. C'est à dire de l'algorithme pure et simple avec des listes chainées.. Par ailleurs je fais du java en apprentissage.
Giorgiolino
Messages postés
251
Date d'inscription
vendredi 15 mai 2009
Statut
Contributeur
Dernière intervention
2 mars 2015
52
29 juin 2009 à 15:08
29 juin 2009 à 15:08
Bonjour,
voici une proposition d'algorithme pour toi, essaye d'en comprendre le fonctionnement.
Pourquoi "-1" ?
Parce qu' entre la 2 et la 4 par exemple il n'y a pas "4 - 2" (soit 2) cellules
mais plutôt "4 - 2 -1" (soit 1) cellule.
Ce même algorithme te permettra même de trouver le nombre de cellules
entre les occurrences de ton choix (si elles existent), par exemple la
2ème et la 4ème.
Il te suffira alors de changer j<3 par j<5.
Bon courage.
voici une proposition d'algorithme pour toi, essaye d'en comprendre le fonctionnement.
val = mavaleur // valeur dont on cherche le nombre d'occurrences)
nb_Cell = 0 // nombre de cellules entre la 1ère et la 2ème occurrence
i = 0 //indice de parcours de la liste qui donne aussi la position
j = 1 //j est l'indice de l'occurence de "mavaleur"
Tant que (pas fin de la liste et j<3)
{
Si (valeur[i] = val)
{
position[j] = i
j = j+1
/*
Si on trouve une occurence, on passe à la suivante,
sinon on ne fait rien.
*/
}
i = i+1
/*
On parcourt toujours le tableau, que l'on ait trouvé
une occurence ou pas (tant qu'on n'est pas à la 3ème bien sûr)
*/
}
nb_Cell = position[2] - position[1] - 1
Pourquoi "-1" ?
Parce qu' entre la 2 et la 4 par exemple il n'y a pas "4 - 2" (soit 2) cellules
mais plutôt "4 - 2 -1" (soit 1) cellule.
Ce même algorithme te permettra même de trouver le nombre de cellules
entre les occurrences de ton choix (si elles existent), par exemple la
2ème et la 4ème.
Il te suffira alors de changer j<3 par j<5.
Bon courage.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
KX
Messages postés
16668
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
17 mars 2023
3 004
29 juin 2009 à 16:19
29 juin 2009 à 16:19
Il y a un gros problème avec ton code Giorgiolino, c'est que tu traites un tableau alors que espe semble plutôt chercher du code avec des listes chainées...
Je propose ce code (en Pascal) qui doit pas être trop mal :
Je fais une fonction qui calcule le nombre de maillons parcouru avant de trouver `val` dans la liste, et qui transmet en paramètre le pointeur de cette position.
Avec la même fonction mais en partant du deuxième pointeur, j'en déduis le deuxième "indice" qui me permet de faire le calcul de distance.
Remarque : je propage un "-1" d'erreur si je ne trouve pas deux éléments de valeur `val`
Je propose ce code (en Pascal) qui doit pas être trop mal :
Je fais une fonction qui calcule le nombre de maillons parcouru avant de trouver `val` dans la liste, et qui transmet en paramètre le pointeur de cette position.
Avec la même fonction mais en partant du deuxième pointeur, j'en déduis le deuxième "indice" qui me permet de faire le calcul de distance.
Remarque : je propage un "-1" d'erreur si je ne trouve pas deux éléments de valeur `val`
type PListe=^ListeChainee; // pointeurs sur un type ListeChainee
ListeChainee=record
v:integer; // on considère des valeurs entières
suiv:PListe; // pointeur vers le maillon suivant
end;
function PremiereOccurrence(p:PListe; var q:PListe; val:integer):integer; // q est le pointeur dont on donne l'indice en résultat
var n:integer;
begin
if p=nil then begin
q:=nil;
result:= -1 // on a plus aucun élément dans la liste
end
else begin
if p^.v=val then begin
q:=p;
result:=0; // élément 0 : 1er élément
end
else begin
n:=PremiereOccurrence(p^.suiv,q,val);
if n= -1 then result:=-1
else result:=n+1;
end;
end;
end;
function Distance(var p:PListe; val:integer):integer;
var q,r:PListe; n1,n2:integer;
begin
n1:=PremiereOccurrence(p,q,val); // n1 : la première occurence
n2:=PremiereOccurrence(q,r,val); // n2 : la deuxième occurence
if (n2= -1) then result:= -1 // il n'y a pas 2 éléments `val` dans la liste
else result:=n2-n1-1; // -1 : voir l'explication de Giorgiolino
end;
blux
Messages postés
24877
Date d'inscription
dimanche 26 août 2001
Statut
Modérateur
Dernière intervention
24 mars 2023
3 311
29 juin 2009 à 16:34
29 juin 2009 à 16:34
Salut,
oui, mais en fait la demande porte sur de l'algo, pas sur un langage spécifique.
Donc, la réponse de Giorgiolino est tout à fait valable, pour peu que l'on suppose qu'une liste chainée peut être un tableau (dont le parcours séquentiel donne le même résultat que le parcours d'une liste).
oui, mais en fait la demande porte sur de l'algo, pas sur un langage spécifique.
Donc, la réponse de Giorgiolino est tout à fait valable, pour peu que l'on suppose qu'une liste chainée peut être un tableau (dont le parcours séquentiel donne le même résultat que le parcours d'une liste).