Inscription / Connexion Nouveau Sujet

1 2 +


Posté par
matovitch
re : Enigmo 1 : Périmètre minimum 02-03-08 à 20:29

Voici une adresse interessante : [url][/url]http://fr.wikipedia.org/wiki/Polyomino

PS : ça va être dur très dur !!!

Posté par
rogerd
Périmètre minimum 02-03-08 à 22:38

gagnéBonjour à tous!
J'ai à peu près fini mon programme Maple.
Comme déjà dit: un contour est défini par une suite d'actions:
+1="tourner à droite",  0="aller tout droit", -1="tourner à gauche".
J'utilise 6 formes élémentaires: les 4 qui sont données et les pièces 2 et 4 retournées.
Quand on lui donne 2 formes, élémentaires ou composites, et qu'on lui impose la longueur de la frontière commune,  le programme sait construire la suite des assemblages possibles de ces deux formes en précisant pour chacun le point de départ (dans la liste associée) de la frontière commune. C'est indispensable si l'on veut un dessin où l'on voit les 2 formes accolées.
Je me suis arrangé pour ne pas avoir à construire des assemblages où la frontière commune ait une longueur<3, car ils risquent d'être trop nombreux et demander un temps non raisonnable.
A partir de là,  j'ai fait des expériences, continuant d'écrire le programme au fur et à mesure des conclusions.
Pour chaque expérience, Maple travaille pendant un temps imperceptible.
En gros:je fais l'hypothèse (absurde?) qu'il y a un périmètre<34; j'assemble 2 formes, puis j'accole la 3°, puis la 4°, en faisant les dessins au fur et à mesure.
J'arrive toujours à une impossibilité.
Il me reste à examiner le cas, peu vraisemblable , où 2 formes, élémentaires ou composites, auraient 2 frontières communes de longueur<3, et où on pourrait loger le reste dans le trou ainsi formé.
Je pense régler ce cas bientôt et prouver ainsi que
le périmètre minimum est bien 34.

Je suis à votre disposition pour toute précision.
Je peux même fournir le programme Maple. Cela me rassurerait que quelqu'un vérifiât mes allégations! (bien dit, n'est-ce pas?)

A bientôt!

Posté par
veleda
re : Enigmo 1 : Périmètre minimum * 03-03-08 à 18:00

gagnébonjour et bravorogerd
quel travail,je suis en admiration et me voilà rassurée,le minimun est bien 34

Posté par
matovitch
re : Enigmo 1 : Périmètre minimum 03-03-08 à 21:05

Bonjour !
Question toute bête : Combien de possibilité avec les frontière communes de longueur <3 (avec ces 4 pieces) ?

Posté par
rogerd
re : Enigmo 1 : Périmètre minimum 03-03-08 à 22:01

gagnéBonsoir matovitch!

Si tu parles d'assemblages où deux pièces élémentaires ont une frontière commune de longueur<3, il y en a certainement beaucoup et le programme exploserait sans doute si je lui demandais.
Mais le problème qui me reste à régler n'est pas celui -là:
Il me faut chercher les couples d'assemblages (1 pièce élémentaire+ 1 pièce élémentaire) ou (assemblage de 2 piéces élémentaires + 1 pièce élémentaire) qui se jouxtent suivant deux frontières communes ayant chacune une longueur<3 (ménageant ainsi un trou susceptible de recevoir ce qui manque).
Il ne doit pas y en avoir beaucoup et je pense y arriver.

Merci pour toute remarque comme la tienne, qui me force à creuser encore le problème.

Posté par
veleda
re : Enigmo 1 : Périmètre minimum * 04-03-08 à 07:18

gagnébonjour rogerd
désolée,j'ai mal lu la fin de ton post du 02 22h38,désolée pour toi que ce ne soit pas tout à fait terminé et merci pour tout le temps que tu passes pour trouver que 34 est bien le minimun
bonne journée

Posté par
rogerd
re : Enigmo 1 : Périmètre minimum 04-03-08 à 08:25

gagnéBonjour à tous et à toutes.

