|
|
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
необходимо сгенерировать фразы русского языка которые были читались одинаково справа налево и наоборот Например Аргентина манит негра Что скажете? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.07.2009, 06:35:28 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
На Прологе решение красиво может выглядеть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.07.2009, 06:39:47 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
_culis_необходимо сгенерировать фразы русского языка которые были читались одинаково справа налево и наоборот Например Аргентина манит негра Что скажете? Могу предложить простой и наверно неэффективный алгоритм, но для его реализации нужна база слов русского языка чем больше тем лучше, да еще желательно с разными падежными формами существительных, раличными формами глаголов и пр. Далее начинаем с минимальной длины фразы в 2 слова. Берем 1 слово из базы, берем следующее отличное от него слово, соединяем их выполняем проверку на палиндром - сравнивается 1 половина склеенного слова начиная с начала со 2 половиной этого слова начиная с конца. Если проверка успешна готовый палиндром, нет далее собираем слова. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.07.2009, 23:12:35 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
Вообще тут много вариантов оптимизаций. Далее когда слов в фразе будет много например 3 и более, то просто сравнивать их 1 слово со 2 словом, если проверка успешна, то вероятность что палиндром вырастет, а иначе продолжаем сборку слов. Таким образом будет сэкономлено много операций сравнения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.07.2009, 23:17:32 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
студентикВообще тут много вариантов оптимизаций. Далее когда слов в фразе будет много например 3 и более, то просто сравнивать их 1 слово со 2 словом , если проверка успешна, то вероятность что палиндром вырастет, а иначе продолжаем сборку слов. Таким образом будет сэкономлено много операций сравнения. Ошибка: не со 2 словом, а с последним. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 09.07.2009, 23:18:44 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
а как насчет проверки на смысл? Бессмысленные фразы не считаются. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 04:21:03 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
Я буду в своем стиле излагать :) 1. Берем словарь 2. сортируем его по возрастанию 3. переворачиваем все слова и сортируем по возрастанию. т.е. здесь у нас уже 2 словаря Сложность пока O(N*logN) 4. Теперь проходим по словарям ищем совпадения O(N): 4.1. слово из 1го словаря совпадает со словом из 2го (ура! мы нашли палиндром!) 4.2. слово из 1го начинается со слова из 2го - собираем словарь из обрезков и сравниваем его со 2м словарем. Т.е. рекурсия п.4. 4.3. слово из 2го начинается со слова из 1го - собираем словарь из обрезков и сравниваем его с 1м словарем. Т.е. рекурсия п.4. Хм... Не такой уж сложный алгоритм получился. Надо только на количество уровней вложенности ограничение наложить, на всякий пожарный. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 08:52:31 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
_culis_а как насчет проверки на смысл? Бессмысленные фразы не считаются. Это уже задача искусственного интеллекта... Или естественного. :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 08:54:17 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
_culis_а как насчет проверки на смысл? Бессмысленные фразы не считаются. Генерация осмысленных фраз сама по себе очень сложная задача, а вам ещё и палиндромы подавай :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 12:17:38 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
Кстати, обратите внимание, в палиндромах встречаются не только существительные, но и существительные в падежах, глаголы в разных формах и склонениях. Поэтому предложение Самойловского еще и надо расширить генератором словарных сочетаний в разных формах. А это еще сильнее усложняет задачу. где-то1. Делили лед 2. Осел окупил липу-колесо 3. Мортиру дурит ром 4. Во зле дудел зов 5. Но земле дудел мезон 6. Лохо-хладо-базу забодал хохол 7. Акве чебурашка как шару бечевка 8. Куда Иван? - на виадук 9. На работе лес, все лето - баран 10. Купил у бабули пук ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 13:16:38 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
Моя фамилия - Самоловских А словарь да, надо со всеми падежами формами и т.д.. Думаю если поискать по интернету, то и такой словарь найти реально. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 14:04:19 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
И, кстати, моя фамилия не склоняется. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 14:04:48 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
Реализовал алгоритм, аналогичный алгоритму Kefir-а. Единственное отличие в том, что у меня середина палиндрома приходится не на границу между словами, а находится внутри слова. В качестве словаря использовал этот словарь английских слов. Получилось вот что: retsina byre porcino mongrel tusseh capacitor cassene nog goneness acrotic apaches sutler gnomonic ropery banister sab mambas regna redraw nonwar deranger snort celesta kielbasa reseda septet pesades erasable ikats electrons sika murderee psylla sanseis pignolis peseta dessert indene vestige lessened unstrap mismeet segni kenaf nonfan eking esteems imparts nudeness elegits evened nitres sedates epsilon gipsies nasally speered rumakis snort celesta kielbasa resedas rotenone torsos rotenone torsades erasable ikats electrons reb butylate padri boobird apetaly tubber halala hetaira vessel dissent parsonage roselle candela virtuosi wises iwis outrivaled nacelles oreganos raptness idlesse variate halalah dere galette lagered halala helio tesla sisals etoile halalah Многие слова в первый раз вижу, но это из-за словаря. Может у кого-нибудь есть русский словарь, или словарь только из общеупотребильных английских слов? Код ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 14:30:08 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
Самоловских Виталий aka KefirИ, кстати, моя фамилия не склоняется. Прошу извинения. Не разглядел. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 14:51:36 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
Сгенерил словарик из книг Стивена Кинга из серии Тёмная башня Весело получилось :D мирового лишило говорим моталась тактике вовеки ткать салатом мирового готовил жевала вежливо того говорим киборги карабин нервов ренни бараки гробик огороде ниши недорого норд ехала хедрон киборги карабина холмом лохани бараки гробик киборги министра замотала хуник усиленно тилли тоннели сукину халатом азарт синими гробик йетса паники могиле трофеи надежд слугу лсд жедание фортели гомики напастей сородичи дорос таков даааа адвокат марена монро почтет чопорно манерам мочи прикончит катере тактично кирпичом котомки мамик моток меч угомони мамино могучем котелка гарбер ужалила взвалил ажуре брага клеток мирового палату паники напутала поговорим ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 15:13:33 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
2rmull Respect ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 19:41:37 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
Забрал исходничек себе в коллецкию. P.S. Палиндромы это скучно. Скороговорки - смешнее. Вот если-бы генератор таких сделать: На билльярде лбом либо битой по балде били белобандитов. Высшие эшелоны подшофе шествовали к подшефным по шоссе. В Кабардино-Балкарии валокардин из Болгарии. Глухо плюханулся обухом Ктулху сухо-посухо да в ухо Плутал Плутарх, хлопотал, похлопывал холопа по попе - ПЛОХО!!! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 10.07.2009, 21:25:51 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
авторP.S. Палиндромы это скучно. Хорошо - вот еще одна задача Есть массив символов A произвольной длины. Скажем 1000 символов. Известно, что это зашифрованное сообщение на русском языке где каждый символ из A соответствует определенной букве алфавита. Необходимо найти соответствие между символами в А и алфавитом. Задача старая но по моему очень интересная. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.07.2009, 22:25:54 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
_culis_авторP.S. Палиндромы это скучно. Хорошо - вот еще одна задача Есть массив символов A произвольной длины. Скажем 1000 символов. Известно, что это зашифрованное сообщение на русском языке где каждый символ из A соответствует определенной букве алфавита. Необходимо найти соответствие между символами в А и алфавитом. Задача старая но по моему очень интересная. В принципе слышал, что такую задачу, если конечно закодированное сообщение не особо изысканное, можно решить с ручкой и листком бумаги. Найти самые часто встречающиеся символы и подставлять на их место самые статистически частые в употреблении буквы в русском языке, например "а", "е" и др. Учитывать чередование гласных и согласных. Ну еще один из частоупотребляемых будет символ пробела. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.07.2009, 23:22:20 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
_culis_Необходимо найти соответствие между символами в А и алфавитом.Тривиально. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 11.07.2009, 23:27:11 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
авторТривиально ну так где решение? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.07.2009, 03:46:06 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
_culis_ну так где решение? Основы Криптографии. Мне эта тема неинтересна, потому-что subj перетирал уже раз двести в этом форуме. Бывай. Успехов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.07.2009, 10:23:48 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
_culis_, Одно из "решений" было опубликовано еще в журнале Юный техник. . А так вообще сложность задачи зависит от того встречаются ли буквы в разных регистрах в тексте, есть ли знаки припинания в тексте, известен ли символ-разделитель между словами. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.07.2009, 11:07:01 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
Спасибо за ссылки, посмотрю. Вообще интересно - вот еще одна версия, накурченная. http://www.ams.org/bull/2009-46-02/S0273-0979-08-01238-X/S0273-0979-08-01238-X.pdf ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.07.2009, 03:57:54 |
|
||
|
задача со словами
|
|||
|---|---|---|---|
|
#18+
_culis_авторP.S. Палиндромы это скучно. Хорошо - вот еще одна задача Есть массив символов A произвольной длины. Скажем 1000 символов. Известно, что это зашифрованное сообщение на русском языке где каждый символ из A соответствует определенной букве алфавита. Необходимо найти соответствие между символами в А и алфавитом. Задача старая но по моему очень интересная. В институте была такая лаба. Нужен исходник?)) Считаются частоты букв, берутся стат данные по частотам для русского текста, подбирается кодирующая таблица, минимизирующая сумму отклонений (как вариант - квадратов отклонений) частот от стат данных. Это в самом тривиальном случае, вообще этого должно хватить, но если хочется поизвращаться, то можно считать частоты пар символов, но для маленьких текстов так и так хреново может дешифроваться. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.07.2009, 10:46:20 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=36083288&tid=1344367]: |
0ms |
get settings: |
5ms |
get forum list: |
9ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
183ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
62ms |
get tp. blocked users: |
1ms |
| others: | 244ms |
| total: | 520ms |
| 0 / 0 |
