Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 38
Текст из файла (страница 38)
Замените следующие инфиксные выражения префиксными: а) а"2+Ь 2; б) а 3+3 а 2+7; в) (а 2+Ь)(с+И"2); г) (а 2+Ь 3) 4; д) а" 2(6+ с). 6. Замените следующие инфиксные выражения префиксными: а) (с+0) — (а+Ь) "2; б) ((а+ Ь) — с) 3; в) (а + 6) "2 — (с+ Н)" 2; г) (а — Ь)(а+ 6); д) а — Ь (с+ Н). 7. Замените следующие префиксные выражения инфиксными: а) —: + аЬ вЂ” сИ; б) ++ а2 Н2+ "с2"Ь2; в) + х хЗаЬ+ х х 4сд х х бай; РЯЗДЕЛ 5.6, Двоичные и шестнадцатеричные числа 219 г) "+ "а2+ "Ь2 с23; д) х + а 2Ь+ сд 2 8.
Замените следующие префиксные выражения инфиксными: а) "+ хаЬсЗ; б) х + +абс + +еде; в) + х х ЗаЬ х х4сд2; г) си+а" Ь2+ с г122; д) х + -аЬс — -або. 9. Напишите процедуру для перехода от инфиксной формы записи выражения к префиксной. 10. Напишите процедуру для перехода от постфиксной формы записи выражения к инфиксной. 5.6. ДВОИЧНЫЕ И ШЕСТНАДЦАТЕРИЧНЫЕ ЧИСЛА Использование цифры 0 для обозначения разрядов в записи числа привело к большому прорыву в развитии математики.
Оно дало возможность различать такие числа, как 47, 4700, 4007 и 4070. В данном примере значение четверки и семерки определяется позицией, которую они занимают в записи числа. Например, в числе 47 цифры 4 и 7 находятся в таких позициях, что цифра 4 обозначает 4 десятка, а цифра 7 обозначает 7 единиц. В числе 4700 цифра 4 обозначает 4 тысячи, а цифра 7 обозначает 7 сотен. Таким образом, число 47 можно записать как 4 10 + 7, а число 4700 — как 4 1000 + 7 100 или 4 10з + 7 10~. Точно так же, число 4007 можно записать как 4 10з + 7 1, а число 4070 — как 4 10з + 7 10. В общем случае, если число п представляется в десятичной системе счисления, в основе которой лежит число 10, как а а ~а з аза~ао, то и = а (10) + а ~(10)"' + . + аз(10) + аг(10) + ао, где а, — целые числа между 0 и 9 для всех 0 < т < гп.
Например, 3124 = 3(10)з+ Ц10)~ + 2(10) + 4. Аналогично, если число п представлено в двоичной системе счисления, в основе которой лежит число 2, то каждая цифра должна быть либо 1, либо О, и ее значение определяется занимаемой позицией. Таким образом, 1101 = Ц2)з + Ц2)з + 0(2) + 1 = 13, где число 13 представлено в десятичной системе. Первые 20 положительных целых чисел, записанные в двоичной системе, имеют вид: 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, 10000, 10001, 10010, 10011 и 10100. В общем случае, двоичному представлению и = а,„а„, ~а,„ з аза~ао соответствует десятичное представление п = а (2) + а„, ~(2) " + ... + аз(2) + аг(2) + ао, где а, равно либо 1, либо 0 для всех 0 < 4 < т. Для исключения возможной путаницы двоичное число, например, 1101101, будем обозначать как 1101101з, а десятичное число, например, 312, будем обозначать как 312го.
220 ГПАВА б. Алгоритмы и рекурсия Когда на одометре машины достигается число 9999 и добавляется еще одна миля, то все девятки сбрасываются и получается !0,000. Аналогично, если к числу 11111з прибавить 1, то все единицы сбрасываются и получается число 100000з. Таким образом, если прибавить 1 к 10111з, получим 11000з. Для того чтобы пеРевести двоичное число а а 1а з . аза1ао в десЯтичное, нам пРосто нужно вычислить значение этого числа, равное а (2) + а 1(2) ' + . + аз(2)з+а1(2)+ао, в обычной ДесЯтичной системе счислениЯ. НапРимеР, 1101011з записывается в виде 1 1 0 1 0 1 1 2е 24 24 2з 2з 2' 1 Ц2)е + 1(2)з + 0(2)4 + Ц2)з + 0(2)г + 1(2)1 + 1 64+ 32+ 8+ 4+1 = 109.
Точно так же находим 10101 1(2)4 + 0(2)з + Ц2)г + 0(2)1 + 1 16 + 4 + 1 21 1 24 2з 24 2з 2з 2' 1 Нам не нужно использовать 24 = 321о, т.к. это число слишком велико, поэтому в колонке, соответствующей 2з, помещаем 0: 1 0 26 25 24 23 22 21 Но 24 = 161о нам нужно, поэтому помещаем 1 в колонку, соответствующую 24: Этот метод нахождения значения двоичного числа часто называют "подсчет обмена", поскольку он аналогичен подсчету наличных денег, если имеется монета в 25 центов, монета в 10 центов и пенни. Сначала мы опишем метод перехода от десятичного числа к двоичному, который часто называют "разменом". Если необходимо определить, какие монеты отдать в обмен за 42 цента, первой будет выбрана монета в 25 центов, поскольку это наибольшая монета, которая меньше 42 центов.
Если вычесть 25 центов, то необходимо еще 17 центов. Теперь выбираем монету в 10 центов, поскольку это наибольшая монета, которая меньше, чем 17 центов. Вычитаем 10 центов из 17 центов и находим, что необходимо еще 7 центов. Следующей выбираем монету в 5 центов и 5 центов вычитаем, остается еще 2 цента, которые необходимо добавить. Подобным образом, если имеется, например, число 831о, которое нужно перевести в двоичное, то сначала выбирается наибольшая степень 2, которая не превосходит 83,о.
В данном случае это 2е = 641о. Помещаем 1 в колонку, соответствующую 2е. Теперь вычитаем 641о из 831о и получаем 191о .. РАЗДЕЛ З.Б. Двоичные и шестнадцатеричные числа 221 Вычитаем 161о из 19ши получаем Зго. Нам не нужно использовать 2 = 8|о или 2з = 4го, т.к. они слишком велики, поэтомУ помещаем 0 в соответствУющие колонки. Но 2 и 1 нам нужны, поэтому мы помещаем по единице в соответствующие колонки: 1 0 1 0 0 1 1 2е 2з 24 2з 2з 2г 1 Следовательно, искомым числом является 1010011з. Аналогично, 199щ = 11000111, т.к. для этого необходимо одно 27 = 128щ, одно 2 = 64го, одно 2 = 4щ, одно 2ш и одно 1го.
Можно получить другой способ преобразования десятичного числа в двоичное, если проанализировать такой процесс: при делении 234 на 10 обычным арифметическим способом получаем частное 23 и остаток 4. Если теперь делить 23 на 10, частным будет 2, а остатком — 3. Наконец, если разделить 2 на 10, получаем частное 0 и остаток 2. Обратите внимание, что расположение остатков в обратном порядке дает исходное число. Используя приведенный ниже алгоритм, целое десятичное число п можно преобразовать в то же самое по значению, но двоичное число и. !. Разделить и на 10, получив частное дг и остаток г,.
2. Разделить дг на 10, получив частное дз и остаток гз. 3. До тех пор, пока дь не равно О, делить дь на 10, получая частное дьч, и остаток гьч-г. 4. Если д„ = О, тогда г„т„ г .гзгзг1 = гг. Использование приведенного выше алгоритма в двоичной системе счисления, где 10 соответствует десятичному числу 2, обеспечит такой же результат. Но, поскольку 10з есть десятичное число 2, деление на 10 в двоичной системе должно давать такие же остатки, как и деление на 2 в десятичной арифметике. Рассмотрим приведенные ниже соответствующие операции для преобразования десятичного числа 57 в двоичное число, в которых все числа одни и те же, за исключением того, что в первом столбце они выражены в двоичной форме, а во втором — в десятичной форме. Следующий алгоритм должен переводить число и из десятичной системы счисления в двоичную: 1.
Разделить и на 2, получив частное дг и остаток гы 2. Разделить 9г на 2, получив частное дз и остаток гз. двоичная запись Разделить 111001 на 10; 4~ = 11100, г1 = 1. Разделить 11100 на 10; аз = 1110, гз = О. Разделить 1110 на 10; дз = 111, гз = О. Разделить 111 на 10; д4 = 11, га = 1, Разделить 11 на 10; чз = 1, гз = 1.
Разделить 1 на 10; че = О, га = 1. 111001 = 111001. десятичная запись Разделить 57 на 2; и1 = 28, г~ = 1. Разделить 28 на 2; аз = 14, гз = О. Разделить 14 иа 2; из = 7, гз = О. Разделить 7 на 2; 44 = 3, га = 1. Разделить 3 на 2; аа = 1, г, = 1. Разделить 1 на 2; де = О, га = 1. 57 = 111001. 222 ГЛКВА 5. алгоритмы и рекурсия 3. До тех пор, пока дк не равно О, делить 9к на 2, получая частное 9ь4.1 и остаток гь4.1.
4. Если 9„= О, тогда (г„г„1 гзгзг1)2 = иго. Для того чтобы записать целое положительное число в шестнадцатеричной системе счисления, в основе которой лежит число 16, нам понадобятся новые символы, поскольку все неотрицательные целые числа, меньшие 16, должны представляться одной цифрой. Иными словами, 101о эквивалентно 16 в десятичной форме. Вводим "цифры" А, В, С, Р, Е и Г для обозначения чисел 10, 11, 12, 13, 14 и 15. Таким образом, первые 20 целых положительных чисел в шестнадцатеричной форме имеют вид 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, Р, Е, Г, 10, 11, 12, 13 и 14. Если число и в шестнадцатеричной форме представлено как а а„, 1а 2 .. аза1ао, то ему соответствует представление в десятичной форме, и = а,„(16) + а 1(16) + + а2(16) + а1(16) + ао, где для всех 0 < 4 < т, 0 < а, < 16. Поэтому числу и = 2АЗВ4го соответствовало бы десятичное число и = 2(16)4 + А(16)з + З(16)2+ В(16) + 4.
Используем следующую таблицу: и 2АЗВ41в = 1719801о. Аналогично, ЗС91в = 3(16)2 + 12(16) + 9 = 3 х 256 + 12 х 16 + 9 = 969ш. Способом, аналогичным "сбрасыванию" для двоичных чисел, после прибавления 1 к ГГГГГ получаем 100000. Поэтому, если прибавить 1 к 23СГГГГ, получим 23РОООО. Первый способ перевода десятичного числа в шестнадцатеричное аналогичен способу перевода десятичного числа в двоичное. Если дано десятичное число, например, 530328, наибольшей степенью числа 16, которая разделит 530328 с ненулевым частным, будет 164 = 65536. Поскольку частное от деления 530328 на 66536 равно 8, запишем 8 в первом столбце: 8 65536 4096 256 16 1 164 16з 162 161 16о Разделим разность 530328 — 8(65536) = 6040 на 4096. Частное от деления равно 1, остаток равен 1944, поэтому помещаем 1 во второй столбец: 8 1 66536 4096 256 16 1 164 163 162 161 160 2(16)4 2 х 65536 А(16)з 10 х 4096 3(16)2 = 3 х 256 В(16) = 11 х 16 4=4х1 Сумма = 130072 = 40960 = 768 = 176 =4 = 171980 РАЗДЕЛ Б.д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
