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

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

Вопрос: Q47-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 на 37 странице книги «2011-gre-cs-practice-book.pdf»

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

• I: i < 10 или j < 10

Из того, что i<10 и j<10, автоматически следует более слабое утверждение i<10 или j<10. Пока цикл ещё не прерван, утверждение «i<10 или j<10» будет верно всегда. Следовательно, I действительно является инвариантом.

• II: i < 11 и j < 11

Внутри цикла мы имеем i <= 9 и j <= 9. Отсюда немедленно следует, что i < 11 и j < 11. Следовательно, II также является инвариантом.

• III: k = i + j

Перед входом в цикл имеем k = i + j = 0. В то же время либо инкрементируется i, либо j. Таким образом, соотношение сохраняется при переходе между итерациями и утверждение III является инвариантом.