algorithm - 这些算法表示之间的区别？

Question

最近我一直在学习算法分析，在我的课上我看到这样的代码来表示一个示例算法:

z = 0
for x = 1; x <= n; x++ do
  for y = 1; y <= n; y++ do
    z = z + 1
  end for
end for

我理解这些 for 循环可以理解为“只要 x/y 等于或小于 n，就执行以下操作，并在每个循环结束时将 1 加到 x/y，然后再次测试条件”。然而，在一些像算法设计手册这样的书中，我看到了这样的东西:

r:= 0
for i:= 1 to n do
  for j:= 1 to i do
    for k:= j to i + j do
      r:= r + 1
return (r)

它与我给出的第一个例子在本质上是一样的还是意味着不同？这也让我感到矛盾，在第二个示例中没有像 x++ 这样的增量，因此循环在一定数量的循环后停止。另外，为什么在此算法中声明 k:= j 而不是简单地 k:= 1 因为 j=1？

澄清:我不是想问他们是否在产生相同输出的意义上做同样的事情，而是指他们两个中的 for 循环是否与在 n 的值后停止时一样工作例如，在每个循环后将 1 添加到变量 i 时匹配(就像在第一个示例中对 x 或 y 所做的那样)。

Answer 1

看起来您的第一个算法使用的是类似 C 的表示法，它指定了起始状态、继续的条件以及每次迭代后状态如何更新。

第二个似乎是使用基于在指定范围内迭代的循环:“对于该范围内的每个值，执行以下操作...”。这在 Python 或 Ruby 等现代脚本语言中相当普遍，可以说更接近人们对迭代的看法。

---

任一算法都可以使用另一算法的符号来编写。

算法1/风格2

z := 0
for x := 1 to n do
  for y:= 1 to n do
    z := z + 1
return(z)       # I’m assuming you actually wanted a return value

算法2/风格1

r = 0
for i = 1; i <= n; i++ do
  for j = 1; j <= i; j++ do
    for k = j; k <= i + j; k++ do
      r = r + 1
    end for
  end for
end for
return(r)

坚持使用一种风格，您会发现计数的差异并不是因为伪代码风格不同。这些是不同的算法。