2.4.25

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

官方实现:https://algs4.cs.princeton.edu/24pq/CubeSum.java.html

注意这道题并不是要打印所有的 $ a^3+b^3 $ 的结果,而是需要找到 $ a^3+b^3=c^3+d^3 $ 这个丢番图方程的解。
因此在官方实现的基础上,每次取出最小值之后和之前的最小值比较,如果相等则输出对应的组合。
关键代码如下:

CubeSum prev = new CubeSum(-1, -1);
long pairCount = 0;
while (!pq.IsEmpty())
{
    CubeSum s = pq.DelMin();
    if (s.sum == prev.sum)            // 如果与之前的数相等
    {
        Console.WriteLine(s + " = " + prev.i + "^3 + " + prev.j + "^3");
        pairCount++;
    }         
    if (s.j < n)
        pq.Insert(new CubeSum(s.i, s.j + 1));
    prev = s;
}

当然,对于 n=10^6 来说结果会非常大,程序的运行时间需要以天为单位计算(约 14 天)。
n=10^4 时,总共可以找到 41570 对数据。(result10K.txt, 下载大小 506 KB,解压后 1.93 MB)
n=10^5 时,总共可以找到 895023 对数据。(result100K.txt,下载大小 12.7 MB,解压后 47.5 MB)
n=10^6 时,总共可以找到 16953323 对数据。(result1M.txt,下载大小 280 MB,解压后 0.98 GB)

结果下载链接:百度云Onedrive

代码

CubeSum.cs

using System;

namespace _2._4._25
{
    /// <summary>
    /// 立方和类,保存 a^3+b^3 的值。
    /// </summary>
    class CubeSum : IComparable<CubeSum>
    {
        /// <summary>
        /// 立方和。
        /// </summary>
        internal readonly long sum;
        /// <summary>
        /// 第一个数。
        /// </summary>
        internal readonly long i;
        /// <summary>
        /// 第二个数。
        /// </summary>
        internal readonly long j;

        /// <summary>
        /// 建立一个立方和类。
        /// </summary>
        /// <param name="i">立方和的第一个数。</param>
        /// <param name="j">立方和的第二个数。</param>
        public CubeSum(long i, long j)
        {
            this.sum = i * i * i + j * j * j;
            this.i = i;
            this.j = j;
        }

        /// <summary>
        /// 比较两个立方和的大小,返回 1, 0, -1 中的一个。
        /// </summary>
        /// <param name="other">需要与之比较的另一个数。</param>
        /// <returns></returns>
        public int CompareTo(CubeSum other)
        {
            return this.sum.CompareTo(other.sum);
        }

        /// <summary>
        /// 返回 "sum = i^3 + j^3" 形式的字符串。
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            return this.sum + " = " + this.i + "^3 + " + this.j + "^3";
        }
    }
}

主程序

using System;
using System.IO;
using PriorityQueue;

namespace _2._4._25
{
    /*
     * 2.4.25
     * 
     * 计算数论。
     * 编写程序 CubeSum.java,
     * 在不使用额外空间的条件下,
     * 按大小顺序打印所有 a^3+b^3 的结果,
     * 其中 a 和 b 为 0 至 N 之间所有的整数。
     * 也就是说,不要全部计算 N^2 个和然后排序,
     * 而是创建一个最小优先队列,
     * 初始状态为 (0^3, 0, 0),(1^3, 0, 0),(2^3, 2, 0),...,(N^3, N, 0)。
     * 这样只要优先队列非空,删除并打印最小的元素 (i^3+j^3, i, j)。
     * 然后如果 j<N,插入元素 (i^3+(j+1)^3, i, j+1)。
     * 用这段程序找出 0 到 10^6 之间
     * 所有满足 a^3+b^3 = c^3+d^3 的不同整数 a, b, c, d。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int n = 1000000;

            MinPQ<CubeSum> pq = new MinPQ<CubeSum>();
            Console.WriteLine("正在初始化");
            for (int i = 0; i <= n; i++)
            {
                pq.Insert(new CubeSum(i, i));
            }

            FileStream ostream = new FileStream("./result.txt", FileMode.Create, FileAccess.Write);
            StreamWriter sw = new StreamWriter(ostream);
            Console.WriteLine("正在写入文件……");
            CubeSum prev = new CubeSum(-1, -1);
            long pairCount = 0;
            while (!pq.IsEmpty())
            {
                CubeSum s = pq.DelMin();
                if (s.sum == prev.sum)
                {
                    sw.WriteLine(s + " = " + prev.i + "^3 + " + prev.j + "^3");
                    pairCount++;
                }         
                if (s.j < n)
                    pq.Insert(new CubeSum(s.i, s.j + 1));
                prev = s;
            }
            sw.WriteLine("共找到" + pairCount + "对数据");
            Console.WriteLine("共找到" + pairCount + "对数据");
            sw.Close();
            Console.WriteLine("结果已经保存到程序所在目录下的 result.txt 文件中");
        }
    }
}

另请参阅

Diophantine Equation-3rd Powers - Wolfram MathWorld
PriorityQueue 库

上一题 下一题