2011-gre-cs-practice-book.pdf/Q46 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| (не показано 17 промежуточных версий 2 участников) | |||
| Строка 1: | Строка 1: | ||
== Вопрос: Q46-08c765 == | == Вопрос: Q46-08c765 == | ||
| − | < | + | <code-c> |
| − | + | 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; | ||
| + | } | ||
| + | } | ||
| + | </code-c> | ||
| − | + | Какие из следующих утверждений могут служить инвариантом цикла для указанного выше цикла 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 | ||
| − | + | === Объяснение === | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | {{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 является инвариантом. | |
| − | + | ||
| − | + | ||
| − | + | {{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 является инвариантом.