Тип Д19 C4 № 3654 
Обработка символьных строк. Последовательности букв и чисел
i
На вход программе подаются строчные английские буквы. Ввод этих символов заканчивается точкой (другие символы, отличные от «.» и букв «а»..«z», во входных данных отсутствуют; в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка). Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет печатать буквы, встречающиеся во входной последовательности, в порядке увеличения частоты их встречаемости. Каждая буква должна быть распечатана один раз. Точка при этом не учитывается. Если какие-то буквы встречаются одинаковое число раз, то они выводятся в алфавитном порядке.
Например, пусть на вход подаются следующие символы:
baobaba.
В данном случае программа должна вывести
oab
Решение. Программа читает все входные символы до точки один раз, подсчитывая в массиве, хранящем 26 целых чисел, количество каждой из букв.
Сами входные символы при этом не запоминаются. В дополнительный массив, состоящий из 26 символов, заносятся буквы от «а» до «z». Затем элементы первого массива сортируются по неубыванию любым алгоритмом сортировки, параллельно переставляются и элементы второго массива (возможно использование одного массива записей, состоящих из двух полей). При этом элементы с равным числом вхождений символов местами не меняются. Во втором из отсортированных массивов пропускаются элементы, количество которых равно 0, остальные элементы печатаются подряд.
Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, для строк, состоящих не более чем из 255 символов).
Пример правильной и эффективной программы на языке Паскаль:
var а:array[0..25] of integer;
m:array[0..25] of 'a'..'z';
с: char;
i, j, k: integer;
begin
for i:=0 to 25 do
begin
a[i]: =0;
m[i] :=chr(ord(' a ')+i)
end;
read(c);
while c<> ' . ' do
begin
a[ord(c)-ord('a')] := a[ord(c)-ord('a')] + 1;
read(c);
end;
for i:=1 to 25 do
for j := 0 to 24 do
if a[j1 > a[j +1] then
begin
k:=а[j]; с:=m[j];
а[j]:=а[j+1]; m[j]:=m[j+1];
a[j + 1] :=k; m[j+1] :=c
end;
i : =0;
while a[i]=0 do i:=i+1;
for j:=i to 25 do
write(m[j]);
writeln
end.
Пример правильной и эффективной программы на языке Бейсик:
DIM i, j, k, а (26) AS INTEGER
DIM s (26) AS STRING * 1
FOR i = 1 TO 26
a (i) = 0
s(i) = CHR$(ASC("a") + i - 1)
NEXT i
INPUT c$
DO WHILE NOT (c$ = ".")
a(ASC (c$) - ASC("a") + 1) =
= a(ASC(c$) - ASC("a") + 1) + 1
INPUT c$
LOOP
FOR j = 1 TO 25
FOR i = 1 TO 25
IF a(i) > a(i + 1) THEN
k = a (i)
c$ = s(i)
a (i) = a (i + 1)
s(i) = s (i + 1)
a (i + 1) = k
s(i + 1) = c$
ENDIF
NEXT i
NEXT j i = 1
DO WHILE a(i) =0
i = i + 1 LOOP
FOR j = i TO 26
PRINT s(j ) ;
NEXT j
END
Критерии проверки:| Критерии оценивания выполнения задания | Баллы |
|---|
| Программа работает верно, т. е. определяет верно определяет частоту встречающихся букв, для любых входных данных произвольного размера, просматривает входные данные один раз, не содержит вложенных циклов, в тексте программы не анализируется каждая английская буква в отдельности. Допускается наличие одной синтаксической ошибки. | 4 |
| Программа составлена верно, но содержит нерациональности: входные данные запоминаются в массиве символов или строке или входной поток просматривается несколько раз, программа может содержать вложенные циклы. Допускается наличие не более трех синтаксических ошибок. | 3 |
| Программа составлена в целом верно с вложенными циклами или без, или обрабатывает каждую букву явным образом (26 или 52 оператора IF или оператор CASE, содержащий 26 или 52 вариантов), но, возможно, выводит значение не первой по алфавиту из искомых букв. Возможно в реализации алгоритма содержатся 1–2 ошибки (используется знак «<» вместо «>», «or» вместо «and» и т. п.). Возможно, некорректно организована работа со входным файлом. Допускается наличие не более пяти синтаксических ошибок. | 2 |
| Программа, возможно, неверно работает при некоторых входных данных, но по приведенному тексту решения ясно, что экзаменуемый понимает, из каких этапов должно состоять решение задачи. Программа, возможно, неверно обрабатывает некоторые входные данные, например, отсутствует или предложен некорректный алгоритм обработки строчных или прописных букв, или они подсчитываются по отдельности, или программа содержит ошибку в алгоритме поиска максимума. Возможно, выводит только искомую букву и не выводит количество букв. Допускается наличие не более семи синтаксических ошибок. | 1 |
| Задание не выполнено или выполнено неверно | 0 |
| Максимальный балл | 4 |
PDF-версии: