найти оптимальный метод решения задачи

[Александр Кравченк]

Задача следующая:

Даны номер автобусного билета – шестизначное натуральное число и целое неотрицательное число N. Между некоторыми парами соседних цифр разрешается ставить знаки арифметических операций (+, -, *) так, чтобы результат полученного арифметического выражения стал равен N.
Требуется:
1) определить количество различных решений для заданного номера билета и N;
2) вывести все решения на экран.
Замечания
· Разрешается предполагать, что число различных решений не превосходит число строк на экране
· Разрешается пренебречь грамматической согласованностью ответа.
· Значение выражения вычисляется с учетом приоритета заданных арифметических операций.
Техническое требование:
· Программа должна проверять корректность ввода шестизначного числа
Пример правильной работы программы:
Введите шестизначное число 128500
Введите N 8512
12+8500=8512
Найдено 1 решений.
Введите шестизначное число 258179
Введите N 100
2*58-1*7-9=100
2*58*1-7-9=100
Найдено 2 решений.
Введите шестизначное число 663570
Введите N 100
Решение не существует.
Введите шестизначное число 1998
Некорректный ввод
Введите шестизначное число CHISLO
Некорректный ввод

Уже третий день не могу придумать адекватного алгоритма для поиска кроме перебора всех возможных вариантов. Есть идеи как можно оптимально решить эту задачу? Пишу на С++. Заранее спасибо.

[digitalis]

А тут кроме тупого полного перебора ничего и на ум не приходит. И сама формулировка задачи мутная:

Между некоторыми парами соседних цифр разрешается

- а между некоторыми другими - не разрешается ? Приоритеты операций нужно соблюдать, если применены знаки операций ? Да, из примера видно - нужно. Подряд знаки разрешаются? Например, 5*-3 ?
Задача идиотская, на мой взгляд. Тупо всовываем в цикле между цифрами + - * или <ничего> (т.е. всего 1024 варианта), парсим на предмет приоритета и считаем.

[Serge_Bliznykov]

если устроит решение на Паскале, то можете брать отсюда - https://www.programmersforum.ru/showthread.php?t=145412

[digitalis]

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

[Serge_Bliznykov]

Сообщение от digitalis

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

Это не имеет отношения к счастливым билетам...

[digitalis]

А жаль... Значит, нет шчасця не только в жизни, но и в автобусах

[Александр Кравченк]

Спасибо, но я же правильно понимаю, что это тоже перебор, просто красивее оформленный?

[Serge_Bliznykov]

Сообщение от Александр Кравченк

Спасибо, но я же правильно понимаю, что это тоже перебор, просто красивее оформленный?

однозначно - перебор. полный. без всяких украшений.