Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37

Группы анаграмм в строке

19.11.2012, 13:49. Показов 2155. Ответов 8
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Всем доброго времени суток.
Я в С++ начинающий.
Есть задача, которую не получается написать; не получается скорее по причине отсутствия нужных знаний... Пожалуйста, если кому-то не лень, объясните, как можно написать попроще. Искал на форуме подобную задачу, но решения сложны для понимания, да и задачи совсем не аналогичные.

Постановка задачи:
В строке найти все группы слов-анаграмм (слова, получаемые одно из другого перестановкой букв, например: автор, отвар, товар; кот, кто, ток – две группы анаграмм).
Присутствуют входной и выходной файлы. В первом записана строка со словами, разделёнными пробелом.
В выходной файл нужно вывести группы анаграмм; каждую группу в отдельную строку.

Пример:
в файле infile лежит строка:
секта автор рост весточка аскет товар сигара трос тесак отвар качество сорт месть ток свет сетка трос
после выполнения содержимое файла outfile будет таким:
секта аскет тесак сетка
автор товар отвар
рост трос сорт
весточка качество
Объясните, как это можно реализовать, пожалуйста. Буду благодарен.
Либо просто пошагово объясните этот код (не мой; не до конца понимаю его), если так будет легче (сомневаюсь думаю, у меня появится куча дополнительных вопросов).
C++ (Qt)
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define MAXLINE   1000   /* максимальная длина строки */
#define MAXWORDS  100    /* максимальное количество слов */
 
int CheckCharsLine(const char *l, const char *set); 
 
/* ищет анаграммы в файле
   и записывает их в ряд в другой файл */
main()    
{
    FILE *ifp, *ofp;
    char line[1000], *dup;
    char *words[100], *p, **w, **cur;
    long nwords, i, j;
    int first, printed;
    enum { NO, YES };
    const char *iname = "infile",
               *oname = "outfile";
    
    ifp = fopen(iname, "r");
    ofp = fopen(oname, "w");
    if (!(ifp && ofp)) {
        fprintf(stderr, "error: files" "\n");
        return 1;
    }
    
    if (!fgets(line, sizeof line, ifp)) {
        fprintf(stderr, "error: no line" "\n");
        return 2;
    }
    
    if (!(dup = malloc(strlen(line)+1))) {  
        fprintf(stderr, "error: memory" "\n");
        return 3;
    }    
        
    strcpy(dup, line);
    
    for (p = strtok(dup, " "), w = words; 
         p;
         p = strtok(NULL, " "))
        *w++ = p;
    
#if 1  
    printf("%s", line);
    printf("%ld" "\n", nwords);
#endif    
    
    for (cur = words, i = 0; i < nwords; i++, cur++) {
        first = YES;
        printed = NO;
        for (w = cur+1, j = i+1; j < nwords-1; j++, w++)
            if (CheckCharsLine(*w, *cur) > 0) {
                if (first == YES) {
                    fprintf(ofp, "%s" " ", *cur);
                    first = NO;
                }    
                fprintf(ofp, "%s" " ", *w);
                *w = '\0';
                printed = YES;
            }    
        if (printed == YES)
            putc('\n', ofp);
    }
    
    free(dup);
    
    fclose(ifp);
    fclose(ofp);
    
    return 0;
}
 
/* CheckCharsLine:  проверяет состоит ли l
                    только из символов в set */
int CheckCharsLine(const char *l, const char *set)
{
    const char *t;
    
    if (!(l && set && *l && *set))
        return EOF;
    for (t = set; *t; t++)
        if (!strchr(l, *t))
            return 0;
    for ( ; *l; l++)
        if (!strchr(set, *l))
            return 0;
    return 1;
}
Добавлено через 18 часов 44 минуты
Кто-нибудь может помочь?
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
19.11.2012, 13:49
Ответы с готовыми решениями:

Студент определяет свой номер N в списке группы. Старосте группы сообщается идентификатор M группы
:cry::cry::cry: Решить задание нужно до 25.11.2018. SOS!!!!!

Замена группы символов в строке
Имеется строка длиной до 100 символов, в которой несколько раз встречается сочетание ”real”. Сформировать строку, содержащую вместо...

Замена группы символов в строке!
Вводится строка, заменить группу более трёх одинаковых символов многоточием(тремя точками). Например: Helllo woood , должно...

8
 Аватар для BRcr
4043 / 2333 / 292
Регистрация: 03.02.2011
Сообщений: 5,066
Записей в блоге: 10
19.11.2012, 16:07
Вот ленивое решение на основе внутренней сортировки по ключам в классе multimap. Нам остается только создать уникальный идентификатор анаграммы - то бишь просто отсортировать буквы в слове(если сортировать буквы в словах-анаграммах, всегда получим строчку одного и того же вида).
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
    fstream file_in( "in.txt", ios_base::in ), file_out( "out.txt", ios_base::out ); // открываем файлы с соответствующими режимами
    multimap <string, string> ana_map; // набор пар типа pair<string, string>, с возможностью дубликации ключей
    string str, sorted_str;
 
    if ( !file_in.is_open( ) || !file_out.is_open( ) ) { // если какой-либо из файлов не открыт - ошибка и завершение программы
        cout << "error opening files\n\n";
        system( "pause" );
        return -1;
    }
    while ( !file_in.eof( ) ) { // заполняем ana_map из потока file_in
        file_in >> str; // слова, разделенные пробелом, по одному помещаются в str
        sorted_str = str;
        sort( sorted_str.begin( ), sorted_str.end( ) ); // сортируем буквы в строчке sorted_str по возрастанию
        ana_map.insert( pair <string, string> ( sorted_str, str ) ); // вставляем пару строчек в ana_map, где ключом служит сортированная строчка, а значением - исходное слово; простая форма записи типа "ana_map[sorted_str] = str;" у меня не компилируется по причине отсутствия оператора + в данном шаблоне multimap для типа string - хз почему, да и бог с ним
    }
    str = ana_map.begin( )->first;
    for ( multimap <string, string> ::iterator it = ana_map.begin( ); it != ana_map.end( ); ++it ) { // проходим циклом по всем парам в ana_map последовательно, так как они отсортированы внутри по ключу, остается только отсечь лишнее и вывести все остальное :)
        if ( ana_map.count( it->first ) > 1 ) { // отсекаем ключи, встречающиеся один раз
            if ( str != it->first && file_out.tellp( ) ) { // разделяем наборы анаграмм по строчкам: если текущий ключ не равен предыдущему И фокус вывода НЕ находится в начале файла, то выводим в файл перенос строки
                file_out << endl;
            }
            file_out << it->second << " ";
            str = it->first;
        }
    }
    file_in.close( );
    file_out.close( );
