Верхняя и нижняя граница цикла while
В прошлой статье я застрял в вопросе о встроенном программном курсе.
Вопрос задает следующее:
Let n be the number of iterations of the while loop. Calculate an upper and lower bound on the value of n given that b <= bmax.
x=a
if x<1
then
x=1
end if
while x<b
loop
x=x+1
end
Я думаю, что верхняя граница будет: n<=bmax, но я не понимаю, как рассчитать нижнюю границу. Кто-нибудь может помочь?
Спасибо
4 ответа
Для нижней границы вы получите это, когда a > 1. Тогда x начинается с a, а не с 1, поэтому вам нужно меньше итераций, чтобы добраться оттуда к b.
Если вы начинаете с x = a, а последняя итерация происходит, когда x = b (вы провалили тест), то вам нужно всего b - a итераций. Поскольку b <= bmax, ответ таков:
lower bound : bmax - a
upper bound : bmax - 1
Обратите внимание, что если a >= bmax, нижняя граница уменьшается до 0, поскольку вы не можете иметь менее 0 итераций.
Я думаю, что вопрос заключается в следующем: b является некоторым b <= bmax. Теперь выразите количество итераций n через bmax и a. Нижняя граница n тривиальна, 0, если a >= bmax; Верхняя граница на n имеет место a < 1, который дает: n = bmax - 1,
Учитывая только предоставленную информацию, лучшее, что вы можете сделать, это тривиальная нижняя граница - 0 итераций. Это потому что когда a>=bцикл не будет выполняться вообще.
Что касается верхней границы, у вас отключена одна ошибка. поскольку x начинается минимум с 1, вы можете иметь до bmax-1 итерации, а не bmax,
upper bound: max(0,b-1) <= max(0,bmax-1)
lower bound: if (a<1) then max(0,b-1), else max(0,b-a)
Нижняя граница не может быть выражена с помощью bmax вместо b, потому что мы имеем b<=bmaxне bmax<=b, Если нам не разрешено использовать bтогда это 0,