algorithm - 如何规范化循环？

Question

我真的很想知道如何规范化循环。换句话说，我想改变 for 循环

来自

for (i = k; i <= n; i += c) // k>=0 n>=0 c>0

到

for (j = 0; j <= itNumber-1; j++) // itNumber is the number of iterations

如何找到 itNumber = f ( n , k , c ) ??

提前致谢。

Answer 1

如何查找:

您正在寻找一种转换，该转换将为您提供一个“规范”循环，从零开始并在每一步中将迭代器递增 1。

首先，让我们偏移循环for (i = k; i <= n; i += c) , 这样 i将从0开始: for (i = 0; i <= n - k; i += c) , 并且对于 i 的每次阅读在循环内执行 i:=i+k . (如果 i 写在循环内，则无法在该方法中进行优化)

现在让我们来处理跳跃间隙。目前，i递增 c每次迭代，所以我们必须除以 c为了增加 1 : for (i = 0; i <= (n - k)/c; i += 1) , 并且对于 i 的每次阅读在循环内执行 i:=i*c .

出于某种原因，您需要一个基本案例 i<=itNumber-1 , 所以我们得到 i <= (n - k)/c + 1 - 1 ，我们可以总结:

条件转换: f(n, k, c) = (n - k)/c + 1

和 i 的转换循环内部是:g(i) = c*(i+k)

计算是在整数之间进行的(就像在'C'中一样)，所以x/y实际上是它的整数部分:floor(x/y)