Файл in.txt:
Code
1
секта автор рост весточка аскет товар сигара трос тесак отвар качество сорт месть ток свет сетка трос
Файл out.txt:
Code
1
2
3
4
весточка качество 
автор товар отвар 
секта аскет тесак сетка 
рост трос сорт трос
1
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
19.11.2012, 17:43  [ТС]
1. Что должно быть в include? (я в с++ начинающий, по коду пока понять не могу; пробовал подключать всё подряд известное мне #include <iostream> #include <fstream> #include <stdio.h> #include <string> #include <string.h> #include <stdlib.h>, пишет много интересного... привожу журнал компиляции:
Кликните здесь для просмотра всего текста
Компилятор: Default compiler
Выполнение g++.exe...
g++.exe "C:\Users\Delmellor\Desktop\erh\reht.cpp " -o "C:\Users\Delmellor\Desktop\erh\reht.exe " -I"C:\Dev-Cpp\lib\gcc\mingw32\3.4.2\include" -I"C:\Dev-Cpp\include\c++\3.4.2\backward" -I"C:\Dev-Cpp\include\c++\3.4.2\mingw32" -I"C:\Dev-Cpp\include\c++\3.4.2" -I"C:\Dev-Cpp\include" -L"C:\Dev-Cpp\lib"
C:\Users\Delmellor\Desktop\erh\reht.cpp: 8: error: `fstream' does not name a type

C:\Users\Delmellor\Desktop\erh\reht.cpp: 9: error: expected constructor, destructor, or type conversion before '<' token

C:\Users\Delmellor\Desktop\erh\reht.cpp: 9: error: expected `,' or `;' before '<' token

C:\Users\Delmellor\Desktop\erh\reht.cpp: 10: error: `string' does not name a type

C:\Users\Delmellor\Desktop\erh\reht.cpp: 12: error: expected unqualified-id before "if"

C:\Users\Delmellor\Desktop\erh\reht.cpp: 12: error: expected `,' or `;' before "if"

C:\Users\Delmellor\Desktop\erh\reht.cpp: 17: error: expected unqualified-id before "while"

C:\Users\Delmellor\Desktop\erh\reht.cpp: 17: error: expected `,' or `;' before "while"

C:\Users\Delmellor\Desktop\erh\reht.cpp: 24: error: expected constructor, destructor, or type conversion before '=' token

C:\Users\Delmellor\Desktop\erh\reht.cpp: 24: error: expected `,' or `;' before '=' token

C:\Users\Delmellor\Desktop\erh\reht.cpp: 25: error: expected unqualified-id before "for"

C:\Users\Delmellor\Desktop\erh\reht.cpp: 25: error: expected `,' or `;' before "for"

C:\Users\Delmellor\Desktop\erh\reht.cpp: 25: error: expected constructor, destructor, or type conversion before '!=' token

C:\Users\Delmellor\Desktop\erh\reht.cpp: 25: error: expected `,' or `;' before '!=' token

C:\Users\Delmellor\Desktop\erh\reht.cpp: 25: error: expected unqualified-id before '++' token

C:\Users\Delmellor\Desktop\erh\reht.cpp: 25: error: expected `,' or `;' before '++' token

C:\Users\Delmellor\Desktop\erh\reht.cpp: 34: error: expected constructor, destructor, or type conversion before '.' token

C:\Users\Delmellor\Desktop\erh\reht.cpp: 34: error: expected `,' or `;' before '.' token

C:\Users\Delmellor\Desktop\erh\reht.cpp: 35: error: expected constructor, destructor, or type conversion before '.' token

C:\Users\Delmellor\Desktop\erh\reht.cpp: 35: error: expected `,' or `;' before '.' token

Выполнение завершено.


Как видите, работаю с Dev-C++ 4.9.9.2 ; Подскажите, что нужно добавить, чтобы работало.

2. Как начинающий, пока слабо представляю, что такое классы, ключи и т.п... ну это я почитаю; если будут вопросы - обращусь.
0
 Аватар для BRcr
4043 / 2333 / 292
Регистрация: 03.02.2011
Сообщений: 5,066
Записей в блоге: 10
19.11.2012, 17:52
Инклуды:
C++
1
2
3
4
#include <map>
#include <string>
#include <fstream>
#include <iostream>
Не опознает у тебя string и fstream. Напиши в самом начале функции main указание пространства имен - using namespace std;
Где в Dev-C++ функция system() или ее аналог - не знаю, пошарь по справке или исключи ее из кода.
1
1 / 1 / 0
Регистрация: 18.11.2012
Сообщений: 37
26.11.2012, 09:43  [ТС]
Спасибо Вам большое, Владимир. Всё понятно, кроме одной вещи... Не нашёл конкретную информацию об операции -> в multimap в программе.. Объясните, пожалуйста, как в классе multimap она работает.

И ещё. Вот строки идут через пробел.. а как программа понимает, что через пробел их нужно считывать?
и ещё кое-что.. как переписать программу, чтобы были доступны и другие разделители? запятая, точка с запятой, тире?

Буду очень благодарен.
0
 Аватар для BRcr
4043 / 2333 / 292
Регистрация: 03.02.2011
Сообщений: 5,066
Записей в блоге: 10
26.11.2012, 20:40
Multimap содержит массив шаблонных структур типа pair - в данном случае pair <string, string> - и массив указателей на них. Метод begin() возвращает первый элемент этого массива указателей - он, как и любой другой элемент этого массива, может служить итератором для последовательного доступа ко всем элементам. В итоге итератор it содержит в себе указатель на какой-либо экземпляр структур pair внутри multimap, и применяя к нему оператор ->, мы получаем непосредственный доступ к содержимому данной структуры, например, к полям first и second.
Цитата Сообщение от Delmellor Посмотреть сообщение
И ещё. Вот строки идут через пробел.. а как программа понимает, что через пробел их нужно считывать?
Так уж реализованы потоки - пробел является разделителем по умолчанию.
Цитата Сообщение от Delmellor Посмотреть сообщение
как переписать программу, чтобы были доступны и другие разделители?
Вот так.
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
38
    fstream file_in( "in.txt", ios_base::in ), file_out( "out.txt", ios_base::out ); // открываем файлы с соответствующими режимами
    multimap <string, string> ana_map; // набор пар типа pair<string, string>, с возможностью дубликации ключей
    string str, sorted_str;
 
    if ( !file_in.is_open( ) || !file_out.is_open( ) ) { // если какой-либо из файлов не открыт - ошибка и завершение программы
        cout << "error opening files\n\n";
        system( "pause" );
        return -1;
    }
 
    typedef ctype <TCHAR> ctype_tchar;
    size_t const size = ctype_tchar::table_size;
    // ctype_tchar::mask table[ctype_tchar::table_size] = {ctype_tchar::mask( )};  <--- по идее, так правильней, относительно типа char, но, во-первых, как ни бейся, у меня выпадает ошибка constant expression requared, а во-вторых, нас ведь может больше интересовать wchar_t
    ctype_tchar::mask table[256] = {ctype_tchar::mask( )}; // создаем таблицу масок символов
    table[static_cast <size_t> ( ' ' )] = ctype_tchar::space; // модифицируем маску интересующих нас символов, ассоциируя их с пробелом
    table[static_cast <size_t> ( ',' )] = ctype_tchar::space;
    table[static_cast <size_t> ( '-' )] = ctype_tchar::space;
    table[static_cast <size_t> ( ';' )] = ctype_tchar::space;
    file_in.imbue( locale( file_in.getloc( ), new ctype_tchar( table ) ) ); // модифицируем локаль потока, добавляя созданные нами маски - все, поток будет считать пробелом любой указанный нами символ и соответственно будет обрабатывать его как разделитель
 
    while ( !file_in.eof( ) ) { // заполняем ana_map из потока file_in
        file_in >> str;         // слова, разделенные пробелом, по одному помещаются в str
        sorted_str = str;
        sort( sorted_str.begin( ), sorted_str.end( ) ); // сортируем буквы в строчке sorted_str по возрастанию
        ana_map.insert( pair <string, string> ( sorted_str, str ) ); // вставляем пару строчек в ana_map, где ключом служит сортированная строчка, а значением - исходное слово; простая форма записи типа "ana_map[sorted_str] = str;" у меня не компилируется по причине отсутствия оператора + в данном шаблоне multimap для типа string - хз почему, да и бог с ним
    }
    str = ana_map.begin( )->first;
    for ( multimap <string, string> ::iterator it = ana_map.begin( ); it != ana_map.end( ); ++it ) { // проходим циклом по всем парам в ana_map последовательно, так как они отсортированы внутри по ключу, остается только отсечь лишнее и вывести все остальное :)
        if ( ana_map.count( it->first ) > 1 ) { // отсекаем ключи, встречающиеся один раз
            if ( str != it->first && file_out.tellp( ) ) { // разделяем наборы анаграмм по строчкам: если текущий ключ не равен предыдущему И фокус вывода НЕ находится в начале файла, то выводим в файл перенос строки
                file_out << endl;
            }
            file_out << it->second << " ";
            str = it->first;
        }
    }
    file_in.close( );
    file_out.close( );
1
75 / 36 / 1
Регистрация: 03.08.2012
Сообщений: 447
24.12.2013, 14:57
Подскажите, а функция sort(); как будет реализована? может у кого есть она?)
0
 Аватар для BRcr
4043 / 2333 / 292
Регистрация: 03.02.2011
Сообщений: 5,066
Записей в блоге: 10
24.12.2013, 23:14
Будет реализована где или когда? Это раз.
В библиотеке stl есть она очень даже давно - это два.

Ну, и на добавку, нынешняя реализация, вероятно, выглядит как-то так - Как реализована сортировка в STL.
1
75 / 36 / 1
Регистрация: 03.08.2012
Сообщений: 447
25.12.2013, 07:51
Если она есть, то не подхватила почему-то... спасибо!!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
25.12.2013, 07:51
Помогаю со студенческими работами здесь

Поиск группы символов в строке
Здрасьте люди! Прошу помоч с решение непонятной мне задачи. Задача на тему строковых переменных (String), формулируется так: С...

Замена группы букв в строке.
Дана строка символов.Заменить в ней каждую группу букв &quot;child&quot; группой букв &quot;choldren&quot;.

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

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

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


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru