Algo et ensembles...

[ghghgh]

Bonjour,
je bloque sur un ptit problème d'ensemble, je dois trouver un algo pour le résoudre :

voici l'énoncé :

Un jeu de (pas forcément distinctes 2 à 2) cartes composées de 1 à rayures colorées
On doit trouver le nombre de cartes tirées à l'aide de questions.
Ces questions sont du type :
- combien de couleur en tout dans les cartes
- combien des cartes tirées possèdent les couleurs (pas forcément exclusivement)

j'ai pensé que lorsque l'on demandait le nombre de carte avec un nombre impair de couleur, "combien de cartes possèdent c1, c2, c3", on devait rajouter ce nombre
et lorsque que l'on demandait le nombre de carte avec un nombre pair de couleur "combien de cartes possèdent c1, c2, c3, c3" on devait retrancher ce nombre,

mais le raisonnement avec lequel je suis parvenu à ça me semble scabreux, et quelques tests m'ont donné des résultats faux... mais ptêtre que je m'y suis mal pris ^^'

En tout cas un grand merci d'avance pour votre aide
peut-être il y a-t-il une relation, loi sur les ensembles qui donnent plus ou moins directement la réponse... je ne sais pas :/

bonne journée

[Flodelarab]

Je résume:
Tu tires M cartes parmi N ayant P rayures choisies parmi un nombre inconnu de couleurs.

Mis à part les cas extrêmes, il me semble que tu ne peux que dénombrer les cas possibles et non fixer M

[ghghgh]

euh, non, ce n'est pas tout à fait ça...
tu tires M cartes parmi N cartes.
et tu sais combien de couleur tu as en tout dans tes M cartes, on te le donne.

puis, à l'aide de question, il faut déterminer le nombre M,
les questions sont : combien de cartes tirées possèdent les couleurs (on choisi) mais la réponse n'est pas exclusive... elle prend en compte les cartes possédant uniquement cette couleur, mais aussi celles qui possèdent cette couleur et des autres...
mais je crois que j'ai ptêtre trouvé la formule sur :
http://www.animath.fr/cours/inclusionexclusion.html

j'pense ça doit être ça
vous êtes d'accord ?

[Patastronch]

Bon alors chaque carte possede P couleurs non forcement distincte c'est ca ?

Et tu veux savoir quelles sont les questions a poser pour savoir combien on a de carte dans la main ?

Alors combien y a t il de couleur en tout ? disons Q si on est censé le savoir.

T'as un nombre maximal de question ou pas ? Parceque sinon il suffit de poser les questions différentes du types combien de cartes possede les couleurs ou est une couleur quelconque et de faire la somme des réponses. Mais l'algo risque d'etre tres lent vu le nombre de questions a poser.

C'est bien sur améliorable en posant comme premiere question : combien y a de couleurs : on te répond et ca fait plus que questions. Mais ca reste encore trees mauvais. Tu peux également ne pas poser les questions redondante en tenant compte des annagrames des possibles dans une question. Mais ca reste toujours un tres mauvais algo a partir d'un certain nombre de rayures et de couleurs.

Y a surment une possibilité de faire malin, mais reste a savoir si t'as besoin d'un algo malin

[ghghgh]

vlà les contraintes :p
LIMITES DE TEMPS ET DE MEMOIRE

Temps : 0.25 s sur une machine à 1Ghz.
Mémoire : 1000 Ko.
CONTRAINTES

1 <= N <= 10 000 000, le nombre de cartes
1 <= P <= 12, le nombre de couleurs différentes du jeu
1 <= C <= P, le nombre de rayures d'une carte (toutes de couleurs différentes)

non, mais le truc c'est que je sais au départ le nombre Q de couleur différentes dans le paquet,
je demande, et on me répond 3

après ce que je dois faire, je dois demander :
combien sont de couleur 1 :
on me reponds 2 cartes
combien sont de couleur 2 :
on me reponds 3 cartes
combien sont de couleur 3 on me repond 2 cartes

et en fait, il n'y a que 3 cartes, (pas 2+3+2=7)
car une carte est de couleur 1,2,3
une autre est de couleur 1,2
et la troisième de couleur 2,3

voilà...

c'est ce qu'il faut faire... ajouter, soustraire, suivant les intersections des ensembles

[Patastronch]

t as rien compris. relis.

Si ya 3 couleur et 2 rayures tu poses les questions :

Combien ont la couleur C1 et C1 ?
Combien ont la couleur C1 et C2 ?
Combien ont la couleur C1 et C3 ?
Combien ont la couleur C2 et C2 ?
Combien ont la couleur C2 et C3 ?
Combien ont la couleur C3 et C3 ?

Et la tu fais la sommes des réponses. Pourqoi on a le droit de sommer ? parceque chaque ensemble correspondant aux questions sont disjoints 2 a 2. Donc leur intersection est nulle et donc tu peux sommer leur cardinal. C'est aussi simple que ca.

Apres si c'est pas assez rapide (ce qui sera surment le cas vu tes contrainte) faut bien sur feinter et faire plus malin. Je verrais bien 2 série de questions, une qui borne inferieurement le cardinal et une autre superieurement. Et quand les 2 bornes sont egales c'est que t as la réponses exact. Je jeterai un oeil dessus si j'ai le temps dans la journée.

[Patastronch]

Bon pour minimiser le nombre de questions il faut créer plusieurs ensemble disjoints et sommer leur cardinal. Dans ce que je t'ai donné au dessus chaque carte distinct définit un ensemble. On peut réduire le nombre de question en rduisant le nombre d'ensemble disjoint créé.

Par exemple si tu fais 2 ensembles disjoints, (genre les carte qui possede du vert et celle squi n'en possedent pas) il va te falloir au plus 1 questions pour définir les carte qui ont du vert et au plus questions pour définir les cartes qui n'en ont pas (soit questions en tout ce qui est mieu que questions mais ca reste encore beaucoup quoique t'es limité a 12 couleurs ca devrait etre bon niveau rapidité).

Exemple :

3 couleurs :
combien ont C1 ? N
combien ont C2 C1 ? A
combien ont C2 ? B
combien ont C3 C1 ? C
combien ont C3 ? D
combien ont C3 C2 C1 ? E
combien ont C3 C2 ? F

Le résultat est N+ B-A + D-C +F-E
Soit 7 questions en tout.

Apres on peut peut-etre encore minimiser le nombre de questions en divisant en 2 ensembles disjoints en les découpant en 2 autres ensembles (par exemple y a 4 couleurs, un ensemble avec les couleurs C1 et C2 et un ensemble les contenant pas). Mais je verrai ca plus tard j'ai plus trop le temps la, ais j'ai l'intuition qu'on minimise les questions en découpant en 2 ensembles de cartes disjoint dont l'un possede Q/2 couleurs fixées et l'autre ne les possedant pas.

Enfin une derniere piste pour encore améliorer la stratégie, définir une stratégie dynamique en fonction des réponses obtenues, par exemple si on te réponds qu'aucune carte possede les couleurs C1,C2 alors innutile de demander si y a des carte qui possedent les couleurs C1,C2,C3 ou encore C1,C2,C3,C4 ou ce genre de choses puisque ce sont des sous ensembles de cartes possedant les couleurs C1,C2.