1

几天前我有一个工作面试，他们问我如何使用 c 语言计算从 1 到 10000 的所有 2 或 5 的倍数的总和。我这样做了：

int mult2_5()
{
     int i, sum=0;
     for(i = 1; i <= 10000; i++)
        if(i % 2 == 0 || i % 5 == 0)
          sum += i;
     return sum;  
}

我想知道是否有比这个更快的实现？

4

5 回答 5

5

模运算符效率低下。一个更快的实现将是这样的：

int multiply2_5(int max)
{
  int i, x2 = 0,x5 = 0,x10 = 0;

  for(i = 2; i < max; i+=2)    x2 += i;    // Store all multiples of 2   O(max/2)
  for(i = 5; i < max; i+=5)    x5 += i;    //  Store all multiples of 3  O(max/5)
  for(i = 10; i < max; i+=10)  x10 += i;   //   Store all multiples 10;  O(max/10)

  return x2+x5-x10;
}

在这个解决方案中，我必须取出 10 的倍数，因为 2 和 5 的倍数是 10，所以在第二个循环中，它将添加已经在第一个循环中添加的 10 的倍数；三个循环组合有 O(8/10 max)。

另一个更好的解决方案是采用数学方法。

您正在尝试对所有数字求和，例如 2 + 4 + 6 + 8 ... 10000 和 5 + 10 + 15 +20 + ... 10000 这与 2 * (1 + 2 + 3 + 4 + ... + 5000) 和 5 * ( 1 + 2 + 3 + 4 + ... + 2000)，'n' 自然数之和是 (n * (n + 1)) ( source ) 所以你可以计算恒定时间，如下：

int multiply2_5(int max)
{
    // x = 2 + 4 + 6 + ... = 2 * (1 + 2 + 3 +...)
    // y = 5 + 10 + 15 + ... = 5 * (1 + 2 + 3 +...)
    // The sun of n natural numbers is sn = (n (n + 1)) / 2
   int x2 = max/ 2;                      // 2 * ( 1 +2 + 3 … max/2)
   int x5 = max /5;                      // 5 * ( 1 +2 + 3 … max/5)
   int x10 = max/ 10;                  
   int sn2 = 0.5 * (x2 * (x2+1));        // (n * (n + 1)) / 2
   int sn5 = 0.5 * (x5 * (x5+1)); 
   int sn10 = 0.5 * (x10 * (x10+1));
   return (2*sn2) + (5 *sn5) - (10*sn10);
}
于 2012-11-20T00:28:30.573 回答
2

如果这就是您所说的“更快”的意思，请先在纸上解决。

$2\sum_{1<=2k<=10000}k + 5\sum_{1<=5k<=10000} - 10\sum_{1<=10k<=10000}k$

对不起，我的 SO equation-fu 很弱......无论如何，这条路线会给你一些你几乎可以在纸上处理的东西：减少几个步骤后的 5000*6001

int
mult2_5(void)
{
    return 5000*6001;
}

Project Euler 问题 1非常相似。有很多人已经发布了他们的解决方案。

于 2012-11-20T01:15:44.050 回答
2

正如前面的回答中提到的，明确地循环遍历相关的倍数比在每个循环中测试余数要好。但不必计算 10 的倍数并减去。只需从 5 点开始，然后按 10 点逐步跳过它们。

int multiply2_5b(int max)
{
  int i, x2 = 0,x5 = 0;

  for (i = 2; i < max; i += 2)    x2 += i;    // Sum all multiples of 2   
  for (i = 5; i < max; i += 10)   x5 += i;    // Sum all odd multiples of 5

  return x2 + x5;
}
于 2012-11-20T01:26:41.070 回答
1

这可以使用数学来完成。像2 * sum(1 to 5000) + 5 * sum(1 to 2000) - 10 * sum(1 to 1000). 一个错误的错误作为练习留下了。

于 2012-11-20T04:00:10.450 回答
0

通过执行一个以 35（2 + 4 + 5 + 6 + 8 + 10 的总和）开始，步长为 60 的简单循环，我几乎得到了一个纯粹而简单的乘法，因为这就是你的结果将增加多少取下一批，例如 12 + 14 + 15 + 16 + 18 + 20 等 for(int i=35;i<5976;i=i+60) { sum=sum+i } 5976 来自 5975 是最后一个以 1000 结尾的数字行，即 992 + 994 + 995 + 996 + 998 + 1000。所以事实证明，这个循环运行了 100 次，第一轮总和增加 35，其余 99 次增加 60。现在可以简化为简单的乘法等。

于 2012-11-20T03:57:14.140 回答