Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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





Формулировка. Дано число типа 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: присваиваем их значение соответствующей переменной, а затем отбрасываем в исходном числе:

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):

x:= 1000 * k + 100 * l + 10 * m + n;

Можно представить, что мы формируем четыре числа, которые затем складываем. Первое число 1000 * k – это разряд единиц исходного числа, к которому справа приписано три разряда (три нуля), то есть, трижды произведено умножение на основание системы счисления 10, проще говоря, число k умножено на 103. Аналогично, к l нужно приписать два нуля, к m – один ноль, а n оставить без изменения, так как эта цифра будет находиться в разряде единиц формируемого «перевертыша». Вспомнив правило, высказанное немного выше, преобразуем предыдущую формулу для двоичной системы счисления (будем умножать цифры на двойку в соответствующих степенях). Она получится такой (для формирования числа используется переменная a):

a:= 8 * a + 4 * b + 2 * c + d;

4) После применения вышеприведенной строки останется лишь вывести на экран результат сравнения полученных чисел:

writeln(n = a);

Код:

1. program BinaryPalindrome; 2. 3. var 4. n, a, b, c, d: byte; 5. 6. begin 7. readln(n); 8. a:= n mod 2; 9. n:= n div 2; 10. b:= n mod 2; 11. n:= n div 2; 12. c:= n mod 2; 13. n:= n div 2; 14. d:= n mod 2; 15. n:= n div 2; 16. a:= 8 * a + 4 * b + 2 * c + d; 17. writeln(n = a) 18. end.

Выполним «ручную прокрутку» программы при вводе числа 102. Покажем в таблице, какие значения будут принимать переменные после выполнения соответствующих строк (операторов) кода. Значения переменных для наглядности представлены как в десятичной, так и в двоичной системе счисления (при этом дописаны старшие нули до заполнения тетрады). При этом прочерк означает, что значение переменных на данном шаге не определено, а красным цветом выделены переменные, которые изменяются:

№ строки Десятичная система Двоичная система
n a b c d n a b c d
    0110 0110
      0110 0110  
      0011 0011  
        0011 0011    
        0001 1001    
          0001 1001      
          0000 1100      
            0000 1100        
            0000 0110        
            0000 0110        

Date: 2015-11-14; view: 484; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.012 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию