c - Sum (i...j) - 是否有更有效/更优雅的解决方案？

Question

我们被赋予了一项简单的任务，即想出最有效的方法来分别使用递归和迭代对起点和终点(“from”和“to”)之间的所有数字求和，而无需使用明显的公式这将是 O(1)。

这个没有申请，我只是好奇和挑战，看看我的解决方案是否可以比现在更多地改进/完善:

/* recursion */
unsigned int sum1(unsigned int from, unsigned int to) {
    if (to - from < 2)
        return from + (from == to ? 0 : to);
    else
        return from + to + sum1(from + 1, to - 1);
}

/* iteration */
unsigned int sum2(unsigned int from, unsigned int to) {
    int p = to - from;
    if (p == 0) return from;
    int i, s, n = p / 2;
    if (p % 2 == 0) s = n + from;
    else {
        s = 0;
        n++;
    }
    for (i = 0; i < n; i++) {
        s += from++ + to--;
    }
    return s;
}

Answer 1

我尝试改进迭代版本:

unsigned int sum2_improved(unsigned int from, unsigned int to) {
    int p = to - from;
    if (p == 0) return from;
    int x = to + from;
    int s = 0;
    int i;
    for (i = p >> 1; i > 0; i--)
    {
        s += x;
    }
    s += (p % 2 == 0) ? x >> 1 : x;
    return s;
}

我测试了你的版本:

for (i = 0; i < 9999999; i++) sum2(1,999);

这是我看到的:

$ time ./addm
real    0m18.315s
user    0m18.220s
sys     0m0.015s

我用相同数量的循环尝试了我的实现。以下是改进功能的执行方式:

$ time ./addm
real    0m14.196s
user    0m14.070s
sys     0m0.015s

---

更新

在我的实现中 x = to + from是序列中第一个和最后一个数字的总和。如果考虑任何连续的整数序列，并将第一个和最后一个、第二个和倒数第二个相加，依此类推……所有这些总和为相同的值。例如，在 (1 ... 6), 1 + 6 = 2 + 5 = 3 + 4 = 7 .然而，对于包含奇数个元素的序列，您将剩下中间的数字，然后您必须将其添加到累积和(这就是 for 循环之后的赋值所做的事情。

另外，请注意这仍然是 O(n) .在我最初发布我的答案后，我意识到我的方法实际上可以在恒定时间内完成。这是更新后的代码:

unsigned int sum0(unsigned int from, unsigned int to) {
    int p = to - from;
    if (p == 0) return from;
    int x = to + from;
    int s = 0;

    s += (x * (p >> 1));

    s += (p % 2 == 0) ? x >> 1 : x;

    return s;
}

我用与之前测试相同的循环次数运行了这个。这是我看到的:

$ time ./addm

real    0m0.158s
user    0m0.093s
sys     0m0.047s

我不确定这是否可以被视为适合您目的的公式变体。无论如何，这对我来说都是一个有趣的练习。