来自麻省理工学院某些课件的伪代码

发布于 2024-08-04 14:34:51 字数 1322 浏览 10 评论 0原文

我从来没有太大的需要编写大量正式的伪代码，但这种需要已经出现，所以我想我应该选择一些标准，以便在代码之间保持一致。

为此，我挑选了一些“iTunes U”课件视频，其中包括 6.046J / 18.410J 算法简介 (SMA 5503)。

在第一个讲座视频中，讲师在黑板上写了插入排序，他写道：

Insertion-Sort(A, N) // Sorts A[1..n]
  for j ← 2 to n
    do key ← A[j]
      i ← j-1
      while i > 0 and A[i] > key
        do A[i+1] ← A[i]
          i ← i-1
      A[i+1] ← key

那么，我的问题：

为什么当 A[i+1] = 时 i ← j-1键？也就是说，为什么在某些情况下 ← ，而在另一种情况下 = ？请注意，在上面的代码中，←也用于后者，但是在网络上提供的讲义中，使用了=，这只是一个拼写错误吗？（我认为是这样）
更重要的是，为什么当i ← j-1时做key ← A[j]？有什么特别之处以至于它需要这样的 do 命令和缩进？

换句话说，为什么上面的伪代码不是这样写的（带有我的亮点）：

Insertion-Sort(A, N) // Sorts A[1..n]
  for j ← 2 to n
    key ← A[j]                  <-- lost the do here
    i ← j-1                     <-- no indentation
    while i > 0 and A[i] > key
      A[i+1] ← A[i]             <-- lost the do here
      i ← i-1                   <-- no indentation
    A[i+1] ← key

最后一个问题：是否有人在某个地方有方便的伪代码代码标准？我的主要目标是一致性，这样我只需“教”接受者一次。

原文

I've never had much need for writing large quantities of formal pseudo-code but the need has arisen, so I thought I'd pick some standards in order to stay consistent across code.

To that effect I picked up some "iTunes U" courseware videos, amongst other things the 6.046J / 18.410J Introduction to Algorithms (SMA 5503).

In the very first lecture video, the lecturer writes Insertion Sort on the blackboard, and he writes this:

Insertion-Sort(A, N) // Sorts A[1..n]
  for j ← 2 to n
    do key ← A[j]
      i ← j-1
      while i > 0 and A[i] > key
        do A[i+1] ← A[i]
          i ← i-1
      A[i+1] ← key

So, my questions:

Why i ← j-1 when A[i+1] = key? That is, why ← in some cases, and = in another? Note that in the above code, the ← is used for the latter too, but in the handouts, available on the web, = is used, is this simply a typo? (I assume so)
More important, why do key ← A[j] when i ← j-1? What is so special that it requires a do command like that, and an indentation?

In other words, why isn't the above pseudo-code written like this (with my highlights):

Insertion-Sort(A, N) // Sorts A[1..n]
  for j ← 2 to n
    key ← A[j]                  <-- lost the do here
    i ← j-1                     <-- no indentation
    while i > 0 and A[i] > key
      A[i+1] ← A[i]             <-- lost the do here
      i ← i-1                   <-- no indentation
    A[i+1] ← key

Final question: Does anyone have a code standard for pseudo-code handy somewhere? My main goal is consistency, so that I only have to "teach" the recipients once.

分享到QQ

分享到微博