23.06 Количество программ из A в B где траектория вычислений N команда

Решение 1 (Рекурсия)

def f(st, fn, count, end_count):
    if st == fn and count == end_count:
        return 1
    if st < fn or count > end_count: # если счетчик перешел максимальное
# значение, то прекращаем считать
        return 0
    x = f(st // 2, fn, count + 1, end_count) * (st % 2 == 0)
    y = f(st - 3, fn, count + 1, end_count)
    z = f(st - 1, fn, count + 1, end_count)
    return x + y + z
print(f(33, 12, 0, 9))

Решение 2 (Динамика)

a = [33]
for i in range(9):
    n = len(a)
    for j in range(n):
        k = a.pop(0)
        if k > 12:
            a.append((k // 2) * (k % 2 == 0))
            a.append(k - 3)
            a.append(k - 1)
print(a.count(12))

Решение 1

def f(st, fn, cmd, a):
    if st in a or cmd > 25:
        return 0
    if st == fn and cmd == 25:
        return 1
    a.add(st)
    x, y, z = 0, 0, 0
    if st % 2 == 0:
        x = f(st // 2, fn, cmd + 1, a.copy())
    y = f(st + 1, fn, cmd + 1, a.copy())
    if st % 3 == 0:
        z = f(st + st // 3, fn, cmd + 1, a.copy())
    return x + y + z

Решение 2

В соавторстве с марафонцем

Примечание: при добавлении в массив b элементов массива a используется символ *, чтобы добавить в массив именно элементы массива а, а не создать дополнительную вложенность массивов. Например: есть массив a = [1, 2, 3]. Если выполнить операцию b.append([a, 4]), то массив b = [[[1, 2, 3], 4]]. Если выполнить b.append([*a, 4]), то массив b = [[1, 2, 3, 4]].

paths = [[1]]
for i in range(25):
    new_paths = []

    for path in paths:
        x = path[-1]
        if x % 2 == 0:
            if x // 2 not in path:
                new_paths.append([*path, x//2])
        if x % 3 == 0:
            if x + x // 3 not in path:
                new_paths.append([*path, x + x//3])
        if x + 1 not in path:
            new_paths.append([*path, x+1])
    paths = new_paths.copy()

ans = 0
k = []
for path in paths:
    if path[-1] == 60:
        k.append(path)
        ans += 1
print(ans)

 

Решение 1 (Рекурсия)

from functools import lru_cache  # программа будет долго считать, если
# не хранить результаты в кэше
@lru_cache(None)
def f(st, fn, count, end_count):
    if st == fn and count == end_count:
        return 1
    if count > end_count:
        return 0
    x = f(st // 2, fn, count + 1, end_count) * (st % 2 == 0)
    y = f(st + 1, fn, count + 1, end_count)
    z = f(st + st // 3, fn, count + 1, end_count) * (st % 3 == 0)
    return x + y + z


print(f(1, 60, 0, 25))

Решение 2 (Динамика)

ans = []
ans.append(1)
for operations in range(25):
    can_get = []
    for i in ans:
        if i % 2 == 0:
            can_get.append(i // 2)
        can_get.append(i + 1)
        if i % 3 == 0:
            can_get.append(i + i // 3)
    ans = can_get
print(ans.count(60))

def f(a,c):#В данной функции у нас будет два параметра: а - изменяемое число, с - количество команд.
    #При каждом изменении числа а мы будем увеличивать c
    if c == 7:#Если количество команд равняется 7,то мы возвращаем 1 или 0 в зависимости от того,равна ли а 27 или нет
        return a == 27
    return f(a+1,c+1)+f(a+4,c+1)+f(a*2,c+1)
print(f(3,0))

a = [1]
for i in range(10):
    n = len(a)
    for j in range(n):
        l = a.pop(0)
        a.append(l + 4)
        a.append(l + 7)
        a.append(l // 2)
print(a.count(1))

a = [245]
for i in range(16):
    a = list(set(a))
    n = len(a)
    for j in range(len(a)):
        l = a.pop(0)
        a.append(l - 1)
        a.append(l * (-2))
a = list(set(a))
print(len([j for j in a if j >= 0]))

Решение 1:

a = [[8, ’0’]]
for i in range(13):
    n = len(a)
    for j in range(n):
        l = a.pop(0)
        last_command = l[1]
        if last_command == ’0’:
            a.append([l[0] + 2, ’1’])
            a.append([l[0] + 5, ’2’])
            a.append([l[0] * 2, ’3’])
        elif last_command == ’1’:
            a.append([l[0] + 5, ’2’])
            a.append([l[0] * 2, ’3’])
        elif last_command == ’2’:
            a.append([l[0] + 2, ’1’])
            a.append([l[0] * 2, ’3’])
        else:
            a.append([l[0] + 2, ’1’])
            a.append([l[0] + 5, ’2’])
arr = set()
for i in range(len(a)):
    arr.add(a[i][0])
print(len(arr))

Решение 2:

s = set()
def f(a, k=0, r=0):
    if k == 13:
        s.add(a)
        return
    if r != 1:
        f(a + 2, k + 1, 1)
    if r != 2:
        f(a + 5, k + 1, 2)
    if r != 3:
        f(a * 2, k + 1, 3)

f(8)

print(len(s))

a = [123]
for i in range(10):
    a = list(set(a))
    n = len(a)
    for j in range(n):
        l = a.pop(0)
        a.append(l - 4)
        a.append(l * (-1))
a = set(a)
print(len([j for j in a if j >= 0]))

a = [[1, ’0’]]
for i in range(10):
    n = len(a)
    for j in range(n):
        l = a.pop(0)
        # Список доступных команд
        command = [[l[0] + 1, ’1’], [l[0] + 2, ’2’], [l[0] + 3, ’3’],
                   [l[0] * 2, ’4’], [l[0] * 3, ’5’], [l[0] * 4, ’6’]]
        # Если первый ход - доступно все
        if l[1] == ’0’:
            for k in range(6):
                a.append(command[k])
        # Анализируем края (по одной команде можем только)
        elif l[1] == ’1’:
            a.append(command[1])
        elif l[1] == ’6’:
            a.append(command[4])
        # Некрайние случаи
        else:
            # Если индекс на 1 меньше, и еще -1 от команды (влево)
            a.append(command[int(l[1]) - 2])
            # Индекс на 1 меньше, и еще +1 от команды (вправо)
            a.append(command[int(l[1])])
a = set([j[0] for j in a])
print(len(a))

# Альтернативное решение:
s = set()
def f(a, h, c):
    if h == 10:
        s.add(a)
        return
    if c == 0:
        f(a + 1, h + 1, 1)
        f(a + 2, h + 1, 2)
        f(a + 3, h + 1, 3)
        f(a * 2, h + 1, 4)
        f(a * 3, h + 1, 5)
        f(a * 4, h + 1, 6)
                                                                                                     
                                                                                                     
    elif c == 1:
        f(a + 2, h + 1, 2)
    elif c == 2:
        f(a + 1, h + 1, 1)
        f(a + 3, h + 1, 3)
    elif c == 3:
        f(a + 2, h + 1, 2)
        f(a * 2, h + 1, 4)
    elif c == 4:
        f(a + 3, h + 1, 3)
        f(a * 3, h + 1, 5)
    elif c == 5:
        f(a * 2, h + 1, 4)
        f(a * 4, h + 1, 6)
    elif c == 6:
        f(a * 3, h + 1, 5)


f(1, 0, 0)
print(len(s))

a = set() # Множество для ответа

def f(n, c):
    # Важно! Условия должны быть раздельными,
    # чтобы сначала проверялось только кол-во команд,
    # а затем знак числа.
    # Если сделать вместе — программа уйдёт в рекурсию из-за отрицательных чисел,
    # которые получились при c = 8
    if c == 8:
        if n >= 0:
            a.add(n)
    else:
        f(n+3, c+1)
        f(n*(-1), c+1)

f(82, 0)
print(a)

a = set() # Множество для ответа

# n — текущее число, c — кол-во совершённых команд
def f(n, c):
    if c == 13:
        a.add(n)
    else:
        f(n+1, c+1)
        f(n*3, c+1)
        f(n*2, c+1)

f(7, 0)
print(len(a))

a = set() # Множество для ответа

# n — текущее число, c — кол-во совершённых команд
def f(n, c):
    if c == 8:
        a.add(n)
    else:
        f(n+2, c+1)
        f(n*2, c+1)

f(3, 0)
print(len(a))

a = set() # Множество для ответа

# n — текущее число, c — кол-во совершённых команд
def f(n, c):
    if c == 6:
        a.add(n)
    else:
        f(n+1, c+1)
        f(n+10, c+1)
        f(n*3, c+1)

f(8, 0)
print(len(a))

def f(a, b, c):
    if c == 10:
        return a == b
    if c < 10:
        return f(a+4, b, c+1) + f(a+7, b, c+1) + + f(a//2, b, c+1)
print(f(1, 1, 0))