Enigme Multiples et diviseurs 2/2 @ Prise2Tete

MthS-MlndN · #26

Tu es sûr que tu ne pouvais pas optimiser ton code ? Ca me paraît étonnant qu'il ne soit pas allé au bout de ses calculs en un WE...

Certes, en théorie, il peut avoir jusqu'à 2x100! tests de divisibilité à faire, mais en pratique il y en aura beaucoup moins, non ?

Sinon, au lieu de la brute-force pure et dure, tu fais d'abord tous les tests de divisibilité (il y en a 5000) pour remplir une table de vérité (une moitié par calcul, l'autre par symétrie). Celle-ci te sert ensuite de graphe non orienté dans lequel tu lances un algo de recherche du plus long chemin. Je ne pense pas qu'un tel programme mettrait un WE à ressortir un résultat ?!

MthS-MlndN · #27

Vasimolo a écrit:
Je fournis le document dès que je sais comment faire

Vasimolo

Edit : seulement 5 pages après vérification , je crois que je vais finir par les scanner et les déposer sur le site .

Les : "il suffit d'aller ici pour uploader machin et suivre les liens qui permettent de créer la bonne page pour ..." ont une facheuse tendance à m'encourager à la paresse

Si je puis me permettre : www.prise2tete.fr/?page=upload pour avoir le formulaire d'upload, tu le mets, ça te renvoie le lien à nous fournir. Quand on l'a récupéré, tu retournes sur la page d'upload pour le supprimer et libérer de la place. Tadaaaam

kosmogol · #28

MthS-MlndN a écrit:
Sinon, au lieu de la brute-force pure et dure, tu fais d'abord tous les tests de divisibilité (il y en a 5000) pour remplir une table de vérité (une moitié par calcul, l'autre par symétrie). Celle-ci te sert ensuite de graphe non orienté dans lequel tu lances un algo de recherche du plus long chemin. Je ne pense pas qu'un tel programme mettrait un WE à ressortir un résultat ?!

wouarf !!!

Vasimolo · #29

J'ai suivi à la lettre les explications de Mathias ( j'adore quand on me dit bêtement ce que je dois faire sans m'ensevelir sous des tonnes de termes techniques qui n'ont pas de sens pour moi )

http://www.prise2tete.fr/upload/Vasimolo-long_max.pdf

Vasimolo

Flying_pyros · #30

j'adore quand on me dit bêtement ce que je dois faire sans m'ensevelir sous des tonnes de termes techniques qui n'ont pas de sens pour moi

Idem pour moi et ton pdf...
J'adore quand on me dit directement que le maximum possible est 77 sans avoir à comprendre quoi que ce soit à tous ces termes mathématiques qui n'ont pas de sens pour moi.

Vasimolo · #31

Je sais bien que ce PDF n'intéressera pas grand monde et je ne l'ai fourni que parce qu'on me l'a demandé : je le trouve aussi un peu âpre . Dhrm77 a dû passer un bon moment pour trouver une solution , prouver qu'on ne peut pas faire mieux ajoute un niveau supplémentaire de difficulté

On peut tout de même se prendre au jeu et laisser les hiéroglyphes du PDF à ceux que ça amuse

Vasimolo

MthS-MlndN · #32

Par exemple : moi

Flying_pyros · #33

Je sais bien que ce PDF n'intéressera pas grand monde

Je n'ai pas dit que ce n'était pas intéressant, j'ai dit que je n'y comprenais pas grand chose.
Blague à part, c'est effectivement très intéressant. Et c'est la première question que je me suis posé (et à laquelle j'ai été bien incapable de répondre) en lisant ton énoncé : Jusqu'à combien on peut espérer aller ?
J'avais retiré d'office 9 des 10 nombres premiers compris entre 50 et 100 puisque n'étant pas divisibles (sauf 1 par 1) mais pour le reste...

dhrm77 · #34

MthS-MlndN a écrit:
Tu es sûr que tu ne pouvais pas optimiser ton code ? Ca me paraît étonnant qu'il ne soit pas allé au bout de ses calculs en un WE...

Certes, en théorie, il peut avoir jusqu'à 2x100! tests de divisibilité à faire, mais en pratique il y en aura beaucoup moins, non ?

Sinon, au lieu de la brute-force pure et dure, tu fais d'abord tous les tests de divisibilité (il y en a 5000) pour remplir une table de vérité (une moitié par calcul, l'autre par symétrie). Celle-ci te sert ensuite de graphe non orienté dans lequel tu lances un algo de recherche du plus long chemin. Je ne pense pas qu'un tel programme mettrait un WE à ressortir un résultat ?!

J'avais écrit le programme en 5 minutes, et au vu des premiers resultats, j'ai eliminé les nombres premiers >31 et leurs multiples pour aller plus vite, et effectivement, ca a permis de trouver des resultats plus grand dans le meme temps de test.
Je ne doute pas qu'il y ait d'autres methodes que la mienne.
Je te propose donc de choisir ton langage préféré et d'ecrire le programme que tu decrit plus haut. Je serais intéréssé de savoir s'il trouve quelque chose dans des temps raisonables.
Et dans la foulée, combien de solutions differentes il trouverait...

MthS-MlndN · #35

Si j'ai un soir de libre, j'y penserai, et je te le proposerai
(Et mon langage préféré est le Fortran 90, je vais bien m'amuser avec )

kosmogol · #36

Fortran

Ça, c'est hype et tendance

Fais au moins semblant et dis C# ou Ruby !

EfCeBa · #37

Le graphe n'est pas orienté ce qui rend le calcul du chemin le plus long compliqué.

J'ai créé la matrice mais je n'ai pas sur l'utiliser correctement :
matrice-multiples-diviseurs-1-a-100.txt

MthS-MlndN · #38

Je dois avouer que je n'avais pas vraiment réfléchi en profondeur au problème...

Je ne vois pas encore d'autre alternative qu'un glouton, mais je vais y réfléchir un peu dans la soirée.

Peut-être une petite idée : ça ressemble pas mal au problème des dames sur l'échiquier. Je choisis un élément de départ, je mets des 0 sur toute sa ligne (pour dire "ce nombre m'a déjà servi de départ), et je choisis un 1 dans sa colonne. Je mets 0 sur la ligne correspondant à ce nouveau nombre, etc.

Code:

Compteur = 1 (pour le nombre d'éléments de la liste)
Choisir (idép=élément de départ)
Liste(1)=idép
Tableau(idép,j)=0 pour tout j de 1 à 100 (Tableau est la table des 1 et des 0 donnée par Ef)
Tant que (possible)
   Choisir iarr tel que Tableau(idép,iarr)=1
   Compteur += 1
   Liste(Compteur) = iarr
   idép=iarr (il deviendra notre élément de départ)
   Tableau(idép,j)=0 pour tout j de 1 à 100
Fin Tant Que

Le problème, ça va être de rajouter des boucles un peu partout

Il faudrait peut-être lire et comprendre le PDF de Vasimolo pour trouver des algos plus performants, qui ne "fassent pas n'importe quoi".

Peut-être ajouter une simple condition "ne t'engage vers ce nombre que s'il y a au moins un 1 sur sa colonne".

Peut-être y a-t-il encore mieux à faire ?..

dhrm77 · #39

Je remarque que tu (Mathias) n'avais pas donné de réponses quand l'énigme était en cours... Je ne te fais pas de reproches, mais je ne sais pas si tu y a pensé sans influence externe...

Voici ce que j'avais un peu pensé:
Il y a 2 groupes de nombres:
- les nombres "pivots" (1, 2, 3, 4, 5, 6, 7, 8)
- et les nombres qui ont peu de multiples (11, 13, 17, 19, 23...)

prenons 17 par exemple:
ses multiples de 1 a 100 sont: 17, 34, 51, 68 et 85.
En mettant 17 au centre, la plus longue chaine que l'on puisse faire est:
- 68, 34, 17, 51 ou 68, 34, 17, 85.
On peut peut pas utiliser 51 et 85 a la fois puisse que une fois 17 utilisé, le seul nombre que l'on peut relier a 51 ou 85 est 1, et 1 peut se relier a bien mieux qu'un nombre seul. comme par exemple 47, 94.
Meme observation pour 19.
Pour 23, c'est simple: 92, 46, 23, 69.
Comme c'est une chaine relativement importante, on est pratiquement assuree que sera dans la solution. donc on trouvera un 3 a droite du 69 et soit un 2 soit un 4 a gauche de 92.

Je pense que de cette maniere, on peut commencer a simplifier les recherches en prenant comme base de depart ce que l'on peut deduire par la logique.

Il ne faut pas oublier que certaines séries de multiples (comme 9, 10, 11, 12 ou 13) peuvent etre divisées en plusieurs segments...
par exemple: 8, 88, 22, 44, 4 puis plus loin : 7, 77, 11, 33, 99, 9
evidement, la solution ou tout est join semble plus beau: 77, 11, 99, 33, 66, 22, 44, 88
Voila...

MthS-MlndN · #40

Joli, de quoi s'amuser

Et pour te répondre : j'y ai pensé sans influence externe. Quand l'énigme est sortie, j'ai eu la flemme de découper des post-it et de faire des puzzles avec, par contre l'idée d'un programme de recherche ne m'avait même pas effleuré. Merci quand même de m'imaginer capable de m'approprier sans vergogne des idées qui ne sont pas les miennes Ca fait plaisir

dhrm77 · #41

Je parle d'influence, pas de plagiat! ^^

Je ne cache pas que mes solutions ait été influencée par ce que mon programme avait trouvé dans les premières heures.
Mes séries de 70 et 73 de long était des améliorations à la main de séries de 68 et 70, respectivement, que mon programme avait trouvé.
Et la série finale est une amélioration d'améliorations.

dhrm77 · #42

Vasimolo a écrit:
1°) dhrm77 : 77 ( prédestination ? )

