2001-gre-vs-practice.pdf/Q10 — различия между версиями

Текущая версия на 07:21, 21 декабря 2024

Вопрос: Q10-e5724f

p := 1; k := 0;
while k < n do
begin
    p := 2 * p;
    k := k + 1
end;

Для фрагмента программы выше, включающего целые числа p, k и n, какой из следующих вариантов является инвариантом цикла, то есть истинным в начале каждого выполнения цикла и при завершении цикла?

Ответы

• p = k + 1
• p = (k + 1)²
• p = (k + 1)2^k
• Правильный ответ: p = 2^k
• p = 2^{k + 1}

Объяснение

В начале каждой итерации цикла p удваивается, а k увеличивается на 1.

Начальные значения: p=1 и k=0. После первой итерации p=2 и k=1, после второй итерации p=4 и k=2, и так далее.

Таким образом, p всегда равно на протяжении 2^k всего цикла.