2

これらは、配列 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;}
}
4

1 に答える 1

2

この方法で配列の最小値を見つけることができます (疑似コード):

// 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]kh==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ます

于 2012-04-18T02:36:38.890 に答える