Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Задача № 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. 3. var 4. n, a, right: longint; 5. digits, i: byte; 6. 7. begin 8. readln(n); 9. a:= n; 10. digits:= 0; 11. while a <> 0 do begin 12. a:= a div 10; 13. inc(digits) 14. end; 15. right:= 0; 16. for i:= 1 to digits div 2 do begin 17. right:= right * 10; 18. right:= right + n mod 10; 19. n:= n div 10 20. end; 21. if odd(digits) then n:= n div 10; 22. writeln(n = right) 23. 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).
Date: 2015-11-14; view: 501; Нарушение авторских прав