10008. Что такое криптоанализ?

По заданному тексту выяснить, сколько раз встречаются в нем буквы латинского алфавита.

Вход. Первая строка содержит количество строк n в тексте. Следующие n строк содержат сам текст.

Выход. Каждая выходная строка содержит заглавную букву латинского алфавита, за которой следует ее частота (количество раз, которое она встречается в тексте). Малые и большие буквы считать одинаковыми. Подсчитывать следует только буквы латинского алфавита. Пары (буква, частота) выводить по убыванию частот. Если частоты букв одинаковы, то выводить пары следует в порядке возрастания ASCII кодов букв.

Пример входа

3

This is a test.

Count me 1 2 3 4 5.

Wow!!!! Is this question easy?

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

S 7

T 6

I 5

E 4

O 3

A 2

H 2

N 2

U 2

W 2

C 1

M 1

Q 1

Y 1

РЕШЕНИЕ

обработка текста

Анализ алгоритма

Читаем посимвольно входной текст, подсчитываем частоты букв. Сортируем пары (буква, частота) по убыванию частот. Если буквы имеют одинаковые частоты, то такие пары сортируем по возрастанию ASCII кодов букв.

Реализация алгоритма

Посимвольно (в переменную ch) читаем входной текст, пока не встретим символ конца файла (EOF). Первую строку, содержащую количество строк в тексте, считываем в массив line и далее нигде не используем. В отображении m будем подсчитывать частоту букв (m содержит набор пар “символ, частота”).

char ch,line[10];

map<char,int> m;

Для каждого входного символа ch проверяем, является ли он буквой. Если ch буква, то переводим его в верхний регистр и увеличиваем на единицу значение m[toupper(ch)].

gets(line);

while((ch = getc(stdin)) != EOF)

if(isalpha(ch)) m[toupper(ch)]++;

С помощью конструктора копирования преобразуем пары “символ, частота” из отображения в вектор и отсортируем его по убыванию частот.

vector<pair<char,int> > v(m.begin(),m.end());

sort(v.begin(),v.end(),f);

Выводим символы и их частоты в требуемом порядке

for(int i = 0; i < v.size(); i++)

printf("%c %d\n",v[i].first,v[i].second);

Функция сортировки f согласно описанному условию имеет вид:

int f(pair<char,int> a, pair<char,int> b)

{

return a.second > b.second;

}