понедельник, 4 мая 2015 г.

Использование 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.count(s1)>1) //если фамилия уже встречалась ранее, то
        cout<<L[s1];//выводим порядковый номер
      cout<<endl;
    }
    return 0;
}

1 комментарий: