这些是查找数组 b[h.k] 最小值的算法的断言:
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;}
}
您可以通过这种方式找到数组的最小值(伪代码):
// 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]
所以你基本上只是改变循环的上限和下限
Since 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
as ++i
as well
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)