0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
|
||||||
1 | ||||||
Поиск анаграмм16.10.2011, 02:01. Показов 14429. Ответов 23
Метки нет (Все метки)
Доброй ночи!
Такая задачка... Возможно многим знакома по Золотому байту. Я в самом начале изучения С++ и до конца не могу разобраться. Есть файл "in.txt" с каким-либо списком слов (до 10000). Одна строка - одно слово. Нужно найти все анаграммы и вывести их в файл "out.txt". Например во входном файле: kot polet tok leto teplo kto zima Тогда на выходе: kot tok kto polet teplo Примерно так... Во время первого считывания файла я определяю кол-во строк. Затем создаю массив строк. Далее сортирую буквы в словах. Это сделал. Вроде и дальше понимаю путь (с помощью strcmp ищем дубликаты). Но на деле не получается. Не пойму , как обратно отсортировать. Или какой другой алгоритм нужен. И как в файл записать... Классы не использовать. Посмотрите код и помогите пожалуйста.
0
|
16.10.2011, 02:01 | |
Ответы с готовыми решениями:
23
Строка: Поиск анаграмм Поиск анаграмм во входном файле Группы анаграмм в строке Комбинаторика, количество анаграмм |
Заблокирован
|
||||||
16.10.2011, 04:29 | 2 | |||||
если вы ограничены только нижним регистром и точно знаете что отсутствуют цифры и знаки препинания то не надо сортировать, ищите совпадения по суммам символов. но помните что сумма это еще не не анаграмма, например "no" == "ex" == 221. вот идея
1
|
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
|
|
16.10.2011, 08:52 [ТС] | 3 |
Оригинально...
А можно эту идею на каком-нибудь небольшом примере показать, пожалуйста...
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
16.10.2011, 08:56 | 4 |
Вместо кодов символов можно суммировать коды из хэш таблицы. Меньше ложных совпадений будет. И заглавные буквы можно будет "приравнять" к строчным.
0
|
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
|
|
16.10.2011, 09:54 [ТС] | 6 |
Файл может быть с разным кол-вом слов. До 10000.
Поэтому и нужен первый пробег по файлу для выяснения кол-ва строк. Цифры, пробелы, знаки препинания отсутствуют. Только буквы. Ну например такой:
0
|
16.10.2011, 13:19 | 7 | |||||
Вот, решил через связность. Алгоритм, конечно, жуткий и жадный на память и ресурсы, но что придумал.
0
|
Заблокирован
|
||||||
16.10.2011, 13:32 | 8 | |||||
у меня тоже чепуха какая-то, более того - из-за смены курсора в файле (строки 50, 70)не хочет завершать цикл
0
|
16.10.2011, 13:33 | 9 | |||||
Вот я писал только не для txt... Алгоритм работает...
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
16.10.2011, 13:35 | 10 |
Создаётся массив пар pair<string,string>. Вторым заносится слово, первым это же слово, но отсортированное по буквам без учёта регистра. Массив сортируется по первому в паре. Дальше всё очевидно.
2
|
16.10.2011, 13:36 | 11 |
Ребят, ну через сумму решать - это же немного не то. 2 + 8 == 1 + 9 == 5 + 5 == 3 + 7 и так далее. Ошибки возможны
KeyGen, у вас, вроде, просто одинаковые строки ищет. А нужно-то анаграммы, то есть слова, которые состоят из одних и тех же букв: кот - ток - кто, и всё в этом роде. Deviaphan, красиво
1
|
Заблокирован
|
|
16.10.2011, 13:42 | 12 |
talis, я взял сложение по модулю чтобы избежать лишних проверок на вхождение, в случае эквивалентно, проверку на вхождение. Ну надо же уметь нестандартно мыслить Deviaphan давайте типа что ли тренинг на проявление смекалки а то я никак не мог увязать хеширование и задачу, а вон как надо
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
16.10.2011, 13:49 | 14 |
Уже увязал или пояснить? Поясню. Это чтобы суммировать не коды символов, а случайные цифры, чтобы меньше совпадений было. Или ксорить вместо суммирования.
Сумма как начальная проверка, оптимизация. Мыла не будет. Будет всё норм.
0
|
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
|
|
16.10.2011, 16:00 [ТС] | 16 |
Непростая задача для меня, который программирование всего пару месяцев изучает.
Если даже у людей с опытом не все получается. talis, код работает. А как его можно переделать, чтобы использовать using namespace std: и чтобы в конце в файл записать? И еще - vector обязателен? Мне главное понять, а не чтобы за меня написали. Да вот без примера понять не получается... Может еще кто вариантов подкинет. Когда видишь код, то и понимание быстрее приходит. Кстати, сделал входной файл на 50 слов.
0
|
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
|
|
16.10.2011, 16:12 [ТС] | 18 |
0
|
16.10.2011, 16:15 | 19 |
slavik, для сортировки используйте std::sort( начало_диапазона, конец_диапазона ). В случае с контейнерами STL (vector тот же) соответствующие итераторы можно получить через vec.begin() и vec.end(). А вообще, http://cplusplus.com/reference. Там есть поиск. Ищите std::string, std:: pair, std::sort и прочие.
0
|
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
|
|
17.10.2011, 08:40 [ТС] | 20 |
буду рыться...
Добавлено через 4 часа 4 минуты бьюсь - не получается... А можно доделать тот код программы, который я написал (см. в начале)? Дело в том, что препод хотел именно так, хоть по другому и красивей. Да и не учили мы еще всего остального. А там я хоть алгоритм понимаю. С технической частью проблемы. Люди, help... Помогите написать работающий код... Добавлено через 12 часов 9 минут sos...sos...sos...
0
|
17.10.2011, 08:40 | |
17.10.2011, 08:40 | |
Помогаю со студенческими работами здесь
20
Вычислить количество слов анаграмм (Слова которые состоят из одних и тех же букв) Поиск анаграмм в файле Расшифровка анаграмм Подсчет количества анаграмм Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |