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

С++ «Неделя вторая - Контейнер set - Синонимы» #15

Войти
Регистрация
Восстановить пароль
Оценить эту запись

С++ «Неделя вторая - Контейнер set - Синонимы» #15

Запись от acmades размещена 01.08.2017 в 04:21

Привет, привет.
Продолжаю решать курс: «Основы разработки на C++: белый пояс». Сегодня несколько задач и столько же решений по контейнеру set.
Задача 1: Количество уникальных строк.
Дан набор строк. Найдите количество уникальных строк в этом наборе.

Формат ввода
Сначала вводится количество строк N, затем — сами N строк, разделённые пробелом. Все строки состоят лишь из латинских букв, цифр и символов подчёркивания.

Формат вывода
Выведите единственное целое число — количество уникальных строк в данном наборе.

Пример:
Ввод
6
first
second
first
third
second
second

Вывод
3
Моё решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*Неделя вторая - Контейнер set - Количество уникальных строк*/
#include <iostream>
#include <string>
#include <set>
using namespace std;
 
 
int main() {
    int Q;
    string str;
    set<string> bs;
    cin >> Q; //узнаем склолько команд будет
    for (Q; Q > 0; Q--) {
        cin >> str;
        bs.insert(str);//вставляем в set
    }
    cout << bs.size(); //узнаем размер, вот и все
    return 0;
}
Задача 2: Множество значений словаря
Напишите функцию BuildMapValuesSet, принимающую на вход словарь map<int, string> и возвращающую множество значений этого словаря
set<string> BuildMapValuesSet(const map<int, string>& m) {
// ...
}
Пример:
Код
set<string> values = BuildMapValuesSet({
{1, "odd"},
{2, "even"},
{3, "odd"},
{4, "even"},
{5, "odd"}
});
for (const string& value : values) {
cout << value << endl;
}
Вывод
even
odd

Моё решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*Неделя вторая - Контейнер set - Множество значений словаря*/
#include <iostream>
#include <string>
#include <map>
#include <set>
using namespace std;
 
set<string> BuildMapValuesSet(const map<int, string>& m) {
    set<string> s;
    for (auto i : m) {
        s.insert(i.second);
    }
    return s;
}
Задача 3: Синонимы
Два слова называются синонимами друг друга, если они имеют похожие значения. Реализуйте следующие операции над словарём синонимов:
ADD word1 word2 — добавить в словарь пару синонимов (word1, word2).
COUNT word — узнать количество синонимов слова word.
CHECK word1 word2 — проверить, являются ли слова word1 и word2 синонимами. Слова word1 и word2 считаются синонимами, если среди запросов ADD был хотя бы один запрос ADD word1 word2 или ADD word2 word1.

Формат ввода
Сначала вводится количество запросов Q, затем Q строк с описаниями запросов. Гарантируется, что в каждом запросе CHECK и ADD слова word1 и word2 различны. Все слова состоят лишь из латинских букв, цифр и символов подчёркивания.

Формат вывода
Для каждого запроса в соответствующей строке выведите ответ на него:
В ответ на запрос COUNT word выведите единственное целое число — количество синонимов слова word.
В ответ на запрос CHECK word1 word2 выведите строку YES, если word1 и word2 являются синонимами, и NO в противном случае.

Пример:
Ввод
8
ADD program code
COUNT cipher
ADD code cipher
COUNT code
COUNT program
CHECK code program
CHECK program cipher
CHECK cpp java

Вывод
0
2
1
YES
NO
NO

