Задать вопрос
@keddad
Ученик
алгоритмы

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

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

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

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

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

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

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
С developer (алгоритмист)
СберТех • Москва
от 350 000 ₽
Бэкенд программист
Grade Factor • Москва
от 80 000 ₽
С++ developer
TQB - хай-тек рекрутмент по-хардкору • Москва
от 300 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Скопировать верстку, посадить на функционал
20 апр. 2024, в 12:01
20000 руб./за проект
Разработать сайт-визитку на Wordpress
20 апр. 2024, в 11:52
5000 руб./за проект
Написать программу иммитирующую поведение человека для выбора услуг
20 апр. 2024, в 11:21
1000 руб./за проект
Ещё заказы