Форум программистов, компьютерный форум CyberForum.ru

Задается словарь. Найти в нем все анаграммы - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.89
curtis65
0 / 0 / 0
Регистрация: 14.04.2013
Сообщений: 12
15.04.2013, 23:33     Задается словарь. Найти в нем все анаграммы #1
задали задачу
Задается словарь. Найти в нем все анаграммы (слова, составленные из одних и тех же букв).
смысл понятен,но непонятно как проверять посимвольно, чтоб выдавал правильный результат!

Помогите!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.04.2013, 23:33     Задается словарь. Найти в нем все анаграммы
Посмотрите здесь:

Дано натуральное число n. Отбросить в нем все цифры, стоящие правее самой правой единицы либо оставить число без изменений, если единицы в нем нет C++
C++ Дан текст. Напечатать все имеющиеся цыфры в нем
C++ С клавиатуры задается двухзначное целое число. Необходимо вывести на экран все его делители
C++ Задается произвольный текст. В тексте заменить все ТЧК, ЗПТ и другие сокращения на соответ-ствующие им знаки препинания
C++ Дано предложение. Вывести все буквы м и н в нем
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
2863 / 1811 / 272
Регистрация: 27.08.2010
Сообщений: 4,908
Записей в блоге: 1
16.04.2013, 04:20     Задается словарь. Найти в нем все анаграммы #2
Поскольку для анаграммы порядок букв неважен, остаются только такие характеристики слова, как использованные буквы и их количество.

Самый простой и быстрый вариант - это испортить словарь: отсортировать внутри каждого слова все буквы по алфавиту, а затем сами слова по по алфавиту. Остальное тривиально.

Если словарь портить нельзя...

Слова с разным количеством букв анаграммами быть не могут - проверяете только слова одинакового размера. Для каждого слова создаете массив счетчиков букв (33, если не различать регистр). Если для двух слов состояния счетчиков букв совпали - они являются анаграммой.

Проходите в цикле по списку слов (словарю) и за квадратичное время находите все анаграммы.

Если словарь предварительно отсортировать по размеру и по алфавиту, то будет быстрее :-)

Как (эквивалентный) вариант, можно выбрать систему счисления с (основание) > (число букв) и (основание) > (максимальная длина слова) и присвоить каждой букве вес - значение единицы отдельного разряда. Тогда, очевидно, все анаграммы будут иметь одинаковый вес.

На первом шаге алгоритма за линейное время взвешиваем все слова, на втором - за логарифмическое - сортируем, на третьем - распечатываем все последовательности одинакового веса. На большом словаре, разница в производительности должна быть значительной.

В любом случае, задача сводится к построению метрики (оценке расстояния между словами), нечувствительной к порядку букв, но чувствительной к самим буквам и их количеству. Слова с нулевым расстоянием являются анаграммами.
curtis65
0 / 0 / 0
Регистрация: 14.04.2013
Сообщений: 12
16.04.2013, 23:06  [ТС]     Задается словарь. Найти в нем все анаграммы #3
gazlan, это все понятно,но сам код мне никак не понятен...как все описывать просто не понимаю
gazlan
2863 / 1811 / 272
Регистрация: 27.08.2010
Сообщений: 4,908
Записей в блоге: 1
16.04.2013, 23:56     Задается словарь. Найти в нем все анаграммы #4
Сам словарь - загруженный в память - у вас есть? Или, хотя бы, вообще словарь?
Что уже сделано - кроме публикации условия?
По обработке текста здесь чуть ли не половина топиков - вы искали по форуму?

Покажите код и ткните пальцем - где не работает?
curtis65
0 / 0 / 0
Регистрация: 14.04.2013
Сообщений: 12
20.04.2013, 21:31  [ТС]     Задается словарь. Найти в нем все анаграммы #5
gazlan, вот сам код.
у меня только переворачивает слова,мне нужно чтобы перебирал буквы

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
 
using namespace std;
 
 
 
int main()
{
    setlocale (LC_ALL,"rus");
   string base[] = {"мор", "туш", "шут", "ром", "хан", "хна",
                    "кот", "ток", "воз", "зов", "гам", "маг","полк","клоп"};
  
   size_t size = sizeof(base) / sizeof(*base);
 
   for (size_t i = 0; i < size-1; ++i)
   {
      string word = base[i];
      reverse(word.begin(), word.end());
 
      for (size_t j = i+1; j < size; ++j)
      {
         if (word == base[j])
         {
             cout<<"Anagramm"<<endl;
            cout << base[i] << "-" << base[j] << endl;
            break;
         }
      }
   }
 
   system("pause");
 
   return 0;
}
gazlan
2863 / 1811 / 272
Регистрация: 27.08.2010
Сообщений: 4,908
Записей в блоге: 1
20.04.2013, 23:06     Задается словарь. Найти в нем все анаграммы #6
Вы уверяли, что вам все понятно. Судя по коду - не все.

Реверсировать ничего не нужно. И переставлять ничего не нужно. От каждого слова нужно построить числовую характеристику ("вес"). И их сравнить.

Вот, начиная с 21 строки, все выбрасываете и делаете как написано в #2.

Пусть, например, ваш алфавит состоит из 5 букв: 'к', 'м','о','р', и 'т'. Тогда, (основание) > 5 - это 6. Присваиваем нашим буквам веса: 'к' - 1, 'м' - 6, 'о' - 36, 'р' - 216, 'т' - 1296

Вес слова "мор": 6 + 36 + 216 = 258
Вес слова "ром": 216 + 36 + 6 = 258
Вес слова "кот": 1 + 36 + 1296 = 1333
Вес слова "ток": 1296+ 36 + 1 = 1333

Веса "мор" и "ром" совпали - анаграмма. Веса "кот" и "ток" совпали - анаграмма. Слова разного размера не проверяете.

Если не учитывать регистр, букву 'ё', и ограничить максимальный размер слова 32 символами, то для русского алфавита 33 будет подходящим основанием.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.06.2013, 02:27     Задается словарь. Найти в нем все анаграммы
Еще ссылки по теме:

C++ Считать текст из файла и найти в нем все палиндромы
C++ Заданный словарь слов. Найти в нем слова-палиндромы, то есть такие, которые одинаково читаются слева направо и наоборот, например, "АННА", "ШАЛАШ"
C++ Найти в тексте все слова анаграммы

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ihor3
3 / 3 / 1
Регистрация: 14.11.2012
Сообщений: 235
04.06.2013, 02:27     Задается словарь. Найти в нем все анаграммы #7
а если мне нужно с файла считывать и у файл записывать как это будет выглядеть?
Yandex
Объявления
04.06.2013, 02:27     Задается словарь. Найти в нем все анаграммы
Ответ Создать тему
Опции темы

Текущее время: 21:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru