Разбор задачи C4 – работа с символами
Создание: 29.03.2013

Одна из классических задач части C4 ЕГЭ по информатике – задание на обработку символов. В этом материалы мы повторим теорию, что нужно знать про ASCII и разберем соответствующую программу.

Текст задачи

Задача из демонстрационной части ЕГЭ по информатики за 2011 год.

На вход программе подается набор символов, заканчивающийся точкой. Напишите эффективную, в том числе и по используемой памяти, программу, которая сначала будет определять, есть ли в этом наборе символы, соответствующие десятичным цифрам. Если такие символы есть, то можно ли переставить их так, чтобы полученное число было симметричным (читалось одинаково как слева направо, так и справа налево). Ведущих нулей в числе быть не должно, исключение – число 0, запись которого содержит ровно один ноль.

Если требуемое число составить невозможно, то программа должна вывести на экран слово «NO». А если возможно, то в первой строке следует вывести слово «YES», а во второй – искомое симметричное число. Если таких чисел несколько, то программа должна выводить максимальное из них. Например, пусть на вход подаются следующие символы:

Do not 911 to 09 do.

В данном случае программа должна вывести

YES
91019

Анализ задачи

При всей «навороченности» сюжета, задача проще чем кажется вначале. Вас спрашивают: можно ли из заданных цифр составить палиндром, т.е. такое число, которое читается одинаково слева направо и справа налево. Прежде чем выделить общее правило палиндрома приведем несколько примеров:

12323 да, цифры можно записать: 32123
1212522411 нет, цифры 5 и 4 встречаются нечетное число раз, а значит, их нельзя «расположить» в центре нового числа.  
109091 да, так как количество всех цифр четное 910019
001 нельзя, так как числа, начинающегося с нуля нет  

итак, симметричным число может быть в случае:

  • все цифры встречаются четное число раз
  • число, встречающееся нечетное число, раз должно быть одно
  • если число 0 встречается нечетное число раз, должны быть другие числа в этом числе или 0 – единственное число.

Так как в задачи сказано, что симметричное число должно быть максимальным, выводить цифры мы должны от 9 до 0.

Теория

Что нужно знать для работы с символами в языке Pascal:

  • Символы в ASCII коде имеют десятичные коды в интервале от 0 до 255.
  • Первые 32 кода [0..31] заняты под спецсимволы.
  • неизменная часть кодовой таблицы куда входят латинские буквы, цифры и знаки препинания находятся в первой половине кодовой таблице (коды до 127).
  • Латинские буквы и цифры идут в ASCII коде последовательно, именно поэтому они относятся к перечисляемым типам.
  • Запоминать код символов необязательно. Вы всегда можете воспользоваться командой ord(‘A’), которая возвращает код первого символа алфавита, от него можно получить код любого другого символа.

    Например:
    c0 := ord(‘0’);
    c9:=c0+9;
    Переменная c0 примет значение кода символа 0 (48). Переменная c9 примет значение, превышающее c0 на 9, это код символа 9 (57).

  • Обратная операция – получение символа из его кода: chr(код). Например,
    ch := chr(55); // ch примет значение символа ‘7’.

Программа

program palindrom;
var ch: char;
    c0,c9:integer;
    i,j,k,cod,n_odd,i_odd: integer;
    m:array[0..9] of integer;
begin
  c0 := ord('0');
  c9 :=c0+9;
  // ввод строки посимвольно
  while ch<>'.' do
  begin
    read(ch);
    cod:=ord(ch);
    if ((cod>=c0) and (cod<=c9)) then m[cod-c0] := m[cod-c0] + 1;
  end;
 
  // анализируем массив цифр
  n_odd := 0; k:=0;
  for i:=0 to 9 do
  begin
     if (m[i] <> 0) then k:=k+1; // узнаем количество разных цифр
     if( ((m[i] mod 2) = 1) and (m[i] <> 0) ) then
     begin
       n_odd := n_odd + 1; // количество нечетных цифр
       i_odd:=i;           // номер нечетной цифры
     end;
  end;
   // проверяем на существование палиндрома
  if ( (n_odd>1) or ( (i_odd=0) and (m[0]>1) and (k=1) ) or (k=0) )then writeln('NO')
  else
  begin
     writeln('YES');
     // печатаем левую часть палиндрома каждая цифра выводится "половину раз"
     for i:=9 downto 0 do
     begin
       if( (m[i]<>0) and (i<>i_odd) ) then
       for j:=1 to (m[i] div 2) do write(chr(i+c0));
     end;
     // выводим "нечетную цифру" нужное количество раз
     for j:=1 to m[i_odd] do
       write(chr(i_odd+c0));
     // печатаем правую часть палиндрома
     for i:=0 to 9 do
     begin
       if( (m[i]<>0) and (i<>i_odd) ) then
       for j:=1 to (m[i] div 2) do write(chr(i+c0));
     end;
  end;
end.

Программа написана и протестирована в среде Pascal ABC.

Комментарии:

  • Строка вводится «посимвольно»,  это не противоречит условию. Ввод строки целиком потребовал бы дополнительную переменную и дополнительные операции.
  • Переменная c0 определяет сдвиг кода символа 0 в таблице ASCII.  
  • Вывод цифры осуществляется командой write(chr(i+c0)) т.е. к индексу массива, например, 2 прибавляется сдвиг и в результате печатается символ с кодом 50.