Chemin parcouru

yan2

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

marsup

Si la puce se trouve par exemple après 229 sauts au point (1789,2018), le chemin emprunté est :

onooennsooossssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss
sssssssssssssssssssssssssssssn

Script lua :

directions =
{
  o = {dir="x",sens=1},
  e = {dir="x",sens=-1},
  n = {dir="y",sens=1},
  s = {dir="y",sens=-1},
}

function calculerPos(str)
  local pos = { x = 0, y = 0 }
  local l = 1 
  for c in str:gmatch"." do
    local increment = directions[c]
    pos[increment.dir] = pos[increment.dir] + increment.sens * l
    l = l * 2
  end
  return pos
end

t = {"o","s","e","n"}
helperUn = {[-1]={},[0]={},[1]={}}
for k,v in pairs(t) do
  local xy=calculerPos(v)
  helperUn[xy.x][xy.y]=v
end

helperDeux = 
{
  [0]={},
  [1]={},
  [2]={},
  [3]={},
}
for k,v in pairs(t) do
  for kk,vv in pairs(t) do
    local xy=calculerPos(v..vv)
    local x,y = (xy.x)%4,(xy.y)%4
    helperDeux[x][y]=v
  end
end

function calculerTraj(x,y,n)
  if n==1 then
    return helperUn[x][y]
  else
    local reponse = helperDeux[x%4][y%4]
    local tmp = calculerPos(reponse)
    local nx,ny = (x - tmp.x)/2,(y - tmp.y)/2
    return reponse..calculerTraj(nx,ny,n-1)
  end
end

Testé avec :

sstr = calculerTraj(1789,2018,229)
print(sstr)
pos = calculerPos(sstr)
print(pos.x,pos.y,#sstr)
-- retourne 1789	2018	229

Vérifié à la main (j'avais du mal à y croire, avec les 2^229 à calculer !)

strVerif="onooennsooo"
verif = calculerPos(strVerif)
print(verif.x,verif.y,2018-verif.y,2^#strVerif)
-- retourne 1789	-30	2048	2048.0

LOU16

Bonjour Marsup,

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.

marsup

Ah désolé pour la confusion Ouest / Est je suis mal latéralisé.

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.

marsup

La version chemin le plus court avec le test en $x^2 + y^2 = 1$ proposé par lou16.

Aussi corrigé l'interversion est $\longleftrightarrow$ ouest.

directions =
{
  e = {dir="x",sens=1},
  o = {dir="x",sens=-1},
  n = {dir="y",sens=1},
  s = {dir="y",sens=-1},
}

function calculerPos(str)
  local pos = { x = 0, y = 0 }
  local l = 1 
  for c in str:gmatch"." do
    local increment = directions[c]
    pos[increment.dir] = pos[increment.dir] + increment.sens * l
    l = l * 2
  end
  return pos
end

helperUn = {[-1]={},[0]={},[1]={}}
for k,v in pairs(directions) do
  local xy=calculerPos(k)
  helperUn[xy.x][xy.y]=k
end

helperDeux = {[0]={},[1]={},[2]={},[3]={}}
for k,v in pairs(directions) do
  for kk,vv in pairs(directions) do
    local xy=calculerPos(k..kk)
    local x,y = (xy.x)%4,(xy.y)%4
    helperDeux[x][y]=k
  end
end

function calculerTraj(x,y,chemin)
  local chemin = chemin or ""
  if x^2 + y^2 == 1 then
    return chemin .. helperUn[x][y]
  else
    local reponse = helperDeux[x%4][y%4]
    local tmp = calculerPos(reponse)
    local nx,ny = (x - tmp.x)/2,(y - tmp.y)/2
    return calculerTraj(nx,ny,chemin..reponse) -- version tail recursive
  end
end

Vérif:

sstr = calculerTraj(1789,2018)
print(sstr) -- eneeonnseeen
pos = calculerPos(sstr)
print(pos.x,pos.y,#sstr) -- 1789	2018	12