Как я могу поменяться между умножением и делением на 2 разных числа?

Question

Мне даны целые числа X, Y и Z. На каждом шаге я могу либо умножить, либо разделить на 2 или 3. Мне нужно преобразовать X в Z точно за Y шагов... или определить, что это невозможно.

Например:

X is 9,
Y is 8,
Z is 4.

9 может стать 4: 9/3/3x2x2x2x2/2/2 = 4 Как вы можете видеть, я сделал 8 операций.

Как это можно сделать в Python?

Answer 1

Прежде всего используйте описательные имена переменных, такие как start, target и steps.

Нет, не существует простого способа сделать это, но есть простые способы.

Во-первых, вам нужно найти необходимые изменения. Разбейте начало и цель на факторы 2, факторы 3 и все остальное. Если это "что-нибудь еще" не совпадает, тогда вы не сможете решить проблему вообще.

Например, посмотрите на вашу заданную проблему: переходите от 9 к 4. Разбивая каждое число:

9 = 3*3    # no 2's, no other stuff
4 = 2*2    # no 3's, no other stuff

Поскольку "другие" вещи совпадают (то есть 1), вы можете сделать переход. Вам нужно удалить 2 фактора из 3 и добавить 2 фактора из 2. Это 4 шага. Оттуда все, что вам нужно сделать, это добавить пары *3/3 или *2/2, пока у вас не будет 8 шагов.

Давайте попробуем изменить 56 на 126:

 56 = 2*2*2*7   # no 3's, other = 7
126 = 2*3*3*7   # other = 7

Чтобы сделать переход, вам нужно удалить два 2 и добавить два 3. Это четыре шага; Вы настраиваете на желаемый номер, как и раньше.

Вот твоя атака; ты можешь это кодировать?

Answer 2

Просто для удовольствия, вот грубый метод, который масштабируется ужасно - O(у ^4),

def bruteforce(x, y, z, acc="", accv=None):
    if accv == z and len(acc) == y*2:
        return acc
    if accv is None:
        accv = x
    if len(acc) == y*2:
        return
    m2 = bruteforce(x, y, z, acc+'*2', accv*2)
    m3 = bruteforce(x, y, z, acc+'*3', accv*3)
    d2 = bruteforce(x, y, z, acc+'/2', accv/2)
    d3 = bruteforce(x, y, z, acc+'/3', accv/3)
    return m2 or m3 or d2 or d3

В бою:

In [49]: exp = bruteforce(9, 8, 4)

In [50]: exp
Out[50]: '*2*2*2*2/2/2/3/3'

In [51]: eval('9'+exp)
Out[51]: 4.0

In [52]: exp = bruteforce(13, 8, 4)

In [53]: exp

In [54]: exp = bruteforce(9, 7, 2)

In [55]: exp
Out[55]: '*2*2*2/2/2/3/3'

In [56]: eval('9'+exp)
Out[56]: 2.0

Будет глючить из-за неточности с плавающей точкой...