[Algorithmie] Les chans IRC
|
21-07-2013, 21h15
Message : #1
|
|
InstinctHack
Posting Freak Messages : 1,366 Sujets : 184 Points: 299 Inscription : Dec 2011 |
[Algorithmie] Les chans IRC
io,
un nouveau challenge de programmation que m'as proposer bofh. Bofh a écrit :y'a un problème sympa qui serait de déterminer combien de chans il faut former, pour que tous les gens qui s'entendent bien aient au moins un chan en commun, et que les gens qui s'entendent pas aient aucun chan en commun en pièce jointe, vous trouverez un fichier de données. sur la première ligne, la liste des pseudos (oui, très classe comme pseudo ) sur les suivantes une liste de couple qui représente des animosités entre deux pseudos. mon résultat : langage : PHP nombre : 30 temps : 4m45.973s bon courage ! Citation :un jour en cours de java j'ai attrapé les seins d'une fille mais elle m'a frappé en disant "c'est privé !!" |
|
21-07-2013, 21h37
Message : #2
|
|
Wabouz
Membre actif Messages : 96 Sujets : 8 Points: 16 Inscription : Nov 2012 |
RE: [Algorithmie] Les chans IRC
Moi qui pensait faire ça avec une feuille et un crayon ^^
C'est l'histoire d'un mec qui rentre dans un canard... ( °3°)♫
|
|
21-07-2013, 22h09
(Modification du message : 21-07-2013, 23h38 par b0fh.)
Message : #3
|
|
b0fh
Membre actif Messages : 210 Sujets : 17 Points: 309 Inscription : Jul 2012 |
RE: [Algorithmie] Les chans IRC
PS: il faut évidemment minimiser le nombre de chans.
Le format de sortie n'est pas précisé, mais une ligne par chan avec la liste des pseudos membres, ça me parait raisonnable ! Deuxième détail: en pratique, on ne ferait pas de chans de deux personnes, on dirait qu'ils causent simplement en privé, mais pour ce problème, considérons les privés comme des petits chans. Ou autrement dit, on cherche a minimiser le nombre total de chans + de privés. Un exemple d'exécution: Input: Code : 1 2 3 4 Signifie que 1 et 2 ne s'aiment pas, et que 1 et 3 ne s'aiment pas, et la solution est: Code : 1 4 soit 2 chans; on voit qu'en effet, 1 et 2 ne sont jamais dans le même chan, 1 et 3 ne sont jamais dans le même chan, et toutes les autres paires possibles [(1,4), (2,3), (2,4), (3,4)] existent dans au moins un chan. |
|
21-07-2013, 23h30
Message : #4
|
|
Wabouz
Membre actif Messages : 96 Sujets : 8 Points: 16 Inscription : Nov 2012 |
RE: [Algorithmie] Les chans IRC
ça soulève un point pour la résolution de l'exo. À partir de combien de personnes dans le chan on considère que c'en est un?...
C'est l'histoire d'un mec qui rentre dans un canard... ( °3°)♫
|
|
21-07-2013, 23h32
(Modification du message : 22-07-2013, 00h14 par notfound.)
Message : #5
|
|
notfound
#!/usr/bin/env bash Messages : 687 Sujets : 47 Points: 271 Inscription : Sep 2012 |
RE: [Algorithmie] Les chans IRC
Bin 3 en tout ! cf. le post de b0fh.
2 personnes sur un chan pourrait-être considéré comme n'en étant pas un, mais plutôt comme étant un private. Mais je crois pas qu'il faille se soucier de ça. |
|
22-07-2013, 16h15
(Modification du message : 22-07-2013, 16h29 par InstinctHack.)
Message : #6
|
|
InstinctHack
Posting Freak Messages : 1,366 Sujets : 184 Points: 299 Inscription : Dec 2011 |
RE: [Algorithmie] Les chans IRC
voilà mon résultat qui montre qu'une amélioration est sûrement possible
Code : 0 1 3 6 8 22 24 28 30 40 43 53 60 61 62 120 138 183 199 216 403 444 449 492 Et oui, le code génére des "groupes" jamais le numéro 0 ne parleras avec 498, pourtant ils se détestent pas. (pour les perf de temps, je crois que je peux pas mal descendre mais avec une augmentation de la mérmoire utilisée) Allez, à vous :p edit : et FUCK j'ai un private entre 470 et 498 edit2 : je confirme je viens de passer de 4m45.973s à 1.752s pour le même résultat Citation :un jour en cours de java j'ai attrapé les seins d'une fille mais elle m'a frappé en disant "c'est privé !!" |
|
« Sujet précédent | Sujet suivant »
|
Sujets apparemment similaires… | |||||
Sujet | Auteur | Réponses | Affichages | Dernier message | |
[Algorithmie] Cron et Calendrier | InstinctHack | 4 | 264 |
05-06-2013, 20h33 Dernier message: b0fh |
|
[Algorithmie] Pentominos | InstinctHack | 5 | 355 |
05-05-2013, 15h09 Dernier message: gruik |
|
[Algorithmie] Compression de donnée "binaire" dans un plan 2D | InstinctHack | 3 | 208 |
25-03-2013, 12h54 Dernier message: InstinctHack |
|
[Algorithmie] Gestion de l'espace dans un plan 2D | InstinctHack | 0 | 123 |
06-03-2013, 01h07 Dernier message: InstinctHack |
Utilisateur(s) parcourant ce sujet : 2 visiteur(s)