c - 求和中每个单独项的除法公式

Question

例子：

当除法作为一个整体应用时，结果是，

求和公式由下式给出，

使用求和规则可以在 O(1) 中轻松计算上述内容。

但是当它单独应用于每个术语时（在商中的小数点后截断），=0+1+1+2+3+3+4+5=19。[在C中使用正常int/int除法]

上述方法需要 O(N)，因为无法应用求和规则。

我了解上述情况是由于将除法应用于每个术语而不是最后一个术语时，精度损失更多。但这正是我所需要的。[在上面的例子中，19 是必需的解决方案，而不是 21]

是否有一个公式可以作为将除法单独应用于每个术语的捷径，类似于求和？

Answer 1

所以，你得到：

0 + (1+1+2) + (3+3+4) + 5

让我们将其乘以 3：

0 + (3+3+6) + (9+9+12) + 15

并将其与 (1+...+15)/3 的分子进行比较：

1 + (3+5+7) + (9+11+13) + 15

您可以清楚地看到，您所寻求的总和平均每 3 个术语会丢失 3 个分子，或者平均每个术语会丢失 1 个。我们如何将术语分组为三元组并不重要：

(0+3+3) + (6+9+9) + 12+15
(1+3+5) + (7+9+11) + 13+15

甚至

0+3 + (3+6+9) + (9+12+15)
1+3 + (5+7+9) + (11+13+15)

因此，您的 sum*3 比 (1+...+15)/3 的分子少大约项数。

分子可以使用算术级数之和的公式计算：n²，其中n是和中的项数：

1+3+5+7+9+11+13+15 = 2 ⁸ = 64

现在从 64 中减去 8，得到 56，然后除以 3，得到 18.6(6)。这个数字不等于 19，因为n（术语的数量）不是 3 的倍数。

因此，最终公式不完全是 ( n² - n)/3，但与正确公式的值最多相差 1。

事实上，它是：

(n*n-n+1)/3 向下舍入或使用整数除法计算。

将数字插入其中，我们得到：

(8*8-8+1)/3 = 57/3 = 19

Answer 2

简短的回答：是的，有这样一个公式。

长答案（我猜你想要公式）：

如何获得：您已经意识到求和公式与 int 除法之和之间的差异来自每个被加数处 int 除法的舍入。

制作一个包含行的表格：

第一行，每个加法的结果，当您以全精度除法时。

第二行，当您执行整数除法时，每个加法的结果。

第三排，两者的区别。

现在你应该意识到这个模式，它总是 1/3、0、2/3。

这来自除以 3，如果你愿意，你可以证明它是正式的（例如归纳）。

所以最后你的公式是： (n^2)/3 - (n/3)

n*n/3 是常规求和公式，对于所有完整的 3 个和数 1 丢失，我们减去 n/3。

Answer 3

结果将是

1+1 + 2 + 3+3 + 4 + 5+5 + 6 + 7+7 + 8 + 9+9 + 10 + ...

换句话说，所有奇数出现两次，所有偶数出现一次。第一个n自然数的和是n*(n+1)/2所以第一个n偶数自然数的和是它的两倍，而第一个n奇数的和是n*n。

我认为你现在拥有所有部件来获得你需要的结果......

Answer 4

为了增加 s，您需要的总和是n：1、2、4、7、10、14、19、24、30、36 ...

将这些插入整数序列在线百科全书™ (OEIS™)，您将获得符合您要求的A007980系列。它的计算公式为 a(n)=ceil((n+1)*(n+2)/3)。

这使得 a(0) = 1, a(1) = 2, a(6) = 19，意味着索引偏移 2：sum(1,8) = a(8-2)。

Answer 5

#include <stdio.h>

typedef struct fraction {
    int n;//numerator
    int d;//denominator
} Fraction;

int gcd(int x, int y){
    x = (x < 0)? -x : x;
    y = (y < 0)? -y : y;
    while(y){
        int wk;
        wk = x % y;
        x = y;
        y = wk;
    }

    return x;
}

Fraction rcd(Fraction x){
    int gcm;
    gcm = gcd(x.n, x.d);
    x.n /= gcm;
    x.d /= gcm;
    return x;
}

Fraction add(Fraction x, Fraction y){
    x.n = y.d*x.n + x.d*y.n;
    x.d = x.d*y.d;
    return rcd(x);
}

int main(void){
    Fraction sum = {0,1};
    int n;

    for(n=1;n<=8;++n){
        Fraction x = { 2*n-1, 3 };
        sum = add(sum, x);
    }
    printf("%d/%d=",sum.n,sum.d);
    printf("%d",sum.n/sum.d);

    return 0;
}

Answer 6

Σ((2i+1)/3) where i =0 to n-1 and Σ((2i+1)/3) = n*n/3