Блог

Главная - Вопросы по программированию - Как мне написать рекурсивную функцию, которая вычисляет способы суммирования до значения в наборе чисел?

Как мне написать рекурсивную функцию, которая вычисляет способы суммирования до значения в наборе чисел?

#python #algorithm #recursion

#python #алгоритм #рекурсия

Вопрос:

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

 def ways_to_sum(number, set:{int}) -> int:
    blah, blah

Вызов

 ways_to_sum(7,{2,3,5})

Дало бы мне

 2

Как, сначала, 5 2 , а затем, 2 2 3 суммируется до семи. Функция должна быть рекурсивной. Я не писал базовый вариант, поскольку я изо всех сил пытаюсь его настроить.

Комментарии:

1. Я не понимаю, почему отображаемые вами входные данные должны давать такой результат. 4 В вашем наборе нет.

2. Вы имеете в виду 1st: 5 2, а не 4 3?

3. «Функция должна быть рекурсивной функцией» Итак, есть ли у вас какой-либо другой опыт написания рекурсивных функций? Вы понимаете, почему рекурсия поможет вам решить эту проблему? Можете ли вы придумать способ разбить проблему на более мелкие задачи, которые выглядят одинаково?

4. @KarlKnechtel Извините, эта часть опечатка. Я исправил это

5. @Alex, я бы попросил вас предоставить «нерекурсивный» код для этого, потому что прямо сейчас кажется, что вы задаете более 1 проблемы — как получить решение этой проблемы и как получить рекурсивный код. Пожалуйста, предоставьте логику решения, чтобы другие могли помочь вам написать его рекурсивную версию, иначе просто кажется, что мы решаем вашу домашнюю работу :).

Ответ №1:

Вероятно, это не самое эффективное решение, но оно должно работать, базовый случай рекурсии — это когда число = 0, шаг уменьшения уменьшает число на каждое значение в заданном наборе чисел (я назвал его значениями). Он отслеживает сумму с помощью словаря трассировки, одним из простых способов ускорить его было бы использовать динамическое программирование и сохранить трассировки для 1,2,3, …, числа в массиве

 def find_sum(number, values, trace = None):
    if trace == None:
        trace = {}
        for i in values:
            trace[i] = 0
    if number == 0:
        return [trace]
    elif number < 0:
        #not a sum
        return None
    stored_trace = []
    for i in values:
        trace_copy = copy.deepcopy(trace)
        trace_copy[i]  = 1
        prev_traces = find_sum(number - i, values, trace_copy)
        if prev_traces == None:
            continue
        for j in prev_traces:
            if j not in stored_trace:
                stored_trace.append(j)
    return (stored_trace)

def function(number, values):
    return len(find_sum(number, values))

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

 def find_sum(number, values, past_traces):
    new_trace = []
    for i in values:
        if number - i < 0:
            #this sum doesn't work
            continue
        if past_traces[number-i] == None:
            find_sum(number - i, values, past_traces)
        for j in past_traces[number - i]:
            curr = copy.deepcopy(j)
            curr[i]  = 1
            if curr not in new_trace:
                new_trace.append(curr)
    past_traces[number] = new_trace
    return new_trace

def function(number, values):
    zero_trace = {}
    for i in values:
        zero_trace[i] = 0
    return find_sum(number, values, [[zero_trace]]   [None] * number)

Ответ №2:

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

Предположения

Мы предполагаем, что числа в наборе S являются различными целыми числами, большими 0. Цель состоит в том, чтобы написать функцию countSubsetSum(target, S) , которая, учитывая целое число target , возвращает целое число, равное общему числу способов суммирования target (игнорируя порядок), используя только кратные числа S .

Базовый вариант

Мы знаем, что ответ равен 0, если набор пуст или если цель меньше или равна 0:

 countSubsetSum(target, S) = 0, if target <= 0
countSubsetSum(target, S) = 0, if S is empty

Индуктивный случай

В противном случае мы проходим через каждый элемент x в S , и для каждого элемента рассмотрим два случая:

  1. Количество способов суммирования target только с использованием кратных чисел в S{x} . Здесь мы считаем решения, не включающие x .
  2. Количество способов суммирования до target - k*x (которое может быть 0 или отрицательным, в этом случае мы переходим к базовому варианту), используя только кратные числа в S{x} , для k = 1..Floor(target/x) . Здесь мы считаем решения, включающие кратные x .

Мы можем объединить оба случая следующим образом:

Количество способов суммирования target - k*x только с использованием кратных чисел в S{x} , для всех k = 0..Floor(target/x) .

Итак, мы получаем:

 countSubsetSum(target, S)
  = Sum { countSubsetSum(target - k*x, S{x}) | for all x in S, for all k from 0 .. Floor(target/x) }

или как псевдокод:

 result := 0;
foreach (x in S)
    for(k:=0; k < target/x; k  )
        result := result   countSubsetSum(target - k*x, S{x});    
return resu<

Временная сложность

Временная сложность этого алгоритма, по крайней мере, экспоненциальная. Обратите внимание, что мы не можем ожидать большего, поскольку эта задача является NP-полной, поэтому, предполагая P<>NP, не может быть алгоритма полиномиального времени.