Решение задачи №4194
Условие задачи №4194:
Дано натуральное число n. Проверить, представляет ли собой палиндром его десятичная запись.Решение
Описание отсутствуетРешение:
Задача является общим случаем задачи 9 (/show-so...). Чтобы решить ее, необходимо разделить число n на две половины одинаковой длины, отбросить серединную цифру в случае нечетной длины n и проверить равенство одной из частей реверсной записи другой части.
Так как нам заранее неизвестна десятичная разрядность n, мы можем посчитать ее с помощью следующего цикла (подробнее это описывалось в предыдущей задаче - /show-so...):
1 2 3 4 5 6 | a := n; digits := 0;while a <> 0 do begin a := a div 10; inc(digits)end; |
Теперь рассмотрим варианты проверки числа на палиндром вместе с разбором на примере.
Пусть дано число нечетной длины, например, 79597. Мы можем отделить его правую половину 97, проведя ряд последовательных делений с взятием остатка в цикле из digits div 2 повторений. При этом необходимо сразу сформировать ее реверс в переменную right (мы делали это в задаче 31 - /show-so...):
1 2 3 4 5 6 | right := 0;for i := 1 to digits div 2 do begin right := right * 10; right := right + n mod 10; n := n div 10end; |
Так как число нечетно, нужно отбросить его центральную цифру 5, после чего в переменной n (равной 79) будет содержаться левая половина числа, а в переменной right (также равной 79) – его перевернутая правая половина. Они равны, следовательно, ответ положительный.
Тот же порядок действий применяется и для чисел четной длины, однако теперь нам не нужно ничего отбрасывать после накопления реверсной левой части числа в переменную right, так как в числах четной длины нет серединной цифры. Например, дано число 1551: переворачиваем правую половину числа 51 (получим 15) и сравниваем ее с левой половиной: 15 = 15, ответ положительный.
Эти допущения говорят о том, что необходима проверка длины числа n на нечетность и, соответственно, отбрасывание серединной цифры в случае нечетности:
1 | if odd(digits) then n := n div 10; |
Итоговый код программы:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | program CheckPalindrome; var n, a, right: longint; digits, i: byte; begin readln(n); a := n; digits := 0; while a <> 0 do begin a := a div 10; inc(digits) end; right := 0; for i := 1 to digits div 2 do begin right := right * 10; right := right + n mod 10; n := n div 10 end; if odd(digits) then n := n div 10; writeln(n = right)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).
