Числа суммы рекурсии * с правилом * - только рекурсия

Question

Итак, упражнение:

Использование только рекурсии (без циклов)

Определите, есть ли подосновы чисел, которые равны заданному числу в массиве, и следуйте правилу.

Допустим, у меня есть этот массив, я даю функции число для суммы, и она должна придерживаться этого правила: вы не можете повторять одно и то же число, и вы не можете суммировать 3 числа подряд (может ' t do i + 1 и i + 2)

int[] a = {5,4,2,1,3};

Итак, в этом случае: num 8 = true (4 + 3 + 1) (5 + 3) num 11 = false (4 + 5 + 2 3, но их три в ряд) (5 + 2 + 1 + 3 также три в ряд)

Моя попытка:

public static boolean sumRule(int[] a , int num){
        if (num == 0){
            return true;
        } else {

    return sumRule(a,num,0,a.length);
        }
}

private static boolean sumRule(int[] a, int num, int low,int high){
    if(low >= high || low < 0){
        return false;
    }

    if (a[low] == -1){
        return false;
    }

    if(a[low] == num || num-a[low] == 0 ){
        return true;
    }

    int temp = a[low];
    a[low] = -1;

    return  sumRule(a,num,low,high) || sumRule(a,num-temp,low+3,high) || sumRule(a,num-temp,low+1,high) ;

}

Но когда я отправляю 11 на это, он по-прежнему возвращает истину, кто-нибудь знает, что мне здесь не хватает?

Спасибо,

Answer 1

У меня есть полный ответ кода ниже, и вот объяснение:

По сути, вам нужно разбить эту проблему на повторение. Это означает, что вы смотрите на выбор на каждом шаге (то есть использовать число или нет в сумме) и рекурсивно вычисляете оба варианта.

Базовый случай: если num == 0, то мы знаем это так. Но если num! = 0 и длина массива 0, то мы знаем, что это ложь.

Рекурсивный случай: мы проверяем, меньше ли первое число в массиве num или равно ему. Если нет, то мы не сможем его использовать. Итак, мы выполняем рекурсивный вызов со всеми теми же параметрами, за исключением того, что массив теперь является исходным массивом за вычетом первого числа

Если мы МОЖЕМ использовать номер (например, a[0] <= num), то в истинном ответе может использоваться это или оно не может его использовать. Мы выполняем рекурсивный вызов для каждого случая и возвращаем истину, если какой-либо из рекурсивных вызовов возвращает истину.

Правило последовательного числа: это легко реализовать. Мы добавляем параметр под названием «left», который сообщает нам количество элементов, которые мы можем последовательно взять из начала массива. Для начала осталось 2, потому что мы можем взять не более 2 последовательных чисел. Затем в случаях, когда мы ДЕЙСТВИТЕЛЬНО используем первое число в массиве в нашей сумме, мы уменьшаем влево. Если мы не используем первое число в массиве, мы сбрасываем left до 2. В случаях, когда left становится 0, у нас нет другого выбора, кроме как пропустить текущее число в верхней части массива.

class Main {
  public static void main(String[] args) {
    int[] a = new int[] {5,4,2,1,3};
    System.out.println(sumRule(a, 8));
    System.out.println(sumRule(a, 11));
  }

  public static boolean sumRule(int[] a , int num){
    if (num == 0){
        return true;
    } else {
      return sumRule(a,num,2);
    }
  }

  private static boolean sumRule(int[] a, int num, int left){
      if (num == 0) {
        return true;
      }

      if (a.length == 0) {
        return false;
      }

      int[] a_new = new int[a.length-1];
      for (int i = 1; i < a.length; i++) a_new[i-1] = a[i];

      if (left == 0) {
        return sumRule(a_new, num, 2);
      }

      boolean using_a0 = false;
      if (a[0] <= num) {
        using_a0 = sumRule(a_new, num-a[0], left-1);
      }

      boolean not_using_a0 = sumRule(a_new, num, 2);

      return (not_using_a0 || using_a0);
  }
}

Изменить - вариант приведенного выше кода без копирования массива:

class Main {
  public static void main(String[] args) {
    int[] a = new int[] {5,4,2,1,3};
    System.out.println(sumRule(a, 8));
    System.out.println(sumRule(a, 11));
  }

  public static boolean sumRule(int[] a , int num){
    if (num == 0){
        return true;
    } else {
      return sumRuleNoLoop(a,num,2,0);
    }
  }

  private static boolean sumRuleNoLoop(int[] a, int num, int left, int startIdx){
      if (num == 0) {
        return true;
      }

      if (startIdx >= a.length) {
        return false;
      }

      if (left == 0) {
        return sumRuleNoLoop(a, num, 2, startIdx+1);
      }

      boolean using_a0 = false;
      if (a[startIdx] <= num) {
        using_a0 = sumRuleNoLoop(a, num-a[startIdx], left-1, startIdx+1);
      }

      boolean not_using_a0 = sumRuleNoLoop(a, num, 2, startIdx+1);

      return (not_using_a0 || using_a0);
  }
}

Answer 2

Вот моя реализация. Он содержит комментарии, объясняющие, что делают разные части.

public class RecurSum {
    /**
     * Determines whether 'sum' equals 'target'.
     * 
     * @param arr         - its elements are summed
     * @param sum         - sum of some elements in 'arr'
     * @param target      - required value of 'sum'
     * @param index       - index in 'arr'
     * @param consecutive - number of consecutive indexes summed to ensure don't exceed 3
     * @param start       - starting element in 'arr' which is used for back-tracking
     * 
     * @return "true" if 'sum' equals 'target'
     */
    private static boolean sumRule(int[] arr, int sum, int target, int index, int consecutive, int start) {
        if (sum == target) {
            return true;
        }
        else {
            if (index >= arr.length) {
                // if we have reached last element in 'arr' then back-track and start again
                if (start < arr.length) {
                    return sumRule(arr, 0, target, start + 1, 0, start + 1);
                }
                // we have reached last element in 'arr' and cannot back-track
                return false;
            }
            else {
                consecutive++;
                if (consecutive == 3) {
                    // skip 3rd consecutive element (because of the rule)
                    consecutive = 0;
                    return sumRule(arr, sum, target, index + 2, consecutive, start);
                }
                else {
                    if (sum + arr[index] > target) {
                        // recursive call but don't add current element of 'arr'
                        return sumRule(arr, sum, target, index + 1, 0, start);
                    }
                    // recursive call: add current element of 'arr' to 'sum' and proceed to next element
                    return sumRule(arr, sum + arr[index], target, index + 1, consecutive, start);
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5, 4, 2, 1, 3};

        // initial call to recursive method with target = 11 (eleven)
        System.out.println(sumRule(arr, 0, 11, 0, 0, 0));

        // initial call to recursive method with target = 8
        System.out.println(sumRule(arr, 0, 8, 0, 0, 0));
    }
}

Answer 3

Первое, что вы можете добавить, это проверить, не добавляются ли 3 числа подряд. Также замена числа в массиве на -1 будет иметь непредвиденные побочные эффекты при рекурсивных вызовах. Ниже то, что у меня есть. Вы можете проигнорировать параметр index, который я использовал для просмотра используемых значений.

Объяснение: рекурсивный метод sumRule делит проблему на две части:

• Первая часть занимает значение текущего индекса и складывается с суммой значений, начиная со следующего индекса.
• Вторая часть предполагает, что текущее значение не может быть принято за сумму. Он только проверяет, есть ли сумма в подмножестве, начиная со следующего значения массива.

В методе lastIndex отслеживает индекс последнего значения, выбранного для суммы. Итак, в первом вызове значение равно 0, 1 во втором и т. Д.

(start - lastIndex <= 1 ? consecutive + 1 : 1) - это проверка, следует ли увеличивать значение consecutive или нет. Последовательный = 1 означает, что к сумме добавляется текущее значение.

  public static boolean sumRule(int[] a, int num) {
    if (num == 0) {
      return true;
    } else {
      return sumRule(a, num, 0, 0, 0, 0, "");
    }
  }

  public static boolean sumRule(final int[] a, int num, int sum, int start, int consecutive, int lastIndex,
      String index) {
    if (consecutive == 3) {
      return false;
    }

    if (sum == num) {
      System.out.println(index);
      return true;
    }

    if (start >= a.length) {
      return false;
    }

    return sumRule(a, num, sum + a[start], start + 1, (start - lastIndex <= 1 ? consecutive + 1 : 1), start,
        index + ", " + start) || sumRule(a, num, sum, start + 1, consecutive, lastIndex, index);
  }