Почему рекурсия неверно отрабатывает?

Question

[Полина Мезенина]

Задача

Ириска весит X грамм, мандарин – Y грамм, пряник – Z грамм.

Требуется написать программу, которая определит, сколько различных вариантов подарков весом ровно W грамм может сделать Дед Мороз.

Входные данные
В единственной строке входного файла INPUT.TXT содержится четыре целых числа X, Y, Z и W (1 ≤ X, Y, Z ≤ 100, 1 ≤ W ≤ 1000).

Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно целое число – количество вариантов подарков.

with open('data317.txt') as f:
     a, h, z, n = [int(x) for x in next(f).split()] # read first line

print(a, h, z, n)

edge = max(a, h, z)
zero = 0
w = open("output.txt", "w")
if n != 0:
    def f(n, edge):
        #print("f", n)

        if n == 0: return 1
        if n < 0:
            return 0

        count = 0

        if edge >= a:
            count = f(n - a, a)
        if edge >= h:
            count = count + f(n - h, h)
        if edge >= z:
            count = count + f(n - z, z)

        return count

    print(f(n, edge))

    w.write(str(f(n, edge)))
else:
    w.write(str(0))
w.close()

Не проходит тестирование, при этом вроде бы определяет верно

Источник: https://acmp.ru/index.asp?main=task&id_task=317

Answer 1

[Wataru]

Ваша программа ломается, если X=Y, например.
Чтобы ее исправить, вместо веса edge и сравнения его со стоимостью товара, передавайте в функцию число от 1 до 3. Если число <=1, то можно брать x и передавать 1. Если <=2 - то можно брать y и передавать 2, и т.д.

Comments

[Полина Мезенина]

Не очень поняла идею.
Беру edge, чтобы забанить повторяющиеся комбинации. Идея в том, что когда в последовательности операций (например: -10 -15 -25) мы сохраняем принцип, что первое число (в нашем случае 10) равно или больше последующего, то мы выбираем одну комбинацию и отсеиваем дублирующие (например -15 -10 -25)

И вообще при числах 2 2 3 4 отработала верно. Как вы поняли, что при X=Y, ломается?

[Wataru]

Проблема в том, что если у вас цены подарков -10, -10 и -15, то, независимо от того, какую из -10 вы взяли, вы потом опять можете взять любую из двух. Согласитесь: принципиально другое поведение, чем когда все числа разные. Идея же в том, что как только вы взяли вторую -10, первую вы уже брать опять не должны. Вы в последовательности из нескольких -10 в ответе будете считать все возможные перестановки двух типов подарков. Что в этой задаче не надо.

Вот запустите на тесте x=2 y=2 z=1000 w=10.

Правильный ответ - 11 (x может быть взято от 0 до 10 раз, остальное - y). Сколько выдает ваша программа? 1024 небось?

> И вообще при числах 2 2 3 4 отработала верно.

Правильный ответ 3 (2 раза первый подарок; 2 раза второй подарок; первый+второй). Ваша же программа, если я не напутал, выдает 4.

Answer 2

[Андрей]

Сила гугла

with open("input.txt", "r") as file:
	x, y, z, w = [int(x) for x in next(file).split()]

count = 0
for i in range(0, w // x + 1):
    rest = w - x * i
    for j in range(0 , rest // y + 1):
        if (rest - y * j) % z == 0:
            count += 1
  
with open("output.txt", "w") as file:
	file.write(str(count))

Comments

[Полина Мезенина]

это же циклическое решение, а не рекурсивное :)