in Introduction aux algorithmes (CLRS) , Cormen et al. Parlez de la résolution du problème de coupe de tige comme suit (Page 369)
EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
let r[0...n] and s[0....n] be new arrays
r[0] = 0
for j = 1 to n:
q = -infinity
for i = 1 to j:
if q < p[i] + r[j - i]: // (6)
q = p[i] + r[j - i]
s[j] = i
r[j] = q
return r and s
3 Réponses :
Voici la clé: pour i = 1 à j
i commencera à 1 et augmentera la valeur j .
i ne sera jamais supérieur à j , donc j-i ne sera jamais inférieur à zéro.
Code Labs - Yup! Une supervision stupide. Merci d'avoir fait remarquer cela.
Pas de problème, nous négligeons tous les choses parfois :)
variable Je ne serai plus grand que la variable J en raison de la boucle interne et que l'indice r ne devient donc jamais moins de zéro.
Vous manquez les conditions dans l'intérieur de la boucle. En cela, la valeur de I ne va que jusqu'à J. Donc, s'il dépasse J, la boucle sera terminée. Par conséquent, aucune question des indices négatifs que vous avez mentionnés.