Olivier Miakinen wrote:
Le 25/05/2008 10:42, nospam@toto.ch a écrit :
Je suis tombé sur un problème qui apparemment est simple mais je ne sais
pas résoudre.. Peut-être que cela vous amusera d'y jeter un coup d'oeil
Soit un grillage (genre papier quadrillé) de n lignes et m colonnes. En
partant du coin en haut à gauche, il faut rejoindre le coin en bas Ã
droite. Les seuls mouvements autorisés sont un déplacement d'une case
vers la gauche ou d'une case vers le bas (on ne rebrousse pas chemin). Et
la question qui tue (je suis certain que ça doit être tout simple, mais
je rame) c'est de trouver combien de chemins différents possible il est
possible de trouver.
J'ai essayé une méthode "révolutionnaire" [...]
Il y a une méthode qui, loin d'être révolutionnaire, a le mérite d'être
toute simple.
Chacune des cases du haut ne peut être atteinte que d'une façon
différente : tu écris 1 dans chacune de ces cases.
111111
......
......
......
Idem pour chacune des cases de gauche : tu écris 1 dans chacune.
111111
1.....
1.....
1.....
Ensuite, chaque case peut être atteinte soit de la case au dessus
d'elle, soit de la case à sa gauche. Le nombre de trajets est la somme
des nombres des deux cases. Par exemple, pour la case de la 2e ligne
2e colonne : 1+1 = 2
111111
12....
1.....
1.....
Et tu continues à remplir...
111111
123456
136...
1.....
etc.
trop simple pour moi ce genre de solution ;-) Il suffit de faire des
additions... même un gamin de 8 ans pourrait comprendre.. Merci pour ton
explication ! j'en étais à des années lumière
--
new
