Форум «Всё о Паскале» _ Задачи _ Нахождение общей части слов
Автор: Patam 18.04.2007 20:44
1. Для задаваемой строки найти все содержащиеся в ней слова и распечатать наибольшую общую часть этих слов. Пример: Для строки мирный примирить перемирие мирить Общая часть слов - мир. 2. Найти в задаваемой строке содержащиеся в ней корни и распечатать для каждого корня однокоренные с ним слова. Пример: Для строки народ мирный родник мир родина род мирить Корни____Однокоренные слова мир______мирный мирить род______народ родник родина
Хелп плз.
Автор: Lapp 19.04.2007 12:44
По п.1 примерно ясно. Задачка неплохая. Вот, я набросал решение.. Ищется самая большая общая подстрока. Если таковых больше одной, найдена будет первая. Как сделать нахождение всех - надо подумать.. Регистр (большие-маленькие буквы) не приводится. Разделителем слов считаю пробел, но это легко исправить, если нужно - достаточно добавить нужные символы в множество Dividers.
;
var s,w,r,t:string; i,j,k,kx,n:integer;
function GetWord(s:string; var i:integer; var w:string):boolean; var j:integer; begin while (i<Length(s))and(s[i] in Dividers) do Inc(i); j:=i; while (j<Length(s))and not(s[j+1] in Dividers) do Inc(j); w:=Copy(s,i,j-i+1); GetWord:=i<=Length(s); i:=j+1; end;
begin s:='смирение примирить перемирие мирный мирить'; n:=1; GetWord(s,n,w); while GetWord(s,n,t) do begin kx:=0; r:='-Nothing-in-common-'; for i:=1 to Length(w) do begin j:=1; while j<=Length(t) do begin k:=0; while (i+k<=Length(w))and(j+k<=Length(t))and(w[i+k]=t[j+k]) do Inc(k); if k>kx then begin r:=Copy(t,j,k); kx:=k end; j:=j+k+1 end end; w:=r end; WriteLn('Root is: ',r); ReadLn end.
А вот с пунктом 2 не знаю, как быть. Одновременно отыскивать корни, как-то разделяя слова на группы однокоренных?.. это задача неслабая.. Или же список корней задан? Если да, тогда нет проблем.
Автор: Patam 19.04.2007 20:06
Список корней задан
Автор: мисс_граффити 19.04.2007 20:21
Цитата
Если да, тогда нет проблем.
не уверена... даны корни: лист, точ. точка точит листочек все три - однокоренные?
а еще есть корни с чередованием (гар-гор, зар-зор) то есть "пригорел" и "загар" - однокоренные, а "горный" не имеет к ним отношения. или "мир", "мирный" | "замереть", "замирать". разделение должны быть именно таким, а не "мир", "мирный", "замирать" | "замереть"
есть еще корни из одной буквы - с ними что делать?
так что вопрос - что понимается под корнем? если просто слог, то проблем нет, а если именно четко определяемая морфема...
Автор: Lapp 20.04.2007 3:13
Цитата(мисс_граффити @ 19.04.2007 17:21)
даны корни: лист, точ. точка точит листочек все три - однокоренные? ... а еще есть корни с чередованием (гар-гор, зар-зор) ... есть еще корни из одной буквы - с ними что делать?
мисс_граффити, ты, мне кажется, переоцениваешь обычную задачу на программирование. Это не есть реальный русский язык, это просто похоже. Кстати, в названии темы ничего про корни нету. Я использую эту терминологию для упрощения общения . Полагаю, что реальные данные, на которых будет проверяться решение, не будут включать перечисленных тобой случаев. Кроме того, первый случай у тебя с наложением "корней", а второй просто противоречит условию задачи . Третий, полагаю, является вырожденным..
Добавлено через 3 мин. По этому же поводу: не так давно я помогал решить задачу на перенос слов. Там были некоторые правила для переноса, которые неплохо вписывались в РЯ во многих случаях. Но конечно, не во всех!.. Тем не менее задача прекрасно демонстрировала принципы программирования. Так же и эта..
Добавлено через 18 мин. Жаль только, автор темы немногословен.. Видимо, ему достаточно оказанной помощи..
Автор: мисс_граффити 20.04.2007 6:46
Цитата
мисс_граффити, ты, мне кажется, переоцениваешь обычную задачу на программирование. Это не есть реальный русский язык, это просто похоже. Кстати, в названии темы ничего про корни нету. Я использую эту терминологию для упрощения общения . Полагаю, что реальные данные, на которых будет проверяться решение, не будут включать перечисленных тобой случаев. Кроме того, первый случай у тебя с наложением "корней", а второй просто противоречит условию задачи . Третий, полагаю, является вырожденным..
по пунктам может быть, и переоцениваю - понятно, что учесть абсолютно все тонкости языка невозможно. но, как мне кажется, стоит уточнить, что именно понимают под словом "корень".
да, скорее всего тесты будут "без заморочек". это я зря... просто полдня пытаюсь угадать, на каком тесте моя программка не работает. вот и увлеклась... *смущенный смайлик*
но все же... где-то сказано, что наложения быть не может? хорошо. корни: лист, очк очки очкарик листочки
противоречие... чему противоречит-то?
вырожденный, но это не значит недопустимый...
ждем автора
Автор: Lapp 20.04.2007 10:42
> по пунктам По пунктам - так по пунктам..
> стоит уточнить, что именно понимают под словом "корень". Зачем? В оригинале речь идет об "общей части слов". Слово "корень" звучит во второй задаче, но, мне кажется, исключительно для упрощения лексики..
> полдня пытаюсь угадать, на каком тесте моя программка не работает. У тебя есть программка? Почему бы не показать?..
> где-то сказано, что наложения быть не может? Нет, не сказано. Беру слова обратно
> противоречие... чему противоречит-то? Да, противоречит условию. Если есть чередование гласных (прошу прощение за употребление специального термина из другой области, не из программирования), то части слов не могут считаться общими в принятых рамках.
> вырожденный, но это не значит недопустимый... Конечно. Просто неинтересный. И моя программа с ним прекрасно справляется..
> ждем автора С нетерпением..
Добавлю, что если бы речь шла о машинной обработке текста на основе правил РЯ, то такая задача потянула бы на кандидатскую..
Автор: Patam 20.04.2007 20:12
Эээмм.. По сложности 2-я задача равна 1-ой, так что не надо учитывать чередования и прочее.
Автор: мисс_граффити 20.04.2007 20:14
Цитата(Lapp @ 20.04.2007 7:42)
> стоит уточнить, что именно понимают под словом "корень". Зачем? В оригинале речь идет об "общей части слов". Слово "корень" звучит во второй задаче, но, мне кажется, исключительно для упрощения лексики..
Вот именно. В первой - об общей части слов, во второй - о корне. "Это жжж неспроста" (с)
Цитата(Lapp @ 20.04.2007 7:42)
> полдня пытаюсь угадать, на каком тесте моя программка не работает. У тебя есть программка? Почему бы не показать?..
Это про шарик и нитку... я про нее писала, никто не заинтересовался.
Цитата(Lapp @ 20.04.2007 7:42)
> противоречие... чему противоречит-то? Да, противоречит условию. Если есть чередование гласных (прошу прощение за употребление специального термина из другой области, не из программирования), то части слов не могут считаться общими в принятых рамках.
я первую задачу вообще не трогаю... только про вторую говорю.
Цитата(Lapp @ 20.04.2007 7:42)
Добавлю, что если бы речь шла о машинной обработке текста на основе правил РЯ, то такая задача потянула бы на кандидатскую..