c - 用两个 for 嵌套循环破译 C 函数的用途，一个 int 输入和一个 int 返回

Question

一位来自另一所大学的 friend 带着这个挑战来找我。我无法帮助他，并且因为我无法理解他应该破译的函数的目的而变得相当困扰。有没有人见过这样的事情？

我尝试过可视化数据，但无法真正从图表中得出任何有意义的结论: (蓝色是mistery的返回值，橙色是上次返回值和当前返回值的差值。为了便于阅读，刻度为对数。)

int mistery(int n){
    int i, j, res=0;
    for(i = n / 2; i <= n; i++){
        for(j = 2; j <= n; j *= 2){
          res += n / 2;
        }
    }
    return res;
}

它看起来像是随机代码，但我实际上已经看到它出现的工作表。欢迎任何意见。

谢谢

Answer 1

在内循环的每次迭代中添加到结果变量的增量仅取决于函数参数 n，函数不会修改该参数。因此，结果是增量 (n/2) 与内循环迭代总数(假设不​​溢出)的乘积。

那么有多少次循环迭代呢？首先考虑外循环。如果 i 的下界为 0，则 n 的包含性上界将产生 n+1 次迭代。但是我们跳过了第一个 n/2 迭代 (0 ... (n/2)-1)，所以这是 n+1-(n/2)。这里的所有除法都是整数除法，对于整数除法，对于所有 m 都是如此 m = (m/2) + ((m+1)/2).我们可以使用它来将外循环迭代次数重写为 ((n+1)/2) + 1，或 (n+3)/2(仍然使用整数除法)。

现在考虑内循环。索引变量 j 从 2 开始，每次迭代都会加倍，直到超过 n。这会产生等于 n 的以 2 为底的对数的底数的迭代次数。因此，总迭代次数为

(n+3)/2 * floor(log2(n))

(假设当 n 是 2 的幂时我们可以假设一个精确的结果)。那么，合并的结果是

((n+3)/2) * (n/2) * floor(log2(n))

其中除法仍然是整数除法，并且在乘法之前执行。这解释了为什么函数的导数在参数的 2 次幂处出现尖峰:外循环迭代次数在每个点处增加 1。

我们没有任何上下文来猜测函数的用途，我不认为它是一个众所周知的函数，但我们可以谈谈它的属性。例如，

• 它渐进地增长得比 n² 快，渐近地比 n³ 慢。事实上，
• 它的形式让人想起那些倾向于出现在计算渐近边界中的形式，因此它可能是某些计算所需的内存或时间的估计或边界。还有，
• 对于 n> 0，它是严格递增的。由于涉及整数除法，这可能不是很清楚，但请注意 n 和 n + 3 具有相反的奇偶校验，因此每当 n 增加 1 时，恰好是 n/2 和 (n+3)/2增加一个，另一个不变(对数项不减)。
• 如前所述，它在 2 的幂处突然跳跃。这可以根据外循环的迭代次数来查看，或者根据 floor()< 的参与来查看 单方程形式的函数。
• 函数的多项式部分与从 1 到 n 的整数之和的方程有关。
• 函数的对数部分与n的二进制表示中的有效位数有关。