Trouver valeurs min et max de x et y ?

Version imprimable

16/01/2008, 12h05
innova

Trouver valeurs min et max de x et y ?

Bonjour,

Je souhaite résoudre sous forme soit d'ordinnogramme et/ou pseudo-code le problème suivant :

J'ai un fichier qui contient des occurences x et y et je ne connais pas la longueur du fichier.

Je souhaite trouver le nombre de valeurs minimales et maximales pour x et y.

Il est à noter que l'on ne peut pas utiliser de formules de math comme la factorielle,etc...

Je débute dans l'analyse et j'ai donc peu d'expérience...

Ce serait bien utile...

Pourriez-vous m'aider ?

Merci d'avance.
++
16/01/2008, 13h05
ToTo13

Bonjour,

Citation:

Envoyé par innova

Je souhaite trouver le nombre de valeurs minimales et maximales pour x et y

Qu'entend tu exactement par "le nombre de valeurs ..." ?
Est ce que tu souhaites :
- savoir combien d'occurence contient ton fichier ?
- savoir qu'elles sont les valeurs min et max pour x et y ?
- Qu'elle est le nombre de valeurs prisent par x et y ?
16/01/2008, 14h52
innova

Citation:

Envoyé par ToTo13

Bonjour,

Qu'entend tu exactement par "le nombre de valeurs ..." ?
Est ce que tu souhaites :
- savoir combien d'occurence contient ton fichier ?
- savoir qu'elles sont les valeurs min et max pour x et y ?
- Qu'elle est le nombre de valeurs prisent par x et y ?

Bonjour,

Merci déjà de me répondre...

Je ne sais pas vraiment...attention on peut pas utiliser de système min et max car le prof dit que c trop facile et il faut d'abord trier le fichier...

Pourrais-tu stp réaliser l'ordinnogramme des trois cas de figures si tu veux bien ?

J'ai un exam très prochainement et c'est le type de question et pour étudier ce serait bien de partir sur de bonnes bases.

Je te remercie d'avance.
Bien amicalement.
++
16/01/2008, 17h16
edfed

hé bein tot13, t'aime bien repondre aux questions avec une autre question toi... tu serai pas de St Tronc par hazard?

pour savoir le min et le max d'une occurence, il faut memoriser ces valeurs, et les tester a chaque fois, ensuite, pour savoir combien de fois apparait un min ou un max, pendant la phase de recherche de valeur min max, on peu incrementer un compteur et lister les occurences.
16/01/2008, 17h29
innova

Citation:

Envoyé par edfed

hé bein tot13, t'aime bien repondre aux questions avec une autre question toi... tu serai pas de St Tronc par hazard?

pour savoir le min et le max d'une occurence, il faut memoriser ces valeurs, et les tester a chaque fois, ensuite, pour savoir combien de fois apparait un min ou un max, pendant la phase de recherche de valeur min max, on peu incrementer un compteur et lister les occurences.

Bonjour,

Tu sais comment il faut faire ?

Tu pourrais m'aider stp en me montrant l'algorithme ?

Je panique c l'exam bientot et là j'aimerais démarrer avec un bon exemple !

Je te remercie d'avance.
++
16/01/2008, 17h41
edfed

si ton fichier est de taille inconnue, on ne peu rien pour toi.
par contre, s'il y a un moyen de savoir quand c'eszt la fin du fichier, ça change tout.

definir 4 tampons, Xmin, Xmax, Ymin, Ymax, initialisés a zero, ensuite, parcourir le fichier, et chauqe fois qu'on rencontre une valeur de X ou de Y, on teste avec les min max, si le record est battu, on l'inscrit dans les min max

chaque fois que le record est battu, il faut le mettre a jour.

pour ce qui est du nombre d'occurences, il faut ajouter 4 compteurs, XmaxN, XminN, YmaxN, YminN
chaque fois que le record est battu, il faut remettre a 1 le compteur correspondant, chaque fois qu'une occurence est egale au record, il faut incrementer le compteur.

