Занятие 9. Палиндром, или почему Аргентина манит негра?

Сегодня мы рассмотрим еще одну стандартную олимпиадную (уровня районной олимпиады) задачу: проверить, является ли НЕЧТО палиндромом.

Во-первых: что такое палиндром. Палиндром - это запись, которая одинаково читается слева направо и справа налево. Например, число 12321 можно считать палиндромом. Как и слово кабак. А бывают целые фразы - палиндромы: Аргентина манит негра; А роза упала на лапу Азора... Встречаются стихи - палиндромы и даже рассказы - палиндромы. О романах-палиндромах лично я не слышала, но я верю в людей.

Во-вторых: почему НЕЧТО. Потому, что в зависимости от того, исследуем мы на палиндромность число, слово или фразу - задача может быть решена по-разному. Давайте рассмотрим все варианты решений.

Итак, вариант 1.

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

Идея решения: вводим число a - то, которое будем проверять. Потом, используя цикл While - "пока" с помощью двух меняющихся в ходе выполнения цикла переменных b и c делаем следующую операцию: "откусываем" последнюю цифру от  a и запоминаем её как временное значение c. На следующем витке цикла мы умножаем полученное ранее  c на 10, и прибавляем следующую цифру... И так, пока не получим конечное число c,  которое по сути является числом a, записанным задом наперед.

Затем мы сравниваем a и c, и, если числа равны, выводим сообщение о том, что число - палиндром, или о том, что не палиндром, в противном случае.

Перед вами результат работы программы, реализовавшей эту идею решения:

Введите целое положительное число a=123456

c=6 b=12345

c=65 b=1234

c=654 b=123

c=6543 b=12

c=65432 b=1

c=654321 b=0

654321

Не палиндром

Понятен ли вам принцип? Возникает вопрос, как "откусить" цифру. Тут нам помогут функции div и  mod, о которых вы можете прочесть в Словарике. Коротко:

19:5=3 (остаток 4)

19 div 5 = 3

19 mod 5=4

Попробуйте решить задачу сами. Если не получится - смотрите в Решения к уроку 9.

Рассмотрим 2 вариант этой задачи. 

Проверить, является ли введенное слово палиндромом.

Тут в решении будет несколько интересных и новых моментов, так что я объясню прямо по ходу программы. Решение без комментариев вы можете увидеть в  Решения к уроку 9.

Итак:

 Program pal_2;

Var

s: string;  - заводим переменную, в которой запомним наше слово.

i,f: byte; - две технических переменных: счетчик и "переключатель" "ДА" - "НЕТ"

begin 

   write('String: ');  - запросили слово

   readln(s);            - запомнили слово

   f := 0;                   - обнулили переключатель 

for i := 1 to length(s) div 2 do  - ДЛЯ (for) i от 1 до ДЛИНЫ СЛОВА (length(s)) деленного на 2                                                       без остатка (div) ДЕЛАТЬ (do)

