[Algorithmique] Figure géométrique, 1/0
Fermé
Orci76
Messages postés
92
Date d'inscription
lundi 20 décembre 2010
Statut
Membre
Dernière intervention
21 avril 2015
-
30 juin 2012 à 05:01
eriiic Messages postés 24570 Date d'inscription mardi 11 septembre 2007 Statut Contributeur Dernière intervention 23 avril 2024 - 4 juil. 2012 à 09:17
eriiic Messages postés 24570 Date d'inscription mardi 11 septembre 2007 Statut Contributeur Dernière intervention 23 avril 2024 - 4 juil. 2012 à 09:17
A voir également:
- [Algorithmique] Figure géométrique, 1/0
- Si #n/a alors 0 - Forum Bureautique
- 0.facebook.cοm ✓ - Forum Facebook
- Erreur 0 free ✓ - Forum Mobile
- Combinaison de 3 chiffres de 0 à 9 ✓ - Forum Programmation
- Disque 1 aucun média 0 octets 0 octets ✓ - Forum Disque dur / SSD
5 réponses
eriiic
Messages postés
24570
Date d'inscription
mardi 11 septembre 2007
Statut
Contributeur
Dernière intervention
23 avril 2024
7 213
Modifié par eriiic le 4/07/2012 à 09:19
Modifié par eriiic le 4/07/2012 à 09:19
Bonjour,
Proposition de simplification :
Numérotons les lignes de 1 à 5 en partant du bas.
Pour chaque 1 de la ligne 5 on agit sur la cellule inférieure pour passer le 1 en 0, ainsi on a la ligne 5 à 0.
Idem pour successivement les lignes 4 à 2.
On se retrouve donc avec seulement la ligne 1 avec des 1.
Par exemple 11011, 11100
A partir de là, si configuration absente du dictionnaire (voir plus bas), utiliser la force brute, ou noter les configurations en privilégiant les lignes basses et utiliser un algorithme alpha-beta pour privilégier (et non pas élaguer) certaines branches.
Une fois la résolution trouvée se créer un dictionnaire des configurations 'ligne 1' et la solution simplifiée (ne pas agir 2 fois sur la même case).
Ajouter également la solution symétrique.
Puis simplifier l'ensemble de la résolution.
Peut-être que toutes les configurations 'ligne 1' n'admettent pas obligatoirement une solution (?)
eric
Proposition de simplification :
Numérotons les lignes de 1 à 5 en partant du bas.
Pour chaque 1 de la ligne 5 on agit sur la cellule inférieure pour passer le 1 en 0, ainsi on a la ligne 5 à 0.
Idem pour successivement les lignes 4 à 2.
On se retrouve donc avec seulement la ligne 1 avec des 1.
Par exemple 11011, 11100
A partir de là, si configuration absente du dictionnaire (voir plus bas), utiliser la force brute, ou noter les configurations en privilégiant les lignes basses et utiliser un algorithme alpha-beta pour privilégier (et non pas élaguer) certaines branches.
Une fois la résolution trouvée se créer un dictionnaire des configurations 'ligne 1' et la solution simplifiée (ne pas agir 2 fois sur la même case).
Ajouter également la solution symétrique.
Puis simplifier l'ensemble de la résolution.
Peut-être que toutes les configurations 'ligne 1' n'admettent pas obligatoirement une solution (?)
eric
Utilisateur anonyme
30 juin 2012 à 11:04
30 juin 2012 à 11:04
Bonjour
Non, pas clair...
Si tu inverses toutes les cases à chaque clic, ton système n'a que deux états : l'état initial et son complémentaire.
Quelles sont les vraies règles ?
Non, pas clair...
Si tu inverses toutes les cases à chaque clic, ton système n'a que deux états : l'état initial et son complémentaire.
Quelles sont les vraies règles ?
Orci76
Messages postés
92
Date d'inscription
lundi 20 décembre 2010
Statut
Membre
Dernière intervention
21 avril 2015
5
Modifié par Orci76 le 2/07/2012 à 00:20
Modifié par Orci76 le 2/07/2012 à 00:20
Han... ouais, j'ai oublié un mot, désolé...
En fait, ce sont toutes les cases adjacentes qui sont inversé...
Exemple:
Lorsque l'on clique sur celui du milieu, ceci devient:
Désolé, je n'avais pas assez attentivement relu mon post :(.
Merci d'avance.
EDIT: J'ai changé la figure, à vrai dire, les 4 boutons sur les extrémités Nord, Sud, Est et Ouest ne sont pas là, il s'agît seulement d'un carré, de 5x5 en l'occurrence en gros, une grille de 0 qu'il faut passer en 1.
En fait, ce sont toutes les cases adjacentes qui sont inversé...
Exemple:
0 1 0 1 1 0 0 0 0
Lorsque l'on clique sur celui du milieu, ceci devient:
0 0 0 0 0 1 0 1 0
Désolé, je n'avais pas assez attentivement relu mon post :(.
Merci d'avance.
EDIT: J'ai changé la figure, à vrai dire, les 4 boutons sur les extrémités Nord, Sud, Est et Ouest ne sont pas là, il s'agît seulement d'un carré, de 5x5 en l'occurrence en gros, une grille de 0 qu'il faut passer en 1.
Utilisateur anonyme
2 juil. 2012 à 08:54
2 juil. 2012 à 08:54
Joli casse-tête...
Je ne sais pas si je trouverai la solution, mais avec un peu de réflexion, on dégage quelques grandes règles :
L'ordre dans lequel on clique les cases n'importe pas
corollaire : si on a besoin de cliquer sur une cellule pour résoudre le problème, on ne doit cliquer qu'une seule fois
Dans le cas particulier du carré 5 x 5 à changer de 0 en 1, il existe un sous-ensemble des cases parmi lesquelles un nombre impair (donc au moins une) doit être cliqué :
Je continue de réfléchir, mais je parie que ce truc fait partie des classiques quelque part.
Je ne sais pas si je trouverai la solution, mais avec un peu de réflexion, on dégage quelques grandes règles :
L'ordre dans lequel on clique les cases n'importe pas
corollaire : si on a besoin de cliquer sur une cellule pour résoudre le problème, on ne doit cliquer qu'une seule fois
Dans le cas particulier du carré 5 x 5 à changer de 0 en 1, il existe un sous-ensemble des cases parmi lesquelles un nombre impair (donc au moins une) doit être cliqué :
1 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0 0 1
Je continue de réfléchir, mais je parie que ce truc fait partie des classiques quelque part.
On ne peut déduire que le sous-ensemble "solution" soit composé d'un nombre impair d'éléments.
0 0 0 1 0
0 0 1 1 1
0 1 0 1 0
1 1 1 0 0
0 1 0 0 0
Solution : 9, 17 => 2 éléments.
@Orci76 : quelle est la règle pour les angles ?
Je ne pense pas qu'il soit nécessaire de faire du brute-force complet là-dessus. La théorie voudrait qu'on cherche à obtenir un max de 1
A mon avis, il faut chercher à optimiser la quantité de 1 à t+2 (en optimisant à t+1, on risque d'être souvent bloqué) tout en utilisant l'idée qu'une case n'a pas être cliquée 2 fois.
0 0 0 1 0
0 0 1 1 1
0 1 0 1 0
1 1 1 0 0
0 1 0 0 0
Solution : 9, 17 => 2 éléments.
@Orci76 : quelle est la règle pour les angles ?
Je ne pense pas qu'il soit nécessaire de faire du brute-force complet là-dessus. La théorie voudrait qu'on cherche à obtenir un max de 1
A mon avis, il faut chercher à optimiser la quantité de 1 à t+2 (en optimisant à t+1, on risque d'être souvent bloqué) tout en utilisant l'idée qu'une case n'a pas être cliquée 2 fois.
Comem je l'avais dit, ma seconde remarque ne s'appliquait qu'au cas du carré 5 x 5 rempli de 0 qu'il faut tous transformer en 1
Le nombre pair d'éléments dont je parle ne concerne pas la solution globale, mais le sous-ensemble des cases que j'avais repérées avec un 1.
Quant à la règle pour les angles et les bords, c'est la même en ignorant simplement les cases qui sont en dehors du terrain, il me semble.
Je suis d'accord qu'il vaudrait mieux trouver une manière intelligente de résoudre le problème. Plutôt que de réfléchir sur t+2, je pense qu'il faut réfléchir à une considération un peu plus générale que la parité, genre ce qui se passe sur toute une ligne à la fois ou tout ce qui se passe sur une colonne à la fois.
Le nombre pair d'éléments dont je parle ne concerne pas la solution globale, mais le sous-ensemble des cases que j'avais repérées avec un 1.
Quant à la règle pour les angles et les bords, c'est la même en ignorant simplement les cases qui sont en dehors du terrain, il me semble.
Je suis d'accord qu'il vaudrait mieux trouver une manière intelligente de résoudre le problème. Plutôt que de réfléchir sur t+2, je pense qu'il faut réfléchir à une considération un peu plus générale que la parité, genre ce qui se passe sur toute une ligne à la fois ou tout ce qui se passe sur une colonne à la fois.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Orci76
Messages postés
92
Date d'inscription
lundi 20 décembre 2010
Statut
Membre
Dernière intervention
21 avril 2015
5
4 juil. 2012 à 03:33
4 juil. 2012 à 03:33
Merci de ta réponse, je ne suis pas vraiment sur d'avoir compris le raisonnement d'amenant à la seconde grande règle, cela me parait tout de même logique.
Je vais aussi continuer de chercher, je penserais aussi à regarder sur Internet, mieux, il ne serait en effet pas étonnant que cette énigme ait déjà été posé.
Merci pour ton aide :).
PS: Désolé du retard pour ma réponse, je n'ai pas pu me connecter plus tôt.
Je vais aussi continuer de chercher, je penserais aussi à regarder sur Internet, mieux, il ne serait en effet pas étonnant que cette énigme ait déjà été posé.
Merci pour ton aide :).
PS: Désolé du retard pour ma réponse, je n'ai pas pu me connecter plus tôt.
Pour ma seconde règle (qui n'apporte pas grand chose comme aide), voici le raisonnement, basé sur des parités comme tu dois t'en douter :
1 - pour faire passer une case de 0 à 1 , tu dois la faire changer d'état (je dirai basculer) un nombre impair de fois.
2 - tu as 25 cases à faire passer de 0 à 1 , tu as donc un nombre impair de basculements à faire
3 - si tu cliques sur une des cases qui a un 0 dans mon tableau, tu fais basculer 4 cases, ça ne change pas la parité du nombre total de basculement effectués
4 - si tu cliques sur une des cases qui a un 1 dans mon tableau, tu fais basculer 3 ou 5 cases, ce qui change la parité du nombre total de basculements. Partant de 0 basculement, il faut donc cliquer un nombre impair de fois sur une de ces cases, pour que le nombre total de basculements soit impair.
c.q.f.d.
Je n'ai pas avancé.
1 - pour faire passer une case de 0 à 1 , tu dois la faire changer d'état (je dirai basculer) un nombre impair de fois.
2 - tu as 25 cases à faire passer de 0 à 1 , tu as donc un nombre impair de basculements à faire
3 - si tu cliques sur une des cases qui a un 0 dans mon tableau, tu fais basculer 4 cases, ça ne change pas la parité du nombre total de basculement effectués
4 - si tu cliques sur une des cases qui a un 1 dans mon tableau, tu fais basculer 3 ou 5 cases, ce qui change la parité du nombre total de basculements. Partant de 0 basculement, il faut donc cliquer un nombre impair de fois sur une de ces cases, pour que le nombre total de basculements soit impair.
c.q.f.d.
Je n'ai pas avancé.