puis pour ce qui est du listing des occurences, il faut un tableau dynamique ou une pile, chauqe fois qu'une occurence = record, on l'empile, si le record est battu, on vide la pile et on empile le nouveau record... en supposant que c'est ce que tu as besoin de faire... car il est vrai que la question de depard n'est pas claire.
16/01/2008, 17h47
innova

Citation:

Envoyé par edfed

si ton fichier est de taille inconnue, on ne peu rien pour toi.
par contre, s'il y a un moyen de savoir quand c'eszt la fin du fichier, ça change tout.

definir 4 tampons, Xmin, Xmax, Ymin, Ymax, initialisés a zero, ensuite, parcourir le fichier, et chauqe fois qu'on rencontre une valeur de X ou de Y, on teste avec les min max, si le record est battu, on l'inscrit dans les min max

chaque fois que le record est battu, il faut le mettre a jour.

pour ce qui est du nombre d'occurences, il faut ajouter 4 compteurs, XmaxN, XminN, YmaxN, YminN
chaque fois que le record est battu, il faut remettre a 1 le compteur correspondant, chaque fois qu'une occurence est egale au record, il faut incrementer le compteur.

puis pour ce qui est du listing des occurences, il faut un tableau dynamique ou une pile, chauqe fois qu'une occurence = record, on l'empile, si le record est battu, on vide la pile et on empile le nouveau record... en supposant que c'est ce que tu as besoin de faire... car il est vrai que la question de depard n'est pas claire.

re,

Sorry pour les messages privés....

Ok mais normalement on peut pas utiliser de variable min et max car le prof dit que c trop facile....

Comment faire alors ?

Merci encore pour ton aide !
++
16/01/2008, 17h58
pseudocode

Citation:

Envoyé par innova

Ok mais normalement on peut pas utiliser de variable min et max car le prof dit que c trop facile....

?? 8O

T'es sûr qu'il n'a pas plutot dit: "vous n'avez pas le droit d'utiliser les FONCTIONS max(a,b,...) et min(a,b,...)" ?
16/01/2008, 18h01
innova

Citation:

Envoyé par pseudocode

?? 8O

T'es sûr qu'il n'a pas plutot dit: "vous n'avez pas le droit d'utiliser les FONCTIONS max(a,b,...) et min(a,b,...)" ?

Bonjour,

C'est ptet bien cela ;-(

Tu pourrais faire éventuellement une ébauche du prog stp?

Merci d'avance.
++

En voila une implémentation en Java, de tête et meme pas testé, mais ca devrait etre bon...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
 
int[] list = new int[] {2,8,41,63,1,58,31,12,1,10,63,2,7};
 
int min=list[0], minocc=0;
int max=list[0], maxocc=0;
 
for(int i:list) {
	if (i==min) {minocc++;}
	if (i<min)  {min=i;minocc=1;}
	if (i==max) {maxocc++;}
	if (i>max)  {max=i;maxocc=1;}
}

16/01/2008, 18h18
droggo

Fio,

Citation:

Envoyé par innova

re,

bah première année...c'est le début tout simplement !

++

Ben oui, et ce n'est pas en faisant faire par d'autres ton travail que tu apprendras.

Tu as toutes les pistes nécessaires et suffisantes. :)
16/01/2008, 18h49
ToTo13

Bonsoir

Citation:

Envoyé par innova

Je ne sais pas vraiment...attention on peut pas utiliser de système min et max car le prof dit que c trop facile et il faut d'abord trier le fichier...

Citation:

Envoyé par edfed

... car il est vrai que la question de depard n'est pas claire.

C'est pour cela qu'avant de répondre je demande à ce que le problème soit clairement posé pour que tous le monde puisse répondre clairement. Ca évite un tas de réponses inadaptées.

