интересно выслушать варианты решения игры http://melitopol.com.ua/forum/viewtopic.php?t=1322.
алгоритм не должен использовать какие-либо сторонние программы.
думаю тема довольно интересная хотя в принципе решение довольно просто но хочется выслушать варианты.
Код:
[root@dev words]# time ./start.sh рнгкмтиеа
Searching:
.................................................................
Найдено:
маркетинг
real 0m1.253s
user 0m0.896s
sys 0m0.096s
Язык реализации - PHP
словарь - 163294 слов
процессор - Semptron 2.2
То что программку написал не поленился эт конешно хорошо, но зачем было брать как пример, последнее использ. слово? эх ты, ну ок, не учёл знач. Придумывай теперь слово, но ток по правилам.
простите я просто запарился поднял из истории последний вызов, а там как раз последнее слово вылезло
Если б ты не сказал то наврятли кто-нить и заметил кстати так как такое сочетание букв сложно запомнить а заметить соответствие тем более
Алгоритм? Ну, если есть словарь в одном файле, то просто:
Ищешь слова, длина которых совпадает с длиной слова-загадки, затем проверяешь количество входящих букв ("уйх": а-0, б-0, ..., у-1, й-1...),
если количество всех букв совпадает, то слово подходит.
Алгоритм? Ну, если есть словарь в одном файле, то просто:
Ищешь слова, длина которых совпадает с длиной слова-загадки, затем проверяешь количество входящих букв ("уйх": а-0, б-0, ..., у-1, й-1...),
если количество всех букв совпадает, то слово подходит.
ну прикинь слово в 5 букв у тебя к примеру выпадет 10000 слов из пяти букв. И что ты потом в каждом будешь искать соответствие букв ? Как по моему будет долго. особенно если учитывать что буква может попадаться несколько раз.
В данном примере тебе прийдется выполнить
100000 - тыс операций на обработку словаря
+ 50 тыс на поиск букв с словах.
как по моему громоздко
ЕСЛИ длина текущего слова = длине искомого ТО
{
подсчитываем количество разных букв в слове // "ротт": р=1, о=1, т=2
ЕСЛИ количество соответствующих букв совпадает ТО слово найдено
}
ИНАЧЕ берем следующее слово
По-моему ничего тут сложного. Разве что искомое слово будет в самом конце. Тогда действительно будут перебираться все слова, длина которых равна длине искомого.
Я кон. уже не помню в Алгебре формулу (не знал, да еще и забыл), но прикол должен быть такой:
Слово из 5 букв "12345", теперь ты должен взять каждую букв. и отд. ей от слова ... бутер, сам не знаю что нач. говорить, продолжим, надо как я понемаю составить макс. кол-во вариации с этими буквами, по форм., пример :
12354
12534 - ну думаю вы меня поняли, потом запомнить, каждый вариант и подставлять/сравнивать каждый вар. с словарём, если слово не образовалось, тоесть вышло что то типо "тпоел", то оно покажется, крит. эрор, а если выйдет реал. слово "тепло", то словарь отреагир. что грамматика прав. ошибки нет. тоесть "Ю вин". Клос. програм.
ЕСЛИ длина текущего слова = длине искомого ТО
{
подсчитываем количество разных букв в слове // "ротт": р=1, о=1, т=2
ЕСЛИ количество соответствующих букв совпадает ТО слово найдено
}
ИНАЧЕ берем следующее слово
По-моему ничего тут сложного. Разве что искомое слово будет в самом конце. Тогда действительно будут перебираться все слова, длина которых равна длине искомого.
Хм, ты в эргономике не силён, думай как упростить. По твоему нужно разбивать тогда каждое слово со словаря и сравнивать отдельно по буквам. Прочти мой вар. , там проще, в конце вар. слова снова дел. одним целым и сравниваеш уже как целое слово, а не это...
Я кон. уже не помню в Алгебре формулу (не знал, да еще и забыл), но прикол должен быть такой:
Слово из 5 букв "12345", теперь ты должен взять каждую букв. и отд. ей от слова ... бутер, сам не знаю что нач. говорить, продолжим, надо как я понемаю составить макс. кол-во вариации с этими буквами, по форм., пример :
12354
12534 - ну думаю вы меня поняли, потом запомнить, каждый вариант и подставлять/сравнивать каждый вар. с словарём, если слово не образовалось, тоесть вышло что то типо "тпоел", то оно покажется, крит. эрор, а если выйдет реал. слово "тепло", то словарь отреагир. что грамматика прав. ошибки нет. тоесть "Ю вин". Клос. програм.
Да, но при наличии словаря, такой метод можно отбросить. Ты знаешь, сколько вариантов перестановок в слове, где 20 неповторяющихся букв? По ходу 20! (!-факториал) К примеру, слово, где 10 разных букв - это уже 3 628 800 вариантов перестановок. А 12 УЖЕ 479 001 600...
И учитывай еще то, с каждым "словом" из миллионов/миллиардов твоих перестановок тебе придется сделать поиск по всему словарю. У меня поиск пройдет только один раз, хоть и тщательно.
Напомни мне формулу для начала, поверь лучше такой вариант, чем тупой перебор каждого слова, ведь компьютеру сначало нужно узнать, состоит ли слово с библиотеки именно с такими параметрами как твоё слово, тоесть по люб. ты перероеш всю библиотеку, на дан. кол-во символов, вот теперь и подумай, что проще будет ).
Мне кажестя, что лучше комп. сначала образовать кучю вариантов, а потом сравн. с библиотекой. Тоесть компьютеру быстрее обр. эт вариант, чем потом начать разбив. кажд, слово из словаря, это уже не так просто.
И учитывай еще то, с каждым "словом" из миллионов/миллиардов твоих перестановок тебе придется сделать поиск по всему словарю. У меня поиск пройдет только один раз, хоть и тщательно.
У тебя поиск делается в 2 раза а у меня в 1. И вообще кто тебе сказал что у меня перебор ?
Раскрою свой алгоритм.
1. создаем словарь с ХЕШЕМ . хеш состит из букв поставленных в алфивитном порядке и знака # содержащий основное слово
не совсем понял что имлось в виду.
Дело в том что все серьезные алгоритмы поиска постороены на том что создается так называемый хеш или индекс. Который упрощает значительно поиск.
Как по мне метод перебора и сравнения со словарем безсмысленный так как вам нужно найти слова которые состоят из набора букв, а как они должны стоят не важно в принципе.
Последний раз редактировалось: Thomas (Пт Сен 29, 2006 13:41 pm), всего редактировалось 1 раз
О ток понял мысль ) Толковая ) упор. по алфав. мне понравилось, намного проще. Кажется я где то уже встречал такой подход.
Эт ты на паскале такое пишеш ? ну да на паскале, я таких функций как у тебя исп. не знаю ). Я только мыслить умею и то не всегда удачно.
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете голосовать в опросах
FAQ
Поиск
Пользователи
Группы
Регистрация
Профиль
Войти и проверить личные сообщения
Вход
![[ скрыт ]](templates/zavsTest/images/lang_russian/icon_email.gif "[ скрыт ]"){kind=icon}
поднял из истории последний вызов, а там как раз последнее слово вылезло 
, Томас, что то у тебя вообще 3 вар., что скажеш нам ламерам про наши ?