Использование map в С++

Очень часто на ЕГЭ при решении задач №27(С4)  и на олимпиадах требуется:

• определить количество уникальных слов в тексте, в котором их количество заранее не известно;
• найти частоту появления символов или слов (провести частотный анализ);
• определить по заданному словарю закодированный текст;
• вывести слова в алфавитном порядке. 

Такие задачи можно решить с помощью массива, а еще лучше - с использованием типа map в С++.

map - это параметризованный класс из библиотека STL в С++, который может применяться для описания множества или ассоциированного массива. В этом массиве вместо числового индекса может быть строка (first), а значение элементов массива - количество слов (повторений) в тексте (second). При этом индекс в массиве не может повторяться.

Описание:

map <string, int> L; 

Для вывода элементов массива - используется итератор (указатель на текущий элемент массива):

map <string, int>::iterator it;

Функции по работе с ассоциированным массивом:

1. количество записей (содержимое элемента массива): int p=L.count ( s ); 
2. добавление новой записи со значением 1: L.insert ( pair <string,int> (s, 1) );
   или L[s]=1;
3. поиск записи по строке s: it = L.find(s);
4. удаление записи по итератору: L.erase (it);
5. количество элементов в массиве: int n=L.size();
6. указатель на начало массива: it = L.begin();
7. указатель на конец массива: it = L.end();

Приведем разбор таких заданий (задачи взяты здесь с сохранением нумерации).

44) На электронную почту Вам пришло письмо, подписанное аббревиатурой (первыми буквами фамилии, имени и отчества (далее - ФИО) отправителя). Аббревиатура оказалась Вам незнакома. У Вас есть список всех предполагаемых отправителей, взятый из ранее полученных писем, среди которых различных людей с такой аббревиатурой не больше 10.

Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая определит всех вероятных адресатов – людей, ФИО которых можно сократить до нужной аббревиатуры. ФИО следует выдать в порядке убывания частоты их встречаемости в списке.

На вход программе в первой строке подается аббревиатура – строка, состоящая из трех заглавных латинских букв. Во второй строке находится число N – количество ФИО, полученных в результате анализа почты, не все из них подходят под указанную аббревиатуру. Значение N может быть очень велико. В каждой из следующих N строк записано три слова: Фамилия Имя Отчество соответствующего человека. Слова разделяются одним пробелом. В конце и в начале строки пробелов нет. Все слова записаны заглавными латинскими буквами. Длина ФИО не превышает 100 символов. Гарантируется, что хотя бы один человек с нужной аббревиатурой есть.

Пример входных данных:

IPI
4
IVANOV PETR IVANOVICH
PETROV IVAN IVANOVICH
IVANOV PETR IVANOVICH
ILYIN PETR ILYICH

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

Пример выходных данных для приведенного выше примера входных данных:
IVANOV PETR IVANOVICH 2
ILYIN PETR ILYICH 1

В этом примере map используется для частотного анализа слов.

Программа на С++:

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main()

{

    map<string,int>L;

    int a,n;

    string a1,S,s1,s2,s3;

    cin>>a1;//вводим аббревиатуру

    cin>>n; //вводим количество строк

    for (int i=0;i<n;i++)

    {

      cin>>s1>>s2>>s3; //вводим фамилию, имя, отчество

      S=s1+" "+s2+" "+s3; //образуем строку из фамилии, имени и отчества

      if(s1[0]==a1[0]&&a1[1]==s2[0]&&a1[2]==s3[0]) 

//если аббревиатура совпала, то 

           L[S]++; //добавим в список и/или увеличим счетчик

    }

    map<string,int>::iterator k, it;

    int m, i, l=L.size();

    for(i=0;i<l;i++) //пока есть еще элементы в списке

    {

      m=0;

      for (k=L.begin();k!=L.end();k++) //от начала до конца списка

        if(k->second>m) //если нашли максимальный - запомним

        {

         m=k->second; 

         S=k->first; 

         it=k;

        } 

       cout<<S<<" "<<m<<endl; //выведем

       L.erase(it); //удалим из списка

    }

    return 0;

}

40) Вам необходимо написать программу распознавания чисел, записанных прописью. Сначала на вход программе подается обучающий блок, состоящий из 27 строк. Первые 9 строк содержат слова «один», «два», ..., «девять», следующие 9 строк - слова «одиннадцать», «двенадцать», ... «девятнадцать», следующие 9 строк - слова «десять», «двадцать», ..., «девяносто». Все слова записаны маленькими русскими буквами без лишних пробелов в начале и в конце строки. 

Затем на вход программе подается значение N - количество записей, которые необходимо обработать. Следующие N строк содержат записанные словами числа. Каждое число записано по-русски, маленькими буквами, без ошибок. Если число состоит из нескольких слов, между словами находится ровно один пробел, лишних пробелов в начале и в конце строк нет. 

Напишите эффективную программу, которая определит сумму тех входных чисел, которые находятся в интервале от 1 до 99. 

