Как решить рекурсивную проблему с возвратом - PullRequest
Новая
       52

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

0 голосов
/ 19 марта 2020

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

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

Примеры:

  • "Array [3, 6, 7]" и "Sum 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)

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

1 Ответ

2 голосов
/ 20 марта 2020

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

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

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

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. (Если вы пока не закончите прохождение массива) вызовите метод еще раз, передав на данный момент увеличенное значение индекса и значение накопленной суммы. (Вы были на правильном пути!)

Вот статья, которая должна помочь вам с возвратом.

...