Inscription / Connexion Nouveau Sujet

1 2 +


Posté par
simon92
re : Enigmo 15 : L'interrupteur aléatoire * * * 30-04-08 à 18:17

Posté par
mikayaou
re : Enigmo 15 : L'interrupteur aléatoire * * * 30-04-08 à 19:16

Et toc !...

second degré, bien sûr

Posté par
infophile
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 00:09

Bonsoir

Juste pour parler un peu de la programmation :

Jusqu'à l'année dernière où je n'avais jamais touché à la programmation je pensais que c'était un "outil magique" qui en tapant deux trois lignes de codes fournissait la réponse à l'énigme sans se casser la tête. J'avais tord, car pour obtenir la réponse de cette façon il faut pouvoir concevoir le programme de A et Z, et il faut faire preuve comme en maths de rigueur et de logique :

1) Etablir une stratégie pour résoudre le problème, c'est-à-dire concevoir un algorithme répondant au problème.
2) Mettre en forme celui-ci avec le langage utilisé.
3) Optimiser le programme ainsi crée.
4) Vérifier la robustesse de ce dernier, en d'autres termes s'assurer que l'exécution du programme couvre bien tous les cas.

Et étant débutant je vous assure que ce n'est franchement pas évident

Donc même si le recours à l'informatique est moins "élégant" qu'une belle démonstration mathématique, cette méthode reste toutefois intéressante et loin d'être simple.

A+

Posté par
master_och
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 09:12

gagnéBonjour

Tout à fait d'accord avec toi infophile, il m'arrive parfois de commencer la réalisation d'un programme pour generer toutes les solutions et au cours de sa réalisation je me dit que j'aurai pu economiser beaucoup de temps si j'ai essayé de trouver une seule solution à la main.

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 09:18

gagnéJe rejoins tout à fait infophile, qui en passant, a dû choisir son pseudo après sa conversion.

