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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ помогите определить баг или недочёт в программе. http://www.cyberforum.ru/cpp-beginners/thread366958.html
Задача ввести с клавиатуры массив и вывести на экран наибольший его элемент. Проблема заключается в if когда s<mas он всё время перескакивает на else вместо s=mas. #include <stdio.h> #include...
C++ Динамическое выделение памяти Подскажите как выделить динамически память мод двумерный массив... Спасибо. ... int *mass = new int ; //int *mass = new int ; ) Не работает... ... http://www.cyberforum.ru/cpp-beginners/thread366957.html
unistd.h C++
как добавить unistd.h в биб Visual studio ??? закидываю в папку с проектом читается не правильно (((
C++ Целочисленная арифметика
Добрый вечер. Пропустил практику по информатике, не понимаю по какому принципу решать задачу. Собственно вот: тема - целочисленная арифметика. Задание: дано вещественное число...
C++ error LNK2019: ссылка на неразрешенный внешний символ Что это? http://www.cyberforum.ru/cpp-beginners/thread366911.html
Всем доброго вечера что это такое за непонятная ошибка? error LNK2019: ссылка на неразрешенный внешний символ и Ошибка 2 fatal error LNK1120: 1 неразрешенных внешних элементов ...
C++ Запуск/Создание Windows Form в Win32 приложение ! Здравствуйте! Использую Visual Studio 2010. Учусь делать приложение игру на директх. Вопрос такой как запустить Форму видоус формс в вин32 приложении? Где его создать ? Как добавить в проект? Как... подробнее

Показать сообщение отдельно
talis
791 / 543 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
16.10.2011, 13:19
Вот, решил через связность. Алгоритм, конечно, жуткий и жадный на память и ресурсы, но что придумал.

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
 
/* определяет равенство строк по количеству вхождений каждой *
 * буквы в эту строку. пробелы цифры и пр. игнорируются      */
bool letter_cmp( const std::string &a, const std::string &b )
{
    unsigned count_a[ 'z' - 'a' + 1 ] = {0}; // количество вхождений букв в строку а
    unsigned count_b[ 'z' - 'a' + 1 ] = {0}; // количество вхождений букв в строку b
 
    // считаем a
    for( int i = 0; i < a.size(); i++ )
    {
        if( isalpha( a[i] ) )
           count_a[ 'z' - tolower( a[i] ) ]++;
    }
 
    // считаем b
    for( int i = 0; i < b.size(); i++ )
    {
        if( isalpha( b[i] ) )
           count_b[ 'z' - tolower( b[i] ) ]++;
    }
 
    // проверяем равенство вхождений каждой буквы
    for( int i = 0; i < 'z' - 'a'; i++ )
    {
        if( count_a[i] != count_b[i] )
           return false; // если количество вхождений этой буквы отличается, возвращаем false
    }
 
    return true; // если все вхождения равны, возвращаем true
}
 
int main()
{
    std::vector<std::string> lines; // здесь хранятся строки файла
    std::string input; // сюда вводится новая строка из файла
 
    // ---------- читаем весь файл ---------
    std::ifstream fs( "in.txt" );
 
    if( !fs.is_open() )
    {
       std::cerr << "error opening in.txt\n";
       return -1;
    }
 
    while( fs >> input )
       lines.push_back( input );
 
    fs.close();
 
    std::cout << "done reading " << lines.size() << " words\n\n";
 
    // ---- заполняем вектор связности -----
    std::vector<int> connectivity( lines.size() );
 
    for( int i = 0; i < lines.size(); i++ )
       connectivity[i] = i;
 
    // ---- определяем связность -----------
 
    for( int i = 0; i < lines.size(); i++ ) // проходим все строки
    {
        for( int u = 0; u < lines.size(); u++ ) // n*n раз
        {
            if( connectivity[i] != connectivity[u] ) // если эти две строки уже связаны, пропускаем их
            {
                if( letter_cmp( lines[i], lines[u] ) ) // иначе если строки равны по количеству вхождений букв
                {
                    // связываем их
                    int old_i = connectivity[i]; // старое значение ключа
 
                    for( int j = 0; j < connectivity.size(); j++ )
                    {
                        if( connectivity[j] == old_i ) // везде, где ключ старый
                           connectivity[j] = connectivity[u]; // меняем его на новый
                    }
                }
            }
        }
    }
 
    // ---- выводим все связанные слова ------
    for( int i = 0; i < connectivity.size(); i++ )
    {
        unsigned int out = 0;
 
        if( std::count( connectivity.begin(), connectivity.end(), i ) > 1 )
        {
            for( int u = 0; u < connectivity.size(); u++ )
            {
               if( connectivity[u] == i )
               {
                  if( out )
                     std::cout << ", ";
 
                  std::cout << lines[u];
                  out++;
               }
            }
 
            if( out )
               std::cout << '\n';
        }
    }
 
    return 0;
}
Интересно было бы увидеть более красивое решение.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru