java - 我将如何为这个不变量编写一个循环？

Question

这些是求出数组 b[hk] 最小值的算法的断言：

Precondition: h <= k < b.length
Postcondition: b[x] is the minimum of b[h...k]

这是这个不变量的正确循环吗？

不变量：b[x] 是 b[h...t] 的最小值

int x = t;    int t = h;
// {inv: b[x] is the minimum of b[h...t]}
while (t != k) {
   t = t+1;
   if (b[t] < b[x])
      { x = t;}
}

Answer 1

您可以通过这种方式找到数组的最小值（伪代码）：

// assume b.length > 0
min = b[0]
for i=1 to b.length
  if b[i] < min
    min = b[i]

将其限制为b[h, ..., k]：

min = b[h]
for i=h+1 to k
  if b[i] < min
    min = b[i]

所以你基本上只是改变循环的上限和下限

因为h<=k<b.length,b[h]是有效的，并且从下一个元素开始执行循环，直到k遍历所需的元素（如果h==k，则循环为空）

更新：由于您在将伪代码实现为 java 时一直失败，我将为您翻译它：

// assume: int b[]; int h; int k; h<=k<=b.length and b.length>0
// find min == b[i] such that b[i]<=b[j] for all h<=j<=k
int min = b[h];
for (int i=h+1; i<k; i=i+1) {
  if (b[i] < min) {
    min = b[i];
  }
}
// here: min contains the (first) minimum element within b[h, ..., k]

注意：你也i=i+1可以++i写