Sinon
- d'un point de vue algorithmique, la réponse de PseudoCode est très bien.
- pour ce qui est de savoir si on est à la fin d'un fichier, généralement la majorité des langages avancés (C, C++, Java, ...) proposent des méthodes pour savoir si on a réussit à lire ou/et si on est à la fin du fichier.
16/01/2008, 19h19
pseudocode

Citation:

Envoyé par ToTo13

- d'un point de vue algorithmique, la réponse de PseudoCode est très bien.

cool... j'ai eu quelle note ?

Citation:

C'est pour cela qu'avant de répondre je demande à ce que le problème soit clairement posé pour que tous le monde puisse répondre clairement. Ca évite un tas de réponses inadaptées.

Oui, d'autant plus que l'énoncer laisse plus entrevoir un exercice d'implémentation, qu'un exercice d'algorithmie.

Citation:
Envoyé par pseudocode
En voila une implémentation en Java, de tête et meme pas testé, mais ca devrait etre bon...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 int[] list = new int[] {2,8,41,63,1,58,31,12,1,10,63,2,7}; int min=list[0], minocc=0; int max=list[0], maxocc=0; for(int i:list) { if (i==min) {minocc++;} if (i<min) {min=i;minocc=1;} if (i==max) {maxocc++;} if (i>max) {max=i;maxocc=1;} }
Bonsoir,

Merci de cet excellent code java !

Je ne connais pas encore ce langage.

Excuse-moi mais pourrais-tu le traduire en pseudo-code ?

Merci encore bcp de ton aide car qd on est débutant c pas évident !

++

16/01/2008, 22h31
edfed

je sais pas, mais ça ressemble pas mal a du pseudo code le java...
si avec tout ce qu'on a posté tu n'y arrives pas, bein...pense a une eventuelle reorientation..
tu sais, defois, il suffit d'eteindre le pc, de prendre une feuille blanche et de faire des dessins pour comprendre....
l'exemple java est plus que simple a comprendre, alors que je ne code pas en java, c'est quoi java?
ps:(pour les moderateurs)
ce n'est pas sarcastique, c'est objectif et serieux qui pourra aider notre ami à comprendre qu'un code source, si on sais pas le lire, ça sert a rien...

Citation:

Envoyé par innova

Merci de cet excellent code java !

Je ne connais pas encore ce langage.