Моё решение:
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
/*Неделя вторая - Контейнер set - Синонимы*/
#include <iostream>
#include <string>
#include <set>
#include <map>
using namespace std;
using sorted_pair = pair<string, string>; //тут я решил намудрить, немного не по курсу. Так будут пары слов храниться
sorted_pair make_sorted_pair(const std::string& word1, const string& word2) { //эта функция будет возвращать отсортированные пары слов
    return (word1 <= word2) ? make_pair(word1, word2) : make_pair(word2, word1); //тут сортировка
}
bool check(const set<sorted_pair>& synonyms, const string& word1, const string& word2) { //тут возвращаем...
    return synonyms.count(make_sorted_pair(word1, word2)) != 0; //есть ли такая пара слов уже или нет
}
void add(set<sorted_pair>& synonyms, map<string, unsigned>& synonyms_count, const string& word1, const string& word2) {
    if (check(synonyms, word1, word2)) return;  //если синоним уже есть, то ничего не добавляем выходим
    ++synonyms_count[word1]; //если нет таких синонимов, то приплюсуем к каждому слову
    ++synonyms_count[word2];
    synonyms.insert(make_sorted_pair(word1, word2)); //и добавим эти синонимы
    
}
int main() {
    set<sorted_pair> synonyms;  // пары синонимов  
    map<string, unsigned> synonyms_count;  // количество синонимов
    int i;
    string comand, word1, word2;
    cin >> i; //количество запросов
    for (i; i > 0; i--) {
        cin >> comand; //считываем команду
        if (comand == "ADD") { //проверяем какая команда пришла
            cin >> word1 >> word2; //считываем слова
            add(synonyms, synonyms_count, word1, word2); //идем в функцию добавления
        }
        else if (comand == "COUNT") {
            string word;
            cin >> word; //считываем слово
            cout << synonyms_count[word] << endl; //проверим какая цифра стоит для этого слова
        }
        else if (comand == "CHECK") {
            string word1, word2;
            cin >> word1 >> word2; //прочитали слова
 
            if (check(synonyms, word1, word2)){ //если функция вернет true, то
                cout << "YES" << endl; //пишем Да
            }
            else cout << "NO" << endl; //иначе НЕТ
        }
    }
    return 0;
}
Задача 4: Автобусные остановки.
В этой задаче вам нужно присваивать номера автобусным маршрутам.
А именно, для каждого маршрута, заданного множеством названий остановок, нужно либо выдать новый номер (первому маршруту — 1, второму — 2 и т. д.), либо вернуть номер существующего маршрута, которому соответствует такое множество остановок.
В отличие от задачи «Автобусные остановки — 2», наборы остановок, которые можно получить друг из друга перестановкой элементов или добавлением/удалением повторяющихся, следует считать одинаковыми.

Формат ввода
Сначала вводится количество запросов Q, затем Q описаний запросов.
Каждый запрос представляет собой положительное количество остановок N, за которым следуют разделённые пробелом N названий остановок соответствующего маршрута (не обязательно различных). Названия остановок состоят лишь из латинских букв и символов подчёркивания.

Формат вывода
Выведите ответ на каждый запрос в отдельной строке.
Если маршрут с данным набором остановок уже существует, в ответ на соответствующий запрос выведите Already exists for i, где i — номер маршрута с таким набором остановок. В противном случае нужно выделить введённому набору остановок новый номер i и вывести его в формате New bus i.

Пример:

Ввод
5
2 Marushkino Kokoshkino
1 Kokoshkino
2 Marushkino Kokoshkino
2 Kokoshkino Marushkino
2 Kokoshkino Kokoshkino

Вывод
New bus 1
New bus 2
Already exists for 1
Already exists for 1
Already exists for 2
Моё решение:
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
#include <iostream>
#include <string>
#include <set>
#include <map>
using namespace std;
int main() {
    set<string> bus_stops; //сюда будем остановки складывать
    map<set<string>, int> marshrut;//каждому набору остановок будем давать номер маршрута
    int i, count_stop, number_marshrut = 0;
    string stop;
    cin >> i; //количество запросов
    for (i; i > 0; i--) {
        cin >> count_stop; //количество остановок
        for (count_stop; count_stop > 0; --count_stop) {
            cin >> stop; //читаем остановки
            bus_stops.insert(stop); //и добавляем в набор остановок
        }
        if (!marshrut.count(bus_stops)) { //проверяем наличие данного набора остановок и если не нашли
            marshrut[bus_stops] = ++number_marshrut; //то добавляем набор и приписываем новый маршрут по-порядку
            cout << "New bus " << number_marshrut << endl; //пишем номер нового маршрута
        }
        else { //иначе, если есть такой набор
            cout << "Already exists for " << marshrut[bus_stops] << endl; //пишем номер существующего маршрута
        }
        bus_stops.clear(); //очистим набор остановок
    }
    return 0;
}
Вроде бы пока не сложно. Спасибо что читаете этот блог )))))
Всего комментариев 3

Комментарии

  1. Старый комментарий
    C++
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    
    #include <iostream>
    #include <set>
    #include <string>
     
    using namespace std;
     
    int main()
    {
        set<string> str_set;
        string s="";
        int n = 0;
        cin >> n;
        for (int i=0;i<n;i++){
            cin >> s;
            str_set.insert(s);
        }
        cout << str_set.size() << endl;
        return 0;
    }
    Запись от flash_back размещена 12.10.2017 в 13:04 flash_back вне форума
  2. Старый комментарий
    Цитата:
    Сообщение от flash_back Просмотреть комментарий
    C++
    1
    2
    
        string s=""; /*согласен */
        int n = 0; /*переменные лучше сразу инициализировать*/
    Инициализировать переменные при объявлении - хорошая штука )))
    Запись от acmades размещена 12.10.2017 в 19:21 acmades вне форума
  3. Старый комментарий
    Аватар для Avazart
    Да причем объявлять именно непосредственно перед использованием. Т.е. максимально локализовывать.
    Потом легче разобраться в коде и его редактировать.
    Запись от Avazart размещена 12.10.2017 в 20:17 Avazart на форуме
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru