Блог

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

Написанный мной код выглядит следующим образом:

 results = []

def findSchedulesHelper(workHours_left, dayHoursLimit, days_left, res):
    if workHours_left < 0:
        return
    elif workHours_left > 0 and days_left == 0:
        return
    elif workHours_left == 0 and days_left != 0:
        for i in range(days_left):
            res.append(0)
        results.append(res)
        return
    elif days_left == 0 and workHours_left == 0:
        results.append(res)
        return
    else:
        for i in range(dayHoursLimit   1):
            res.append(i)
            findSchedulesHelper(workHours_left - i, dayHoursLimit, days_left - 1, res)
            res.pop()


def findSchedules(workHours, dayHours, pattern):
    # Write your code here
    num_question_mark = 0
    total_hours_so_far = 0
    for char in pattern:
        if char == "?":
            num_question_mark  = 1
        else:
            total_hours_so_far  = int(char)

    hours_left_to_fill = workHours - total_hours_so_far

    for i in range(dayHours   1):
        findSchedulesHelper(hours_left_to_fill - i, dayHours, num_question_mark - 1, [i])
    print results

findSchedules(3,2,"??2??00")
  

но это дает неправильный ответ.

Если я изменю одну строку и сделаю ее:

 results = []

def findSchedulesHelper(workHours_left, dayHoursLimit, days_left, res):
    if workHours_left < 0:
        return
    elif workHours_left > 0 and days_left == 0:
        return
    elif workHours_left == 0 and days_left != 0:
        for i in range(days_left):
            res.append(0)
        results.append(res)
        return
    elif days_left == 0 and workHours_left == 0:
        results.append(res)
        return
    else:
        for i in range(dayHoursLimit   1):
            findSchedulesHelper(workHours_left - i, dayHoursLimit, days_left - 1, res   [i])


def findSchedules(workHours, dayHours, pattern):
    # Write your code here
    num_question_mark = 0
    total_hours_so_far = 0
    for char in pattern:
        if char == "?":
            num_question_mark  = 1
        else:
            total_hours_so_far  = int(char)

    hours_left_to_fill = workHours - total_hours_so_far

    for i in range(dayHours   1):
        findSchedulesHelper(hours_left_to_fill - i, dayHours, num_question_mark - 1, [i])
    print results

findSchedules(3,2,"??2??00")
  

Тогда все правильно. Я действительно не понимаю, почему это так. Я попытался выполнить некоторую отладку и обнаружил, что append и pop работают не так, как я ожидал от них. Было бы здорово, если бы кто-нибудь мог объяснить, в чем именно разница между двумя способами, которыми я выполнил функцию.

Первая программа добавляет элемент в конец res , выполняет рекурсивный вызов findSchedulesHelper() и после вызова удаляет добавленный элемент:

 res.append(i)
findSchedulesHelper(workHours_left - i, dayHoursLimit, days_left - 1, res)
res.pop()
  

В то время как вторая программа передает новый список, в котором есть все, что есть res плюс дополнительный элемент. Его не нужно очищать после рекурсивного вызова:

 findSchedulesHelper(workHours_left - i, dayHoursLimit, days_left - 1, res   [i])
  

Одно из различий между ними связано с этим кодом:

 for i in range(days_left):
    res.append(0)
  

То есть рекурсивный вызов к findSchedulesHelper() может измениться res . Если это произойдет, res.pop() при возврате может удаляться что-то другое, чем вы думаете. И в конце res следующего вызова могут быть дополнительные данные. Вторая программа не сталкивается с этой проблемой, поскольку она передает копию res и никогда больше не просматривает и не использует копию повторно.

Следующими потенциальными проблемами являются множественные вызовы:

 results.append(res)
  

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