PROGRAMMATION - Placer des CAMERA dans PARIS

On vous donne un plan d'un quartier de Paris, le but est de placer des camera afin de voir qui porte ou non le masque.
Cependant la mairie de Paris n'a pas beaucoup de budget donc elle vous demande d'en mettre le moins possible, et qu'elles couvrent le plus de rues possibles.

Sur le plan il y a des croisements, et des rues.
Vous pouvez placer les camera uniquement sur les croisements.
Une camera sur un croisement couvre toutes les rues connectées à ce croisement.

En entrée on vous donne la liste des croisements, avec les rues auxquels ils sont connectés

En sortie vous devez indiquer sur quel croisement vous placez les camera

------

Des idées d'algorithmes ? si vous en avez go sur le discord ou postez ici

Paris a besoin de vous

tu veux qu'on fasse ton taff à ta place ?

Le 22 décembre 2020 à 01:17:43 JeanKabyle a écrit :
tu veux qu'on fasse ton taff à ta place ?

C'est pas un taff hein

isse

J'ai eu le sujet en DS Go écrire le programme mathématiques associé

Le 22 décembre 2020 à 01:26:05 aigrevin a écrit :
J'ai eu le sujet en DS Go écrire le programme mathématiques associé

Tu peux faire ça mais pas sûr que ça soit rapide

Châtelet

Le 22 décembre 2020 à 01:30:01 cringered66 a écrit :
Châtelet

Oui

Ecoute j'ai un truc pas optimal mais qui fait le taff :
Chaque croisement est un node avec comme attributs toutes ses rues.
Tu prends le premier, celui qui a le plus de rues, et tu flag les rues qu'il a comme attribut.
Puis le 2eme avec le plus de rues et tu regarde les rues qu'il a comme attribut. Si toutes ses rues sont déjà marquées, tu l'élimine et tu passes au suivant et ainsi de suite.

C'est pas l'optimum je pense mais c'est déjà une première base.

Le 22 décembre 2020 à 01:33:22 SimpsCity a écrit :
Ecoute j'ai un truc pas optimal mais qui fait le taff :
Chaque croisement est un node avec comme attributs toutes ses rues.
Tu prends le premier, celui qui a le plus de rues, et tu flag les rues qu'il a comme attribut.
Puis le 2eme avec le plus de rues et tu regarde les rues qu'il a comme attribut. Si toutes ses rues sont déjà marquées, tu l'élimine et tu passes au suivant et ainsi de suite.

C'est pas l'optimum je pense mais c'est déjà une première base.

Ouai ça donne un algo glouton en O(n)

C'est pas une connerie genre théorie des grpahes avec des noeuds et des arêtes?

Le 22 décembre 2020 à 01:37:51 Ailiganonv18 a écrit :
C'est pas une connerie genre théorie des grpahes avec des noeuds et des arêtes?

si

si

Bonne chance clé, j'ai vu ça en cours mais j'ai rien branlé, juste de quoi assurer la moyenne donc je suis incapable de t'aider

Le 22 décembre 2020 à 01:43:02 Ailiganonv18 a écrit :

si

Bonne chance clé, j'ai vu ça en cours mais j'ai rien branlé, juste de quoi assurer la moyenne donc je suis incapable de t'aider

c'est pas pour moi
C'est pour s'amuser

Pour moi c'est un problème de graphe, sûrement une vague histoire de coloration

Le moi étudiant aurait sûrement trouver une solution en réfléchissant un peu, mais le moi diplômé en est totalement incapable

J'avais l'idée que le khey a posté au dessus en parcourant les nœuds 1 par 1, mais je sais que c'est pas du tout optimisé.