@keddad
Ученик

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

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

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

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

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

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

Войти через центр авторизации
Похожие вопросы