2011-gre-cs-practice-book.pdf/Q46 — различия между версиями
Материал из DISCOPAL
(→Вопрос: Q46-08c765) |
(→Вопрос: Q46-08c765) |
||
Строка 27: | Строка 27: | ||
Какие из следующих утверждений могут служить инвариантом цикла для указанного выше цикла while? | Какие из следующих утверждений могут служить инвариантом цикла для указанного выше цикла while? | ||
− | I. i < 10 или j < 10 | + | * I. i < 10 или j < 10 |
− | II. i < 11 и j<11 | + | * II. i < 11 и j<11 |
− | III. k = i + j | + | * III. k = i + j |
=== Ответы === | === Ответы === |
Версия 23:42, 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
Из того, что 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.
- Утверждение III: k = i + j
Перед входом в цикл имеем k = i + j = 0. В то же время либо инкрементируется i, либо j. Таким образом, соотношение сохраняется при перехоже между итерациями.
Задача зарезервирована: Nikitashapovalov 20:53, 8 января 2025 (UTC)