2011-gre-cs-practice-book.pdf/Q46

Вопрос: Q46-08c765

i = 0;
j = 0;
k = 0;
 
while (i < 10 and j < 10)
{
    if (A[i] > B[j])
    {
        C[k] = A[i];
        k = k + 1;
        i = i + 1;
    }
    else
    {
        C[k] = B[j];
        k = k + 1;
        j = j + 1;
    }
}

Какие из следующих утверждений могут служить инвариантом цикла для указанного выше цикла while?

I.

i<10i<10

или

j<10j<10

II.

i<11i<11

и

j<11j<11

III.

k=i+jk=i+j

Ответы

(A) Только I
(B) I и II
(C) I и III
(D) II и III
Правильный ответ: (E) I, II и III

Объяснение

Исходники — вопрос 46 на 46 странице книги «2011-gre-cs-practice-book.pdf»

Разберём каждое из утверждений

инвариант цикла – это некоторое утверждение о переменных, которое остаётся истинным:

перед входом в цикл,
после каждой итерации цикла (если цикл продолжается),
при завершении цикла.

I: или

1. Условие цикла: .
2. Если мы находимся внутри цикла, то одновременно и (то есть и то, и другое меньше 10).
  - Из того, что и , автоматически следует более слабое утверждение или .

1. Значит, пока цикл ещё не прерван, утверждение « или » будет верно всегда (оно слабее, чем само условие цикла).
2. I действительно является инвариантом.

---

II: и

1. Во время работы цикла и могут принимать значения от до включительно.
  - Как только станет равным (или ), цикл прервётся.
2. Внутри цикла мы имеем и .
  - Отсюда немедленно следует, что и .
3. При приращении или на они не могут «перескочить» сразу через , так что в любой момент внутри цикла условие и сохраняется.