Hosted by uCoz

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

Формулировка. Дано натуральное число n. Проверить, представляет ли собой палиндром его десятичная запись.

Решение. Задача является общим случаем задачи 9. Чтобы решить ее, необходимо разделить число n на две половины одинаковой длины, отбросить серединную цифру в случае нечетной длины n и проверить равенство одной из частей реверсной записи другой части.

Так как нам заранее неизвестна десятичная разрядность n, мы можем посчитать ее с помощью следующего цикла (подробнее это описывалось в предыдущей задаче):

a := n;

digits := 0;

while a <> 0 do begin

  a := a div 10;

  inc(digits)

end;

Теперь рассмотрим варианты проверки числа на палиндром вместе с разбором на примере.

Пусть дано число нечетной длины, например, 79597. Мы можем отделить его правую половину 97, проведя ряд последовательных делений с взятием остатка в цикле из digits div 2 повторений. При этом необходимо сразу сформировать ее реверс в переменную right (мы делали это в задаче 31):

right := 0;

for i := 1 to digits div 2 do begin

  right := right * 10;

  right := right + n mod 10;

  n := n div 10

end;

Так как число нечетно, нужно отбросить его центральную цифру 5, после чего в переменной n (равной 79) будет содержаться левая половина числа, а в переменной right (также равной 79) – его перевернутая правая половина. Они равны, следовательно, ответ положительный.

Тот же порядок действий применяется и для чисел четной длины, однако теперь нам не нужно ничего отбрасывать после накопления реверсной левой части числа в переменную right, так как в числах четной длины нет серединной цифры. Например, дано число 1551: переворачиваем правую половину числа 51 (получим 15) и сравниваем ее с левой половиной: 15 = 15, ответ положительный.

Эти допущения говорят о том, что необходима проверка длины числа n на нечетность и, соответственно, отбрасывание серединной цифры в случае нечетности:

if odd(digits) then n := n div 10;

Код:

  1. program CheckPalindrome;
  2. var
  3. n, a, right: longint;
  4. digits, i: byte;
  5. begin
  6. readln(n);
  7. a := n;
  8. digits := 0;
  9. while a <> 0 do begin
  10. a := a div 10;
  11. inc(digits)
  12. end;
  13. right := 0;
  14. for i := 1 to digits div 2 do begin
  15. right := right * 10;
  16. right := right + n mod 10;
  17. n := n div 10
  18. end;
  19. if odd(digits) then n := n div 10;
  20. writeln(n = right)
  21. end.

Выполним «ручную прокрутку» алгоритма на числе 147741:

1)      Считаем длину числа, она равна 6 (строки 11-14);

2)      В цикле из 6 div 2 = 3 повторений прибавляем к right (формируя реверсную запись) последние три цифры числа n, после чего отбрасываем их и имеем в n 147, в right 147 (строки 16-20);

3)      Так как odd(digits) = odd(6) = false, ничего не делаем (строка 21);

4)      Выводим на экран значение выражения n = right – ответ положительный (строка 22).