Énigmatique Xunor • Afficher le sujet - La mouche et l'araignée

Cette page en français This page doesn't exist in English
Énigmatique Xunor
Le Forum
Nous sommes le Jeu Mar 28, 2024 22:49

Heures au format UTC + 2 heures




Poster un nouveau sujet Répondre au sujet  [ 1 message ] 
Auteur Message
 Sujet du message: La mouche et l'araignée
MessagePosté: Jeu Avr 09, 2009 00:58 
Hors ligne
Le patron
Avatar de l’utilisateur

Inscription: Ven Juin 22, 2007 14:20
Messages: 81
Bon voici une question intéressante que j'ai reçu via la partie anglaise du site...
(Traduit de l'anglais)
Alex a écrit:
Oui, oui, c'est une énigme célèbre que j'ai résolue pour ma classe, mais avec des dimensions différentes.
Ceci nous a conduit à une variante intéressante : Comment résoudre ce problème pour le cas général d'un parallélépipède rectangle de dimension x par y par z et 2 points sur la surface ?
Il y a-t-il toujours un chemin optimal ?

Donc pour qu'on sache de quoi je parle, un petit lien vers l'énoncé :
http://xunor.free.fr/enigmes/araignee.php

Donc deux questions ici :
-Il y a-t-il toujours un chemin optimal ?
-Comment le trouver ?

Il y a-t-il toujours un chemin optimal ?
OUI
ok ok c'est un peu court comme réponse, développons...
Quelque-soit la pièce et la position de la mouche et de l'araignée il y aura toujours au moins une solution optimale, par contre il peut y en avoir plusieurs : dans le cas de notre pièce un nombre fini...
Cette remarque sur la solution optimale est toujours vraie, quelque soit la forme de la pièce et quelque soit la position des deux protagonistes (même biscornue).
Il faut bien garder à l'idée que le chemin optimal dépend des dimensions de la pièce et des positions des protagonistes ....


Comment trouver le chemin optimal ?
"Voilà une question qu'elle est bonne !"
Bon il faut bien voir qu'il y a 3 cas (et seulement 3 cas) :
1) la mouche et l'araignée sont sur la même face
2) la mouche et l'araignée sont sur 2 faces qui se touchent (ayant une arête en commun)
3) la mouche et l'araignée sont sur 2 faces "face à face"

Ces cas sont rangés par difficultés croissantes (le dernier cas étant largement bien plus compliqué que les deux autres)
1) si la mouche et l'araignée sont sur la même face le chemin optimal est la ligne droite sur cette face sans passer par ailleurs (et le chemin optimal est toujours unique)

2) si la mouche et l'araignée sont sur 2 faces qui se touchent (ayant une arête en commun), ce n'est pas bien plus compliqué : on déplie le patron de la pièce en laissant les deux faces se toucher par l'arête et on trace une ligne droite, et pouf on a le chemin optimal qui est encore unique !
<< ATTENTION UNE ERREUR ICI : je corrigerais quand je trouverais le temps ;)

3) Le cœur du problème ! Quel est donc le chemin optimal si les deux points sont sur des faces opposées ?
Et bien c'est largement plus compliqué ! Il faut raisonner sur 20 façons différentes de déplier le patron de la pièce...
de tracer une ligne droite sur chacun de ces patron et de prendre le chemin le plus court.
Remarques:
-si le trait dépasse du patron le chemin doit être rejeté (mais bon même sans le faire ce chemin ne peut pas être le plus court donc on pourrait quand même le garder dans nos tests).
-je parle de 20 façons de déplier le patron alors qu'il en existe bien plus des façon de déplier un patron de parallélépipède rectangle, mais les 20 que je présente ci-dessous suffisent, à vous de voir pourquoi...

Image
Sur cette image le sol est en jaune, le plafond en vert et chaque mur a sa couleur propre avec une flèche qui indique le haut du mur...
j'ai supposé que la mouche (ou l'araignée) était sur le mur violet, et l'araignée (ou la mouche) sur le mur rose.
La difficulté du problème est de bien définir, la position de la mouche et de l'araignée et de ne pas se mélanger !
Pour chaque patron la distance parcourue est régie par une équation "simple" dépendant "seulement" des dimensions de la pièce et des positions des deux animaux.
Pour déterminer le chemin optimal on doit donc comparer ces 20 distances !
Si il y en a qui s'ennuient et veulent catégoriser le chemin optimal en fonction de x,y,z et les positions des 2 animaux : qu'ils essaient ;) C'est quand même un problème à 7 variables : x,y,z (3 variables), la position de la mouche (2 variables) et la position de l'araignée (2 variables)
Par contre si quelqu'un s'ennuie on peut très bien imaginer un code qui dise quel est le chemin optimal en utilisant ces différents patrons...


Haut
 Profil  
 
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 1 message ] 

Heures au format UTC + 2 heures


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 4 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages
Vous ne pouvez pas joindre des fichiers

Rechercher:
Aller à:  
cron
Développé par phpBB® Forum Software © phpBB Group
Traduction par phpBB-fr.com