如何正确使用Math.Pow()？

Question

我想找到方程的所有正整数解, a^3 + b^3 = c^3 + d^3其中a,b,c,d是1到1000之间的整数;

for (int a = 1; a <= 1000; ++a)
{
    for (int b = 1; b <= 1000; ++b)
    {
        for (int c = 1; c <= 1000; ++c)
        {
            for (int d = 1; d <= 1000; ++d)
            {
                if (Math.Pow(a, 3) + Math.Pow(b, 3) == Math.Pow(c, 3) + Math.Pow(d, 3))
                {
                     Console.WriteLine("{0} {1} {2} {3}", a,b,c,d);
                }
            }
      }
}

我知道d = Math.Pow(a^3 + b^3 - c^3, 1/3),所以

for (int a = 1; a <= 1000; ++a)
{
    for (int b = 1; b <= 1000; ++b)
    {
        for (int c = 1; c <= 1000; ++c)
        {
            int d = (int)Math.Pow(Math.Pow(a, 3) + Math.Pow(b, 3) - Math.Pow(c, 3), 1/3);

            if (Math.Pow(a, 3) + Math.Pow(b, 3) == Math.Pow(c, 3) + Math.Pow(d, 3))
            {
                Console.WriteLine("{0} {1} {2} {3}", a,b,c,d);
            }
        }
   }
}

但是第二种算法产生的结果数量要少得多.我的代码中的错误在哪里？

我尝试(double)1/3但第二个算法仍然给我少量的结果然后第一个

Answer 1

几乎没有一个答案是正确的.

你的问题是:

我的代码中的错误在哪里？

如果您使用双精度算法来解决整数问题,那么您做错了.根本不要使用Math.Pow,特别是不要使用它来提取立方根,并期望你得到一个确切的整数答案.

那你怎么解决这个问题呢？

让我们更聪明地做不做不必要的工作.你的程序发现1 ³ + 12 ³ = 9 ³ + 10 ³,还有12 ³ + 1 ³ = 10 ³ + 9 ³,依此类推.如果您知道第一个,那么您可以很容易地知道第二个.

那么我们该怎么做才能提高效率呢？

首先,b必须大于a.这样我们就不会浪费任何时间来搞清楚1 ³ + 12 ³ = 12 ³ + 1 ³.

同样,d必须大于c.

现在,我们也可以说,c并且d必须介于 a和之间b.你明白为什么吗？

一旦我们实施了这些限制:

    for (int a = 1; a <= 1000; ++a)
        for (int b = a + 1; b <= 1000; ++b)
            for (int c = a + 1; c < b; ++c)
                for (int d = c + 1; d < b; ++d)
                    if (a * a * a + b * b * b == c * c * c + d * d * d)
                        Console.WriteLine($"{a} {b} {c} {d}");

你的程序变得更快.

现在,如果你愿意用更少的时间交换更多的内存,有办法让它更快.你能想到这个节目浪费时间的一些方法吗？一遍又一遍地完成相同计算的次数是多少次？我们怎样才能改善这种状况？

我们可能会注意到,例如,a * a * a每次通过三个内部循环计算!

    for (int a = 1; a <= 1000; ++a)
    {
        int a3 = a * a * a;
        for (int b = a + 1; b <= 1000; ++b)
        {
            int b3 = b * b * b;
            int sum = a3 + b3;
            for (int c = a + 1; c < b; ++c)
            {
                int c3 = c * c * c;
                int d3 = sum - c3;
                for (int d = c + 1; d < b; ++d)
                    if (d3 == d * d * d)
                        Console.WriteLine($"{a} {b} {c} {d}");
            }
        }
    }

但我们可能比那更聪明.例如:如果我们创建了一个Dictionary<int, int>将立方体映射到其立方根的内容,该怎么办？只有1000个!然后我们可以说:

    for (int a = 1; a <= 1000; ++a)
    {
        int a3 = a * a * a;
        for (int b = a + 1; b <= 1000; ++b)
        {
            int b3 = b * b * b;
            int sum = a3 + b3;
            for (int c = a + 1; c < b; ++c)
            {
                int c3 = c * c * c;
                int d3 = sum - c3;
                if (dict.HasKey(d3))
                {
                    d = dict[d3];
                    Console.WriteLine($"{a} {b} {c} {d}");
                }
            }
        }
    }

现在您不必计算d的立方体或立方根; 你只是查看它是否是一个立方体,如果它是,它的立方根是什么.