0

“求 1000 以下的 3 或 5 的所有倍数之和”

我无法理解为什么下面的解决方案仍然返回正确的结果，因为 x3、x5 和 x15 在除法后使用 int。这意味着除法的结果总是四舍五入，小数点被忽略。

当我尝试用双打替换所有 3 个整数时，我得到了错误的结果。

该解决方案基于以下观察：

1 + 2 + ... + n = n*(n+1)/2

public static void main(String[] args) {
    int nr = 1000;
    nr--;
    int x3 = nr/3;
    int x5 = nr/5;
    int x15 = nr/15;

    long sum1 = 3*x3*(x3+1); 
    long sum2 = 5*x5*(x5+1);
    long sum3 = 15*x15*(x15+1);

    long sum = (sum1+sum2-sum3)/2;
    System.out.println(sum)
}

参考

4

3 回答 3

0

举3个例子，能被3和小于的数之和1000是：(3 + 6 + 9 + 12 + ... + 999)

上式可以改写为3 * (1 + 2 + 3 + .... + 333)。和333 = integer part of (999/3)。也可以写成floor(999/3)。

总和(1 + 2 + 3 + .... + 333) = 333 * (333 + 1) / 2或floor(999/3) * (floor(999/3) + 1) / 2 = 55611。这正是上面的代码所做的。使用int为您提供了一种简单的floor操作方法。

如果你用过double，你会做333.333 * (333.333 + 1) / 2的就是55722.111，一个不同的号码55611。这带来了你所看到的差异。

于 2017-01-25T23:59:25.470 回答
0

整数 x3、x5 和 x15 只是对“有多少小于 M 的正整数是 N 的倍数？”这个问题的简单回答。当 N = 3 时，下表说明了这一点：

M Count
1 0
2 0
3 0
4 1
5 1
6 1
7 2
...

如您所见，答案的概括是Count = floor((M - 1) / N)，这恰好是 Java 中定义正整数除法的方式。

我推断这个舍入就是你要问的，因为这是上面代码中唯一截断的整数除法。

于 2017-01-25T22:31:15.170 回答
0

当我尝试用双打替换所有 3 个整数时，我得到了错误的结果。

您需要从整数除法中进行地板计算，因为没有可被除数整除的小数数：没有小于 1000 可被 5 整除的 199.8 个正数，有 199 个。

因此，通过使用double，您多算了总数：

sum2 = floor(5 * 199.8 * 200.8) = floor(200599.2) = 200599
  vs
sum2 = floor(5 * 199   * 200  ) = floor(199000  ) = 199000
于 2017-01-25T22:18:34.267 回答