Ca viendra (sauf si C# le mange avant).
Quel autre langage tu connais ?

Citation:

Excuse-moi mais pourrais-tu le traduire en pseudo-code ?

Hum... ce code Java est la transcription de l'algo donné par "edfed".
Je veux bien tenter une traduction dans un pseudo-langage:
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 list: LISTE<VALEUR> min,max: VALEUR minocc,maxocc: ENTIER min <- premierElement(list) minocc <- 0 max <- premierElement(list) maxocc <- 0 TANT QUE list est non vide FAIRE i <- extraireElement(list) SI i est egal a min ALORS minocc <- minocc+1 FIN SI SI i est inférieur a min ALORS min <- i minocc <- 1 FIN SI SI i est egal a max ALORS maxocc <- maxocc+1 FIN SI SI i est supérieur a max ALORS max <- i maxocc <- 1 FIN SI FIN TANT QUE

16/01/2008, 22h34
innova

Citation:

Envoyé par edfed

je sais pas, mais ça ressemble pas mal a du pseudo code le java...
si avec tout ce qu'on a posté tu n'y arrives pas, bein...pense a une eventuelle reorientation..
tu sais, defois, il suffit d'eteindre le pc, de prendre une feuille blanche et de faire des dessins pour comprendre....
l'exemple java est plus que simple a comprendre, alors que je ne code pas en java, c'est quoi java?
ps:(pour les moderateurs)
ce n'est pas sarcastique, c'est objectif et serieux qui pourra aider notre ami à comprendre qu'un code source, si on sais pas le lire, ça sert a rien...

Slt,

Tu as raison !

Je viens juste de savoir le faire sur papier !
Je pense que je dois maitriser mieux la panique tout simplement !

Encore merci pour tous les renseignements...

Il a fallut le temps mais ca commence à aller !

Allez bonne soirée!
++

hip hip hip ...

hourrah!!!!!:resolu:???

edit:
pour appeler la fonction:

Code:

1
2
3
4
5
6
 
 .....
         mov esi,liste
         mov edi,datas
         call minimax
 .....

la fonction: (desolé si elle marche pas, je l'ai pas essayée)

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
48
49
50
51
52
53
54
55
56
57
58
59
 
minimax:
;esi=tableau a lire
;edi=table de données pour bosser dessus
.max=0
.min=4
.Nmax=8
.Nmin=12
.maxlist=16
.minlist=20
       xor ebx,ebx
       mov [edi+.max],ebx 
       mov [edi+.min],ebx
       mov [edi+.Nmax],ebx
       mov [edi+.Nmin],ebx
       lea ecx,[ebx+4]
.iteration:
       mov eax,[esi+ecx]
       cmp eax,[edi+.max]
       jle @f
       mov [edi+.max],eax
       mov dword[edi+.Nmax],1
       mov edx,edi
       mov edx,[edi+.maxlist]
       mov dword[edx],4
       add edx,[edx]
       mov [edx],ecx
       jmp .endmax
@@:        
       jne @f
       inc dword[edi+.Nmax]
       mov edx,edi
       add dword[edx],4
       add edx,[edx]
       mov [edx],ecx
@@:
.endmax:
       jge @f
       mov [edi+.min],eax
       mov dword[edi+.Nmin],1
       mov edx,edi
       mov edx,[edi+.minlist]
       mov dword[edx],4
       add edx,[edx]
       mov [edx],ecx
       jmp .endmin
@@:        
       jne @f
       inc dword[edi+.Nmin]
       mov edx,edi
       add dword[edx],4
       add edx,[edx]
       mov [edx],ecx
@@:
.endmin:
       add ecx,4
       cmp ecx,[esi]
       jle .iterate
       ret

ici, les données pour travailler dessus:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
list:
dd @f-$-4  ;pour connaitre la taille des données
dd ?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?
@@:
datas:
dd 0,0,0,0
dd maxlist
dd minlist
 
maxlist:
dd 0
rd 1000  ; pour lister jusqu'à 1000 valeurs egales à max
minlist:
dd 0
rd 1000  ;idem

perso, je pense que ça, c'est pas tout cuit à lire, par contre l'exemple en java, c'est pas dur du tout... en fait, je vais paut etre me mettre au HLL... qui sait.

Citation:
Envoyé par pseudocode
Ca viendra (sauf si C# le mange avant).
Quel autre langage tu connais ?

Hum... ce code Java est la transcription de l'algo donné par "edfed".
Je veux bien tenter une traduction dans un pseudo-langage:
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 list: LISTE<VALEUR> min,max: VALEUR minocc,maxocc: ENTIER min <- premierElement(list) minocc <- 0 max <- premierElement(list) maxocc <- 0 TANT QUE list est non vide FAIRE i <- extraireElement(list) SI i est egal a min ALORS minocc <- minocc+1 FIN SI SI i est inférieur a min ALORS min <- i minocc <- 1 FIN SI SI i est egal a max ALORS maxocc <- maxocc+1 FIN SI SI i est supérieur a max ALORS max <- i maxocc <- 1 FIN SI FIN TANT QUE
re,

super je vais pouvoir comparer avec ma propre version !

Moi c'est le C que j'étudie pour le moment....

bah je suppose que cela ne change pas vraiment l'agorithme ou le code source....

Encore un grand merci !

J'espère que dans le futur ce sera moi qui pourrai aider les autres ;-)
++

Bonne soirée !