Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 40, средняя оценка - 4.73
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
#1

Поиск анаграмм - C++

16.10.2011, 02:01. Просмотров 5585. Ответов 23
Метки нет (Все метки)

Доброй ночи!
Такая задачка... Возможно многим знакома по Золотому байту. Я в самом начале изучения С++ и до конца не могу разобраться.
Есть файл "in.txt" с каким-либо списком слов (до 10000). Одна строка - одно слово.
Нужно найти все анаграммы и вывести их в файл "out.txt".
Например во входном файле:
kot
polet
tok
leto
teplo
kto
zima

Тогда на выходе:
kot
tok
kto
polet
teplo

Примерно так...
Во время первого считывания файла я определяю кол-во строк. Затем создаю массив строк.
Далее сортирую буквы в словах.
Это сделал. Вроде и дальше понимаю путь (с помощью strcmp ищем дубликаты). Но на деле не получается. Не пойму , как обратно отсортировать. Или какой другой алгоритм нужен. И как в файл записать... Классы не использовать.
Посмотрите код и помогите пожалуйста.
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
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<iostream>
#include <cstdlib>
#include<stdio.h>
#include <iomanip>
#include<cctype>
#include<cstring>
using namespace std;
void BubbleSort1(char[],int);
int main()
{
    setlocale(LC_ALL,"rus");
    FILE *file;
    char str[255];
    int N,M=0;
    if((file=fopen("in.txt", "r"))!=NULL)
    {
    do
        {
            fgets(str,255,file);
            M++;
        } while(!feof(file));
        fclose(file);
    }
    else
    {
        cout<<"File not found"<<endl;
    }
    char **mas = new char*[M];
    for(int i=0;i<M;i++)
    {
        mas[i]=new char[255];
    }
    if((file=fopen("in.txt", "r"))!=NULL)
    {
        for(int i=0;i<M;i++)
        {
            fgets(mas[i],255,file);
        }
        fclose(file);
    }
    else
    {
        cout<<"Error";
    }
    for(int i=0;i<M;i++)
    {
        cout<<mas[i];
    }
    cout<<"\n\n";
    for(int i=0;i<M;i++)
    {
        N=strlen(mas[i]);
        BubbleSort1(mas[i],N);
    }
    for(int i=0; i<M-1; i++)
    {
        cout<<mas[i];
    }
    cout<<"\n\n";
    for(int i=0;i<M;i++)
    {
        char*y=mas[i];
        for(int j=i+1;j<M;j++)
        {
            if(strcmp(y,mas[j])==0)
            {
                cout<<y;
            }
        }
    }
    cout<<endl;
    system("pause");
    return 0;
}
void BubbleSort1(char*mas,int M)
{
    bool sort=true;
    while(sort)
    {
        sort=false;
        for(int i=0;i<M-1;i++)
        {
            if(mas[i]>mas[i+1])
            {
                int x=mas[i];
                mas[i]=mas[i+1];
                mas[i+1]=x;
                sort=true;
            }
        }
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.10.2011, 02:01
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск анаграмм (C++):

Строка: Поиск анаграмм - C++
Дана строка длиной не более 255 символов, в которой вписаны слова, разделенные пробелами (словом считается любой набор букв и цифр). ...

Поиск анаграмм во входном файле - C++
Условие. В заданном алфавите слов найти все анаграммы. Входные данные. Есть файл &quot;input.txt&quot; в нем список слов. Выходные данные....

Комбинаторика, количество анаграмм - C++
Здравствуйте, решаю задачу, но не знаю какой цикл использовать и как его задать. Суть задачи проста, в консоль вводят слово, далее...

Группы анаграмм в строке - C++
Всем доброго времени суток. Я в С++ начинающий. Есть задача, которую не получается написать; не получается скорее по причине...

Вычислить количество слов анаграмм (Слова которые состоят из одних и тех же букв) - C++
Дано предложение, необходимо посчитать количество анаграмм в этом предложении. Пример: Ввод: abc cba two abcc. Вывод: 2. (это...

Поиск символа не могу переделать под поиск сочетания символов - C++
Есть код программы на поиск и замену по одному символу.Не могу понять, как сделать код на поиск сочетания символов. Чтобы найдя в введённой...

23
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
16.10.2011, 16:00  [ТС] #16
Непростая задача для меня, который программирование всего пару месяцев изучает.
Если даже у людей с опытом не все получается.

talis, код работает. А как его можно переделать, чтобы использовать using namespace std:
и чтобы в конце в файл записать? И еще - vector обязателен?
Мне главное понять, а не чтобы за меня написали. Да вот без примера понять не получается...
Может еще кто вариантов подкинет. Когда видишь код, то и понимание быстрее приходит.
Кстати, сделал входной файл на 50 слов.
0
Вложения
Тип файла: txt in.txt (391 байт, 17 просмотров)
talis
792 / 544 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
16.10.2011, 16:05 #17
slavik, вариант Deviaphan лучше, используйте его.

Добавлено через 49 секунд
vector - это, считайте, тот же массив, только саморасширяющийся. Можно без него, но зачем?
1
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
16.10.2011, 16:12  [ТС] #18
Цитата Сообщение от talis Посмотреть сообщение
slavik, вариант Deviaphan лучше, используйте его.
Еще бы понять, как его реализовать...
0
talis
792 / 544 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
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
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
17.10.2011, 08:40  [ТС] #20
буду рыться...

Добавлено через 4 часа 4 минуты

бьюсь - не получается...
А можно доделать тот код программы, который я написал (см. в начале)?
Дело в том, что препод хотел именно так, хоть по другому и красивей.
Да и не учили мы еще всего остального.
А там я хоть алгоритм понимаю. С технической частью проблемы.
Люди, help...
Помогите написать работающий код...

Добавлено через 12 часов 9 минут
sos...sos...sos...
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
17.10.2011, 18:08 #21
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
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
/////////////////////////////////////////////////////////////////////////////////////////
//Есть файл "in.txt" с каким-либо списком слов (до 10000). Одна строка - одно слово.
//Нужно найти все анаграммы и вывести их в файл "out.txt".
//Например во входном файле:
//kot
//polet
//tok
//leto
//teplo
//kto
//zima
//
//Тогда на выходе:
//kot
//tok
//kto
//polet
//teplo
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <fstream>
#include <functional>
#include <iostream>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
typedef std::set<char>  T_char_set;
/////////////////////////////////////////////////////////////////////////////////////////
struct T_anagrams_less : public std::binary_function<const T_str&, const T_str&, bool>
{
    bool operator() 
        (
            const T_str&  A,
            const T_str&  B
        )
    {
        return      T_char_set( A.begin(), A.end() )
                <   T_char_set( B.begin(), B.end() );
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::multiset<T_str, T_anagrams_less>  T_anagrams;
/////////////////////////////////////////////////////////////////////////////////////////
void  find_anagrams
    (
        const T_str&  ifilename,
        const T_str&  ofilename
    )
{
    std::ifstream   ifile( ifilename.c_str() );    
    T_anagrams      anagrams;
 
    std::copy
        (
            std::istream_iterator<T_str>(ifile),
            std::istream_iterator<T_str>(),
            std::inserter( anagrams, anagrams.begin() )      
        );
 
    std::ofstream   ofile( ofilename.c_str() );
    for(T_anagrams::const_iterator  anagr_it = anagrams.begin();
        anagr_it != anagrams.end(); ++anagr_it)
    {
        if(anagrams.count(*anagr_it) == 1) continue;
        ofile << *anagr_it
              << std::endl;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{    
    find_anagrams("in.txt", "out.txt");
}
1
slavik
0 / 0 / 0
Регистрация: 11.09.2011
Сообщений: 15
17.10.2011, 20:48  [ТС] #22
Всем спасибо!
Есть такой вопрос... А можно ли вообще написать эту программу по тому алгоритму, который я описывал в начале?
А то он у меня не получается.
Ваши решения , конечно, намного красивей и изящней.
Просто интересует можно ли это в принципе. И если можно то как...
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
17.10.2011, 22:50 #23
Пардон, в мою программу вкралась ошибка. Вот так правильно:
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
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
/////////////////////////////////////////////////////////////////////////////////////////
//Есть файл "in.txt" с каким-либо списком слов (до 10000). Одна строка - одно слово.
//Нужно найти все анаграммы и вывести их в файл "out.txt".
//Например во входном файле:
//kot
//polet
//tok
//leto
//teplo
//kto
//zima
//
//Тогда на выходе:
//kot
//tok
//kto
//polet
//teplo
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <fstream>
#include <functional>
#include <iostream>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string             T_str;
typedef std::multiset<char>     T_char_multiset;
/////////////////////////////////////////////////////////////////////////////////////////
struct T_anagrams_less : public std::binary_function<const T_str&, const T_str&, bool>
{
    bool operator() 
        (
            const T_str&  A,
            const T_str&  B
        )
    {
        return      T_char_multiset( A.begin(), A.end() )
                <   T_char_multiset( B.begin(), B.end() );
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::multiset<T_str, T_anagrams_less>  T_anagrams;
/////////////////////////////////////////////////////////////////////////////////////////
void  find_anagrams
    (
        const T_str&  ifilename,
        const T_str&  ofilename
    )
{
    std::ifstream   ifile( ifilename.c_str() );    
    T_anagrams      anagrams;
 
    std::copy
        (
            std::istream_iterator<T_str>(ifile),
            std::istream_iterator<T_str>(),
            std::inserter( anagrams, anagrams.begin() )      
        );
 
    std::ofstream   ofile( ofilename.c_str() );
    for(T_anagrams::const_iterator  anagr_it = anagrams.begin();
        anagr_it != anagrams.end(); ++anagr_it)
    {
        if(anagrams.count(*anagr_it) == 1) continue;
        ofile << *anagr_it
              << std::endl;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{    
    find_anagrams("in.txt", "out.txt");
}
1
isaak
103 / 40 / 9
Регистрация: 17.10.2010
Сообщений: 670
09.03.2012, 13:06 #24
Подскажите пожалуйста как исправить ошибки, чтобы компилятор не ругался:

1 IntelliSense: namespace "std" has no member "istream_iterator" c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 37 18 Searching anagram
2 IntelliSense: type name is not allowed c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 37 35 Searching anagram
3 IntelliSense: namespace "std" has no member "istream_iterator" c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 38 18 Searching anagram
4 IntelliSense: type name is not allowed c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 38 35 Searching anagram
5 IntelliSense: expected an expression c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 38 42 Searching anagram
6 IntelliSense: namespace "std" has no member "inserter" c:\users\администратор\documents\visual studio 2010\projects\c++\console\p1644\searching anagram\searching anagram\searching anagram.cpp 39 18 Searching anagram

Заранее огромное спасибо!!!!
0
09.03.2012, 13:06
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.03.2012, 13:06
Привет! Вот еще темы с ответами:

Реализовать поиск заданного файла в древе каталогов и поиск указанной информации в этом файле - C++
Имеется много папок в каждой папке есть файл proc.txt, как можно по всем этим папкам пройтись и из каждой папки в этом файле достать...

Поиск циклов в графе. Поиск центра взвешенного графа - C++
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?

Поиск числа в двумерном массиве (бинарный поиск) - C++
Произвожу поиск элемента в массиве двумя способами: линейным(последовательным) поиском и бинарным(двоичным). Первый работает на ура. Второй...

Поиск пикселя и поиск изображения на экране - C++
Переписываю код из clickermann для запуска его на C++. Мне нужны две функции которые выполняли бы сканирование экрана и поиск пикселя...


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

Или воспользуйтесь поиском по форуму:
24
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.