Taille d'un ensemble

Version imprimable

21/05/2009, 20h24
taat84

Taille d'un ensemble

Bonjour à tous,

j'ai un td à faire dans lequel on me demande d'utiliser un type ensemble.
Ma question est la suivante : j'ai deux ensembles que je veux comparer; j'ai besoin de savoir combien d'éléments ils ont en commun. Mais d'après ce que j'ai compris, à l'inverse d'un tableau, je n'ai pas accès à chaque élément séparément. Donc existe-t-il une fonction qui permet de faire ça ? Par quels moyens dois-je m'y prendre ? Je pensais définir l'intersection de mes deux ensembles et ensuite voir la taille de l'ensemble d'arrivée, mais je ne sais pas si c'est possible.

Merci à tous,
bonne soirée.
21/05/2009, 21h53
Alcatîz

Bonjour et bienvenue !

Il n'existe en effet pas de fonction permettant de retourner directement le contenu ou la taille d'un ensemble. Pourrais-tu donner plus de précisions sur les ensembles que tu manipules (leur déclaration) ?

;)
21/05/2009, 22h03
taat84

Merci pour la réponse rapide.

Les ensembles que je manipule sont de type intervalle, comme:

Code:

type t_ens = set of 1..20;

( je pense que je pourrai aussi les déclarer comme

Code:

type t_ens = set of byte;

? dès que je dépasse byte, freepascal crie au dépassement de capacité, notamment lors de l'utilisation du test "in" ).

les deux ensembles contiennent le même nombre de nombres ( aléatoires et défini par l'utilisateur ) et j'aimerai pouvoir déterminer combien de nombres les deux ensembles ont en commun ( peu importe lesquels, leur nombre me suffit ).

Voilà, en espérant avoir été un peu plus clair
Merci encore
21/05/2009, 22h28
droggo

Boe,

Citation:

Envoyé par taat84

? dès que je dépasse byte, freepascal crie au dépassement de capacité, notamment lors de l'utilisation du test "in"

C'est normal, les ensembles standards du Pascal sont limités à 256 valeurs, elles-mêmes comprises de 0 à 255.

Pour compter le nombre de coïncidences, une petite réflexion devrait te permettre de trouver (piste, on en revient généralement là : comment ferais-tu à la main ?).
21/05/2009, 22h43
taat84

Salut,
à la main je voit trois solutions:
- je ferais l'intersection des deux ensembles et je déterminerais le cardinal de l'ensemble d'arrivée, mais ça ne ma pas l'air possible en pascal.
-je prends chaque nombre, je regarde si ils sont dans les deux ensembles, et je dit merci d'en avoir qu'une 50 aine.
-je garde en mémoire les valeurs rentrées par l'utilisateur et je les compare avec mon ensemble ( condition "in" ) mais je ne respecte plus le sujet car j'utilise un autre type de donnée.

Si une solution évidente m'a échappée, merci de me la faire remaquer!:ccool:
merci encore pour vos réponses
22/05/2009, 10h35
droggo

Bie,

La deuxième solution est la bonne, facile à implémenter, à ceci près qu'il faut "prendre chaque nombre" possible.
22/05/2009, 12h53
taat84

Bonjour,
et bien merci, je pensais implémenter cette solution, mais par curiosité, je voulais savoir si c'était possible autrement et plus "facilement" ou naturellement.

Encore merci,
bonne continuation!

Il est possible de simplifier la tâche du comptage en descendant au niveau de la représentation de l'ensemble en mémoire. En effet, chaque élément de l'ensemble est codé sur un seul bit.

Voici une fonction de comptage du nombre d'éléments d'un ensemble quelconque (mais dont il faut fournir la taille comme paramètre) qui a l'air de tourner correctement :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Function Nombre_Elements (const Ensemble; Taille : Byte) : Byte;
Type tEnsemble = Array [1..32] of Byte;   { 32 octets est la taille maximale d'un ensemble }
Var i, j : Byte;
    { Result : Byte; } // Activer sous Turbo Pascal
Begin
  Result := 0;
  for i := 1 to Taille do
    begin
      j := $01;
      while j <> 0 do
        begin
          if tEnsemble(Ensemble)[i] and j <> 0
             then
               Inc(Result);
          j := j shl 1;
        end;
    end;
End;

Et un exemple qui donne de bonnes réponses :

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
Program Comptage;
 
{$mode objfpc}{$H+}  // Effacer sous Turbo pascal
 
Uses Classes, SysUtils,  // Effacer sous Turbo pascal
     Crt;
 
Type Mois = (janvier,fevrier,mars,avril,mai,juin,juillet,aout,septembre,octobre,novembre,decembre);
 
Var Ensemble1, Ensemble2, Ensemble3 : Set of Mois;
    Nombres : Set of Byte;
 
Function Nombre_Elements (const Ensemble; Taille : Byte) : Byte;
Type tEnsemble = Array [1..32] of Byte;
Var i, j : Byte;
    { Result : Byte; } // Activer sous Turbo Pascal
Begin
  Result := 0;
  for i := 1 to Taille do
    begin
      j := $01;
      while j <> 0 do
        begin
          if tEnsemble(Ensemble)[i] and j <> 0
             then
               Inc(Result);
          j := j shl 1;
        end;
    end;
End;
 
Begin
  Ensemble1 := [janvier..juin];
  WriteLn('Nb éléments dans l''ensemble 1 : ',Nombre_Elements(Ensemble1,SizeOf(Ensemble1)));
  Ensemble2 := [mars,juillet..decembre];
  WriteLn('Nb éléments dans l''ensemble 2 : ',Nombre_Elements(Ensemble2,SizeOf(Ensemble2)));
  Ensemble3 := Ensemble1 * Ensemble2;
  WriteLn('Nb éléments dans l''ensemble 3 : ',Nombre_Elements(Ensemble3,SizeOf(Ensemble3)));
  WriteLn;
  Nombres := [14..17];
  WriteLn('Nb éléments dans l''ensemble Nombres : ',Nombre_Elements(Nombres,SizeOf(Nombres)));
  ReadLn;
End.

;)

22/05/2009, 14h22
droggo

Bie,

Citation:

Envoyé par Alcatîz

Il est possible de simplifier la tâche du comptage en descendant au niveau de la représentation de l'ensemble en mémoire. En effet, chaque élément de l'ensemble est codé sur un seul bit.
...

Ça marche, bien entendu.

Mais le problème concernant un td, la solution désirée par l'enseignant est sans le moindre doute une solution utilisant les possibilités des ensembles, sans chercher à contourner les possibilités ainsi offertes. :)
22/05/2009, 14h49
darrylsite

Salut,
Je crois que le Pascal dispose dejà des outils pour manipuler les ensembles. Les opérations élémentaires suivantes sont supportées : union, intersection, ...
Voici un lien vers un tutoriel sur l'utilisations des ensembles en Pascal :
http://pascal.developpez.com/cours/c...ge=pg_Set#LXXX
22/05/2009, 16h28
droggo

Boa,

Citation:

Envoyé par darrylsite

Salut,
Je crois que le pascal dispose dejà des outils pour manipuler les ensembles. Les operations elementaires suivantes sont supportées : union, intersection, ...

Oui, l'intersection donne un ensemble contenant toutes les valeurs communes.

MAIS, le type ensemble ne dispose pas de fonction permettant d'obtenir le nombre de valeurs qu'il contient, et on est donc obligé de faire ce compte avec une boucle sur toutes les valeurs possibles. :)