查找 a^3 + b^3 = c^3 + d^3 的所有结果，由 Math.pow() 方法引起的问题
finding all results of a^3 + b^3 = c^3 + d^3, problem caused by Math.pow() method
问题：打印方程的所有+ve整数解
a^3 + b^3 = c^3 + d^3
其中 a, b, c, d 是整数 bw 1 to 1000
Math.pow() 函数遇到问题。
所以我写了两个代码，一个是蛮力的，另一个是稍微优化的。
第一个显示正确的输出而第二个不是，这是由于幂函数。
Math.pow(0,1/3) = 1 而应该是 0
class Find_a3_b3__c3_d3{
// final static int n = 100;
// solution 1 : BRUTE FORCE
public static void bruteForce(){ // O(N^4)
int n = 5;
int resultCount = 0;
for(int a=0; a<n ; a++){
for(int b=0; b<n; b++){
for(int c=0; c<n; c++){
for(int d=0; d<n; d++){
int a_3 = a*a*a;
int b_3 = b*b*b;
int c_3 = c*c*c;
int d_3 = d*d*d;
if(a_3 + b_3 == c_3 + d_3){
System.out.println((resultCount++) + " a: "+a +" b: "+b + " --- c: "+c + " d: "+d );
break;
}
}
}
}
}
System.out.println("\n\n");
}
// solution 2 : BRUTE FORCE
// idea is : as we know d is going to have one value for each pair of a,b & c so
// if we know a b & c , then we can find d by the relation cubeRoot (a_3 + b_3 - c_3);
public static void littleBetter(){ // O(N^4)
int n = 5;
int resultCount = 0;
for(int a=0; a<n ; a++){
for(int b=0; b<n; b++){
for(int c=0; c<n; c++){
int a_3 = a*a*a;
int b_3 = b*b*b;
int c_3 = c*c*c;
System.out.println(a +" " + b+" " + c +" ");
System.out.println(a_3 +" " + b_3+" " + c_3 +" " + Math.pow(a_3 + b_3 - c_3, 1/3));
int d = (int) Math.pow(a_3 + b_3 - c_3, 1/3);
int d_3 = d*d*d;
if(a_3 + b_3 == c_3 + d_3){
System.out.println((resultCount++) + " a: "+a +" b: "+b + " --- c: "+c + " d: "+d );
}
}
}
}
System.out.println("\n\n");
}
public static void main(String[] args) {
bruteForce();// O(n^4)
littleBetter(); // O(n^3)
System.out.println( Math.pow(0,1/3));
System.out.println( Math.pow(0,1));
System.out.println( Math.pow(0,0));
System.out.println( Math.pow(34,0));
System.out.println( Math.pow(34,-0));
System.out.println( Math.pow(0,1));
}
}
如果你执行程序，你会看到结果的行号也不一样。
输出
~/Documents/CTCI Codes >> javac Find_a3_b3__c3_d3.java
~/Documents/CTCI Codes >> java Find_a3_b3__c3_d3
0 a: 0 b: 0 --- c: 0 d: 0
1 a: 0 b: 1 --- c: 0 d: 1
2 a: 0 b: 1 --- c: 1 d: 0
3 a: 0 b: 2 --- c: 0 d: 2
4 a: 0 b: 2 --- c: 2 d: 0
5 a: 0 b: 3 --- c: 0 d: 3
6 a: 0 b: 3 --- c: 3 d: 0
7 a: 0 b: 4 --- c: 0 d: 4
8 a: 0 b: 4 --- c: 4 d: 0
9 a: 1 b: 0 --- c: 0 d: 1
10 a: 1 b: 0 --- c: 1 d: 0
11 a: 1 b: 1 --- c: 1 d: 1
12 a: 1 b: 2 --- c: 1 d: 2
13 a: 1 b: 2 --- c: 2 d: 1
14 a: 1 b: 3 --- c: 1 d: 3
15 a: 1 b: 3 --- c: 3 d: 1
16 a: 1 b: 4 --- c: 1 d: 4
17 a: 1 b: 4 --- c: 4 d: 1
18 a: 2 b: 0 --- c: 0 d: 2
19 a: 2 b: 0 --- c: 2 d: 0
20 a: 2 b: 1 --- c: 1 d: 2
21 a: 2 b: 1 --- c: 2 d: 1
22 a: 2 b: 2 --- c: 2 d: 2
23 a: 2 b: 3 --- c: 2 d: 3
24 a: 2 b: 3 --- c: 3 d: 2
25 a: 2 b: 4 --- c: 2 d: 4
26 a: 2 b: 4 --- c: 4 d: 2
27 a: 3 b: 0 --- c: 0 d: 3
28 a: 3 b: 0 --- c: 3 d: 0
29 a: 3 b: 1 --- c: 1 d: 3
30 a: 3 b: 1 --- c: 3 d: 1
31 a: 3 b: 2 --- c: 2 d: 3
32 a: 3 b: 2 --- c: 3 d: 2
33 a: 3 b: 3 --- c: 3 d: 3
34 a: 3 b: 4 --- c: 3 d: 4
35 a: 3 b: 4 --- c: 4 d: 3
36 a: 4 b: 0 --- c: 0 d: 4
37 a: 4 b: 0 --- c: 4 d: 0
38 a: 4 b: 1 --- c: 1 d: 4
39 a: 4 b: 1 --- c: 4 d: 1
40 a: 4 b: 2 --- c: 2 d: 4
41 a: 4 b: 2 --- c: 4 d: 2
42 a: 4 b: 3 --- c: 3 d: 4
43 a: 4 b: 3 --- c: 4 d: 3
44 a: 4 b: 4 --- c: 4 d: 4
0 0 0
0 0 0 1.0
0 0 1
0 0 1 1.0
0 0 2
0 0 8 1.0
0 0 3
0 0 27 1.0
0 0 4
0 0 64 1.0
0 1 0
0 1 0 1.0
0 a: 0 b: 1 --- c: 0 d: 1
0 1 1
0 1 1 1.0
0 1 2
0 1 8 1.0
0 1 3
0 1 27 1.0
0 1 4
0 1 64 1.0
0 2 0
0 8 0 1.0
0 2 1
0 8 1 1.0
0 2 2
0 8 8 1.0
0 2 3
0 8 27 1.0
0 2 4
0 8 64 1.0
0 3 0
0 27 0 1.0
0 3 1
0 27 1 1.0
0 3 2
0 27 8 1.0
0 3 3
0 27 27 1.0
0 3 4
0 27 64 1.0
0 4 0
0 64 0 1.0
0 4 1
0 64 1 1.0
0 4 2
0 64 8 1.0
0 4 3
0 64 27 1.0
0 4 4
0 64 64 1.0
1 0 0
1 0 0 1.0
1 a: 1 b: 0 --- c: 0 d: 1
1 0 1
1 0 1 1.0
1 0 2
1 0 8 1.0
1 0 3
1 0 27 1.0
1 0 4
1 0 64 1.0
1 1 0
1 1 0 1.0
1 1 1
1 1 1 1.0
2 a: 1 b: 1 --- c: 1 d: 1
1 1 2
1 1 8 1.0
1 1 3
1 1 27 1.0
1 1 4
1 1 64 1.0
1 2 0
1 8 0 1.0
1 2 1
1 8 1 1.0
1 2 2
1 8 8 1.0
3 a: 1 b: 2 --- c: 2 d: 1
1 2 3
1 8 27 1.0
1 2 4
1 8 64 1.0
1 3 0
1 27 0 1.0
1 3 1
1 27 1 1.0
1 3 2
1 27 8 1.0
1 3 3
1 27 27 1.0
4 a: 1 b: 3 --- c: 3 d: 1
1 3 4
1 27 64 1.0
1 4 0
1 64 0 1.0
1 4 1
1 64 1 1.0
1 4 2
1 64 8 1.0
1 4 3
1 64 27 1.0
1 4 4
1 64 64 1.0
5 a: 1 b: 4 --- c: 4 d: 1
2 0 0
8 0 0 1.0
2 0 1
8 0 1 1.0
2 0 2
8 0 8 1.0
2 0 3
8 0 27 1.0
2 0 4
8 0 64 1.0
2 1 0
8 1 0 1.0
2 1 1
8 1 1 1.0
2 1 2
8 1 8 1.0
6 a: 2 b: 1 --- c: 2 d: 1
2 1 3
8 1 27 1.0
2 1 4
8 1 64 1.0
2 2 0
8 8 0 1.0
2 2 1
8 8 1 1.0
2 2 2
8 8 8 1.0
2 2 3
8 8 27 1.0
2 2 4
8 8 64 1.0
2 3 0
8 27 0 1.0
2 3 1
8 27 1 1.0
2 3 2
8 27 8 1.0
2 3 3
8 27 27 1.0
2 3 4
8 27 64 1.0
2 4 0
8 64 0 1.0
2 4 1
8 64 1 1.0
2 4 2
8 64 8 1.0
2 4 3
8 64 27 1.0
2 4 4
8 64 64 1.0
3 0 0
27 0 0 1.0
3 0 1
27 0 1 1.0
3 0 2
27 0 8 1.0
3 0 3
27 0 27 1.0
3 0 4
27 0 64 1.0
3 1 0
27 1 0 1.0
3 1 1
27 1 1 1.0
3 1 2
27 1 8 1.0
3 1 3
27 1 27 1.0
7 a: 3 b: 1 --- c: 3 d: 1
3 1 4
27 1 64 1.0
3 2 0
27 8 0 1.0
3 2 1
27 8 1 1.0
3 2 2
27 8 8 1.0
3 2 3
27 8 27 1.0
3 2 4
27 8 64 1.0
3 3 0
27 27 0 1.0
3 3 1
27 27 1 1.0
3 3 2
27 27 8 1.0
3 3 3
27 27 27 1.0
3 3 4
27 27 64 1.0
3 4 0
27 64 0 1.0
3 4 1
27 64 1 1.0
3 4 2
27 64 8 1.0
3 4 3
27 64 27 1.0
3 4 4
27 64 64 1.0
4 0 0
64 0 0 1.0
4 0 1
64 0 1 1.0
4 0 2
64 0 8 1.0
4 0 3
64 0 27 1.0
4 0 4
64 0 64 1.0
4 1 0
64 1 0 1.0
4 1 1
64 1 1 1.0
4 1 2
64 1 8 1.0
4 1 3
64 1 27 1.0
4 1 4
64 1 64 1.0
8 a: 4 b: 1 --- c: 4 d: 1
4 2 0
64 8 0 1.0
4 2 1
64 8 1 1.0
4 2 2
64 8 8 1.0
4 2 3
64 8 27 1.0
4 2 4
64 8 64 1.0
4 3 0
64 27 0 1.0
4 3 1
64 27 1 1.0
4 3 2
64 27 8 1.0
4 3 3
64 27 27 1.0
4 3 4
64 27 64 1.0
4 4 0
64 64 0 1.0
4 4 1
64 64 1 1.0
4 4 2
64 64 8 1.0
4 4 3
64 64 27 1.0
4 4 4
64 64 64 1.0
1.0
0.0
1.0
1.0
1.0
0.0
~/Documents/CTCI Codes >>
当您将两个整数相除时，答案也会变成整数，这是因为您得到的是 1 而不是零。 1/3 等于 0，Math.pow(0,0) 等于 1。您可以使用 Math.pow(0,1./3)) 得到 0。
UPDATE
您可以检查 this 以查看已经提供的更好的解决方案。
正如我在评论中所述，您遇到的问题可能是由于 1/3 被评估为 0。将 1 或 3 转换为浮点数应该可以解决该问题。
但是，我建议进一步优化：计算 x = 1 到 n 的 x^3 并将结果存储在数组和哈希集中。然后对于数组中 3 个数字的每个组合测试 a+b-c 是否在哈希集中（由于 a+b 的对称性，您还可以通过在 b 上稍微好一点的迭代来保留一些重复项）。
编辑：当然，我的优化牺牲了 space 复杂性。
问题：打印方程的所有+ve整数解
a^3 + b^3 = c^3 + d^3
其中 a, b, c, d 是整数 bw 1 to 1000
Math.pow() 函数遇到问题。
所以我写了两个代码，一个是蛮力的，另一个是稍微优化的。 第一个显示正确的输出而第二个不是，这是由于幂函数。
Math.pow(0,1/3) = 1 而应该是 0
class Find_a3_b3__c3_d3{
// final static int n = 100;
// solution 1 : BRUTE FORCE
public static void bruteForce(){ // O(N^4)
int n = 5;
int resultCount = 0;
for(int a=0; a<n ; a++){
for(int b=0; b<n; b++){
for(int c=0; c<n; c++){
for(int d=0; d<n; d++){
int a_3 = a*a*a;
int b_3 = b*b*b;
int c_3 = c*c*c;
int d_3 = d*d*d;
if(a_3 + b_3 == c_3 + d_3){
System.out.println((resultCount++) + " a: "+a +" b: "+b + " --- c: "+c + " d: "+d );
break;
}
}
}
}
}
System.out.println("\n\n");
}
// solution 2 : BRUTE FORCE
// idea is : as we know d is going to have one value for each pair of a,b & c so
// if we know a b & c , then we can find d by the relation cubeRoot (a_3 + b_3 - c_3);
public static void littleBetter(){ // O(N^4)
int n = 5;
int resultCount = 0;
for(int a=0; a<n ; a++){
for(int b=0; b<n; b++){
for(int c=0; c<n; c++){
int a_3 = a*a*a;
int b_3 = b*b*b;
int c_3 = c*c*c;
System.out.println(a +" " + b+" " + c +" ");
System.out.println(a_3 +" " + b_3+" " + c_3 +" " + Math.pow(a_3 + b_3 - c_3, 1/3));
int d = (int) Math.pow(a_3 + b_3 - c_3, 1/3);
int d_3 = d*d*d;
if(a_3 + b_3 == c_3 + d_3){
System.out.println((resultCount++) + " a: "+a +" b: "+b + " --- c: "+c + " d: "+d );
}
}
}
}
System.out.println("\n\n");
}
public static void main(String[] args) {
bruteForce();// O(n^4)
littleBetter(); // O(n^3)
System.out.println( Math.pow(0,1/3));
System.out.println( Math.pow(0,1));
System.out.println( Math.pow(0,0));
System.out.println( Math.pow(34,0));
System.out.println( Math.pow(34,-0));
System.out.println( Math.pow(0,1));
}
}
如果你执行程序，你会看到结果的行号也不一样。
输出
~/Documents/CTCI Codes >> javac Find_a3_b3__c3_d3.java
~/Documents/CTCI Codes >> java Find_a3_b3__c3_d3
0 a: 0 b: 0 --- c: 0 d: 0
1 a: 0 b: 1 --- c: 0 d: 1
2 a: 0 b: 1 --- c: 1 d: 0
3 a: 0 b: 2 --- c: 0 d: 2
4 a: 0 b: 2 --- c: 2 d: 0
5 a: 0 b: 3 --- c: 0 d: 3
6 a: 0 b: 3 --- c: 3 d: 0
7 a: 0 b: 4 --- c: 0 d: 4
8 a: 0 b: 4 --- c: 4 d: 0
9 a: 1 b: 0 --- c: 0 d: 1
10 a: 1 b: 0 --- c: 1 d: 0
11 a: 1 b: 1 --- c: 1 d: 1
12 a: 1 b: 2 --- c: 1 d: 2
13 a: 1 b: 2 --- c: 2 d: 1
14 a: 1 b: 3 --- c: 1 d: 3
15 a: 1 b: 3 --- c: 3 d: 1
16 a: 1 b: 4 --- c: 1 d: 4
17 a: 1 b: 4 --- c: 4 d: 1
18 a: 2 b: 0 --- c: 0 d: 2
19 a: 2 b: 0 --- c: 2 d: 0
20 a: 2 b: 1 --- c: 1 d: 2
21 a: 2 b: 1 --- c: 2 d: 1
22 a: 2 b: 2 --- c: 2 d: 2
23 a: 2 b: 3 --- c: 2 d: 3
24 a: 2 b: 3 --- c: 3 d: 2
25 a: 2 b: 4 --- c: 2 d: 4
26 a: 2 b: 4 --- c: 4 d: 2
27 a: 3 b: 0 --- c: 0 d: 3
28 a: 3 b: 0 --- c: 3 d: 0
29 a: 3 b: 1 --- c: 1 d: 3
30 a: 3 b: 1 --- c: 3 d: 1
31 a: 3 b: 2 --- c: 2 d: 3
32 a: 3 b: 2 --- c: 3 d: 2
33 a: 3 b: 3 --- c: 3 d: 3
34 a: 3 b: 4 --- c: 3 d: 4
35 a: 3 b: 4 --- c: 4 d: 3
36 a: 4 b: 0 --- c: 0 d: 4
37 a: 4 b: 0 --- c: 4 d: 0
38 a: 4 b: 1 --- c: 1 d: 4
39 a: 4 b: 1 --- c: 4 d: 1
40 a: 4 b: 2 --- c: 2 d: 4
41 a: 4 b: 2 --- c: 4 d: 2
42 a: 4 b: 3 --- c: 3 d: 4
43 a: 4 b: 3 --- c: 4 d: 3
44 a: 4 b: 4 --- c: 4 d: 4
0 0 0
0 0 0 1.0
0 0 1
0 0 1 1.0
0 0 2
0 0 8 1.0
0 0 3
0 0 27 1.0
0 0 4
0 0 64 1.0
0 1 0
0 1 0 1.0
0 a: 0 b: 1 --- c: 0 d: 1
0 1 1
0 1 1 1.0
0 1 2
0 1 8 1.0
0 1 3
0 1 27 1.0
0 1 4
0 1 64 1.0
0 2 0
0 8 0 1.0
0 2 1
0 8 1 1.0
0 2 2
0 8 8 1.0
0 2 3
0 8 27 1.0
0 2 4
0 8 64 1.0
0 3 0
0 27 0 1.0
0 3 1
0 27 1 1.0
0 3 2
0 27 8 1.0
0 3 3
0 27 27 1.0
0 3 4
0 27 64 1.0
0 4 0
0 64 0 1.0
0 4 1
0 64 1 1.0
0 4 2
0 64 8 1.0
0 4 3
0 64 27 1.0
0 4 4
0 64 64 1.0
1 0 0
1 0 0 1.0
1 a: 1 b: 0 --- c: 0 d: 1
1 0 1
1 0 1 1.0
1 0 2
1 0 8 1.0
1 0 3
1 0 27 1.0
1 0 4
1 0 64 1.0
1 1 0
1 1 0 1.0
1 1 1
1 1 1 1.0
2 a: 1 b: 1 --- c: 1 d: 1
1 1 2
1 1 8 1.0
1 1 3
1 1 27 1.0
1 1 4
1 1 64 1.0
1 2 0
1 8 0 1.0
1 2 1
1 8 1 1.0
1 2 2
1 8 8 1.0
3 a: 1 b: 2 --- c: 2 d: 1
1 2 3
1 8 27 1.0
1 2 4
1 8 64 1.0
1 3 0
1 27 0 1.0
1 3 1
1 27 1 1.0
1 3 2
1 27 8 1.0
1 3 3
1 27 27 1.0
4 a: 1 b: 3 --- c: 3 d: 1
1 3 4
1 27 64 1.0
1 4 0
1 64 0 1.0
1 4 1
1 64 1 1.0
1 4 2
1 64 8 1.0
1 4 3
1 64 27 1.0
1 4 4
1 64 64 1.0
5 a: 1 b: 4 --- c: 4 d: 1
2 0 0
8 0 0 1.0
2 0 1
8 0 1 1.0
2 0 2
8 0 8 1.0
2 0 3
8 0 27 1.0
2 0 4
8 0 64 1.0
2 1 0
8 1 0 1.0
2 1 1
8 1 1 1.0
2 1 2
8 1 8 1.0
6 a: 2 b: 1 --- c: 2 d: 1
2 1 3
8 1 27 1.0
2 1 4
8 1 64 1.0
2 2 0
8 8 0 1.0
2 2 1
8 8 1 1.0
2 2 2
8 8 8 1.0
2 2 3
8 8 27 1.0
2 2 4
8 8 64 1.0
2 3 0
8 27 0 1.0
2 3 1
8 27 1 1.0
2 3 2
8 27 8 1.0
2 3 3
8 27 27 1.0
2 3 4
8 27 64 1.0
2 4 0
8 64 0 1.0
2 4 1
8 64 1 1.0
2 4 2
8 64 8 1.0
2 4 3
8 64 27 1.0
2 4 4
8 64 64 1.0
3 0 0
27 0 0 1.0
3 0 1
27 0 1 1.0
3 0 2
27 0 8 1.0
3 0 3
27 0 27 1.0
3 0 4
27 0 64 1.0
3 1 0
27 1 0 1.0
3 1 1
27 1 1 1.0
3 1 2
27 1 8 1.0
3 1 3
27 1 27 1.0
7 a: 3 b: 1 --- c: 3 d: 1
3 1 4
27 1 64 1.0
3 2 0
27 8 0 1.0
3 2 1
27 8 1 1.0
3 2 2
27 8 8 1.0
3 2 3
27 8 27 1.0
3 2 4
27 8 64 1.0
3 3 0
27 27 0 1.0
3 3 1
27 27 1 1.0
3 3 2
27 27 8 1.0
3 3 3
27 27 27 1.0
3 3 4
27 27 64 1.0
3 4 0
27 64 0 1.0
3 4 1
27 64 1 1.0
3 4 2
27 64 8 1.0
3 4 3
27 64 27 1.0
3 4 4
27 64 64 1.0
4 0 0
64 0 0 1.0
4 0 1
64 0 1 1.0
4 0 2
64 0 8 1.0
4 0 3
64 0 27 1.0
4 0 4
64 0 64 1.0
4 1 0
64 1 0 1.0
4 1 1
64 1 1 1.0
4 1 2
64 1 8 1.0
4 1 3
64 1 27 1.0
4 1 4
64 1 64 1.0
8 a: 4 b: 1 --- c: 4 d: 1
4 2 0
64 8 0 1.0
4 2 1
64 8 1 1.0
4 2 2
64 8 8 1.0
4 2 3
64 8 27 1.0
4 2 4
64 8 64 1.0
4 3 0
64 27 0 1.0
4 3 1
64 27 1 1.0
4 3 2
64 27 8 1.0
4 3 3
64 27 27 1.0
4 3 4
64 27 64 1.0
4 4 0
64 64 0 1.0
4 4 1
64 64 1 1.0
4 4 2
64 64 8 1.0
4 4 3
64 64 27 1.0
4 4 4
64 64 64 1.0
1.0
0.0
1.0
1.0
1.0
0.0
~/Documents/CTCI Codes >>
当您将两个整数相除时，答案也会变成整数，这是因为您得到的是 1 而不是零。 1/3 等于 0，Math.pow(0,0) 等于 1。您可以使用 Math.pow(0,1./3)) 得到 0。
UPDATE
您可以检查 this 以查看已经提供的更好的解决方案。
正如我在评论中所述，您遇到的问题可能是由于 1/3 被评估为 0。将 1 或 3 转换为浮点数应该可以解决该问题。
但是，我建议进一步优化：计算 x = 1 到 n 的 x^3 并将结果存储在数组和哈希集中。然后对于数组中 3 个数字的每个组合测试 a+b-c 是否在哈希集中（由于 a+b 的对称性，您还可以通过在 b 上稍微好一点的迭代来保留一些重复项）。
编辑：当然，我的优化牺牲了 space 复杂性。