0

我被困在过去一篇关于嵌入式软件课程的论文中的一个问题上。

该问题提出以下问题：

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

4 回答 4

3

对于下限，当 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。

于 2013-04-21T21:41:42.093 回答
0

仅给定所提供的信息，您能做的最好的就是微不足道的下限 - 0 次迭代。这是因为当 时a>=b，循环根本不会执行。

至于上限，您有一个错误。由于x至少从 1 开始，因此您最多可以进行bmax-1迭代，而不是bmax.

于 2013-04-21T21:44:56.527 回答
0

我认为问题是：b 是一些 b <= bmax。现在用 bmax 和 a 表示迭代次数 n。n 的下界是微不足道的0，如果a >= bmax; n 的上限是 case a < 1，产生：n = bmax - 1。

于 2013-04-21T21:47:34.390 回答
0 
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。

于 2016-02-03T13:16:45.943 回答