поиск всех результатов a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3, проблемы, вызванной методом Math.pow () - PullRequest
0 голосов
/ 25 декабря 2018

Задача : вывести все + 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 >> 

Ответы [ 2 ]

0 голосов
/ 25 декабря 2018

Как я уже говорил в комментарии, проблема, с которой вы сталкиваетесь, вероятно, связана с тем, что 1/3 оценивается как 0. Преобразование 1 или 3 в число с плавающей запятой должно решить эту проблему.

Как бы то ни было, я бы предложил дальнейшую оптимизацию: вычислить x ^ 3 для x = 1 до n и сохранить результаты как в массиве, так и в хэш-наборе.Затем для каждой комбинации из 3 чисел в тесте массива, если a + bc находится в хэш-наборе (из-за симметрии a + b вы также можете сэкономить некоторые дубликаты, немного улучшив итерации по b).

Редактировать:Конечно, моя оптимизация жертвует сложностью пространства.

0 голосов
/ 25 декабря 2018

Когда вы делите два целых числа, ответ также становится целым числом, потому что вы получаете 1 вместо нуля.1/3 равно нулю, а Math.pow(0,0) равно 1. Вместо этого вы можете использовать Math.pow(0,1./3)), чтобы получить 0.

ОБНОВЛЕНИЕ
Вы можете проверить это чтобы увидеть лучшее решение, которое уже предоставлено.

...