Дан ряд 123456, нужно расставить в нем скобки и знаки +, -, * и / так, чтобы в результате получалось 100.
Я знаю 1 вариант: 
-1*2+3*(4+5*6)
Но нужно чтобы программа перебирала все возможные.
Какой алгорит перебора можно пременить?

Ну можно решить эту задачу с помощью генетических алгоритмов, хотя тут и без них неплохо...

Только в этой задаче нужно работать с другим представлением данных... (т.е. чуток преформулировать задание) В этой задаче основную комбинаторную сложность вносят скобки и хрен знает как их ставить: в одном месте может стоять 3 скобки открывающих в другом 2 закр и еще нужно следить чтобы они были парными... короче жесть. Так как по сути скобки меняют расположение вершин в дереве решений, то можно работать с этим деревом. Но можно еще проще -- дерево решений замечательно работает на стеке в префиксной форме алгебраического выражения... (или в двух стеках) 
не учитывая унарного минуса
стек1: 123456 (или 654321)
стек2: xzxzxzxzx
где x  это произвольная операция * + - /
а z это модификатор позиции т.е скобки, и принимает значения 0,1,2 (операция сразу после операции в стеке, операция после одного и с двух операндов в стеке), причем надо проверять чтобы для каждой операции в стеке оставалось два операнда. Этого можно добиться последовательным подбором при случайном переборе... 12 кидаем кубик выпало * записываем 12*=2 (сразу вычисляем) в стеке один операнд значит z может принимать значения 1 и 2, т.е мы можем добавить в стек следующее число 3 затем случайную опрацию или добавить 34 и случ операцию. 
префиксная форма 12+34+*56- /    ~   (1+2)*(3+4)/(5-6)


Унарный минус добавляет бинарную опратор к каждой цифре +-
стек1: 1у2у3у4у5у6у (или стек1: 123456 стек3: уууууу)
стек2: xzxzxzxzx

ЗЫ: Рассуждения можно не читать. Кратко: пользуйтесь префиксной формой (с этой формой проще кодировать скобки)

Это сообщение отредактировал(а) dereyly - 5.12.2007, 14:41

dereyly, что такое префиксная форма?

Мое видение префиксной формы
Матчасть

Строим возможные деревья вычислений (их будет немного) в польской нотации и начинаем подставлять в узлы и ветви все подряд. В простейшем случае (не допускается решение типа 123-4!-5+6 ) операндов - 6, вариантов мат. действий - 5, вариантов перебрать (для каждого дерева) - 6!*5^5... развернуть же подходящее дерево обратно в выражение тоже не проблема.

дерево теоретически понял, а как это на С++ написать?