0

我目前正在研究循环不变量，我在选择线性搜索算法的不变量时遇到了麻烦。

Inpput: A[1 ... n] of integers, k an integer value
Output: true if k belongs to A[1 ... n] false otherwise

LSearch(A,k)
i := 1
found := false
 WHILE i<=n AND found=false DO
   IF A[i] = k THEN
     found := true
   i:=i+1
return found

我选择的断言是：

  • 如果 k 存在于 A[1] 和 A[i] 中，found 包含真或假

在第一次迭代之前它成立，因为当时 A[1] 是单个元素，并且 found 被初始化为 false。

在循环之后 i 可以等于 i := 1 found := falseto n 和/或 found 可以为真（while 条件），因此在考虑 i<=n 的情况下断言保持不变。
你认为这可能是正确的吗？

4

1 回答 1

-1

断言是正确的，但也是无用的。found 是一个布尔值，无论 A 的属性如何，都将包含 True 或 False。这不会帮助您证明算法的正确性。

这是一道选择题吗？其他选择是什么？

于 2013-03-22T17:09:35.573 回答