Найти минимальное количество операций, необходимых для вычисления числа, используя указанный диапазон чисел

Question

Позвольте мне начать с примера - У меня есть диапазон чисел от 1 до 9. И скажем, целевое число, которое я хочу, это 29. В этом случае минимальное количество требуемых операций будет (9 * 3) +2 = 2 операции. Аналогично для 18 минимальное количество операций равно 1 (9 * 2 = 18). Я могу использовать любой из 4 арифметических операторов - +, -, / и *.

Как программно определить минимальное количество требуемых операций? Заранее благодарим за любую предоставленную помощь.

уточнение: только целые числа, десятичные дроби не допускаются в середине расчета. то есть следующее недопустимо (из комментариев ниже): (( 9/2 ) + 1) * 4 == 22 * ​​1008 * Я должен признать, что я не думал об этом полностью, но для моей цели не имеет значения, появляются ли десятичные числа в середине расчета. ((9/2) + 1) * 4 == 22 действительно. Извините за путаницу.

Answer 1

Для особого случая, когда установлено Y = [1..9] и n> 0:

• n <= 9: 0 операций </li>
• n <= 18: 1операция (+) </li>
• в противном случае: удалить любой делитель, найденный в Y. Если этого недостаточно, выполнить рекурсию для остатка для всех смещений -9 .. +9.Смещение 0 можно пропустить, поскольку оно уже было опробовано.

Обратите внимание, что в этом случае деление не требуется.Для других Y это не так.

Этот алгоритм является экспоненциальным в log (n).Точный анализ - это работа для кого-то с большим знанием алгебры, чем я.

Для большей скорости добавьте сокращение, чтобы исключить поиск большего числа.

Пример кода:

def findop(n, maxlen=9999):
    # Return a short postfix list of numbers and operations

    # Simple solution to small numbers
    if n<=9: return [n]
    if n<=18: return [9,n-9,'+']

    # Find direct multiply
    x = divlist(n)
    if len(x) > 1:
        mults = len(x)-1
        x[-1:] = findop(x[-1], maxlen-2*mults)
        x.extend(['*'] * mults)
        return x

    shortest = 0

    for o in range(1,10) + range(-1,-10,-1):
        x = divlist(n-o)
        if len(x) == 1: continue
        mults = len(x)-1

        # We spent len(divlist) + mults + 2 fields for offset. 
        # The last number is expanded by the recursion, so it doesn't count. 
        recursion_maxlen = maxlen - len(x) - mults - 2 + 1

        if recursion_maxlen < 1: continue
        x[-1:] = findop(x[-1], recursion_maxlen)
        x.extend(['*'] * mults)
        if o > 0:
            x.extend([o, '+'])
        else:
            x.extend([-o, '-'])
        if shortest == 0 or len(x) < shortest:
            shortest = len(x)
            maxlen = shortest - 1
            solution = x[:]

    if shortest == 0:
        # Fake solution, it will be discarded
        return '#' * (maxlen+1)
    return solution

def divlist(n):
    l = []
    for d in range(9,1,-1):
        while n%d == 0:
            l.append(d)
            n = n/d
    if n>1: l.append(n)
    return l

Answer 2

Действительно крутой вопрос:)

Обратите внимание, что вы можете начать с конца!Из вашего примера (9 * 3) +2 = 29 эквивалентно высказыванию (29-2) / 3 = 9.Таким образом, мы можем избежать двойной петли в ответе киборга.Это предполагает следующий алгоритм для набора Y и результата r:

nextleaves = {r}
nops = 0
while(true):
   nops = nops+1
   leaves = nextleaves
   nextleaves = {}
   for leaf in leaves:
      for y in Y:
         if (leaf+y) or (leaf-y) or (leaf*y) or (leaf/y) is in X:
             return(nops)
         else:
             add (leaf+y) and (leaf-y) and (leaf*y) and (leaf/y) to nextleaves

. Это основная идея, производительность, безусловно, можно улучшить, например, избегая «обратных дорожек», таких как * 1008.* или r*a*b/a.

Answer 3

Основная идея состоит в том, чтобы протестировать все возможности с k операциями, для k начиная с 0.Представьте, что вы создаете дерево высотой k, которое ветвится для каждой возможной новой операции с операндом (4 * 9 ветвей на уровень).Вам нужно пройти и оценить листьев дерева для каждого k перед тем, как перейти к следующему k.

Я не проверял этот псевдокод:

for every k from 0 to infinity
  for every n from 1 to 9
    if compute(n,0,k):
      return k


boolean compute(n,j,k):
  if (j == k):
    return (n == target)
  else:
    for each operator in {+,-,*,/}:
       for every i from 1 to 9:
         if compute((n operator i),j+1,k):
           return true
    return false

Он не учитывает приоритет арифметических операторов и фигурные скобки, которые потребуют некоторой переделки.

Answer 4

Я думаю, что моя идея похожа на идею Peer Sommerlund:

Для больших чисел вы продвигаетесь быстро, умножая их на большие шифры.

Является ли Y = 29 простым?Если нет, разделите его на максимальный делитель (от 2 до 9).В противном случае вы можете вычесть число, чтобы получить делимое число.27 хорошо, так как он делится на 9, поэтому

(29-2)/9=3 => 
3*9+2 = 29 

Так что, может быть, я не думал об этом до конца: Поиск следующего делимого на 9 число ниже Y. Если вы недостигните числа, которое является цифрой, повторите.

Формула - обратные шаги.

(попробую для некоторых чисел. :))

Я пробовал с 2551, то есть

echo $((((3*9+4)*9+4)*9+4))

Но я не проверял каждый промежуточный результатбудь то премьер.Но

echo $((8*8*8*5-9)) 

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