java - 问题理解cstutoringcenter问题43解决bug

Question

问题:前 100,000,000 个六边形数中有多少个可以被 1 到 20 的所有数字整除？

第二个解决方案 - 简单的蛮力(有效)

 public static void main(String[] args) {
  long hnr = 100000000L, count = 0L;

  for (long i = 1, h = getHexNr(i); i <= hnr; i++, h = getHexNr(i)) 
   if (h % 2 == 0 && h % 3 == 0 && h % 4 == 0 && h % 5 == 0
     && h % 6 == 0 && h % 7 == 0 && h % 8 == 0
     && h % 9 == 0 && h % 10 == 0 && h % 11 == 0
     && h % 12 == 0 && h % 13 == 0 && h % 14 == 0
     && h % 15 == 0 && h % 16 == 0 && h % 17 == 0
     && h % 18 == 0 && h % 19 == 0 && h % 20 == 0) count++;

  System.out.println(count);
 }

第一个解决方案(不起作用)

public static void main(String[] args) {
  long nr = 1L, hnr = 100000000L, count = 0L;
  double tmp = 0;

  for (long i = 2L; i < 21; i++)
   nr = lcm(nr, i);
  for (double qes : getQES(2, 1, -nr)) {
   if (qes < 0) continue;
   int limit = (int) (getHexNr(hnr) / Math.floor(qes));
   for (int i = 0; i < limit; i++) {
    // if ((i * qes) % 1 == 0) count++;
    if ((tmp += qes) % 1 == 0) count++;
   }
  }

  System.out.println(count);
 }

和实用程序:

 static long gcd(long a, long b) {
  if (b == 0) return Math.abs(a);
  return gcd(b, a % b);
 }

 static long lcm(long a, long b) {
  return (a * b) / gcd(a, b);
 }

 static long getHexNr(long n) {
  return n * (2 * n - 1);
 }

 static double[] getQES(long a, long b, long c) {
  double d = b * b - 4 * a * c;
  if (d < 0) return new double[0];
  return new double[] { (-b + Math.sqrt(d)) / (2 * a),
    (-b - Math.sqrt(d)) / (2 * a) };
 }

第一个解决方案出了什么问题？ (小数精度？)

编辑: 解决方案 1 的算法:

1. 找到能被 1 到 20 的所有数字整除的小数 x
2. 求解由十六进制数公式 x = n * (2 * n - 1) 导出的二次方程
3. 如果n的倍数没有剩余增加计数
4. 重复3.当n的倍数小于第100000000个六角数

编辑 2:

1. 232792560//对
2. [10788.460769248566, -10788.960769248566]//对
3. 像 6418890 这样的数字正在通过测试，google "6418890*10788.460769248566%1="

编辑 3:

是的，蛮力版本应该只检查 21 以下素数的均分性。但更有趣的是找出 Goldberg 谈到的内容。我确实知道它，但更像是five monkeys story .

稍后，我考虑将数字四舍五入，当我记起来时，数学库不包含执行此操作的函数。但我可以使用 BigDecimal，当我查找 BigDecimal 和 double 时，我发现 this .多么愉快的似曾相识。

四舍五入看起来像:

public static double round(double d, int nr) {
    return new BigDecimal(Double.toString(d)).setScale(nr,
        BigDecimal.ROUND_HALF_UP).doubleValue();
}

Answer 1

虽然可能还有其他问题:

((tmp += qes) % 1 == 0)

tmp和qes都是double，也就是说==比较很可能会失败；见What Every Computer Scientist Should Know About Floating-Point Arithmetic