Heureusement que Doc91 n'a pas joué...

kosmogol · #43

pour ma part, avec un tout petit effort j'aurais pu sponsorisé Maïtou

DOC91 · #44

kosmogol a écrit:
j'aurais pu sponsorisé Maïtou

l'un ou l'autre a écrit:
et moi je viens de me sponsoriser itou

kosmogol · #45

Et oui, quand je suis fatigué je fais plein de fautes !

piode · #46

on est deux !!...

MthS-MlndN · #47

Ah bon, c'est parce que t'es fatigué ?

kosmogol · #48

Qu'une seule faute dans son clin d'œil à Hamel
Ok, en ne lisant pas les indices

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#26 - 16-11-2009 18:19:40

multiples et diviqeurs

#0 Pub

#27 - 16-11-2009 18:25:40

Multiples et divviseurs

Vasimolo a écrit:

#28 - 16-11-2009 18:29:40

Multiples et diviiseurs

MthS-MlndN a écrit:

#29 - 16-11-2009 22:13:05

multipmes et diviseurs

#30 - 16-11-2009 22:17:09

multiples et dibiseurs

#31 - 16-11-2009 22:35:03

ultiples et diviseurs

#32 - 16-11-2009 22:39:42

Multiples et diviserus

#33 - 16-11-2009 22:51:19

Multiples et diivseurs

#34 - 17-11-2009 00:30:59

Multiples et dviseurs

MthS-MlndN a écrit:

#35 - 17-11-2009 10:23:01

multiples et diviqeurs

#36 - 17-11-2009 11:21:47

Mulitples et diviseurs

#37 - 17-11-2009 11:40:17

Multiples et divseurs

#38 - 17-11-2009 13:46:01

multiples zt diviseurs

Code:

#39 - 17-11-2009 14:46:02

multiples et duviseurs

#40 - 17-11-2009 15:43:42

Multiples t diviseurs

#41 - 17-11-2009 16:14:00

Multiples et idviseurs

#42 - 20-11-2009 17:01:28

MMultiples et diviseurs

Vasimolo a écrit:

#43 - 20-11-2009 17:14:03

Multiples et diviseus

#44 - 20-11-2009 19:47:06

Multiples et dviseurs

kosmogol a écrit:

l'un ou l'autre a écrit:

#45 - 20-11-2009 20:35:40

Multiples et divieurs

#46 - 20-11-2009 22:59:55

multiplrs et diviseurs

#47 - 21-11-2009 12:24:30

Multiples et iviseurs

#48 - 21-11-2009 12:37:22

muktiples et diviseurs

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums