Вычислительная техника и программирование/Занятие 2

Системы счисления

Теория

Общий способ обозначения и наименования натуральных чисел называется системой счисления. Система обозначения натуральных чисел, в основе которой лежат десять цифр, называется десятичной.Число 10 - основанием такой системы счисления.

В записи по десятичной системе счисления первая, вторая, третья и т.д. цифры, считая справа налево, называются единицами первого, второго, третьего и так далее разрядов.

Так, в числе 84735 имеется:

                       5 единиц первого разряда,
                       3 единицы второго разряда,
                       7 единиц третьего,
                       4 единицы четвертого,
                       8 единиц пятого разряда.

Десять единиц какого-либо разряда составляют одну единицу следующего, высшего разряда.

За основание системы счисления можно взять любое число, например 8. Тогда получится восьмеричная система счисления. Для изображения любого натурального числа по восьмеричной системе достаточно восьми цифр:

0, 1, 2, 3, 4, 5, 6, 7.

Здесь восемь единиц какого-либо разряда составляют одну единицу следующего, высшего разряда. Причем, понятие разряда числа здесь такое же как в десятичной системе.

Если число 1971 записано в десятичной системе, то в восьмеричной системе оно запишется как 3663.

Любое натуральное число в той или иной системе счисления можно изобразить с помощью некоторого количества (равного основанию системы счисления) цифр.

Но цифры имеют разное значение, в зависимости от места, которое они занимают в изображении числа.

Такой принцип представления натурального числа называется позиционным.

Если за основание системы выбрать число k, то в записи числа N по k-й системе k единиц одного разряда составляют единицу следующего, высшего разряда.

Как правило число N в системе с основанием k записывается в следующем виде: B₀B₁...B_m-1B_m ,

где каждое из чисел B₀B₁...B_m-1B_m меньше k.

Таким образом, если запись числа N по цифрам имеет вид B₀B₁...B_m-1B_m , то его значение вычисляется следующим образом:

N= B₀k^m+B₁k^m-1+...+B_m-1k+B_m

где каждое из чисел B₀, B₁, B₂, ..., B_m меньше k.

Например, число 2746 имеет 2 тысячи, 7 сотен, 4 десятка и 6 единиц. Поэтому его можно записать так:

2746=2*10³+ 7*10²+ 4*10 + 6

Для того, чтобы перевести число, записанное по системе с основанием k, в десятичную систему необходимо все цифры B₀,B₁,...,B_m-1,B_m и основание k числа N записать в десятичной системе, а затем также в десятичной системе произвести вычисление. Такую операцию называют подстановкой.

Например, переведем число 3663₈ в десятичную систему (индекс 8 означает, что число 3663 представлено в восьмеричной системе):

3663₈==3*8³ +6*8² +6*8¹ +3*8⁰ =1971 ₁₀

Здесь основание системы счисления меньше 10 (8<10), поэтому цифры числа N и основание k при подстановке в формулу не изменили своего вида. То есть использовались цифры из того же набора 0, 1, ..., 9.

Задание 1

Перевести заданное число, записанное в восьмеричной системе, в десятичную систему, сделать подробную запись в тетраде (на странице обсуждения).

1. вариант - 5174 (восьмеричное)
2. вариант - 3714 (восьмеричное)
3. вариант - 3776 (восьмеричное)
4. вариант - 7623 (восьмеричное)
5. вариант - 4531 (восьмеричное)
6. вариант - 2525 (восьмеричное)
7. вариант - 5252 (восьмеричное)
8. вариант - 7456 (восьмеричное)
9. вариант - 1266 (восьмеричное)
10. вариант - 7007 (восьмеричное)
11. вариант - 60065 (восьмеричное)
12. вариант - 65535 (восьмеричное)
13. вариант - 66643 (восьмеричное)
14. вариант - 24033 (восьмеричное)
15. вариант - 61412 (восьмеричное)
16. вариант - 75522 (восьмеричное)
17. вариант - 23773 (восьмеричное)
18. вариант - 44770 (восьмеричное)
19. вариант - 23127 (восьмеричное)
20. вариант - 5432 (восьмеричное)

Теория

Если основание системы k больше 10, то k и каждую из цифр числа N следует перед подстановкой перевести в десятичную систему. Так в шестнадцатеричной системе помимо "обычных" десятичных цифр 0,1,2,3,4,5,6,7,8,9 используются ещё шесть цифр A,B,C,D,E,F, которые в десятичной системе равны соответст- венно 10,11,12,13,14,15, а основание k этой системы в десятичной системе соответствует 16.

В качестве примера рассмотрим перевод шестнадцатеричного числа 8DC3 ₁₆</small десятичную систему.

8DC3 ₁₆ = 8*16 ³ +13*16 ² +12*16 ¹ +3*16 ⁰ = 36291 ₁₀

Задание 2

Перевести заданное число, записанное в шестнадцатеричной системе, в десятичную систему сделать подробную запись в тетраде (на странице обсуждения)..

1. вариант - A235 (шестнадцатеричное)
2. вариант - B4CD (шестнадцатеричное)
3. вариант - 6975 (шестнадцатеричное)
4. вариант - C409 (шестнадцатеричное)
5. вариант - 1234 (шестнадцатеричное)
6. вариант - FFCE (шестнадцатеричное)
7. вариант - 785 (шестнадцатеричное)
8. вариант - 263 (шестнадцатеричное)
9. вариант - 125 (шестнадцатеричное)
10. вариант - 2A4 (шестнадцатеричное)
11. вариант - 3BF (шестнадцатеричное)
12. вариант - EEE9 (шестнадцатеричное)
13. вариант - 2645 (шестнадцатеричное)
14. вариант - 5678 (шестнадцатеричное)
15. вариант - ABC0 (шестнадцатеричное)
16. вариант - 563C (шестнадцатеричное)
17. вариант - 70C9 (шестнадцатеричное)
18. вариант - 1125 (шестнадцатеричное)
19. вариант - C8B9 (шестнадцатеричное)
20. вариант - 4457 (шестнадцатеричное)

Теория

С помощью приведенного выше алгоритма можно переводить числа из двоичной системы в десятичную.

В качестве примера рассмотрим перевод двоичного числа 1011 ₂ в десятичную систему.

1011 ₂ = 1*2 ³+0*2 ² +1*2 ¹ +1*2 ⁰ = 11 ₁₀

Задание 3

Переведите заданное число, записанное в двоичной системе, в десятичную сделать подробную запись в тетраде (на странице обсуждения)...

1. вариант - 11001
2. вариант - 10101
3. вариант - 10011
4. вариант - 100101
5. вариант - 1111
6. вариант - 11100
7. вариант - 11101
8. вариант - 11110
9. вариант - 11111
10. вариант - 100000
11. вариант - 10110
12. вариант - 10111
13. вариант - 10110
14. вариант - 10001
15. вариант - 10000
16. вариант - 10010
17. вариант - 100001
18. вариант - 100010
19. вариант - 100011
20. вариант - 100100

--Сергей1852 (обсуждение) 10:40, 14 сентября 2012 (UTC)=== Теория ===

В области человеческой деятельности, связанной с производством и применением ЭВМ находили и находят применение следующие системы счисления:

а) двоичная

б) восьмеричная

в) шестнадцатеричная

г) двоично-восьмеричная

д) двоично-десятичная.

Поэтому нужно уметь переводить числа из одной системы в другую. Со способом подстановки мы уже познакомились.

По этому способу из числа в произвольной k-ичной системе можно было получить то же число в десятичной системе, при этом очень существенным является то обстоятельство, что все действия при подстановке производились в десятичной системе.

Способ подстановки годится и для перехода от любой системы с основанием k к системе с основанием t, если только все действия производить в системе с основанием t. При вычислениях, производимых в десятичной системе (или в системе с основанием t), для перехода от десятичной системы (или от системы с основанием t) к системе с основанием k способ подстановки непригоден.

Начнём рассмотрение способа перехода от десятичной системы к системе с основанием k с примера. Переведём в восьмеричную систему целое число 843 ₁₀.

Разделив данное число на 8, найдём в частном 105 и в остатке 3.

843₁₀ = 105*8+3

Это означает, что наше число, кроме некоторого количества восьмёрок, содержит ещё три единицы, т.е. последняя цифра восьмеричной записи данного числа есть 3.

Для определения следующей (справа налево) цифры разделим на 8 получен- ное частное 105. Найдём, что частное равно 13, а остаток 1, то есть

105=13*8+1 . Т.о. получаем 843₁₀ =(13*8+1)*8+3=13*8 ² +1*8 + 3

Иначе говоря, остаток 1 даст нам вторую справа цифру восьмеричного представления.

Наконец, разделив новое частное 13 на 8, получим 13=1*8+5 Результат деления можно представить в виде:

843=105*8+3=(13*8+1)*8+3=((1*8+5)*8+1)*8+3=1*8 ³ +5*8 ² +1*8 ¹ +3*8 ⁰

Это значит, что число 843 ₁₀ имеет в восьмеричной системе вид 1513 ₈.

Естественно, что этот приём является общим. Действительно, пусть целое число M записано в некоторой системе счисления с основанием t и его нужно перевести в новую систему счисления с основанием n.

Разделив M на n, получим: M=b₀*n+a₀

(деление производится в системе счисления с основанием t). Разделив далее b₀ на n, найдём, что b₀ =b₁*n+a₁, откуда

M=(b₁*n+a₁)*n+a₀.

Этот процесс будем продолжать до тех пор, пока последнее частное, которое будет обозначено a_i не станет меньше n.

Тогда получим

M=a&<i&=*n&>i&=+a&<i-1&=*n&>i-1&=+...+a&<2&=*n&>2&=+a&<1&=*n&>1&=+a&<0&=*n&>0&=

т.е. цифрами, представляющими число M в системе с основанием n, будут остатки, получающиеся при последовательном делении M на n, но записанные в обратном порядке.

Этот приём перевода целых чисел называется алгоритмом последовательного деления.

Деление в этом алгоритме производится в первоначальной системе счисления с основанием t. Если n<t, то делитель, а значит, и все остатки однозначны, и мы сразу получаем нужные цифры. Если же n>t, то в системе с основанием t делитель и, быть может, некоторые остатки будут содержать больше одной цифры. В новой системе счисления их следует заменить новыми цифрами, которые в системе с основанием t отсутствовали.

Чтобы последнее замечание стало понятнее, рассмотрим пример.

Переведём число 7113₁₀ в шестнадцатеричную систему. Новое основание в десятичной системе равно 16. Деление производим в десятичной системе:

Учитывая что 12₁₀ = C₁₆ и 11₁₀ = B₁₆ получим:

7113₁₀=1BC9₁₆

Т.о., если действия над числами производятся в системе с основанием n, то для перевода числа из системы с основанием s в систему с основанием n используется алгоритм подстановки. Обратный перевод производится при помощи алгоритма последовательного деления.

При переходе от одной системы счисления к другой оказываются полезными смешанные формы записи чисел. Если представить число в какой-либо системе счисления, а затем каждую цифру этого числа записать в другой системе, то мы получим смешанную форму записи числа. Практически используются двоично- восьмеричная и двоично-десятичная системы.

В двоично-десятичной системе число представляется в десятичной форме, а затем каждая десятичная цифра записывается в двоичной системе. При этом различные десятичные цифры требуют для своего двоичного написания различного числа двоичных разрядов от одного (для нуля и единицы) до четырёх (для восьми и девяти). Чтобы не применять никаких разделительных знаков, для двоичного изображения десятичной цифры всегда выделяется четыре двоичных разряда, которые называются тетрадой.

