帮助作业 [英] help with an assignment

问题描述

计算数论.

编写一个程序CubeSum.java，它以排序的方式打印出a3 + b3形式的所有整数，其中a和b是按排序顺序在0到N之间的整数.

也就是说，不是计算N2和的数组并对其进行排序，而是建立一个面向最低优先级的队列，该队列最初包含(03，0，0)，(13，1，0)，(23，2，0) ...，(N3，N，0).

然后，当优先级队列为非空时，删除最小的项(i3 + j3，i，j)，打印它，然后如果j< N，插入项目(i3 +(j + 1)3，i，j + 1).使用此程序查找0到10 ^ 6之间的所有不同整数a，b，c和d，以便a3 + b3 = c3 + d3，例如1729 = 9 ^ 3 + 10 ^ 3 = 1 ^ 3 + 12 ^ 3.

[edit]
用户更新:

Computational number theory.

Write a program CubeSum.java that prints out all integers of the form a3 + b3 where a and b are integers between 0 and N in sorted order, without using excessive space.

That is, instead of computing an array of the N2 sums and sorting them, build a minimum-oriented priority queue, initially containing (03, 0, 0), (13, 1, 0), (23, 2, 0), ..., (N3, N, 0).

Then, while the priority queue is nonempty, remove the smallest item (i3 + j3, i, j), print it, and then, if j < N, insert the item (i3 + (j+1)3, i, j+1). Use this program to find all distinct integers a, b, c, and d between 0 and 10^6 such that a3 + b3 = c3 + d3, e.g., 1729 = 9^3 + 10^3 = 1^3 + 12^3.

[edit]
Update from user:

public class CubeSum implements Comparable<CubeSum> {
    private final int sum;
    private final int i;
    private final int j;

    public CubeSum(int i, int j) {
        this.sum = i*i*i + j*j*j;
        this.i = i;
        this.j = j;
    }

    public int compareTo(CubeSum that) {
        if (this.sum < that.sum) return -1;
        if (this.sum < that.sum) return +1;
        return 0;
    }

    public String toString() {
        return sum + " = " + i + "^3" + " + " + j + "^3";
    }


    public static void main(String[] args) {

        int N = Integer.parseInt(args[0]);

        // initialize priority queue
        MinPQ<CubeSum> pq = new MinPQ<CubeSum>();
        for (int i = 0; i <= N; i++) {
            pq.insert(new CubeSum(i, i));
        }

        // find smallest sum, print it out, and update
        while (!pq.isEmpty()) {
            CubeSum s = pq.delMin();
            StdOut.println(s);
            if (s.j < N) pq.insert(new CubeSum(s.i, s.j + 1));
        }
    }

}

Iam现在对如何使用该程序查找介于0和10 ^ 6之间的所有不同整数a，b，c和d感到困惑，从而使a3 + b3 = c3 + d3，例如1729 = 9 ^ 3 + 10 ^ 3 = 1 ^ 3 + 12 ^ 3.

[edit]

Iam now confused on how to use this program to find all distinct integers a, b, c, and d between 0 and 10^6 such that a3 + b3 = c3 + d3, e.g., 1729 = 9^3 + 10^3 = 1^3 + 12^3.

[edit]

推荐答案

如果我没事的话，输出将按结果pow 3 + b pow 3排序.
这意味着，如果有两行结果相同，则将它们紧挨着放置.第一行将为您提供a和b，第二行将为您提供c和d.
因此，假设您从不从列表中删除元素，则只需要遍历列表一次即可检查包含相同结果的两个连续行.
现在，因为实际上您要删除元素，所以要复杂得多.
建立清单，就像在下一个清单中一样.
然后，您在列表中扫描包含相同结果的连续行.
这样，您只占一小部分结果.
然后开始添加元素，但是在添加元素时，需要获取insert的返回值，以使自己成为一个迭代器，该迭代器指向其插入位置.如果pq不支持，则必须自己找到一种方法.然后，如果您具有该迭代器，则在其之前检查元素的值.如果结果相同，则命中，接下来检查其后的元素值.如果相同的话，您会再次点击.

我没预见到这里有任何代码，因为这是家庭作业.

If I get things right the output is sorted on the result a pow 3 + b pow 3.
That means that if there are two rows with the same result, they will be placed right after eachother. The first row would give you a and b, the second row would give you c and d.
So suppose you never remove elements from the list, you would simply have to traverse the list once to check for two consequetive rows containing the same result.
Now because you are in fact removing elements it is a bit more complicated than that.
You build the list, like you do in your for next.
Then you scan the list for consequetive rows containing the same result.
This way you have a small part of the results.
Then you start adding elements, but as you add elements, you need to take the return value of insert to get yourself an iterator pointing to the position where it got inserted. If pq does not support that you have to find a way to do that yourself. Then if you have that iterator you check the value of the element before it. If the result is the same you have a hit, next you check the value of the element after it. If it is the same you have another hit.

I did not foresee any code here, since it is homework.

这篇关于帮助作业的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！