不变性不够强，无法在数组中找到 'e' 的第一个实例

Question

我正在为我的 Dafny 考试学习，我想不出一个足够强大的不变量来解决这个问题。

Given an array of characters, it returns the index of the first ‘e’.

我们可以假设输入数组有一个 'e'.

到目前为止，这是我的代码：

method firstE(a: array<char>) returns (i: int)
requires a.Length > 0
ensures exists i :: 0 <= i < a.Length && a[i] == 'e'
{
    i := 0;
    while i < a.Length
    invariant 0 <= i <= a.Length
    invariant forall j | 0 <= j < i :: a[j] != 'e'
    // invariant exists j :: 0 <= j < a.Length && a[j] == 'e'
    {
        if (a[i] == 'e') {
            return i;
        }
        i := i + 1;
    }
}

预期行为：

[‘c’,’h’,’e’,’e’,’s’,’e’] -> 2

关于如何解决这个问题的任何提示？

Answer 1

不变量不是问题，这是后置条件（感谢@JamesWilcox）

ensures exists i :: 0 <= i < a.Length && a[i] == 'e'

不考虑数组没有'e'的情况。

所以这是经过验证的代码：

method firstE(a: array<char>) returns (i: int)
requires a.Length > 0
ensures if 'e' in a[..] then exists i :: 0 <= i < a.Length && a[i] == 'e' else i == -1
{
    if ('e' !in a[..]) {
        return -1;
    }
    i := 0;
    while i < a.Length
    invariant 0 <= i <= a.Length
    invariant forall j :: 0 <= j < i ==> a[j] != 'e'
    {
        if (a[i] == 'e') {
            return i;
        }
        i := i + 1;
    }
}

不变性不够强，无法在数组中找到 'e' 的第一个实例

Invariant not strong enough to find the first instance of 'e' in an array

dafny