2011-gre-cs-practice-book.pdf/Q46 — различия между версиями

Версия 23:27, 8 января 2025

Вопрос: 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 < 10 или j < 10 II. i < 11 и j<11 III. k = 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: i < 10 или j < 10

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

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

---

• II: i < 11 и j < 11

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

• 1. II тоже является инвариантом (он даже слабее, чем , но тем не менее остаётся истинным всюду, пока цикл не завершён).

---

• Утверждение III: k = i + j

• 1. Проверим на шагах цикла:
     • Начальные значения: , , .
       1. Очевидно, . Утверждение верно перед входом в цикл.

• 1. • Шаг цикла:
       1. Если , то выполняется:

• 1. • 1. Новая сумма увеличится на (так как увеличили на , не трогали). Параллельно тоже увеличился на . Значит, соотношение сохранится.

• 1. • 1. Если , то выполняется:

• 1. • 1. Аналогично, теперь снова увеличилось на (увеличился ), и тоже на . Значит, остаётся равным .

• 1. После каждой итерации связь сохраняется.
  2. III однозначно является инвариантом.