algorithm - 一个while循环被执行了多少次？

Question

昨天我申请了计算机工程硕士学位，这是他们的问题之一。我无法解决它，所以我很好奇。

...
i = 1;
while (i <= n)
{
    i = i * 2;
}
...

这个while循环会被执行多少次，请以公式的形式给出你的答案。例如：登录 n...

谢谢

Answer 1

在循环的第 x^次i迭代中，等于 2 ^x（您可以通过归纳轻松证明这一点）。假设循环在 X 次迭代后停止，这意味着 n < 2 ^X。这也意味着在迭代 X-1 时循环仍在运行，因此 2 ^X-1 ≤ n。换句话说 ：

2 ^X-1 ≤ n < 2 ^X

从那里，很容易找到 X 作为 log ₂ (n) 的函数。