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

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

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

 
 Ответить  Открыть новую тему 
> Задача на грамматики, помогите решить задачу
Виталий`Сергеевич
сообщение 5.04.2006 9:08
Сообщение #1





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

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


Активной емкостью некоторого вывода в грамматике назовем максимум числа нетерминалов, встречающихся в каждом из промежуточных слов этого вывода
По заданным удлиняющей грамматике и слову найти вывод этого слова с минимальной активной емкостью!
Зараннее благодарен smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
APAL
сообщение 5.04.2006 10:49
Сообщение #2


Смотрю...
*****

Группа: Модераторы
Сообщений: 1 055
Пол: Мужской
Реальное имя: Пшеничный Алексей Анатольевич

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


А теперь на "нормальном русском" условие напишите.
Я лингво-грамматический факультет не заканчивал...


--------------------
Если что-то не делает того, что вы запланировали ему делать - это еще не означает, что оно бесполезно.
--------------------
Прежде, чем задать вопрос - Правила :: FAQ :: Поиск
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Виталий`Сергеевич
сообщение 5.04.2006 12:03
Сообщение #3





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

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


Цитата(APAL @ 5.04.2006 10:49) *

А теперь на "нормальном русском" условие напишите.
Я лингво-грамматический факультет не заканчивал...

А в чем собственно загвоздка ?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
мисс_граффити
сообщение 5.04.2006 12:13
Сообщение #4


просто человек
******

Группа: Модераторы
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

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


задание хотя бы сформулируйте более.... эээ... технически.
а по-хорошему, напишите, что пытались делать.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
GoodWind
сообщение 5.04.2006 12:17
Сообщение #5


Автооответчик
*****

Группа: Модераторы
Сообщений: 1 188
Пол: Мужской
Реальное имя: Александр

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


Цитата
некоторого вывода

по русски это звучит как "предложения" ? или как "последовательность слов"...
Цитата
нетерминалов

что такое "нетерминал" ?
Цитата
удлиняющей грамматике

а это что такое?


--------------------
Неадекватная чушь может быть адекватным ответом на неадекватный вопрос. Понятно или разжевать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
volvo
сообщение 5.04.2006 12:21
Сообщение #6


Гость






Ну, допустим, задачка-то скопирована... Copy/Paste рулит. Предположим, отсюда:
http://pco.iis.nsk.su/ICP/Practice/dd8-5/node3.html (Задача №19)... А вот объяснения там нет, поэтому и автор вопроса объяснить затрудняется...

P.S. Вот тут:
http://pco.iis.nsk.su/ICP/Practice/dd8-1/node3.html
есть "словарь" понятий, используемый в заданиях...
 К началу страницы 
+ Ответить 
APAL
сообщение 5.04.2006 12:23
Сообщение #7


Смотрю...
*****

Группа: Модераторы
Сообщений: 1 055
Пол: Мужской
Реальное имя: Пшеничный Алексей Анатольевич

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


Цитата
слова с минимальной активной емкостью
- и это тоже хорошо бы пояснить.


--------------------
Если что-то не делает того, что вы запланировали ему делать - это еще не означает, что оно бесполезно.
--------------------
Прежде, чем задать вопрос - Правила :: FAQ :: Поиск
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
GoodWind
сообщение 5.04.2006 12:43
Сообщение #8


Автооответчик
*****

Группа: Модераторы
Сообщений: 1 188
Пол: Мужской
Реальное имя: Александр

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


APAL, все просто:
Цитата
Активной емкостью некоторого вывода в грамматике назовем максимум числа нетерминалов, встречающихся в каждом из промежуточных слов этого вывода

lol.gif надо внимательнее читать задание wink.gif
т.е. я понимаю так - берем из "вывода" слово, считаем его активную емкость, если она меньше текущей минимальной активной емкости, то сохраняем слово и его активную емкость rolleyes.gif


--------------------
Неадекватная чушь может быть адекватным ответом на неадекватный вопрос. Понятно или разжевать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
APAL
сообщение 5.04.2006 13:19
Сообщение #9


Смотрю...
*****

Группа: Модераторы
Сообщений: 1 055
Пол: Мужской
Реальное имя: Пшеничный Алексей Анатольевич

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


Да, точно! Пока дочитаешь до конца теряется смысл начала...

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


