[résolu]Visite guidée

vous pensez à une visite au musée?

Mathias a suivi le plan du musée et a visité les salles 1 à 9, dans l'ordre, sans jamais passer deux fois dans la même salle. Complétez le plan du musée.

[Vous devez être inscrit et connecté pour voir cette image]

1 à l'entrée et 9 à la sortie.

Code:

1->2->3
8<-7  4
9  6<-5


J'essaye.

Je propose:

1 . 4 . 5
2 . 3 . 6
9 . 8 . 7

C'est correct?

il ne faut pas changer l'emplacement du de la 4ème salle

Il y a raisonnement sous forme d'arbre si on le fait, il nous aide à trouver d'une raçon systématique et exacte la solution de ce problème, et même d'aurtes versions plus compliquées que celui ci (5 x 5 par exemple)

On raisonne en partant de la fin.
Le 8 précède le 9.
Donc on a:

1 . X . X
8 . X . 4
9 . X . X
ou bien
1 . X . X
X . X . 4
9 . 8 . X

Si on retient:
1 . X . X
8 . X . 4
9 . X . X

on sera obligé de mettre le 7 comme suit
1 . X . X
8 . 7 . 4
9 . X . X

Revenons à l'autre cas, le 7 a deux positions
1 . X . X
X . X . 4
9 . 8 . 7
ou bien
1 . X . X
X . 7 . 4
9 . 8 . X

On remarque que le cas
1 . X . X
X . X . 4
9 . 8 . 7

conduit à une impasse !!! où mettre le 6 ???

Donc la seule place du 7 et du 8 est
1 . X . X
8 . 7 . 4
9 . X . X

Continuons avec le 6. Il a une seule place:

1 . X . X
8 . 7 . 4
9 . 6 . X

Tout le reste est facile maintenant...

1 . 2 . 3
8 . 7 . 4
9 . 6 . 5
_________________

mosa a écrit:il faut pas changer l'emplacement du 4ème salle

est-il possible d'informatiser cette tâche pour trouver tous les chemins qui mênent à la sortie

OUI, c'est faisable.
Mais la récursivité n'est pas conseillée je crois car le facteur de branchement moyen d'un tel problème est 4 (max), donc im imaginer une complexité en mémoire de 4^n où n est la taille de l'échiquier.

Facteur de branchement = le nombre de successeurs d'un noeud donné dans l'arbre de recherche du problème.