J'ajoute qu'une branche très importante et très active des mathématiques actuelles étudie justement les processus de programmation (algorithmique, preuves, optimisations, cryptages, et j'en passe), et que c'est justement en grande partie grâce à cette recherche que vous pouvez, amis Toiliens, partager aujourd'hui de si beaux instants mathématiques à travers le réseau, les images si rapidement échangées et affichées, le silicium qui, de vulgaire sable de plage, est devenu le cerveau oh combien performant de vos ordinateurs.

La recherche de solutions singulières dans la théorie des groupes n'a pu se faire que grâce à des programmes informatiques et donc grâce à des chercheurs mathématiciens qui, heureusement pour l'avancement des sciences, ne se sont pas sentis dévalorisés par l'utilisation de cet outil.

Notre activité à nous est ludique. Les énigmes proposées ont déjà été résolues, nos trouvailles ne vont pas faire avancer la connaissance de l'humanité. Aussi, il est concevable que celui qui propose l'énigme émette des règles du jeu, comme par exemple l'interdiction de tout moyen électromécanique pour prouver sa solution. Mais en dehors de tels préceptes explicitement énoncés à l'occasion de chaque énigme, je ne vois pas quel manque d'élégance il y aurait à utiliser un outil ma foi fort puissant.

Et la maitrise de l'outil n'est pas en soi un motif de rejet, ce serait comme de reprocher à un sauteur à la perche sa grande taille. Ou à Srivanasa Ramanujan son cerveau ou les conditions de sa jeunesse qui l'ont poussé vers la voie qu'il a choisie.

Au final, les résolutions que je mène par ordinateur m'apportent moins de satisfaction que celles que je résouds par la logique pure, mais quand celle-ci se montre rétive à ma sagacité, j'avoue que l'alternative me convient.

@master : je te conseille par la suite d'inverser le processus, de commencer d'abord par rechercher des solutions par la logique. C'est cette recherche, si elle s'avère stérile dans un premier temps, qui doit mener aux idées qui vont te permettre de concevoir un programme adapté, voire élégant.

Ceci dit, je vais maintenant à la manif. Il n'y a pas, hélas, que les activités purement intellectuelles dans la vie.

Posté par
master_och
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 09:25

gagnéBien dit dhalte .

Posté par
borneo
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 09:38

Hello,

ceux qui pensent que le recours à l'informatique est "fastoche" sont souvent ceux qui ne savent pas s'en servir  

Posté par
master_och
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 09:40

gagné

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 10:54

perduBonjour à tous!
Je ne sais pas si c'était du second degré, mais en tout cas c'était de l'humour!
Je fais partie des sous-programmeur (et même en-dessous ) vu que je programme particulièrement en VB6...
qui d'après de nombreux avis (issus de codes sources) est plus rapide que le VB.net.
J'ai aussi fait un test entre le VB6 et le C (avec un test de primalité), et le C s'avère un peu plus rapide.
Je vais essayer de verifier tes calculs en faisant mon algorythme on pourra ainsi comparer.

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 16:00

gagnéAlors c'était du second degré, ou de l'auto dérision.

algorithme et pas algorythme, quoique dans un algorithme qui balance, on y trouve souvent du rythme.

Bonne programmation à toi alors.

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 16:02

perduMerci dhalte, mais j'ai du mal! (ça fait une demi heure que je fait du débug )

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 16:05

perduouille! (je fais)
Peux-tu m'expliquer brièvement comment fonctionne ton programme ?
(une boucle que tu  mets en binaire ?)

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 16:09

gagné  ' Technique de recherche de connectivité des circuits :
  ' On part de circuits élémentaires qui sont représentés par les extrémités de chaque cavalier.
  ' On compare chaque circuit avec les autres pour déterminer s'ils ont au moins un point en commun.
  ' Si oui, on fusionne ces deux circuits.
  ' On recommence tant que on trouve au moins une intersection.
  ' A la fin, on a les circuits individuels.
  '
  ' Dans notre cas présent, on ajoute aux circuits représentés par les 9 cavaliers les deux circuits reliant d'une part les quatre plots de gauche, et d'autre part les quatre plots de droite.
  ' Ainsi au final, si on trouve un circuit contenant le plot en haut à gauche ainsi que le plot en bas à droite, alors les deux bords sont connectés.

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 16:14

gagnéJ'ai oublié de dire que cette recherche que je décris dans mon topic précédent concerne uniquement une configuration donnée. Je fais aussi une boucle externe sur les 3$ 2^{n^2} positions possibles des 3$ n^2 cavaliers.

L'algorithme définitif de recherche de connectivité est légèrement différent de l'explication car j'y ai ajouté des optimisations purement techniques.

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 01-05-08 à 16:23

perduJe me noie dans ton vocabulaire technique, enfin de toute manière quand on programme, on ne comprend jamais que soit même, et ce malgré l'abondance des commentaires

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 16:05

perduOuf!
J'ai enfin terminé mon programme, mais, chose inquiètante : je ne trouve pas pareil que toi !

P(1) = 1 (instantané)
P(2) = 14/16 (instantané)
P(3) = 434/512 (instatané)
P(4) = 54704/65536 (5 secondes)

Je vais mettre le code sur internet ce soir...si tu veux plus d'informations je suis disponible.
(sache que je suis persuadé que mon algo marche je l'ai verifié et revérifié...)

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 16:52

gagnéMatovitch. Je crois que Code Source a analysé ton programme et qu'il l'a refusé, va savoir pourquoi...

Plutôt que polluer le topic de crapul, je te propose de continuer à polluer Enigmo15.

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 17:00

perduOui, pardon excuse-moi, c'est bon (j'ai du télécharger firefox   )
Voici le lien (pas d'exe et désolé pour le multipost):

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 20:49

perduJe trouve : P(5) = 27811232/33554432 (1h 5min)

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 21:08

gagnéDésolé, mais avec aucun commentaire pour me guider, je n'ai pas la fibre humanitaire suffisante pour déboguer ton programme.

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 21:22

perduAlors tu es humain !
D'accord, je mets à jour tout de suite !

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 22:11

perduBonsoir dhalte!
J'avais tort, il y a un bug dans mon programme.
Il ne prends pas en compte les vrai rebroussement comme :

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 22:22

perduEnigmo 15 : L\'interrupteur aléatoire

Je te renverrai la version corrigée de mon programme (commentée)!
Sinon merci, car tu m'as fait aprécier la vrai difficulté du problème.

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 23:13

gagnéParce qu'il y a des vrais et des faux rebroussements ?

Posté par
simon92
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 23:17

tu savais pas?

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 23:24

gagnéEh, Simon, tu te marres comme une baleine et ça fait vraiment plaisir à voir.
Tu l'avais cherchée la réponse à cette énigme ? Qu'est-ce que tu en penses ?

Posté par
simon92
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 23:34

oulala, j'essaie de mettre de la bonne humeur, j'espère que c'est pas reproché.
En tout cas, je vous felicite tous pour vos programmes car je serais incapable de faire votre travail.
J'ai lu plus haut que tu n'aimais les gens qui disaient que c'était de la triche les solutions programmées et tout, je suis tout a fait d'accord avec toi, mais je pense tout de même qu'une solution purement mathématiques, est beaucoup plus élégante.
Je n'ai pas reflechit à ce problème car, je fais moins souvents maintenant les enigmes mensuelles, je vais peut-être m'y remettre un peu .  Vu que celle ci ne m'a pas inspiré et ne m'aurait rapporté qu'un poisson je n'ai donc pas participé .
J'espère que j'ai le droit de parler sur ce topic si je n'ai pas participer a l'énigme.

J'espère avoir mal compris le sens de ton post

Posté par
borneo
re : Enigmo 15 : L'interrupteur aléatoire * * * 02-05-08 à 23:44

Hello,

moi j'ai cherché, mais pas trouvé.

Bravo à ceux qui s'y sont risqués.

Posté par
isisstruiss
re : Enigmo 15 : L'interrupteur aléatoire * * * 03-05-08 à 01:22

Bonsoir,

Je me permets de m'immiscer dans votre discussion maths/info pour apporter un nouveau regard, étant moi-même amatrice de mathématiques appliquées, donc à cheval entre les deux manières de procéder.

Autant en maths qu'en info on peut se contenter de raisonnements très bêtes ou développer la manière de procéder. Faire un algorithme "force brute" pour résoudre un problème est du même niveau que tester toutes les possibilités de tête, à la main, avec un tableur ou peu importe. On peut, de tête, éliminer beaucoup de possibilités et chercher une solution au problème par raisonnement. De même, on peut, de tête, réfléchir à un algorithme efficace, c'est-à-dire de faible compléxité, qui ne se contentera pas de faire des bêtes boucles. L'algorithme réfléchi éliminera certains sous-arbres de l'exploration soit parce qu'on ne trouvera pas de meilleure solution que celle trouvée pour l'instant, soit parce que le calcul est équivalent à un autre sous-arbre. On évitera à l'ordinateur de faire le même calcul des nombreuses fois tout comme on ne le ferait pas nous-même. Ceci est très important dans les algorithmes itératifs ou dans des nombreuses boucles.

Ma conclusion est que choisir entre papier-crayon et programmation n'est en aucun cas une indication du niveau du raisonnement caché derrière. Tout réside dans la manière de le faire. Et le choix papier/programmation doit dépendre aussi du problème à traiter.

En particulier à propos des énigmes de l', on les fait tous pour le plaisir. Ceux qui ne jurent que par le papier-crayon, qu'ils soient heureux ainsi. Ceux qui prennent plus de plaisir à développer un algorithme et programmer, qu'ils s'amusent aussi. Soyez un peu plus ouverts d'esprit pour vous rendre compte que nous sommes tous différents et qu'il est très bien ainsi, il n'y a pas une seule vérité. La beauté est subjective.

Isis

Posté par
infophile
re : Enigmo 15 : L'interrupteur aléatoire * * * 03-05-08 à 06:49

+1 Isis

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 03-05-08 à 09:22

perduJe dis "vrai" rebroussement, car le chemin que suit le circuit "recule" d'une colonne, ce qui est possible lorsque l'on a 16 cavaliers où plus...
D'où le bug...que je corrige avant ce soir.

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 03-05-08 à 09:51

gagnéA Simon :

Tu as tout à fait mal interprété le sens de mon message. Je pensais que mon smiley tout souriant éviterait la méprise. Je suis franchement et sincèrement désolé que tu aies pu même un instant avoir un doute.

Comme tu avais répondu à nos échanges, je souhaitais seulement t'inviter au débat.

Je t'assure que tu es le bienvenu et te réaffirme qu'il n'y avait strictement aucune acrimonie dans mon propos précédent, bien au contraire.

A isisstruiss :
Bienvenue dans notre Club, où Infophile et moi (les deux seuls membres actuellement, mais il reste très ouvert) partageons tes vues.
- Recherche initiale cérébrale
- Analyse du problème, recherche des invariants, d'une méthode de résolution (c'est l' "algorithme", mais il peut très bien être à ce moment humainement réalisable).
- Si le résultat des cogitations ne permet pas humainement de trouver la solution, création d'un "programme" informatique qui réalise le "programme" cérébral établi ci-dessus.
- Plus la réflexion humaine aura été féconde, plus le programme sera compact, élégant, efficace.

Finalement, se jeter sur l'écriture d'un programme sans avoir réfléchi à simplifier le problème initialement, c'est une attitude qui va à l'encontre de l'esprit des énigmes, mais inversement, s'interdire l'outil par principe quand le cerveau seul ne peut aller plus loin dans la démarche, c'est se condamner à continuer à vivre au 16ième siècle.

Mathématiquement et informatiquement vôtre.

Posté par
gloubi
re : Enigmo 15 : L'interrupteur aléatoire * * * 16-05-08 à 10:34

gagnéBonjour,

dhalte, matovitch >> Très étonné du temps de réflexion de vos programmes !

Pour ma part, je trouve p(4) = 54722/216 en 0.016 s
et p(5) = 27858752/225 en 9 s !

J'ai fait des essais sur des interrupteurs rectangulaires;
largeur d'électrode 5, distance inter-électrodes 6: p(5*6) = 783996236/230 en 422 s,

de même p(6*5) = 968197822/230 en 360 s.

Je ne me suis pas attaqué au cas 6*6, qui devrait prendre environ 7 heures.


L'explication vient certainement de l'algorithme utilisé.
Personnellement j'emploie la "méthode du labyrinthe":
partant de la case du haut à gauche je suis le "mur de gauche", jusqu'à me retrouver sur une des cases de droite (le courant passe),
ou alors retour sur l'électrode de gauche, case du bas (pas de solution).

Je tiens la procédure, en Pascal (sous Delphi), à votre disposition.

A+,
gloubi
  

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 16-05-08 à 19:45

gagnéSuper, gloubi.

Ton idée est bonne, mais ton explication surement insuffisante, car si je suis ta directive, je trouve que le circuit ci dessous ne connecte pas les bords. Je suppose que tu t'autorises à traverser quelques murs !

Mais elle est effectivement à retenir car certainement plus efficace que mon approche de fusion des circuits, au vu des temps que tu annonces.

J'avais pensé à cette approche de fusion plutôt que de labyrinthe pour le cas d'un interrupteur à 3 dimensions, où l'algo du labyrinthe tombe en défaut.

Posté par
matovitch
re : Enigmo 15 : L'interrupteur aléatoire * * * 19-05-08 à 18:52

perduBonjour gloubi!
Je précise que mon programme ne marche pas...
Et je dis bravo à vous 2 car j'ai laissé tomber !

Posté par
gloubi
re : Enigmo 15 : L'interrupteur aléatoire * * * 20-05-08 à 10:08

gagnéBonjour,

dhalte
>>

Citation :
je trouve que le circuit ci dessous ne connecte pas les bords.


Lequel?

Et pour info, je n'ai pas de murs a traverser! S'il y a un chemin d'une électrode à l'autre, je le trouve forcément.
Pour un interrupteur à deux dimensions, bien sûr.

gloubi

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 20-05-08 à 17:55

gagnéTiens, c'est vrai, lequel ?
J'ai dû faire une fausse manœuvre, parce que l'aperçu montrait l'image jointe.

Bon, je la reposte :
Tu disais partir "de la case du haut à gauche" et suivre le "mur de gauche". Je ne dois certainement pas comprendre ce qui est pourtant limpide...

Enigmo 15 : L\'interrupteur aléatoire

Posté par
gloubi
re : Enigmo 15 : L'interrupteur aléatoire * * * 21-05-08 à 10:24

gagnéBonjour,

Le mur de gauche, en rouge sur le dessin:
en bleu, les murs inutilisés.
Enigmo 15 : L\'interrupteur aléatoire
A propos j'ai testé le cas 6*6, mais avec une variable qui ne sait compter que jusqu'à 2 milliards et des brouettes,
j'en ai été pour mes frais (6h45 de temps PC perdu). Je vais recommencer avec un réel sur 80 bits, ce sera mieux !

gloubi

Posté par
dhalte
re : Enigmo 15 : L'interrupteur aléatoire * * * 21-05-08 à 12:17

gagnéPigé, j'étais parti sur l'idée que tu considérais les cavaliers comme les murs. En fait, le cavalier est le chemin... De plus, les bords sont eux aussi reliés.
J'ai donc compris ton idée jusqu'au bout. Félicitations.

1 2 +


Challenge (énigme mathématique) terminé .
Nombre de participations : 0
:)0,00 %0,00 %:(
0 0

Temps de réponse moyen : 80:11:44.
Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !