Версия для печати темы

Автор: RathaR 18.07.2009 17:47

Вот собственно задача, вызвала затруднения...
Условие:
Археологи проводили розкопки древнего города неизвестной нам африканской цывилизации. Во время розкопок им удалось найти листы неизвестного материала с таинственными символами на них. После длительных изучений ученые решили, что эти надписи на самом деле могли быть обычными числовыми равенствами. Это доказывало б то, что население этого города уже имело представление о математике. Ученые поняли, что означают найденые символы, и перевели эти равенства на обычный язык - язык цыфр, скобок, арифметических действий и равенства. Кроме того ученые узнали, что эти люди знали только три арифметических операции: сложение, вычитание и умножение.Также они никогда не использовали "унарный минус": вместо "-2" они писали "0-2". Было доказано, что эти древние люди не наделяли операции разными приоритетами, а просто высчитывали выражения (если в них не было скобок) слева на право: например, 4+7*2 у них ровнялось 22, а не 18.Арифметическим операциям эти люди придавали магического значения и наносили их специальными цветными чернилами, которые как оказалось, были нестойкими, и со временем исчезли. Поэтому вместо знаков действий на найденых листах были пропуски. Если вся вышеописаная теория верна, то вместо пропусков можна поставить знаки действий ( +,-,*), так, чтобы равенство стало правельным. Например если был найден лист с записью:"46=6 3 (7 2) 1", то возможна следующая розтановка знаков"46=6+3*(7-2)+1" (помните про порядок вычисления выражений!). В тоже время если подавалась запись "10=4 4", то написавшый её явно не имел в ввиду числовоё равенство.
Задание: Написать программу, которая найдёт необходимую розтановку знаков, или укажет что подобная розтановка не существует.
Входные данне: Входящий текстовый файл содержит в первой строчке натуральное число, которое не превышает 2^30, знак равенства ы последовательность натуральных чисел (не больше 10), произведение которых не превышает 2^30. Некоторые групы чисел (одна или больше) могут быть взяты в скобки. Длинна ряда не превышает 80 символов. Между двумя соседними симолами не розделёнными скобками всегда будет хоть один пропуск.
Выходной файл содержет полученое равенство, или "-1" если составить его невозможно.

Фантазия с которой составлено условие заслуживает уважения

По поводу решения у меня только одна мысль, не знаю правильна ли: попробовать использовать перебор с отходом назад, начиная со знака равенства подставляем по очереди в пропуски "+","-", и"*", и считаем до тех пор пока не получится нужное значение.... но вот это реализовать неполучаеться, и вообще, верна ли идея?

Автор: volvo 18.07.2009 18:58

Чему ж тут не получаться? Смотри:

const
  signs: array[1 .. 3] of char = ('+', '-', '*');

procedure proc(s: string);
var i, p: integer;
begin
  p := pos(' ', s);
  if p = 0 then begin
    if check(s) then writeln(s); { <--- тут можно сделать какой-нибудь счетчик }
  end
  else begin
    for i := 1 to 3 do begin
      s[p] := signs[i];
      proc(s);
    end;
  end;
end;

begin
  proc('46=6 3 (7 2) 1');
end.

Функцию Check напишешь самостоятельно. Она должна считать значение выражения ПОСЛЕ знака равенства, и сравнивать его со значением, записанным ДО знака равенства. Если значения совпадают - True, если нет - False...

Хотя, нерекурсивное решение может быть побыстрее. У тебя ограничения есть какие-нибудь на скорость?

Автор: RathaR 18.07.2009 19:38

нет, на время ограничений нету...