Палиндром (конспект урока)

Задачи данного типа встречаются в заданиях ЕГЭ в разделе С. Для перехода к созданию программ соответствующего содержания необходимо ввести ряд понятий, которые помогут понять принцип построения алгоритма.

Вводим следующие понятия:

Палиндром 

Подпалиндром данной строки 

Приводятся примеры палиндрома и подполиндрома

Команда определения длины строки, основы работы со строками 

Дальше предлагаем обучающимся составить программу, которая будет определять, является ли строка палиндромом или нет.

Составляем алгоритм решения этой задачи: 

1.             Брать очередной символ с начала строки и сравнивать его с противоположным. 

2.             Если символы не равны, то выдать сообщение "не палиндром", изменить значение флага и остановить сравнение.

3.             Если значение флага не было изменено, то выдать сообщение "палиндром".

var

    s: string;    i,f: byte; begin

   write('String: ');     readln(s);     f := 0;

    for i := 1 to length(s) div 2 do         if s[i] <> s[length(s)-i+1] then begin             writeln('No palindrome');             f := 1;             break         end;     if f = 0 then         write('Palindrome'); readln end.

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

На основе этой программы предлагается составить программу для следующей задачи.

Следующая программа составляется учителем при активной помощи обучающихся.

Формулировка задачи: Составить  программу, находящую в данной строке подпалиндром максимальной длины.

Формат входных данных

Строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита.

Формат выходных данных

В первой строке вывести длину максимального подпалиндрома, а во второй строке сам максимальный подпалиндром. Если таких подпалиндромов несколько, то вывести любой из них. 

Рассуждения: 

Лобовое решение

Задачу возможно решить «в лоб» для небольших строк, перебирая каждый символ и пытаясь строить от него максимальный палиндром, если этот символ является центром палиндрома (для нечетной длины) или одним из центральных символов (для палиндромов четной длины).

Решение при помощи суффиксных деревьев

Задача решается при помощи суффиксных деревьев и быстрого алгоритма LCA.

Сложность такого алгоритма O(Nlog N), где N — длина строки.

Решение с динамическим программированием

Решение при помощи динамического программирования — один из самых быстрых и простых алгоритмов для решения данной задачи.

Разберем нахождение палиндрома нечетной длины от символа в строке с номером

i. Будем сравнивать символы, отстоящие слева и справа от i на какое-то число k, и увеличивать k пока они равны и пока выполняются условия i+k <= length(s), i-k >= 1.

Будем хранить границы самого правого уже найденного палиндрома. Пусть L — левый символ этого палиндрома, а R — правый.

Итак, рассматривая очередное i, мы проверяем, является ли оно больше правой границы самого правого из уже найденных палиндромов. Если i > R, то находим палиндром с центром в i по вышеописанному алгоритму. Если i <= R, то найдем элемент, симметричный i относительно центра самого правого палиндрома. Назовем этот элемент j, j = R + L — i. Поиск количества палиндромов для подстроки с центром в i можно начинать с того количества, которое записано в А[j], увеличивая далее это значение по алгоритму, описанному выше. Если правая граница полученного палиндрома больше R, тогда обновляем L и R.

После ряда логических рассуждений можно оформить решение задачи:

 Function F(i, j : Integer) : Integer;  var Ch : Char; R1, R2 : Integer; k : byte;

 begin

                                   if Mat[i, j] = -1 then

                                   BEGIN

                                                   k := j;

                        while Inp[i] <> Inp[k] do dec(k);                  R1 := F(i + 1, j);

                                                   if i <> k then R2 := F(i + 1, k - 1) + 2 else R2 := 1;

                                                  if R1 > R2 then Mat[i, j] := R1 else Mat[i, j] := R2

                                   END;

                                   F := Mat[i, j]

 end;

После подробного исследования программы, обучающимся предлагается задача ЕГЭ С-4. Задачу необходимо подробно описать.

Формулировка задачи:

На вход программе подается набор символов, заканчивающийся точкой. Напишите эффективную, в том числе и по используемой памяти, программу, которая сначала будет определять, есть ли в этом наборе символы, соответствующие десятичным цифрам. Если такие символы есть, то можно ли переставить их так, чтобы полученное число было симметричным (читалось одинаково как слева направо, так и справа налево). Ведущих нулей в числе быть не должно, исключение – число 0, запись которого содержит ровно один ноль. Если требуемое число составить невозможно, то программа должна вывести на экран слово ―NO‖. А если возможно, то в первой строке следует вывести слово ―YES‖, а во второй – искомое симметричное число. Если таких чисел несколько, то программа должна выводить максимальное из них. Например, пусть на вход подаются следующие символы: Do not 911 to 09 do. В данном случае программа должна вывести YES  91019.

 Обучающиеся составляют алгоритм решения Алгоритм:

1.  Подсчитать частоту повтора цифр в исходной строке.

2.  Проверить условие: кол-во четных

3.  Составить палиндром: начиная с 9, отдельно левую, правую и среднюю части Программа:

VAR Arr: array['0'..'9'] of integer;    // Массив для подсчета частот повторов цифр    InStr: string;             // Входящая строка    i: integer;                // Счѐтчик    ch: char;                  // текущий символ

   Chet, Nechet: integer;     // Кол-во четных и нечетных частот повторов

   ResL: string;              // Левая часть палиндрома

   ResR: string;              // Правая часть палиндрома

   ResM: string;              // Средняя часть палиндрома

   ResultStr: string;         // Результирующая строка палиндрома

BEGIN

   cls; writeln('Введите строку:'); Read(InStr);

   // Подсчет частоты цифр исходной строки    for i:=1 to length(InStr) do Begin        ch:=InStr[i];

       if (ch>='0') and (ch<='9') then Inc(Arr[ch]);    End;

   // Подсчет кол-ва четных и нечетных количеств    Chet:=0; NeChet:=0;    for ch:='0' to '9' do Begin        if Arr[ch]=0 then continue;

       if (Arr[ch] mod 2=0) then Inc(Chet) else Inc(NeChet); End;

   // Проверка возможности составить палиндром    if (Arr['0']>0) and (Arr['0'] mod 2=0) and (Chet=1) then begin       writeln('no'); exit; End;

   // Условие: Если кол-во четных больше 0 и кол-во нечетных меньше 1 тогда можно    if (Chet>=0) and (NeChet<=1) then writeln('yes') else

   // В остальных случаях нельзя!    Begin

       writeln('no'); exit; End;

   // Составляем палиндром - максимально возможное число    ResL:='';  ResR:=''; ResM:='';    for ch:= '9' downto '0' do Begin

       if Arr[ch]=0 then continue;       for i:=1 to (Arr[ch] div 2) do Begin           ResL:=ResL+ch; ResR:=ch+ResR; End;       if (Arr[ch] mod 2)=1 then ResM:=ch; End;

   // Собрать строку

   ResultStr:= ResL + ResM + ResR;

   // Вывести результат

   Writeln(ResultStr);

END.

Задачи для самостоятельного выполнения:  

1.                         Вводится с клавиатуры массив слов. Определить, есть ли словапалиндромы в данном наборе слов, и, если есть, то вывести эти слова.

2.                         Определить, является ли натуральное число палиндромом.  

3.                         Сколько палиндромов в первой тысяче натуральных чисел? 

4.                         Задана строка, которая составляется из малых латинских букв. Разрешается удалять из строки определенные буквы. Сколькими разными образами можно при этом получить палиндром?