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

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Количество скобок

Автор: 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, у нас когда-то даже конкурс был на программу, проверяющую правильность расстановки скобок... Так что в Поиск (ссылка - у меня в подписи)...