Je pense finir le travail en ne faisant pratiquement pas appel au programme Maple.
Pointons du doigt le raisonnement à préciser:
Tout est basé sur la formule: périmètre d'un assemblage= 66-2*S où S est la somme des longueurs des frontières communes à 2 pièces. 66 est la somme des périmètres des 4 formes (20+14+20+12).
D'autre part, pour faire un assemblage, je pars d'une pièce, lui en accole une 2°, puis une 3°, puis une 4°.  Pour calculer la longueur de la frontière commune à la nouvelle pièce B et à l'assemblage déjà fait A, je considère que la frontière commune à A et B est d'un seul tenant.
Il me faut prouver que l'autre cas, où A et B isolerait donc un trou ne peut pas se produire.
Déjà, si B est la dernière pièce, et si trou il y a, on ne peut le boucher.
Supposons donc que A est formée de 1 ou 2 pièces et qu'il y a un trou entre A et B.
On peut essayer de le boucher avec un assemblage de 2 pièces, qui aura un périmètre minimum de 27 (20+12-5). Ca ne marchera pas, le contact entre une pièce du trou et une pièce du bord ayant une longueur maximale de 5.
Même raisonnement si on essaie de boucher le trou avec une seule pièce, de périmètre 20.
Même raisonnement  si A est formée d'une seule pièce et qu'on essaie de boucher le trou entre A et l'autre pièce (B) avec une seule pièce.
Reste à examiner le cas où A est formée de 2 pièces et qu'on essaie de caser , dans le trou ménagé par A et B, la dernière pièce, de périmètre 12 ou 14.
Compte tenu du fait que la frontière entre 2 pièces est de longueur 5 au maximum, cela fait peu de cas à envisager. On examine alors les configurations données par le programme avec ces contraintes . Ces configurations ont déjà été préparées. On voit qu'aucune ne marche.
Si je n'ai pas fait de faute, ni dans mon raisonnement, ni dans mon programme (qui, suivi pas à pas, semble bien fonctionner):
Le périmètre minimum est bien de 34
  

Posté par
gui_tou
re : Enigmo 1 : Périmètre minimum * 04-03-08 à 19:11

Bonjour,

Quelle perspicacité rogerd !

Posté par
mikayaou
re : Enigmo 1 : Périmètre minimum * 04-03-08 à 19:15

en effet gui-tou, salut !

je sens rogerd bientôt futur étoilé, frenicle et no_futur2 ont à bien se tenir...

Posté par
gui_tou
re : Enigmo 1 : Périmètre minimum * 04-03-08 à 19:16

Salut Mika ! Quant à toi, très belle démo pour l'énigme du camion !

Posté par
mikayaou
re : Enigmo 1 : Périmètre minimum * 04-03-08 à 19:21

merci gui-tou

en revanche j'aurais mérité un car je n'ai pas vu la subtilité de la distance max et j'ai arrondi mal à propos...

monrow a été sympa sur ce coup là

anw, ou , je ne participe que rarement et la sanction a peu d'importance

Posté par
LeChacal619
re : Enigmo 1 : Périmètre minimum 23-03-09 à 00:12

Bonjour,

Je propose au lieu d'essayer de représenter tout les côtés de chaque case, de représenter les figures sous forme de case uniquement (par exemple dans une matrice de 5x5, ou 0 = rien, 1 = case:

Exemple pour la figure en croix :

{
{ 0, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0 },
{ 1, 1, 1, 1, 1 },
{ 0, 0, 1, 0, 0 },
{ 0, 0, 1, 0, 0 }
}

Si deux 1 se superposent, c'est que 2 cases sont l'une sur l'autre. Pour compter le nombre de côtés, si un 0 a gauche de la case, 1 côté à gauche, sinon pas de côté. Si un 0 au dessus, 1 côté, sinon pas de côté, etc.

Pour les symétries il suffit de faire une fonction qui interverti les valeurs des cases:

i = 0
variable temporaire = derniere cellule -i
derniere cellule -i = premiere cellule + i
premiere cellule +i = variable temporaire

Au prochain passage,
i = 1

On stoppe la boucle lorsque i >= nombre de cases /2 (quand on arrive à la moitié, pour un nombre impair la case centrale reste inchangée, pour un nombre pair on intervertit toutes les cases sans dépasser la moitié). Pour la symétrie verticale, on fait pareil en travaillant sur les colonnes au lieu des cellules.

Pour les rotations, on peut partir de n'importe quel côté. Un rotation de 90° suffit, pour faire la rotation de 180 il suffit de faire 90°+90°. Un seul sens de rotation suffit aussi.

Quant à trouver tout les possibilités, j'ai peur qu'il faille faire des boucles récursives (au moins deux) qui renvoient le périmètre à chaque fois que celui-ci est inférieur à tout ceux précédemment testés. La solution finale sera le périmètre minimum pour toutes les solutions.

Qu'en pensez-vous ?

1 2 +


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

Temps de réponse moyen : 105:13:07.


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 !