Размер памяти, которую использует Ваша программа, не должен зависеть от длины исходного списка. 

Пример входных данных (обучающий блок показан в примере с сокращениями):
один
два
…
девяносто
5
двадцать восемь
два миллиона
четырнадцать
сто двадцать три
тысяча девятьсот восемьдесят четыре

Пример выходных данных для приведённого выше примера входных данных:
42 

В данном примере map нам нужен как словарь названий чисел с сохранением его значения.

Программа на С++:

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main()

{

    map<string,int>L;

    int t,i,a,n,m,r=0;

    string s;

//готовим словарь для обозначений чисел

    for(i=1;i<=9;i++)

    { 

       cin>>s;

       L[s]=i;

    } 

    for(i=11;i<=19;i++)

    { 

       cin>>s;

       L[s]=i;

    } 

    for(i=10;i<=90;i=i+10)

    { 

       cin>>s;

       L[s]=i;

    } 

    

    cin>>n; //вводим количество строк

    for (i=0;i<n;i++)

    {

      m=0;//число

      t=1;//флаг для неправильного числа

      do{

         cin>>s;//вводим слово-значение числа

         if (L.count(s)==0)//если слово отсутствует в словаре, то

           t=0;//меняем флаг

         m+=L[s];//собираем число по его значению

      }while (cin.get()!=10); //вводим до конца строки

      if(t==1 && m>=1 && m<100)//если число удовлетворяет условию,то

        r+=m; //добавляем к сумме

    }

    cout<<r; //вывод суммы

    return 0;

}

12) В некотором вузе абитуриенты проходили предварительное тестирование, по результатам которого они могут быть допущены к сдаче вступительных экзаменов в первом потоке. Тестирование проводится по трём предметам, по каждому предмету абитуриент может набрать от 0 100 баллов. При этом к сдаче экзаменов в первом потоке допускаются абитуриенты, набравшие по результатам тестирования не менее 30 баллов по каждому из трёх предметов, причём сумма баллов должна быть не менее 140. На вход программы подаются сведения о результатах предварительного тестирования. Известно, что общее количество участников тестирования не превосходит 500. 

В первой строке вводится количество абитуриентов, принимавших участие в тестировании, N. Далее следуют N строк, имеющих следующий формат: 

<Фамилия> <Имя> <Баллы>

Здесь <Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов, <Баллы> – строка, содержащая два целых числа, разделенных пробелом – баллы, полученные на тестировании по каждому из трёх предметов. При этом <Фамилия> и <Имя>, <Имя> и <Баллы> разделены одним пробелом. Пример входной строки: 

Романов Вельямин 48 39 55

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

В данном примере map нужен для хранения отсортированного массива строк и быстрого его вывода.

Программа на С++:

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main()

{

    map<string,int>L;

    int a1,a2,a3,n,i;

    string S,s1,s2;

    cin>>n; //вводим количество строк

    for (i=0;i<n;i++)

    {

      cin>>s1>>s2>>a1>>a2>>a3; //вводим фамилию, имя и баллы за тест

      S=s1+" "+s2; //образуем строку из фамилии, имени

      

      if(a1>=30 && a2>=30 && a3>=30 && a1+a2+a3>=140) 

//если по баллам проходит в первый тур, то 

           L[S]=1; //добавим в список

    }

    map<string,int>::iterator k;

    for (k=L.begin();k!=L.end();k++) //от начала до конца списка

        сout<<k->first<<endl; //выведем строку

    return 0;

}

4) На вход программы подаются фамилии и имена учеников. Известно, что общее количество учеников не превосходит 100. В первой строке вводится количество учеников, принимавших участие в соревнованиях, N. Далее следуют N строк, имеющих следующий формат: 

<Фамилия> <Имя>

Здесь <Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов. При этом <Фамилия> и <Имя> разделены одним пробелом. Примеры входных строк: 

Иванова Мария
Петров Сергей

Требуется написать программу, которая формирует и печатает уникальный логин для каждого ученика по следующему правилу: если фамилия встречается первый раз, то логин – это данная фамилия, если фамилия встречается второй раз, то логин – это фамилия, в конец которой приписывается число 2 и т.д. Например, для входной последовательности 

Иванова Мария
Петров Сергей
Бойцова Екатерина
Петров Иван
Иванова Наташа 

будут сформированы следующие логины:

Иванова
Петров
Бойцова
Петров2
Иванова2

В данном примере map будет служить для хранения одинаковых фамилий и их повторений, что обеспечит быстрый вывод результата.

Программа на С++:

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main()

{

    map<string,int>L;

    int n,i;

    string s1,s2;

    cin>>n; //вводим количество строк

    for (i=0;i<n;i++)

    {

      cin>>s1>>s2; //вводим фамилию и имя

      L[s1]++; //добавляем в список фамилию и увеличиваем счетчик

      cout<<s1; //выводим фамилию

      if(L[s1]>1) //если фамилия уже встречалась ранее, то

        cout<<L[s1];//выводим порядковый номер

      cout<<endl;

    }

    return 0;

}