求一道java面试算法题如下

求A³+B³+C³=D³ ABCD∈(0-999) 求ABCD
:( 当时想到的最笨的方法就是for循环的嵌套，从效率方面考虑，请教其它算法

下面是我的代码，在没有打印的情况下在我机器上是1948ms
[code]
long start = System.currentTimeMillis();
int[] cubeArray = new int[1000];
for (int i = 0; i < 1000; i++) {
cubeArray[i] = i * i * i;
}
for (int a = 1; a <= 999; a++) {
for (int b = a; b <= 999; b++) {
for (int c = b; c <= 999; c++) {
for(int d=c+1;d<=999;d++)
if(cubeArray[a]+cubeArray[b]+cubeArray[c]==cubeArray[d]);
// System.out.printf("a=%d,b=%d,c=%d,d=%d\n",a,b,c,d);
}
}
}
System.out.println(System.currentTimeMillis()-start);
}
[/code]

一种想法：把1-999所有数的立方存到一个数组，然后用穷举法遍历数组寻找其中3个数的和等于另一个数的情况，至少优化了大量的乘法运算。

可以参照一下
[url]http://liuqing-2010-07.iteye.com/blog/1396859[/url]

不过依然是循环。

[code="java"]
public static final int[] CUBE_ARRAY={0,1,8,27,.......};
public static void main(String[] args)
{

     double time = System.currentTimeMillis();
     calc();
     System.out.println(System.currentTimeMillis()-time);
}

public static void calc()
{
    int sum = 0;
    for (int i = 0; i < 1000; i++)
        for (int j = i; j < 1000; j++)
            for (int k = j; k < 1000; k++)
            {
                sum = i * i * i + j * j * j + k * k * k;
                int c = isCube(sum);
                if (c >= 0)
                {
                     System.out.println(c+"*"+c+"*"+c+"="+i+"*"+i+"*"+i+"+"+j+"*"+j+"*"+j+"+"+k+"*"+k+"*"+k);
                }
            }
}

public static int isCube(int n)
{
    for (int i = 0; i * i * i <= n && i < 1000; i++)
        if (i * i * i == n)
            return i;
    return -1;
}

public static int isCube2(int n){
    for(int i=0;i<1000;i++){
        int temp =CUBE_ARRAY[i]-n;
        if(temp<0) continue;
        if(temp>0) return -1;
        if(temp==0) return i;
    }
    return -1;
}

[/code]
其中那个CUBE_ARRAY数据很多，没有一一列出来
因为a，b，c对称可以假设a>=b>=c所以去除重复的数据
经测试，结果并不是1楼说的那样，直接列出来那个立方的数组，效率没有直接确认
a^3+b^3+c^3是不是立方数来的快
我电脑在未打印结果的测试结果
为
488354.0 ms
425869.0 ms

你最后一个循环是错的吧。。。
d应该是从0开始

首先（0,999）其实是不包括0的（也不包括999，但我这里用<=999），其次，d肯定比a、b、c中的任何一个都大

哦我刚算了下，用这个方法还是要差不多是172秒
我觉得还能再优化
a>=b>=c
a^3+b^3+c^3=d^3
可以得到
d^3<=3*a^3
所以
[code="java"]
public static void calc(){
for (int i = 0; i < 1000; i++)
for (int j = i; j < 1000; j++)
for (int k = j; k < 1000; k++)
for(int m=k;m < 1000&&m*m*m<=3*i*i*i;m++)
if((CUBE_ARRAY[i] + CUBE_ARRAY[j] + CUBE_ARRAY[k])==CUBE_ARRAY[m]){
//System.out.println(m+"*"+m+"*"+m+"="+i+"*"+i+"*"+i+"+"+j+"*"+j+"*"+j+"+"+k+"*"+k+"*"+k);
}
}
[/code]
用时仅12秒

看来你的方向是对了，从这个数学表达式上面去挖掘它的性质...我是暂时没有精力去翻数学书研究这个表达式了...
给你一个建议：尽量减少乘法运算，加法比乘法快10倍以上

[code="java"]
public static void calc(){
for (int i = 0; i < 1000; i++)
for (int j = i; j < 1000; j++)
for (int k = j; k < 1000; k++)
for(int m=k;m < 1000&&k*k*k<=3*i*i*i;m++)
if((CUBE_ARRAY[i] + CUBE_ARRAY[j] + CUBE_ARRAY[k])==CUBE_ARRAY[m]){
//System.out.println(m+"*"+m+"*"+m+"="+i+"*"+i+"*"+i+"+"+j+"*"+j+"*"+j+"+"+k+"*"+k+"*"+k);
}
}
[/code]
犯困，上面写错了些，先睡了，明天再考虑考虑

好吧，我上面还是写错了，这不睡不行了，手脑不能统一了。。
for(int m=k;m < 1000&&m*m*m<=3*k*k*k;m++)

求一道java面试算法题 如下

求一道java面试算法题如下