Форум «Всё о Паскале» _ Задачи _ Количество скобок
Автор: Metrax 29.10.2006 17:06
И так , условие: в файле iekavas.in хранится последовательность скобок, например )()())( записать в файл iekavas.out сколько скобок лишних (например 3(смотрите выше)) мой код:
program iekavas; var i,j:integer; f,f1:text; ST:string; begin assign(f,'iekavas.in'); assign(f1,'iekavas.out'); reset(f); while not eof(f) do read(f,ST); i:=1; while i<>length(ST) do if (ST[i]='(') and (ST[i+1]=')') then begin delete(ST,i,2); dec(i); end else inc(i); rewrite(f1); write(f1,length(ST)); close(f1); end.
ето самое последнее мое решение, вродь лучше и ниможет быть, почему непроходит по времени????? напишите свои решегия... заранее благодарен
Автор: volvo 29.10.2006 17:28
Во-первых, как ты думаешь, что будет в строке ST после окончания вот этого цикла:
while not eof(f) do read(f,ST);
?
А во-вторых: в файле *.IN (если он текстовый) последняя строка должна быть пустая, т.е. если после введенной тобой строки не был нажат Enter, то Паскаль будет делать проблемы...
Тегами, кстати, тоже пользуйся...
Автор: Гость 30.10.2006 0:37
Цитата(volvo @ 29.10.2006 13:28)
Во-первых, как ты думаешь, что будет в строке ST после окончания вот этого цикла:
while not eof(f) do read(f,ST);
?
А во-вторых: в файле *.IN (если он текстовый) последняя строка должна быть пустая, т.е. если после введенной тобой строки не был нажат Enter, то Паскаль будет делать проблемы...
Тегами, кстати, тоже пользуйся...
По окончанию цикла в строке будет содержимое файла, если нет то в чем ошибка????? ok можно изменить на writeln(f1,length(ST)) ???????
Автор: Michael_Rybak 30.10.2006 6:45
Цитата(Metrax @ 29.10.2006 12:06)
ето самое последнее мое решение, вродь лучше и ниможет быть, почему непроходит по времени????? напишите свои решегия... заранее благодарен
Твое решение имеет квадратичную сложность. Ты все делаешь одним линейным циклом, но процедура delete работает тоже за линейное время; меняя строку (потенциально на каждой итерации), ты замедляешься до квадрата.
На самом деле тебе строку менять не надо. Суть твоего алгоритма: идем слева направо, как только нашли "()" - удаляем из строки, откатываем на 1 позицию влево, и продолжаем поиск.
То же самое можно сделать несколько по-другому. Идем слева направо. Храним счетчик количества открытых скобок, и счетчик "лишних" скобок. В начале оба равны 0. Встретив открытую скобку, увеличиваем счетчик открытых. Встретив закрытую, проверяем счетчик открытых. Если он больше нуля, уменьшаем его на 1 (нашли "()"). Если же он равен нулю, это значит, что встреченная закрывающая скобка - лишняя. Увеличиваем счетчик "лишних". Дойдя до конца строки, добавляем значение счетчика открытых скобок к счетчику "лишних" (потому что эти открытые так и не закрылись).
Т.е. я не менял идеи твоего алгоритма, но перешел от изменения строки к запоминанию промежуточных результатов. Пробуй, должно пройти.
Автор: volvo 30.10.2006 12:45
Цитата
По окончанию цикла в строке будет содержимое файла, если нет то в чем ошибка?
ВСЕГО файла? Ошибаешься... Последняя строка (группа символов, после последнего пробела/табуляции)... А если в файле будет БОЛЬШЕ одной строки?
Цитата
Т.е. я не менял идеи твоего алгоритма, но перешел от изменения строки к запоминанию промежуточных результатов. Пробуй, должно пройти.
Кстати, Metrax, у нас когда-то даже конкурс был на программу, проверяющую правильность расстановки скобок... Так что в Поиск (ссылка - у меня в подписи)...