IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Количество скобок
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Мужской
Реальное имя: Artem

Репутация: -  0  +


И так , условие: в файле 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 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Во-первых, как ты думаешь, что будет в строке ST после окончания вот этого цикла:
while not eof(f) do
read(f,ST);
?

А во-вторых: в файле *.IN (если он текстовый) последняя строка должна быть пустая, т.е. если после введенной тобой строки не был нажат Enter, то Паскаль будет делать проблемы...

Тегами, кстати, тоже пользуйся...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Цитата(volvo @ 29.10.2006 13:28) *

Во-первых, как ты думаешь, что будет в строке ST после окончания вот этого цикла:
while not eof(f) do
read(f,ST);
?

А во-вторых: в файле *.IN (если он текстовый) последняя строка должна быть пустая, т.е. если после введенной тобой строки не был нажат Enter, то Паскаль будет делать проблемы...

Тегами, кстати, тоже пользуйся...

По окончанию цикла в строке будет содержимое файла, если нет то в чем ошибка????? ok можно изменить на writeln(f1,length(ST)) ???????
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(Metrax @ 29.10.2006 12:06) *

ето самое последнее мое решение, вродь лучше и ниможет быть, почему непроходит по времени????? напишите свои решегия... заранее благодарен


Твое решение имеет квадратичную сложность. Ты все делаешь одним линейным циклом, но процедура delete работает тоже за линейное время; меняя строку (потенциально на каждой итерации), ты замедляешься до квадрата.

На самом деле тебе строку менять не надо. Суть твоего алгоритма: идем слева направо, как только нашли "()" - удаляем из строки, откатываем на 1 позицию влево, и продолжаем поиск.

То же самое можно сделать несколько по-другому. Идем слева направо. Храним счетчик количества открытых скобок, и счетчик "лишних" скобок. В начале оба равны 0. Встретив открытую скобку, увеличиваем счетчик открытых. Встретив закрытую, проверяем счетчик открытых. Если он больше нуля, уменьшаем его на 1 (нашли "()"). Если же он равен нулю, это значит, что встреченная закрывающая скобка - лишняя. Увеличиваем счетчик "лишних". Дойдя до конца строки, добавляем значение счетчика открытых скобок к счетчику "лишних" (потому что эти открытые так и не закрылись).

Т.е. я не менял идеи твоего алгоритма, но перешел от изменения строки к запоминанию промежуточных результатов. Пробуй, должно пройти.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата
По окончанию цикла в строке будет содержимое файла, если нет то в чем ошибка?
ВСЕГО файла? Ошибаешься... Последняя строка (группа символов, после последнего пробела/табуляции)... А если в файле будет БОЛЬШЕ одной строки?

Цитата
Т.е. я не менял идеи твоего алгоритма, но перешел от изменения строки к запоминанию промежуточных результатов. Пробуй, должно пройти.
Кстати, Metrax, у нас когда-то даже конкурс был на программу, проверяющую правильность расстановки скобок... Так что в Поиск (ссылка - у меня в подписи)...
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 12:27
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name