我将如何为该不变式编写循环? [英] How would I write a loop for this invariant?
问题描述
这些是算法的断言,用于找到数组b [h.k]的最小值:
These are assertions for an algorithm to find the minimum of an array b[h.k]:
Precondition: h <= k < b.length
Postcondition: b[x] is the minimum of b[h...k]
这是该不变式的正确循环吗?
Is this the correct loop for this invariant?
不变式:b [x]是b [h ... t]的最小值
invariant: b[x] is the minimum of 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;}
}
推荐答案
您可以通过以下方式找到数组的最小值(伪代码):
You can find the minimum of an array this way (pseudocode):
// 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]
因此,您基本上只需更改循环的上限和下限
So you basically just change the upper and lower bound of the loop
由于h<=k<b.length
,b[h]
有效,因此从下一个元素开始执行循环,直到k
遍历所需的元素为止(如果h==k
,则该循环为空)
Since h<=k<b.length
, b[h]
is valid and executing the loop from the next element until k
iterates over the reqiured elements (if h==k
, the loop is empty)
更新:由于您始终无法将伪代码实现到Java中,因此我将为您翻译它:
UPDATE: as you are consistently failing with the implementation of the pseudocode into java, I'll translate it for you:
// 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
Note: you could write i=i+1
as ++i
as well
这篇关于我将如何为该不变式编写循环?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!