寻找算法或一些编码提示以找到解决方案
a^3 + b^3 = c^3 + d^3,a, b, c and d所有都在范围内[1 .. 10000]
是面试题。
我正在考虑优先级队列至少迭代a和b值。一些提示会很棒，会尝试从那里解决。
问问题
26040 次
9 回答
23
使用哈希映射来存储(cube,(a,b))，您可以迭代所有可能的整数对，并在您发现所需的立方体总和已经在映射中时输出解决方案。
伪代码：
map <- empty hash_map<int,list<pair<int,int>>>
for each a in range(0,10^5):
for each b in range(a,10^5): //making sure each pair repeats only once
cube <- a^3 + b^3
if map.containsKey(cube):
for each element e in map.get(cube):
output e.first(), e.last(), a, b //one solution
else:
map.put(cube,new list<pair<int,int>>)
//for both cases, add the just found pair to the relevant list
map.get(cube).add(cube,new pair(a,b))
该解决方案平均为 O(n^2) 空间(1)和 O(n^2 + OUTPUT) 时间，其中 OUTPUT 是输出的大小。
编辑：
所需空间实际上是O(n^2 logn)，n范围是 (10^5)，因为要表示10^5整数，您需要ceil(log_2(10^15)) = 50位。因此，您实际上需要大约 58.2 GB（+ 开销）的 500,000,000,000 位（+ 映射和列表的开销）。
因为对于大多数机器来说它有点太多了——你可能想要考虑将数据存储在磁盘上，或者如果你有 64 位机器——只需存储到“内存”中，让操作系统和虚拟内存系统尽可能地做到这一点能够。
(1) 正如编辑澄清的那样，它实际上是O(n^2log(n))空间，但是如果我们将每个整数存储作为O(1)（通常是这种情况）我们得到O(n^2)空间。显然，相同的原则将适用于时间复杂度。
于 2013-01-22T09:36:01.970 回答
6
使用优先级队列几乎可以肯定是最简单的解决方案，也是最实用的解决方案，因为它是 O(n) 存储（如果您需要 bignums，则使用日志因子）。任何涉及计算所有可能的总和并将它们放入地图的解决方案都需要 O(n^2) 存储，这很快就会变得不切实际。
我使用优先级队列的天真、未优化的实现是 O(n^2 log(n)) 时间。即便如此，n = 10000 只用了不到 5 秒，n = 100000 只用了大约 750 秒，使用了几兆字节的存储空间。它当然可以改进。
根据您的评论，基本思想是用对 (a, a+1) 为范围 [1, N) 中的 a 初始化一个优先级队列，然后重复增加最小值的第二个值（通过立方体的总和) 元组，直到它达到 N。如果在任何时候队列中最小的两个元素相等，则您有一个解决方案。（我可以粘贴代码，但您只要求提示。）
于 2013-01-22T17:36:48.570 回答
4
使用 Hashmap（O(n^2) 解决方案）：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import static java.lang.Math.pow;
/**
* Created by Anup on 10-10-2016.
*/
class Pair {
int a;
int b;
Pair(int x, int y) {
a = x;
b = y;
}
}
public class FindCubePair {
public static void main(String[] args) {
HashMap<Long, ArrayList<Pair>> hashMap = new HashMap<>();
int n = 100000;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
long sum = (long) (pow(i, 3) + pow(j, 3));
if(hashMap.containsKey(sum)) {
List<Pair> list = hashMap.get(sum);
for(Pair p : list) {
System.out.println(i + " " + j + " " + p.a + " " + p.b);
}
} else {
ArrayList<Pair> list = new ArrayList<>();
hashMap.put(sum, list);
}
hashMap.get(sum).add(new Pair(i, j));
}
}
}
}
不幸的是，由于资源限制，在我的计算机上打印的整数值甚至没有达到 1000。
于 2016-10-10T17:42:25.410 回答
2
一个比简单的解决方案更快的解决方案如下：计算 a^3 + b^3 可以具有的所有值，并用它存储 a 和 b 的所有可能值。这是通过循环 a 和 b，将结果 (a^3 + b^3) 存储在二叉树中并具有与每个结果相关联的值列表（a's 和 b's）来完成的。
在这一步之后，您需要遍历列表并为每个值选择 a、b、c、d 的所有可能分配。
我认为这个解决方案需要 O(n^2 log n) 时间和 O(n^2) 空间，但我可能会遗漏一些东西。
于 2013-01-22T09:16:15.747 回答
2
int Search(){
int MAX = 10000000;
for(int a = 0; a < MAX; a++){
int a3 = a * a * a;
if(a3 > MAX) break;
for(int b = a; b < MAX; b ++){
int b3 = b * b * b;
if(a3 + b3 > MAX)break;
for(int c = 0; c < a; c++){
int c3 = c*c*c;
int m = a3 - c3;
int d = b+1;
while(true){
int d3 = d * d * d;
if(d3-b3 <= m){
if((d3 - b3) == m){
count++;
PUSH_Modified(a3, b3, c3, b3, a, b, c, d);
}
d++;
continue;
}
else
break;
}
}
}
}
return 0;
}
于 2014-01-03T10:37:46.430 回答
1
让我们假设一个解决方案：
a=A, b=B, c=C, and d=D.
给定任何解决方案，我们可以生成另外 3 个解决方案
abcd
ABCD
ABDC
BACD
BADC
实际上，如果A=B或C=D，那么我们可能只有 1 或 2 个进一步的解决方案。
A <= B我们可以通过订购和选择我们首先寻找的解决方案C <= D。这将减少搜索空间。我们可以从找到的解决方案中生成遗漏的解决方案。
总会有至少一种解决方案，其中A=C和B=D。我们正在寻找的是何时A>C和B<D。这来自排序：C不能大于A，因为我们选择只查看 的解决方案D>C，立方和太大。
我们可以计算A^3 + B^3，将其放入 amap作为 key，以 a vectorof pairsA,B作为 value。
会有(n^2)/2价值观。
如果它们中已经存在值，vector它们的值都会更低A，它们就是我们正在寻找的解决方案。我们可以立即输出它们以及它们的排列。
我不确定复杂性。
于 2013-01-22T09:41:50.133 回答
1
逻辑：
a^3 + b^3 = c^3 + d^3
然后，a^3+b^3-c*3-d^3 = 0
尝试通过将 a 的所有值组合来求解这个方程， b,c 和 d 在 [0 , 10^5] 的范围内。
如果方程已求解，则打印 a、b、c 和 d 的值
public static void main(String[] args) {
//find all solutions of a^3 + b^3 = c^3 + d^3
double power = 3;
long counter = 0; // to count the number of solution sets obtained
int limit = 100000; // range from 0 to limit
//looping through every combination of a,b,c and d
for(int a = 0;a<=limit;a++)
{
for(int b = 0;b<=limit;b++)
{
for(int c = 0;c<=limit;c++)
{
for(int d = 0;d<=limit;d++)
{
// logic used : a^3 + b^3 = c^3 + d^3 can be written as a^3 + b^3 - c^3 - d^3 = 0
long result = (long)(Math.pow(a,power ) + Math.pow(b,power ) - Math.pow(c,power ) - Math.pow(d,power ));
if(result == 0 )
{
counter++; // to count the number of solutions
//printing the solution
System.out.println( "a = "+ a + " b = " + b + " c = " + c + " d = " + d);
}
}
}
}
}
//just to understand the change in number of solutions as limit and power changes
System.out.println("Number of Solutions =" + counter);
}
于 2017-01-19T21:19:16.347 回答
1
一种解决方案 - 使用在排序数组中查找 2 和的概念。这是 O(n3)
public static void pairSum() {
int SZ = 100;
long[] powArray = new long[SZ];
for(int i = 0; i< SZ; i++){
int v = i+1;
powArray[i] = v*v*v;
}
int countPairs = 0;
int N1 = 0, N2 = SZ-1, N3, N4;
while(N2 > 0) {
N1=0;
while(N2-N1 > 2) {
long ts = powArray[N1] + powArray[N2];
N3 = N1+1; N4 = N2-1;
while(N4 > N3) {
if(powArray[N4]+powArray[N3] < ts) {
N3++;
}else if(powArray[N4]+powArray[N3] > ts) {
N4--;
}else{
//System.out.println((N1+1)+" "+(N2+1)+" "+(N3+1)+" "+(N4+1)+" CUBE "+ts);
countPairs++;
break;
}
}
N1++;
}
N2--;
}
System.out.println("quadruplet pair count:"+countPairs);
}
于 2016-09-09T15:30:52.880 回答
1
从蛮力方法开始，很明显它将 O(n^4) 时间来执行。如果空间不是限制，我们可以选择列表和地图的组合。代码是不言自明的，我们使用嵌套列表来跟踪特定总和（映射中的键）的所有条目。时间复杂度因此从 O(n^4) 降低到 O(n^2)
public void printAllCubes() {
int n = 50;
Map<Integer, ArrayList<ArrayList>> resMap = new HashMap<Integer, ArrayList<ArrayList>>();
ArrayList pairs = new ArrayList<Integer>();
ArrayList allPairsList = new ArrayList<ArrayList>();
for (int c = 1; c < n; c++) {
for (int d = 1; d < n; d++) {
int res = (int) (Math.pow(c, 3) + Math.pow(d, 3));
pairs.add(c);
pairs.add(d);
if (resMap.get(res) == null) {
allPairsList = new ArrayList<ArrayList>();
} else {
allPairsList = resMap.get(res);
}
allPairsList.add(pairs);
resMap.put(res, allPairsList);
pairs = new ArrayList<Integer>();
}
}
for (int a = 1; a < n; a++) {
for (int b = 1; b < n; b++) {
int result = (int) (Math.pow(a, 3) + Math.pow(b, 3));
ArrayList<ArrayList> pairList = resMap.get(result);
for (List p : pairList) {
System.out.print(a + " " + b + " ");
for (Object num : p)
System.out.print(num + " ");
System.out.println();
}
}
}
}
于 2017-02-17T19:24:07.177 回答