Арифметические действия с цифрами числа

[rwss gle]

Дан автобусный билет с номером, состоящим из N цифр. Расставить между цифрами знаки арифметических операций (+;-;*;/) и скобки таким образом, чтобы значение полученного выражения было равно 100. Можно образовывать многозначные числка из стоящих рядов цифр.

Как нужно сделать перебор операций, и для конкретного набора операций сделать еще перебор по порядку вычисления?
Помогите, плиз!

[evg_m]

"избыточная генерация"

ZZZZ....ZZ (исходное число)
X комбинация из N скобок(любых)
_ пустой оператор или "склеивание" цифр
* один из операторов +-/*_
построение комбинации(перебор всех)
X_ZX*XZX*XZX*X....XZX*XZX_
проверка на ДОПУСТИМОСТЬ(правильность).
проверка на требования (=100).

Рекурсивный перебор
(ABCZ...ZZ)

(A) + (bczz..zz)
(A) - (bczz..zz)
(A) * (bczz..zz)
(A) / (bczz..zz)
(AB) + (czz..zz)
(AB) - (czz..zz)
(AB) * (czz..zz)
(AB) / (czz..zz)
(ABC) + (zz..zz)
....

[rwss gle]

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

"избыточная генерация"

ZZZZ....ZZ (исходное число)
X комбинация из N скобок(любых)
_ пустой оператор или "склеивание" цифр
* один из операторов +-/*_
построение комбинации(перебор всех)
X_ZX*XZX*XZX*X....XZX*XZX_
проверка на ДОПУСТИМОСТЬ(правильность).
проверка на требования (=100).

Рекурсивный перебор
(ABCZ...ZZ)

(A) + (bczz..zz)
(A) - (bczz..zz)
(A) * (bczz..zz)
(A) / (bczz..zz)
(AB) + (czz..zz)
(AB) - (czz..zz)
(AB) * (czz..zz)
(AB) / (czz..zz)
(ABC) + (zz..zz)
....

Можете написать краткую подобную программу?

[BoozZzilla]

evg_m
Мне тоже чрезвычайно интересно, не могли бы вы набросать хотя бы вчерне этот перебор через рекурсию.

[rwss gle]

Да и я хочу понять, как пишется на программе

[Serge_Bliznykov]

ох, мне кажется, что я решил данную задачу.
но, скажу честно, решение совершенно неожидано для меня оказалось достаточно сложным!
я даже больше скажу - я не уверен, что моё решение находит ВСЕ возможные варианты.
Ещё из особенностей - моё решение находит варианты в постфиксной форме (она ещё известна, как "обратная польская запись" выражения). В принципе совсем несложно перевести из постфиксной формы в привычную инфиксную. Но я не стал этим заниматься (кому надо, тот легко это сделает сам).

и последнее.
ядро перебора у меня следующее:

const
  Oper : array[1..4] of string[1] = ('+', '-', '*', '/' );


procedure NextVariant(Left : string; s : string; Right : string);
var  i, k, N : integer;
  L, R, rr : string;
begin
  WriteLn(Left+' ', s, ' '+Right);

  N := Length(s);
  for i:=1 to N-1 do begin
      L := Copy(s,1,i);
      R := Copy(s,i+1,N-i);
      for k:=1 to 4 do
        NextVariant(Left,L,R+' '+Oper[k]+' '+Right);
  end;
end;

begin
  WriteLn('---');
  NextVariant('','ABCDE','');
  readln;
end.

а полностью (без перевода постфиксной формы в инфиксную!) готовая программа во вложении.

--------------- Digits Solver v1.0 (c) 2011 by Serge Bliznykov ---
Введите исходное число:
12345
Введите, какое значение нужно получить (0 - выдавать все варианты) :
100
 1 23 + 4 - 5 *    =      100
 1 2 * 3 + 4 * 5 *    =      100
Подбор завершён.

[Золушка]

Serge_Bliznykov, спасибо вам большое!

[Serge_Bliznykov]

Золушка, а вот и не за что!
К сожалению, мои опасения оправдались - код перебора работает правильно, но НЕ ВСЕ ВОЗМОЖНЫЕ операции, которые могут быть получены с помощью круглых скобок, получаются в результате моего перебора...

например,
для числа 123456 мой вышеприведённый код не найдёт решения...
т.к. решение такое (в инфиксной и в обратной польской записи):

  (1+(((2+3)+4)*(5+6))) = 100
  1 2 3 + 4 + 5 6 + * + = 100

я завтра постараюсь выложить дополненное решение...

[Serge_Bliznykov]

ну вот, как и обещал - новый переборщик вариантов.
Теперь вроде бы все возможные варианты расстановки скобок и знаков охвачены.

Результат (как и сам перебор) выдаётся в форме обратной польской записи.

для 123456 и числа 100 программа выдаёт следующие ответы:

 1 2   3 /+ 4   56 +* =      100
 1 2   3 + 4 + 5   6 +*+ =      100
 1 2   3   4 ++ 5   6 +*+ =      100
Подбор завершён.

[Galtran]

Доброго всем вечера!

Сергей, а вас не затруднит в 2-3 словах описать алгоритм, который использовался при написании программки? Паскаль в школе был - туго вспоминается((

Насколько я понял, помимо всех возможных перестановок арифметических действий, учитываются и перестановки порядка выполнения этих самых действий.. Если вас не затруднит, на псевдо-языке опишите алгоритм?