На вход программе подаются строчные английские буквы. Ввод этих символов заканчивается точкой (другие символы, отличные от «.» и букв «а»..«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