Разделите массив на 2 подмассива и проверьте, равны ли умножения - PullRequest
Новая
       15

Разделите массив на 2 подмассива и проверьте, равны ли умножения

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

Я практикуюсь на экзамене по Java.Один из вопросов, с которыми я столкнулся сегодня: «Учитывая массив с n числами, мне нужно проверить, есть ли 2 подмассива (не обязательно равные), что их умножение равно - если они есть, вернет true, иначе false.например: если массив: {2,15,3,4,2,5} - вернет True, если массив: {2,4,6,2,3,4} - вернет False.

ответ должен быть рекурсивным, без каких-либо циклов.

поэтому я подумал, что если есть 2 подмассива, у которых их умножение равно, это означает, что общее умножение всего массива должно быть числом с квадратным корнем,например, в первом массиве это 3600, то есть 60.

Пока я не смог найти ни одного случая, для которого он не будет работать, но все еще не уверен на 100%, что он охватит все возможные случаи.

Вот мой код для этого: 

    public static boolean splitEqualMult(int[] a) {
      double multi = isArrSqrt(a,0);

      if(Math.sqrt(multi) == Math.floor(Math.sqrt(multi))) {
          return true;
    }

    return false;
}

private static double isArrSqrt(int[] a, int i) {

    if(i == a.length) {
        return 1;
    }

    return a[i] * isArrSqrt(a,i+1);
}

, желающий услышать ваши мысли!

1 Ответ

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

Ваше решение дает ложные срабатывания.Например, массив {2,8} нельзя разделить на два подмассива одинакового продукта, но вы вернете true, поскольку квадратный корень из 2 * 8 равен 4.

Когда вы пытаетесьЧтобы решить такую ​​рекурсию, вы должны попытаться подумать, что произойдет, если вы уменьшите размер ввода на 1.

Предположим, что данный массив arr имеет правильное разбиение (на две подгруппы с одинаковым произведением).Это означает, что если вы удалите первый элемент a[0], вы должны иметь возможность разделить оставшуюся часть массива на две подгруппы, так что p1 == p2 * a[0] или p1 == p2 / a[0], где p1 - это произведение элементовпервая группа и p2 является произведением элементов второй группы.

Это говорит о том, что рекурсивный метод должен проверять наличие заданного хвоста входного массива (т.е. arr [from] ...arr [arr.length-1] для некоторых из> = 0), существует разделение на две группы, так что произведение первой группы, деленное на произведение второй группы (или наоборот), равно заданному коэффициенту: 

public static boolean canSplit(int[] arr, int from, double factor)
{
    if (from == arr.length - 1) {
        return arr[from] == factor;
    }
    return canSplit(arr, from + 1, factor * arr[from]) || canSplit(arr, from + 1, factor / arr[from]);
}

Первоначальный вызов будет: 

public static boolean canSplit(int[] arr)
{
    if (arr.length < 2) {
        return false;
    } else {
        return canSplit(arr, 0, 1); // the second parameter is 0, since the first recursive call
                                    // applies to the whole array
                                    // the third parameter is 1, since we want to check if there 
                                    // are two groups such that the product of the first divided
                                    // by the product of the second is 1 (i.e. the two products
                                    // are equal)
    }
}

Тесты: 

System.out.println (canSplit(new int[]{2,15,3,4,2,5}));
System.out.println (canSplit(new int[]{2,4,6,2,3,4}));
System.out.println (canSplit(new int[]{2,2,4}));
System.out.println (canSplit(new int[]{2,8}));

Выход: 

true
false
true
false
...