Например, число 8709 в двоично-десятичной форме будет иметь вид 1000 0111 0000 1001. В этом примере тетрады записаны с промежутками между ними. На самом деле все цифры могут быть поставлены рядом и надо помнить, что каждая группа состоит из четырёх разрядов. Например, двоично-десятичная запись 00101001011000000101 означает десятичное число 29605.

Из возможных шестнадцати различных тетрад 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100,1101, 1110, 1111 в двоично-десятичной системе используются только первые десять, остальные тетрады не означают никакой десятичной цифры и поэтому не имеют смысла в двоично-десятичной системе.

Как известно, физические элементы в ЭВМ имеют два устойчивых состояния и поэтому не могут быть использованы для непосредственного изображения чисел в системе, требующей более двух цифр. Вместе с тем, исходные данные для вычислений, естественно, представляются в десятичной системе. Для записи десятичных чисел в ЭВМ и служит двоично-десятичная система.

Аналогично двоично-десятичной, двоично-восьмеричная форма записи чисел состоит в том, что цифра восьмеричного числа записывается в двоичном виде. Так как наибольшая цифра в восьмеричной системе есть 7, то для изображения любой восьмеричной цифры достаточно трёх разрядов. Такая группа из трёх разрядов, отведённая для изображения восьмеричной цифры, называется триадой.

Так, например, восьмеричное число 6127345 запишется в двоично-восьмеричной системе семью триадами: 110 001 010 111 011 100 101.

В отличие от тетрад, используемых в двоично-десятичной системе, в двоично-восьмеричной системе все возможные триады используются. Это преимущество двоично-восьмеричной системы. Другим - и самым важным - преимуществом является то, что двоично-восьмеричная запись числа совпадает с его двоичной записью.

Это утверждение можно доказать в общем виде.

Для определённости ограничимся рассмотрением двоичного числа с шестью разрядами. Пусть оно имеет вид:

N=b ₅ b ₄ b ₃ b ₂ b ₁ b ₀.

В двоичной системе это число равно:

N=b₅*2⁵+b₄*2⁴+b₃*2³+b₂*2²+b₁*2¹+b₀*2⁰

Представим это число в виде

N=(b₅*2²+b₄*2¹+b₃*2⁰)*2³+(b₂*2²+b₁*2¹+b₀*2⁰) = a₁*8¹+a₀*8⁰,

где

a₁ = b₅*2²+b₄*2¹+b₃*2⁰,

a₀ = b₂*2¹+b₁*2¹+b₀*2⁰.

Из представления N=a₁*8¹ + a₀*8⁰ следует, что восьмеричными цифрами числа N являются a₁ и a₀.

Вместе с тем равенство a₁ = b₅*2²+b₄*2¹+b₃*2⁰

показывает, что если записать восьмеричную цифру a₁ в виде триады двоичных цифр, то этими двоичными цифрами будут b₅, b₄, b₃. Поскольку аналогичное равенство имеет место и для a₀, то таким образом доказано, что двоичная запись числа совпадает.

Задание 4

Заданное десятичное число переведите в двоичную, восьмеричную,двоично-восьмеричную,шестнадцатеричную и двоично-десятичную системы. Ответы записать через какой либо разделитель (запятую, пробел, точку и т.п) в тетраде или страниц обсуждения.

1. вариант - 222
2. вариант - 375
3. вариант - 800
4. вариант - 846
5. вариант - 1015
6. вариант - 2800
7. вариант - 3520
8. вариант - 7477
9. вариант - 8400
10. вариант - 6531
11. вариант - 1417
12. вариант - 1920
13. вариант - 5249
14. вариант - 4327
15. вариант - 615
16. вариант - 4875
17. вариант - 2003
18. вариант - 2999
19. вариант - 1000
20. вариант - 4096