@keddad
Ученик

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

Даны N целых чисел, задача - расставить между ними знаки + и - для получения числа S с сохранением исходной последовательности чисел в выражении, или доказательства невозможности получения такого S. Например, если числа - [7, 3, 9] и S = 13, то ответ, удовлетворяющий задаче = 7-3+9=13

Как можно реализовать такой алгоритм?

  • Если единственное решение - тупой перебор, то как сделать премутацию для получения всех возможных вариантов расстановки знаков?
  • Если есть более эффективное решение (умный перебор, или что то вкуснее), то как его реализовать?
  • Как выглядел бы алгоритм без сохранения исходной последовательности чисел?
  • Вопрос задан
  • 129 просмотров
Решения вопроса 1
Полным перебором можно считать каждый знак битом: 0 это плюс, 1 минус. Получается, надо перебрать все числа от 0 до 2^(n-1) и их двоичная запись кодирует знаки.

Для оптимизации можно сначала проверить некоотрые крайние условия:
  • например, «все плюсы» должны быть >= S. Чтобы сразу отсечь проверку вариантов получения 1E9 из всего 1E6 единиц. Эта же проверка имеет смысл в процессе перебора, для оценки, дотянутся ли оставшиеся цифры до оставшейся до S суммы
  • Проверить четность - из четного числа нечетных не получить нечетное.
  • Подумать, что делать с одинаковыми числами, как-то отсечь их зеркальные комбинации.
  • Ещё подумать
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Если у вас только два знака и ставиться они могут только между числами, то просто генерируете все числа от 0 до 2N-1 и принимаете, например, бит 0 за минус, а бит 1 за плюс.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
CSort Барнаул
от 40 000 до 90 000 руб.
SegmentStream Москва
от 250 000 до 350 000 руб.
от 120 000 руб.