if s[i] <> s[length(s)-i+1] then - ЕСЛИ (if) дальше будет изменение в зависимости от номера                                                          шага: 
                                                     на первом шаге ПЕРВАЯ БУКВА (s[i], i=1) не равна                                                                          ПОСЛЕДНЕЙ БУКВЕ (s[длина слова - i, i=1, +1) 
                                                     на втором шаге ВТОРАЯ БУКВА (s[i], i=2) не равна                                                                          ПРЕДПОСЛЕДНЕЙ БУКВЕ (s[длина слова - i, i=2, +1)
                                                     и так до середины слова... 

   begin                                        - делать такой набор действий

        writeln('No palindrome');   - написать "Не палиндром"

        f := 1;                                   - присвоить f значение 1

        break                                   - прервать выполнение программы (ну смысл нам проверять                                                               слово до конца, если уже вторая пара букв, скажем, не                                                                    совпала?)

    end;                                            - конец блока действий, если " все плохо"

 if f = 0 then write('Palindrome');  - если к концу проверки не совпавших пар не нашлось, f                                                                         осталось равным 0, написать сообщение, что слово -                                                                       палиндром.

end.                                                   - конец программы.

Чем интересно это решение?

• Во-первых, мы повторили оператор div, который использовали для сокращения количества шагов в цикле. Слово проверяется за количество шагов, равное половине длины слова. Это позволяет корректно проверять слова, состоящие из нечетного количества букв. Например, слово "КАБАК" будет проверено так: сравним первую и последнюю буквы - это "К", все хорошо. Затем сравним вторую и предпоследнюю. Обе - "А". У буквы "Б" нет пары, но ее наличие не мешает слову быть палиндромом. Эту букву мы вообще не проверяем, потому, что...
• Во-вторых мы познакомились с оператором  length(s) , который считает ДЛИНУ любой переменной типа String, типа, который соответствует значению "много букв". Так вот, мы теперь можем узнать, сколько - много.
• В-третьих посмотрите, почему цикл задан только до середины слова. На примере "КАБАК" - length(s) = 5. length(s) div 2 = 2. Именно по этой причине мы не трогали букву "Б", о чем было сказано в разделе "Во-первых".
• В-четвертых, эта программа будет проверять ЛЮБЫЕ введенные символы. Т.е. ей будет все равно, введете вы реально существующее слово, случайный набор букв, число или смесь букв разных языков и цифр. Если введенная вами строка будет читаться одинаково с обоих концов - вам сообщат, что это - палиндром. 

А теперь - вариант 3.

Проверить, является ли палиндромом фраза.

Первый вариант решения не подходит, так как фраза не может быть типа integer. Второй вариант решения тоже не подходит, так как в фразе, в отличие от слова, есть пробелы между словами. И они крайне редко совпадают по своему положению при чтении с разных концов. Например, фразу "Кабак казак кабак" вариант 2 посчитает палиндромом. А вот фразу "Аргентина манит негра", с которой мы начинали - нет, так как на 6 шаге проверки встретятся буква "Т" из слова "Аргентина" и пробел перед словом "негра"... 

Но мы справимся и с этой задачей.

Итак, ход решения. Давайте сразу договоримся, что мы будем брать фразу из файла input.txt и выводить сообщение о том, палиндром это или нет, в файл output.txt.

Давайте будем считать, что в наших фразах для проверки будет не более 50 символов вместе с пробелами. 

Опираясь на этот факт мы заведем себе три массива типа CHAR:

• Массив a, в который мы запишем всю введенную нам фразу, в том числе и пробелы, по одному символу в каждой a[ i ].
• Массив b, в котором мы будем сохранять только те символы, которые окажутся НЕ пробелами.
• Массив c, в который мы запишем массив b в обратном порядке.

Если бы мы точно знали, сколько символов в нашей фразе, мы могли бы сразу сократить программу на четверть, но...

Мы введем переменные типа INTEGER:

• i , j - счетчики переменных. Уже при вводе массива a и массива b мы получим разное количество элементов. Ведь с пробелами наша фраза - пример "Аргентина манит негра" займет 21 элемент массива a (столько символов, включая пробелы, в этой фразе), и только 19 элементов массива b - откинем два пробела.
• k - у меня в программе это счетчик итогового количества элементов в массиве b. Если я нахожу "не пробел" в массиве a, я записываю этот символ в массив b и увеличиваю k на 1. Тогда к концу цикла я буду знать, сколько у меня букв без пробелов в фразе.
• d - эту переменную я использую при проверке совпадений массивов b и c. Если находится несовпадение - d увеличивается на 1. В итоге я смогу даже сказать, сколько конкретно несовпадений в фразе, если они есть. В этой программе я не делала сброса при первом же несовпадении, но вы можете это сделать.
• f, g - традиционные переменные типа TEXT для организации работы с файлами ввода и вывода.

С переменными разобрались. Теперь - ход работы:

Открываем файл input.txt и ДО КОНЦА ФАЙЛА (мы же помним про оператор eof?) записываем ВСЕ символы в массив a, а если символ оказывается НЕ ПРОБЕЛОМ, то и в массив b. 

В процессе мы считаем количество элементов, не являющихся пробелами.

Получив массив b, мы записываем его в обратном порядке в массив c. 

Затем мы сравниваем элементы массивов b и c. Если пара не совпадает, переменной d присваивается значение d+1.  

Если к концу сравнения d =0, выводим сообщение, что фраза - палиндром. В противном случае - что нет.