2004-gre-cs-practice-book.pdf/Q15 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: « == Вопрос: Q15-4c9f66 == <i>Тут вставьте перевод вопроса. Используйте [https://wiki.4intra.net/Help:%D0%A4%D0%BE%D1%80…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| − | |||
== Вопрос: Q15-4c9f66 == | == Вопрос: Q15-4c9f66 == | ||
| + | Инвариантом для приведенного ниже цикла является <m>z*x^k=b^n</m> и <m>k \ge 0</m>. | ||
| − | < | + | <code-c> |
| − | + | x := b; k := n; z := 1; | |
| − | + | while (k != 0) | |
| − | + | { | |
| + | if odd(k) then z := z*x; | ||
| + | x := x*x; | ||
| + | k := [k/2]; | ||
| + | } | ||
| + | </code-c> | ||
| + | |||
| + | Когда цикл завершается, что из перечисленного ниже должно быть '''истинным'''? | ||
=== Ответы === | === Ответы === | ||
| − | < | + | * <m>x=b^n</m> |
| − | + | * Правильный ответ: <m>z=b^n</m> | |
| + | * <m>b=x^n</m> | ||
| + | * <m>b=z^n</m> | ||
| + | * <m>k \ne 0</m> | ||
| − | + | === Объяснение === | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | Это классический алгоритм «быстрого возведения в степень». | |
| − | + | ||
| − | + | ||
| + | {{cstest-source|2004-gre-cs-practice-book.pdf|18|15}} | ||
| − | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 00:43, 14 декабря 2024 (UTC)}} | |
| − | + | ||
| − | {{ | + | |
| − | + | ||
| − | + | ||
| − | + | [[Категория:Циклы]] | |
Версия 00:43, 14 декабря 2024
Вопрос: Q15-4c9f66
Инвариантом для приведенного ниже цикла является и .
x := b; k := n; z := 1; while (k != 0) { if odd(k) then z := z*x; x := x*x; k := [k/2]; }
Когда цикл завершается, что из перечисленного ниже должно быть истинным?
Ответы
- Правильный ответ:
Объяснение
Это классический алгоритм «быстрого возведения в степень».
Исходники — вопрос 15 на 18 странице книги «2004-gre-cs-practice-book.pdf»