Как решить проблему рекурсивного возврата

У меня есть рекурсивная проблема Backtracking для школы, и я не понимаю, как я буду ее решать.

Учитывая массив целых чисел, определите, можно ли выбрать группу тех целых чисел, которые складываются в определенную сумму. Используйте рекурсивный метод под названием sum_to_total для решения проблемы (без циклов!).

Примеры:

  • "Массив [3, 6, 7]" и "Сумма 10" возвращают true, так как 3 + 7 = 10
  • "Массив [1, 2, 3]" и "Сумма 6" возвращают true, так как 1 + 2 + 3 = 6
  • «Массив [2, 4, 6]» и «сумма 5» возвращают false, так как никакая комбинация этих чисел не дает в сумме 5

Это то, что я получил до сих пор:

def self.sum_to_total(sum, array, index)

  @@sum_num += array[index]
  return false if @@sum_num > sum || @@sum_num < sum
  return false if index<board.length || index<0
  return true if @@sum_num == sum

  return solvable(sum, array, index+1) 
end


@@sum_num = 0
puts sum_to_total(10, [3, 5, 7], 0)

Несколько указателей помогут.


ruby recursion recursive-backtracking
person JosephKidd    schedule 19.03.2020    source источник
comment
Если система не позволяет вам отправить свой вопрос из-за плохого заголовка, пожалуйста, не добавляйте (Ruby) в конце, чтобы пройти фильтр. Вот для чего нужны теги. В stackoverflow.com/help/how-to-ask есть раздел о написании заголовков; Я предлагаю прочитать его, а затем вернуться и сделать заголовок вашего вопроса более описательным.   -  person anothermh    schedule 20.03.2020
comment
Добро пожаловать в СО! Пожалуйста, прочтите Как задавать домашние вопросы и отвечать на них? и Как форматировать сообщения... вместе с Как форматировать блоки кода? . Вы просите нас приложить усилия, чтобы помочь вам; Мы просим вас приложить усилия, чтобы задать хорошо заданный вопрос. Грамматика и правильное форматирование важны для SO.   -  person the Tin Man    schedule 20.03.2020
comment
Прочтите MCVE. Ваш код не соответствует рекомендациям, поскольку solvable не определен.   -  person the Tin Man    schedule 20.03.2020

Ответы (1)


arrow_upward
2
arrow_downward

Вы попробовали это, поэтому вот несколько советов, которые должны помочь вам двигаться вперед.

  1. Под «рекурсивным» мы подразумеваем метод, который вызывает сам себя. Ваш solvable должен быть вызовом sum_to_total.
  2. Рекурсивный метод должен передавать любые значения, которые изменяются во время работы метода, если вам нужно получить доступ к обновленным значениям при следующем вызове. Итак, index как у вас правильно, но вы также должны пройти в sum_num.
  3. Вы можете использовать значения по умолчанию для инициализации ваших index и sum_num при первом вызове. Вам не нужно возиться с глобальными переменными. (И не должен. Глобальные переменные — это зло. В большинстве случаев.)
  4. Вы хотите вернуться только тогда, когда вы прошли через весь массив. Вы не используете return при вызове рекурсивного метода, вы просто вызываете метод.
  5. Вам не нужно делать это методом класса, используя self.method_name.

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

def sum_to_total(sum, array, index = 0, sum_num = 0)
  sum_num += array[index]
  return sum_num == sum if index == array.size - 1
  sum_to_total(sum, array, index + 1, sum_num)
end

Три строки кода делают это:

  1. Добавьте к сумме текущее значение массива. (У вас в значительной степени было это хорошо.)
  2. Если вы закончили просмотр массива, верните значение, равное ли сумма массива предоставленному значению суммы.
  3. (Если вы еще не закончили просмотр массива), снова вызовите метод, передав увеличенное значение индекса и значение накопленной суммы на данный момент. (Вы были на правильном пути!)

Вот статья это должно помочь вам с обратной частью.

person BobRodes    schedule 20.03.2020