DjangoBB LoFi version

Начало » Центр помощи » Задача на рекурсию

fiyehes639

Янв. 26, 2021 15:04:02

Приветствую, господа! У меня возникла проблема с решением задачи, надеюсь на вашу помощь.

"У исполнителя Калькулятор есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Сколько разных целых чисел на отрезке от 34 до 59 может быть получено из числа 1 с помощью программ, состоящих из 6 команд?"

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

Код программы:

 for i in range(34,59):
    def func(start,i):
        if i < start: return 0
        if i == start: return 1
        K = func(start,i-1)
        K += func(start,i-2)
        if i % 2 == 0:
            K += func(start,i//2)
        return K
    print(func(1,i)

Заранее спасибо!

py.user.next

Янв. 26, 2021 19:34:37

Изучай классические задачи. Про Ханойскую башню и про прыгающего кузнечика. Они решаются примерно одинаково. Переходишь в конец как будто решённой задачи и от конца двигаешься к началу. Тогда начнёшь видеть алгоритм.

  
>>> def f(x, a, b, n, xset, line):
...     if n == 0:
...         if a <= x <= b and x not in xset:
...             print(line, '->', x)
...             xset.add(x)
...             return 1
...         else:
...             return 0
...     return (
...         f(x + 1, a, b, n - 1, xset, line + '+1')
...         + f(x + 2, a, b, n - 1, xset, line + '+2')
...         + f(x * 2, a, b, n - 1, xset, line + '*2')
...     )
... 
>>> out = f(1, 34, 59, 6, set(), '1')
1+1+1+2*2*2*2 -> 40
1+1+1*2*2*2*2 -> 48
1+1+2*2+1*2*2 -> 36
1+1+2*2*2+1*2 -> 34
1+2+2+2*2*2*2 -> 56
1+2+2*2+1*2*2 -> 44
1+2+2*2*2+1*2 -> 42
1+2+2*2*2*2+1 -> 41
1+2*2*2+1*2*2 -> 52
1+2*2*2*2+1*2 -> 50
1+2*2*2*2*2+1 -> 49
>>> out
11
>>>

tags: dynamic

jegodo6878

Янв. 26, 2021 21:17:38

py.user.next
Изучай классические задачи. Про Ханойскую башню и про прыгающего кузнечика. Они решаются примерно одинаково. Переходишь в конец как будто решённой задачи и от конца двигаешься к началу. Тогда начнёшь видеть алгоритм.

Что можете сказать про такое решение? К слову, оно верное.

 # 's' - начало, 'x' - цель, 'l' - кол-во команд, 'count' - кол-во чисел
def func(s,x,l):
    if x < s or l < 0: return 0
    if x == s: return 1
    K = func(s,x-1,l-1)
    K += func(s,x-2,l-1)
    if x % 2 == 0:
        K += func(s,x//2,l-1)
    return K
count = 0
for i in range(34,60):
    if func(1,i,6) != 0: count += 1
    
print(count)

fiyehes639

Янв. 26, 2021 21:31:52

Спасибо вам за помощь! Но как же быть, если в условии не дан промежуток? То есть, просто нужно найти количество разных чисел, которые можно получить из a при b команд в программе? Пробовал делать промежуток очень большим (от 1 до 100000), так как знал, что дальше чисел не будет. По сути, все должно работать также, но ответ оказывался неверным, при этом очень близким к верному.

py.user.next

Янв. 27, 2021 02:28:43

jegodo6878
Что можете сказать про такое решение? К слову, оно верное.

Оно верное, на первый взгляд (верность программы доказывается математически обычно), но я запустил его от 1 до 100000 за 6 операций с 1 и оно просто повисло. А моё выдаёт сразу ответ 40. То есть всё-таки разница есть.

fiyehes639
То есть, просто нужно найти количество разных чисел, которые можно получить из a при b команд в программе?

  
>>> def f(x, n, xset, line):
...     if n == 0:
...         if x not in xset:
...             print(line, '->', x)
...             xset.add(x)
...             return 1
...         else:
...             return 0
...     return (
...         f(x + 1, n - 1, xset, line + '+1')
...         + f(x + 2, n - 1, xset, line + '+2')
...         + f(x * 2, n - 1, xset, line + '*2')
...     )
... 
>>> out = f(1, 6, set(), '1')
1+1+1+1+1+1+1 -> 7
1+1+1+1+1+1+2 -> 8
1+1+1+1+1+1*2 -> 12
1+1+1+1+1+2+2 -> 9
1+1+1+1+1+2*2 -> 14
1+1+1+1+1*2+1 -> 11
1+1+1+1+1*2*2 -> 20
1+1+1+1+2+2+2 -> 10
1+1+1+1+2+2*2 -> 16
1+1+1+1+2*2+1 -> 13
1+1+1+1+2*2*2 -> 24
1+1+1+1*2+1*2 -> 18
1+1+1+1*2*2+1 -> 17
1+1+1+1*2*2*2 -> 32
1+1+1+2+2*2+1 -> 15
1+1+1+2+2*2*2 -> 28
1+1+1+2*2+1*2 -> 22
1+1+1+2*2*2+1 -> 21
1+1+1+2*2*2*2 -> 40
1+1+1*2*2+1*2 -> 26
1+1+1*2*2*2+1 -> 25
1+1+1*2*2*2*2 -> 48
1+1+2*2+1*2+1 -> 19
1+1+2*2+1*2*2 -> 36
1+1+2*2*2+1*2 -> 34
1+1+2*2*2*2+1 -> 33
1+1+2*2*2*2*2 -> 64
1+2+2+2*2+1*2 -> 30
1+2+2+2*2*2+1 -> 29
1+2+2+2*2*2*2 -> 56
1+2+2*2+1*2+1 -> 23
1+2+2*2+1*2*2 -> 44
1+2+2*2*2+1*2 -> 42
1+2+2*2*2*2+1 -> 41
1+2+2*2*2*2*2 -> 80
1+2*2*2+1*2+1 -> 27
1+2*2*2+1*2*2 -> 52
1+2*2*2*2+1*2 -> 50
1+2*2*2*2*2+1 -> 49
1+2*2*2*2*2*2 -> 96
>>> out
40
>>>