2011-gre-cs-practice-book.pdf/Q46 — различия между версиями
Материал из DISCOPAL
(→Вопрос: Q46-08c765) |
StasFomin (обсуждение | вклад) |
||
| (не показано 12 промежуточных версий 2 участников) | |||
| Строка 22: | Строка 22: | ||
} | } | ||
</code-c> | </code-c> | ||
| − | |||
| − | |||
Какие из следующих утверждений могут служить инвариантом цикла для указанного выше цикла while? | Какие из следующих утверждений могут служить инвариантом цикла для указанного выше цикла while? | ||
| − | I. | + | * I. i < 10 или j < 10 |
| − | II. | + | * II. i < 11 и j < 11 |
| − | III. | + | * III. k = i + j |
=== Ответы === | === Ответы === | ||
| − | * | + | * Только I |
| − | * | + | * I и II |
| − | * | + | * I и III |
| − | * | + | * II и III |
| − | * Правильный ответ: | + | * Правильный ответ: I, II и III |
=== Объяснение === | === Объяснение === | ||
| − | {{cstest-source|2011-gre-cs-practice-book.pdf| | + | {{cstest-source|2011-gre-cs-practice-book.pdf|37|46}} |
Разберём каждое из утверждений | Разберём каждое из утверждений | ||
| − | + | * I: i < 10 или j < 10 | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | * I: | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Из того, что 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 является инвариантом. | |
| − | + | ||
| − | k = | + | |
| − | + | ||
| − | + | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 09:59, 9 января 2025 (UTC)}} | |
| − | + | ||
| − | + | [[Категория:Понимание кода]] | |
| − | + | ||
Текущая версия на 10:01, 9 января 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
Ответы
- Только I
- I и II
- I и III
- II и III
- Правильный ответ: 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 является инвариантом.