找出输入和循环执行次数之间的关系。

Question

鉴于此代码：

k = 1;
p = 0;
while (k < n){
  k *= 3;
  p++;
}

根据 n 定义第 03 行将执行的次数，其中 n 是输入。（提示：在第 06 行的循环末尾找出 p 和 k 与 n 的关系。用 n 的热量表示 p 并用它来回答这个问题。）

到目前为止，我所做的是计算出与这些 n 值相关的 p 和 k 执行次数：

n = 1 -> k/p 迭代 = 1
n = 3 -> k/p 迭代 = 3
n = 10 -> k/p 迭代 = 3
n = 30 -> k/p 迭代 = 4

我正在努力弄清楚如何定义 n 和 k/p 的迭代次数之间的关系。如果有人可以解释如何确定这一点，我们将不胜感激。

Answer 1

首先，你的观察有点不对。

对于不同的n值，第6行结束后的k和p的值将是：-

n = 1 => k = 1 and p = 0.

n = 3 => k = 3 and p = 1.

n = 9 => k = 9 and p = 2.

n = 10 => k = 27 and p = 3.

n = 27 => k = 27 and p = 3.

n = 30 => k = 81 and p = 4.

现在，在第 6 行的末尾，

if n == k
  then 3^p == n
otherwise,
  3^(p-1) < n < 3^p

Answer 2

您已经通过尝试几个不同的示例并查看是否可以发现一个模式来解决这个问题。这是一种合理的方法，但要开始工作有点棘手。相反，您可能想查看 k 在循环迭代时采用的值，看看是否可以从那里开始工作。

请注意，k 作为循环迭代次数的函数呈指数增长：它取值 1、3、9、27、81，...。换句话说，它具有值

3⁰, 3¹, 3², 3³, 3⁴, etc.

而且，更一般地，在循环迭代 i 中，它的值为 3ⁱ。

鉴于这个循环一旦k大于或等于n就停止，我们可以通过求解i的最小值来计算将有多少次循环迭代，其中3ⁱ≥n。我们可以这样做：

3ⁱ = n

i = log₃ n

这个数字可能不是整数，所以我们取上限取整，迭代次数为⌈log₃ n⌉.

一般来说，如果您看到某个过程通过以恒定因子重复增长（总是三倍，或总是加倍，或总是上升 10 倍等）来工作，您应该期望看到某种的对数项出现。这是您看到 O(log n) 出现的最常见方式之一。

找出输入和循环执行次数之间的关系。

Find the relationship between input and number of times a loop executes.

algorithm

sequences