Верхняя и нижняя граница цикла while

Я застрял в вопросе в прошлом документе для встроенного программного обеспечения.Верхняя и нижняя граница цикла 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

Я думаю, что верхняя граница будет: п < = Bmax, но я не понимаю, как вычислить нижнюю границу. Может ли кто-нибудь помочь?

Благодаря

источник

2013-04-21 sam

Для нижней границы, вы получите, что при а> 1. Тогда х начинается с, а не на 1, так что вам нужно меньше итераций, чтобы получить оттуда б.

Если вы начинаете с x = a, а последняя итерация происходит, когда x = b (вы терпите неудачу), вам понадобилось всего b - итераций. Так как б < = Bmax, ответ:

lower bound : bmax - a 
upper bound : bmax - 1

Обратите внимание, что если> = Bmax, нижняя граница сводится к 0, так как вы не можете иметь меньше, чем 0 итераций.

источник

2013-04-21 21:41:42 Floris

Учитывая только предоставленную информацию, лучшее, что вы можете сделать, это тривиальная нижняя граница - 0 итераций. Это происходит потому, что когда a>=b, цикл не будет выполняться вообще.

Что касается верхней границы, у вас есть одна ошибка. Начиная с x начинается с минимума 1, вы можете иметь до bmax-1 итераций, а не bmax.

источник

2013-04-21 21:44:56 Antimony

Я думаю, что вы упрощаете нижнюю границу. Да, это может быть как ноль, но может быть выражено в терминах – Floris

Но неизвестно. Вы также можете выразить верхнюю часть в терминах b, но поскольку проблема дает вам привязку к b в терминах явной константы bmax, предполагается, что ваши намерения не связаны с a и b. – Antimony

@Floris, в этом случае это будет bmax - a, для a> = 1. – user268396

Я думаю, что вопрос: b есть некоторые b < = bmax. Теперь выражаем число итераций n в терминах bmax и a. Нижняя граница на n тривиальна, 0, если a >= bmax; Верхняя граница по n - это случай a < 1, который дает: n = bmax - 1.

источник

2013-04-21 21:47:34 user268396

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<=bmax, не bmax<=b. Если нам не разрешено использовать b, то это 0.

источник

2016-02-03 13:16:45

Верхняя и нижняя граница цикла while

ответ

Смежные вопросы