--------------------
Если что-то не делает того, что вы запланировали ему делать - это еще не означает, что оно бесполезно.
--------------------
Прежде, чем задать вопрос - Правила :: FAQ :: Поиск
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
GoodWind
сообщение 5.04.2006 14:19
Сообщение #10


Автооответчик
*****

Группа: Модераторы
Сообщений: 1 188
Пол: Мужской
Реальное имя: Александр

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


если сегодня автор не появится и не объяснит что ему собстно нужно, закроем тему...


--------------------
Неадекватная чушь может быть адекватным ответом на неадекватный вопрос. Понятно или разжевать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Виталий`Сергеевич
сообщение 8.04.2006 8:45
Сообщение #11





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

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


Не пошутилsmile.gif А сам смысл задачи мне самому не сильно понятен, я сюда и написал с целью разобраться!! И я кстати ее не копировал, а списал с учебника, даже и не знал что есть электронный вариант!!!! Все серьезно;) Помогите пожалуйста если сможете rolleyes.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
hardcase
сообщение 8.04.2006 11:43
Сообщение #12


code warrior
****

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

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


Задача странная какая-то.
Получается, у нас есть грамматика Г и в ней есть куча правил, причём если использовать, допустим, цепочку правил А(Г), то через Р шагов мы придём к цепочке терминальных символов, а если использовать правило Б(Г), то мы придём к точно такойже цепочке темриналов но за К шагов, причём К <> Р, и след-но, актиная емкость будет различаться. ЗначиЦа нам нужно для предложенного ввода найти самую короткую цепочку вывода; в случае, когда К < Р это й цепочной будет, вероятно, Б(Г), и А(Г) в противном случае.....

Да, недольшая поправка: вывод не обязательно должен быть самым коротким, он должен включать в минимальное количество нетерминалов.

Сообщение отредактировано: hardcase - 8.04.2006 12:09


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Виталий`Сергеевич
сообщение 10.04.2006 17:02
Сообщение #13





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

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


как все плохо то nea.gif Люди помогайте !!!! Пожалуста !!!! give_rose.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Виталий`Сергеевич
сообщение 11.04.2006 11:01
Сообщение #14





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

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


Цитата(GoodWind @ 5.04.2006 12:43) *

APAL, все просто:

lol.gif надо внимательнее читать задание wink.gif
т.е. я понимаю так - берем из "вывода" слово, считаем его активную емкость, если она меньше текущей минимальной активной емкости, то сохраняем слово и его активную емкость rolleyes.gif

я блин че то вообще не представляю как задать грамматику и посчитать активную емкость, объясни пожалуйста как ты себе это представляешь! smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
GoodWind
сообщение 11.04.2006 12:19
Сообщение #15


Автооответчик
*****

Группа: Модераторы
Сообщений: 1 188
Пол: Мужской
Реальное имя: Александр

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


ни как =) я в грамматиках не шарю...


--------------------
Неадекватная чушь может быть адекватным ответом на неадекватный вопрос. Понятно или разжевать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
hardcase
сообщение 11.04.2006 18:12
Сообщение #16


code warrior
****

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

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


Полагаю, это устная задача. И принципиальное решение её я уже привёл выше. Если бы это была задача на программирование, то задача не стояла бы так широко.


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
asVitaly
сообщение 3.05.2006 17:20
Сообщение #17





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

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


Цитата(hardcase @ 11.04.2006 22:12) *

Полагаю, это устная задача. И принципиальное решение её я уже привёл выше. Если бы это была задача на программирование, то задача не стояла бы так широко.

Да твое принципиальное решение верно, и задача действительно такая широкая, есть у кого нибудь идеи этой минимизации ? Ведь полный перебор использовать здесь глупо!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
hardcase
сообщение 3.05.2006 21:30
Сообщение #18


code warrior
****

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

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


Цитата(asVitaly @ 3.05.2006 18:20) *
Ведь полный перебор использовать здесь глупо!
Согласен. Но мочему-то другого способа не видно.
Правда нужно использовать выводы, которые по возможности не удлинняют цепочку нетерминалов и в тоже время не приводят в левой рекурсии.


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
asVitaly
сообщение 9.05.2006 9:24
Сообщение #19





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

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


есть еще у кого идеи? blink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 

- Текстовая версия 17.07.2025 22:37
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"