Решение задачи №597
Условие задачи №597:
Дано число типа byte. Проверить, является ли палиндромом его двоичное представление с учетом того, что сохранены старшие нули. Пример таких чисел: 102 (т. к. 102 = 0110 01102, а это палиндром), 129 (129 = 1000 00012) и т. д.Решение
Подробное решениеДанная задача частично повторяет задачу 9. Сходство состоит в том, что и там, и здесь у проверяемых чисел фиксированная разрядность (длина), ведь здесь нам уже задан тип и получено указание сохранить старшие нули, так что в данном случае двоичные представления всех по-даваемых на вход программе чисел будут восьмизначными.
Но как же упростить решение, чтобы не делать сравнение всех разрядов «в лоб»? Для этого нам нужно вспомнить правило, упомянутое в задаче 5, на этот раз несколько уточненное и допол-ненное:
– Остаток от деления любого числа x в системе счисления с основанием p на само число p дает нам крайний справа разряд числа x.
– Умножение любого числа x в системе счисления с основанием p на само число p добавляет числу x новый разряд справа.
Для примера возьмем число 158 в десятичной системе счисления. Мы можем получить его крайнюю цифру справа, которая равна 8, если возьмем остаток от деления 158 на число 10, явля-ющееся в данном случае основанием системы счисления. С другой стороны, если мы умножим 158 на 10, то появляется новый разряд справа, и в результате мы получаем число 1580.
Согласно правилу те же самые арифметические законы актуальны и для двоичной системы счисления. А это в свою очередь означает, что мы можем разработать алгоритм наподобие того, который использовался в задаче 9 для формирования числа, представляющего собой правую по-ловину исходного числа, которая записана в реверсном порядке. Для этого нам нужно использо-вать четыре переменных для хранения двоичных разрядов правой половины двоичной записи введенного числа, добыть эти самые разряды с удалением их в исходном числе, сформировать из них двоичную реверсную запись и выполнить сравнение. Обозначим эти переменные типа byte как a, b, c, и d.
Опишем сам алгоритм:
1) Вводим число n;
2) Последовательно получаем 4 крайних справа разряда двоичной записи числа n: присваи-ваем их значение соответствующей переменной, а затем отбрасываем в исходном числе:
1 2 3 4 5 6 7 8 | a := n mod 2; n := n div 2; b := n mod 2; n := n div 2; c := n mod 2; n := n div 2; d := n mod 2; n := n div 2; |
3) Теперь нужно подумать, как видоизменится формула, с помощью которой мы получали реверсную запись числа в задаче 4 и задаче 9. Очевидно, что в десятичной системе счис-ления реверсную запись четырехзначного числа, разряд единиц которого находится в пе-ременной k, разряд десятков – в переменной l, сотен – в m и тысяч – в n мы можем найти по следующей формуле (x в данной случае – любая переменная типа word):
1 | x := 1000 * k + 100 * l + 10 * m + n; |
Можно представить, что мы формируем четыре числа, которые затем складываем. Первое число 1000 * k – это разряд единиц исходного числа, к которому справа приписано три разряда (три нуля), то есть, трижды произведено умножение на основание системы счисления 10, проще говоря, число k умножено на 103. Аналогично, к l нужно приписать два нуля, к m – один ноль, а n оставить без изменения, так как эта цифра будет находиться в разряде единиц формируемого «перевертыша». Вспомнив правило, высказанное немного выше, преобразуем предыдущую формулу для двоичной системы счисления (будем умножать цифры на двойку в соответствующих степенях). Она получится такой (для формирования числа используется переменная a):
1 | a := 8 * a + 4 * b + 2 * c + d; |
4) После применения вышеприведенной строки останется лишь вывести на экран результат сравнения полученных чисел:
1 | writeln(n = a); |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | program BinaryPalindrome; var n, a, b, c, d: byte; begin readln(n); a := n mod 2; n := n div 2; b := n mod 2; n := n div 2; c := n mod 2; n := n div 2; d := n mod 2; n := n div 2; a := 8 * a + 4 * b + 2 * c + d; writeln(n = a)end. |
