Zébulon : premiers calculs

• Depuis $0$, le glouton compare $R[2]=3$ et $R[3]=4$ et va en $3$ ; depuis $3$, il compare $R[5]=1$ et $R[6]=6$ et va en $6$ ; depuis $6$, seule la case $8$ est accessible. Chemin $0\to 3\to 6\to 8$, de valeur $2+4+6+3=15$.

nom : R
valeurs : 2 -1 3 4 -5 1 6 -2 3
vert : 0 3 6 8
fleches : 0->3 3->6 6->8
legende : chemin glouton 0 → 3 → 6 → 8, de valeur 2 + 4 + 6 + 3 = 15

• Avec $m(0)=r_0$, $m(1)=-\infty$, $m(2)=r_0+r_2$ et $m(j)=\max \{m(j-2),m(j-3)\}+r_j$ :

$$M=[2,-\infty ,5,6,0,7,12,5,15].$$

Par exemple

$$m(6)=\max \{m(4),m(3)\}+6=12,m(8)=\max \{m(6),m(5)\}+3=15.$$ On remonte : $8$ vient de $6$ ($m(6)>m(5)$), $6$ vient de $3$, $3$ vient de $0$. Le chemin optimal est $0\to 3\to 6\to 8$, de valeur $15$ : ici le glouton trouve l'optimum, ce qui ne prouve rien en général (voir le cours).

nom : M
valeurs : 2 -∞ 5 6 0 7 12 5 15
colorier : 8
vert : 0..7
fleches : 5->8 6->8
legende : m(8) = max(m(6), m(5)) + 3 = max(12, 7) + 3 = 15

• $N(0)=1$, $N(1)=0$, $N(2)=1$, puis $N(j)=N(j-2)+N(j-3)$ : $N(3)=1$, $N(4)=1$, $N(5)=2$, $N(6)=2$, $N(7)=3$, $N(8)=4$. Les quatre chemins sont $0\to 2\to 4\to 6\to 8$ (valeur $9$), $0\to 2\to 5\to 8$ ($9$), $0\to 3\to 5\to 8$ ($10$) et $0\to 3\to 6\to 8$ ($15$).

nom : N
valeurs : 1 0 1 1 1 2 2 3 4
colorier : 8
vert : 0..7
fleches : 5->8 6->8
legende : N(8) = N(6) + N(5) = 2 + 2 = 4

$ java ZebulonExos
Exercice 1 : R = [2, -1, 3, 4, -5, 1, 6, -2, 3]
  chemin glouton : 0 -> 3 -> 6 -> 8
glouton : 15
M = [2, -inf, 5, 6, 0, 7, 12, 5, 15]
chemin optimal : 0 -> 3 -> 6 -> 8
nombre de chemins de 0 a 8 : 4