Chemin parcouru
Bonjour,
l'exercice suivant est tiré de la 25ème Olympiade Italienne de mathématiques (année 2009).
Une puce se trouve initialement au point $(0,0)$ du plan euclidien. Elle fait ensuite $n$ sauts. Chaque saut est dans l'une des quatre directions cardinales (nord, est, sud ou ouest). Le premier saut a pour longueur $2^0$, le deuxième saut a pour longueur $2^1,$ le troisième saut a pour longueur $2^2$, et ainsi de suite, le $n$-ème saut a pour longueur $2^{n-1}$.
Montrer que si nous connaissons le nombre de sauts et la position finale, nous pouvons déterminer de façon unique le chemin pris par la puce.
Bon, en prenant $e_1=(1,0)$ et $e_2=(0,1)$, et en considérant le vecteur $u=\displaystyle\sum_{k=0}^{n-1}2^kv_k=\sum_{k=0}^{n-1}2^kw_k$ avec $v_k,w_k\in\{\pm e_1,\pm e_2\}$, on montre par récurrence sur $n$ que $v_k=w_k,\,\,\, k=0,1,\cdots,n-1$. On a ainsi montré l'existence et l'unicité du chemin pris par la puce.
Cependant, j'ai une question (peut-être bête), trouver un algorithme qui donne ce chemin. Concrètement, si la puce se trouve par exemple après $229$ sauts au point $(1789,2018)$, quel chemin a-t-elle emprunté ?
Cordialement,
Yan2
l'exercice suivant est tiré de la 25ème Olympiade Italienne de mathématiques (année 2009).
Une puce se trouve initialement au point $(0,0)$ du plan euclidien. Elle fait ensuite $n$ sauts. Chaque saut est dans l'une des quatre directions cardinales (nord, est, sud ou ouest). Le premier saut a pour longueur $2^0$, le deuxième saut a pour longueur $2^1,$ le troisième saut a pour longueur $2^2$, et ainsi de suite, le $n$-ème saut a pour longueur $2^{n-1}$.
Montrer que si nous connaissons le nombre de sauts et la position finale, nous pouvons déterminer de façon unique le chemin pris par la puce.
Bon, en prenant $e_1=(1,0)$ et $e_2=(0,1)$, et en considérant le vecteur $u=\displaystyle\sum_{k=0}^{n-1}2^kv_k=\sum_{k=0}^{n-1}2^kw_k$ avec $v_k,w_k\in\{\pm e_1,\pm e_2\}$, on montre par récurrence sur $n$ que $v_k=w_k,\,\,\, k=0,1,\cdots,n-1$. On a ainsi montré l'existence et l'unicité du chemin pris par la puce.
Cependant, j'ai une question (peut-être bête), trouver un algorithme qui donne ce chemin. Concrètement, si la puce se trouve par exemple après $229$ sauts au point $(1789,2018)$, quel chemin a-t-elle emprunté ?
Cordialement,
Yan2
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Script lua :
Testé avec :
Vérifié à la main (j'avais du mal à y croire, avec les 2^229 à calculer !)
L'algorithme suivant, propose , pour passer du point $(0;0)$ au point $(1789; 2018)$ en 229 étapes, un cheminement qui débute par la séquence $ONOOENNSOOO$ suivie d 'une longue course effrénée vers le Sud et ponctuée par un grand bond en arrière vers le Nord. Ce n'est pas exactement la route que tu as suivie , mais c'est normal, car tu as trouvé original de coder $(1;0)$ par $O$ , alors que j'ai cru bon de faire $(1;0) =E$.
Mes faibles compétences en algorithmique font que j'ai du mal à décrypter ton code, et je ne sais pas si "mon" algorithme est vraiment différent du tien.
Entrer $x$,$y$ ,$n$ ($x,y,n \in\N^*, x,y$ de parités différentes, $(x,y)$ sont les coordonnées de l'objectif, $n$ le nombre d'étapes.)
$i$ prend la valeur $0$.
Tant que $x^2+y^2\neq1$ OU $i<n-1$
$\:\:\:\: $ $a$ prend la valeur ($x\mod2)\times((x+y)\mod4-2)$ ($x\mod k$ désigne le reste de la division euclidienne de $x$ par $k$.)
$\:\:\:\: $ $b$ prend la valeur ($y\mod2) \times((x+y)\mod4-2)$.
$\:\:\:\: $ Afficher $(a, b)$. (en le codant par $O,E,N$ ou $S$.)
$\:\:\:\:$ $ x$ prend la valeur $\frac{x-a}2$.
$\:\:\:\: $ $y$ prend la valeur $\frac{y-b}2$.
$\:\:\:\: $ $ i $ prend la valeur $i+1$.
Fin du Tant que.
Afficher $(x,y)$ ( en le codant par la direction cardinale adéquate).
Si l'on souhaite obtenir l'unique chemin de longueur minimale allant de $(0;0)$ à $(x;y)$, il suffit de supprimer dans le "Tant que" la condition "OU $i<n-1$" ainsi que les lignes "$i$ prend la valeur $0$" et "$i$ prend la valeur $i+1$" qui ne servent plus à rien.
Amicalement.
Mon algorithme consiste à coder l'application qui à une suite de mouvements associe la position finale (à l'erreur, que tu as relevée, près !)
Pour revenir en arrière : des positions finales au trajet, je construis deux tableaux associatifs, qui permettent de ne faire aucun calcul à la main.
helperUn ne sert que pour un trajet de longueur 1 : aux quatre positions possibles, après un saut, il associe la lettre correspondante.
Donc helperDeux associe, lui aux seize couples $(x,y) \mod 4$ possibles après deux saut, le premier de ces deux sauts.
La remarque fondamentale est que le premier saut d'une suite de longueur $n\ge 2$ quelconque est déterminé par la classe modulo 4 de $(x,y)$.
La façon dont ce premier saut est déterminé ne dépend pas de $n$ à partir de $n\ge2$.
helperDeux permet donc d'identifier le premier saut dans une suite de longueur $>1$ quelconque.
Voilà tout, après, on résout récursivement.
Aussi corrigé l'interversion est $\longleftrightarrow$ ouest.
Vérif: