gpt4 book ai didi

algorithm - 伪代码中的负数组索引

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:05:56 25 4
gpt4 key购买 nike

考虑 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 开始?

或者也许伪代码中的负索引在某种程度上与正常的语言相关代码中的负索引不同(例如被忽略或其他),因此伪代码会很好吗?

最佳答案

一般来说:大多数编程语言的索引约束不需要也适用于伪代码(即使大多数伪代码不使用负索引)。

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

代码是计算编辑距离的动态规划实现

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

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

关于algorithm - 伪代码中的负数组索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57771692/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com