伪代码中的负数组索引

Question

考虑这个 Levenshtein 距离的伪代码示例：

function Leven_dyn(S1[1..m], S2[1..n], m, n);
var D[0..m, 0..n];
begin
  for i := 0 to m do
    D[i, 0] := i;
  end for
  for j := 0 to n do
    D[0, j] := j;
  end for
  for i := 0 to m do
    for j := 0 to n do
      a := D[i - 1, j] + 1;    // here accessing negative index
      b := D[i, j - 1] + 1;    // and here
      c := D[i - 1, j - 1];    // and here
      if S1[i] != S2[j] then
        c := c + 1;
      end if
      if min(a, b, c) = c then
        D[i, j] := c;
      else if min(a, b, c) = a then
        D[i, j] := a;
      else
        D[i, j] := b;
      end if
    end for
  end for
  return D
end

我的第一个想法是它试图访问负数数组的索引，我想这不是故意的行为。

伪代码是否完全错误，嵌套的 for 循环应该从 1 开始？

或者伪代码中的负索引可能以某种方式与正常的语言相关代码不同地处理（例如忽略或其他），因此伪代码会很好吗？

Answer 1

总的来说： 大多数编程语言的索引约束不需要也适用于伪代码（即使大多数伪代码不使用负索引）。

但在这种情况下，我认为嵌套循环应该从 1 开始。

该代码是计算编辑距离的动态编程实现

前2个循环初始化矩阵的上边界和左边界。嵌套循环填充矩阵的内部。

您可以找到此伪代码的大量实现。例如。 https://en.wikipedia.org/wiki/Levenshtein_distance

伪代码中的负数组索引

Negative array index in a pseudocode

language-agnostic

algorithm

pseudocode

levenshtein-distance