Блог

Главная - Вопросы по программированию - Учитывая список целых чисел, найдите наименьшее целое число, которое не может быть выражено как комбинация этих чисел (с , / и*).

Учитывая список целых чисел, найдите наименьшее целое число, которое не может быть выражено как комбинация этих чисел (с , / и*).

#python #math #combinatorics

Вопрос:

«Учитывая список целых чисел, найдите наименьшее целое число, которое не может быть выражено в виде комбинации этих чисел, по порядку. (с , / и * мы используем / только в том случае, если результат деления является целым числом)»

Пример:
Учитывая 1, 2 и 3, я могу выразить:

 1 = (1   2) / 3  
2 Cannot be expressed  
3 Cannot be expressed  
4 Cannot be expressed  
5 = 1 * 2   3  
6 = 1   2   3  
7 Cannot be expressed (we cannot write "1   (2*3)" because it's not in order.)

Таким образом, 2-это наименьшее число, которое не может быть выражено в виде комбинации 1, 2 и 3.

Я попытался сгенерировать все возможные комбинации, чтобы проверить первое число в диапазоне, которое не может быть выражено в виде комбинации :

 def gen_ints(nbs, s=None):
    if s is None:     # If there's no sum (first time we enter in the func)
        s = nbs[0]    # Take the first number
        nbs = nbs[1:]

    if len(nbs) == 0:  # If there's no number left
        if s >= 0:
            return [s] # Return the sum
        return []

    a = nbs[0]         # If there's still some numbers, take the first nb
    l = []
    l  = gen_ints(nbs[1:], s   a) # Recursively compute every combination with it
    l  = gen_ints(nbs[1:], s * a)
    if s % a == 0:
        l  = gen_ints(nbs[1:], s // a)
    return l # Final list of all combinations

Но сложность слишком высока (я не могу вычислить все комбинации из более чем 15 чисел).

Комментарии:

1. Попробуйте запомнить рекурсивную функцию, временная сложность должна уменьшиться до O(n^2)

2. Также сначала отсортируйте массив, а затем переходите один за другим от малого к большому

3. Это заставит вас в основном выполнять что-то похожее на рюкзак 0-1, даже если рюкзак 0-1 нужно будет вычислить для каждого элемента массива, вы можете совместно использовать таблицу dp в течение итераций….?

4. @AnuraagBarde Что следует запомнить ?

Ответ №1:

Для развлечения, вот решение грубой силы:

ПРИМЕЧАНИЕ. если вам нужно только решение для того, чтобы был один блок кода для комментариев

получает первую возможность

 from itertools import product
from functools import reduce
from operator import add, sub, mul, truediv

ops = {'/': truediv, '×': mul, ' ': add, '−': sub}

a,b,c = 1,2,3
for i in range(10):
    for op1, op2 in product(ops, repeat=2):
        f1 = ops[op1]
        f2 = ops[op2]
        if f2(f1(a,b),c) == i:
            print(f'{i:>3}: ({a}{op1}{b}){op2}{c}')
            break
        if f1(a,f2(b,c)) == i:                       # remove this block 
            print(f'{i:>3}: {a}{op1}({b}{op2}{c})')  # for only solutions
            break                                    # in order (a…b)…c
    else:
        print(f'{i:>3}: no result')

выход:

   0: (1 2)−3
  1: (1 2)/3
  2: (1−2) 3
  3: no result
  4: no result
  5: (1×2) 3
  6: (1×2)×3
  7: 1 (2×3)
  8: no result
  9: (1 2)×3

получает все возможности

 from itertools import product
from functools import reduce
from operator import add, sub, mul, truediv

ops = {'/': truediv, '×': mul, ' ': add, '−': sub}

a,b,c = 1,2,3
for i in range(10):
    print(f'{i:>3}: ', end='')
    sep = ''
    for op1, op2 in product(ops, repeat=2):
        f1 = ops[op1]
        f2 = ops[op2]
        if f2(f1(a,b),c) == i:
            print(f'{sep}({a}{op1}{b}){op2}{c}', end='')
            sep = ', '
        if f1(a,f2(b,c)) == i:
            print(f'{sep}{a}{op1}({b}{op2}{c})', end='')
            sep = ', '
    print()

выход:

   0: (1 2)−3, 1 (2−3)
  1: (1 2)/3
  2: (1−2) 3, 1−(2−3)
  3: 
  4: 
  5: (1×2) 3, 1×(2 3)
  6: (1×2)×3, 1×(2×3), (1 2) 3, 1 (2 3)
  7: 1 (2×3)
  8: 
  9: (1 2)×3
Метки: , , ,