Инфознайка
Главная

Информация вокруг нас

Виды информации
Измерения информации
Алфавитный подход
Содержательный подход
Файловая система
Кодирование графики
Кодирование звука
Скорость передачи
Электронная таблица Excel
Графы
Система счисления
Кодирование информации
Логика
Адресация в Интернете
Поиск в Интернете
Алгоритмы
Кумир
Массивы

Тема: Система счисления

Коротко о главном

Системы счисления - это способ представления чисел и соответствующие ему правила действия над числами.

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

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

В непозиционных системах счисления от положения цифры в записи числа не зависит величина, которую она обозначает.

Примером непозиционной системы счисления является римская система. В римской системе в качестве цифр используются латинские буквы:

 

I

V

X

L

C

D

M

1

5

10

50

100

500

1000

 Пример:

Число CCXXXII складывается из двух сотен, трех десятков и двух единиц и равно двумстам тридцати двум.

 В позиционных системах счисления величина, обозначаемая цифрой в записи числа, зависит от ее позиции. Количество используемых цифр называется основанием позиционной системы счисления.

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

Основание

Название

Алфавит

n=2

двоичная

0  1

n=3

троичная

0  1  2

n=8

восьмиричная

0  1  2  3  4  5  6  7

n=16

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

0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F

Тема: Перевод десятичных чисел в другие системы счисления

Перевод целых чисел.

1). основание новой системы счисления выразить в десятичной системе счисления и все последующие действия производить в десятичной системе счисления;.

2). последовательно умножать данное число и получаемые дробные части произведений на основание новой системы до тех пор, пока дробная часть произведения не станет равной нулю или не будет достигнута требуемая точность представления числа в новой системе счисления;

3). полученные целые части произведений, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления;

4). составить число в новой системе счисления, записывая его, начиная с последнего частного.

Пример: Перевести число в двоичную, восьмеричную и шестнадцатеричную системы счисления:

 

37

2

 

 

 

 

 

 

315

8

 

 

 

315

16

 

 

 

-36

18

2

 

 

 

 

 

-24

39

8

 

 

-16

19

16

 

 

1

-18

9

2

 

 

 

 

75

-32

4

 

 

155

-16

1

 

 

 

0

-8

4

2

 

 

 

-72

7

 

 

 

-144

3

 

 

 

 

 

1

-4

2

2

 

 

3

 

 

 

 

11

 

 

 

 

 

 

 

0

-2

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

 

 

                            Отсюда: 3710=1001012                                                     Отсюда: 31510=4738                                 Отсюда: 31510=13В16

 Перевод дробных чисел.

1). Основание новой системы счисления выразить в десятичной системе счисления и все последующие действия производить в десятичной системе счисления;.

2). последовательно умножать данное число и получаемые дробные части произведений на основание новой системы до тех пор, пока дробная часть произведения не станет равной нулю или не будет достигнута требуемая точность представления числа в новой системе счисления;

3). полученные целые части произведений, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления;

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

Пример: Перевести десятичную дробь 0,1875 в двоичную, восьмеричную и шестнадцатеричную системы счисления: 

 

 

0

1875

 

 

0

1875

 

 

0

1875

 

 

 

 

 

×2

 

 

 

×8

 

 

 

×16

 

 

 

 

0

3750

 

 

1

5000

 

 

1

1250

 

 

 

 

 

×2

 

 

 

×8

 

 

1

875

 

 

 

 

0

7500

 

 

4

0000

 

 

3

0000

 

 

 

 

 

×2

 

 

 

 

 

 

 

 

 

 

 

 

1

5000

 

 

 

 

 

 

 

 

 

 

 

 

 

×2

 

 

 

 

 

 

 

 

 

 

 

 

1

0000

 

 

 

 

 

 

 

 

 

 

                                                                    Отсюда: 0,187510 = 0,00112 = 0,148 = 0,316

Тема: Перевод смешанных чисел

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

Тема: Обратный перевод в десятичную систему счисления

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

перевод из двоичной системы счисления в десятичную:

Пример:     10112 = 1×23+0×22+1×21+1×20=8+0+2+1=1110

перевод из восьмеричной системы счисления в десятичную:

Пример:     4738 = 4×82+7×81+3×80=256+56+3=31510

перевод из шестнадцатеричной системы счисления в десятичную:

Пример:    13В16 = 1×162+3×161+11×160=256+48+11=31510

Полезно помнить, что в двоичной системе:

·    четные числа оканчиваются на 0, нечетные – на 1;

·    числа, которые делятся на 4, оканчиваются на 00, и т.д.; числа, которые делятся на 2k, оканчиваются на k нулей

·    если число N принадлежит интервалу 2k-1 £ N < 2k, в его двоичной записи будет всего k цифр, например, для числа 125:

·                                                    26 = 64 £ 125 < 128 = 27,    125 = 11111012  (7 цифр)

·    числа вида 2k записываются в двоичной системе как единица и k нулей, например:

          16 = 24 = 100002

·    числа вида 2k-1 записываются в двоичной системе k единиц, например:

          15 = 24-1 = 11112

·    если известна двоичная запись числа N, то двоичную запись числа 2·N можно легко получить, приписав в конец ноль, например:
     15 = 11112,          30 = 111102,         60 = 1111002,   120 = 11110002

 Пример задания:

Для хранения целого числа со знаком используется один байт. Сколько единиц содержит внутреннее представление числа (-78)?

 1) 3            2)  4              3)  5             4) 6

 Решение:

1)      переводим число 78 в двоичную систему счисления:

78 = 64 + 8 + 4 + 2 = 26 + 23 + 22 + 21 = 10011102

2)      по условию число занимает в памяти 1 байт = 8 бит, поэтому нужно представить число с помощью 8 разрядов

3)      чтобы получилось всего 8 разрядов (бит), добавляем впереди один ноль:

78 = 010011102

4)      делаем инверсию битов (заменяем везде 0 на 1 и 1 на 0):

010011102     →    101100012 

5)      добавляем к результату единицу

101100012  + 1 = 101100102

это и есть число (-78) в двоичном дополнительно коде

6)      в записи этого числа 4 единицы

7)      таким образом, верный ответ – 2 .

 Еще пример задания:

Чему равно наименьшее основание позиционной системы счисления  х, при котором 225x = 405y? Ответ записать в виде целого числа.

 Решение:

1)      Поскольку в левой и в правой частях есть цифра 5, оба основания больше 5, то есть перебор имеет смысл начинать с x=xmin=6

2)      Очевидно, что  x>y , однако это не очень нам поможет.

3)      Для каждого «подозреваемого» x  вычисляем значение 225x = 2 · x2 + 2x + 5 = N и решаем уравнение N=405y = 4 · y2 + 5 , причем нас интересуют только натуральные y>5 .

4)      Для x=6  и x=7  нужных решений нет, а для x=8  получаем

N=2·82 + 2·8 +5 =149=4·62 +5

так что y=6.

5)      Таким образом, верный ответ (минимальное значение x ): 8.

Еще пример задания:

Запись числа 6710 в системе счисления с основанием N оканчивается на 1 и содержит 4 цифры. Укажите основание этой системы счисления N.

 Решение:

1)      поскольку запись в системе счисления с основанием N заканчивается на 1, то остаток от деления числа 67 на N равен 1, то есть при некотором целом  k  имеем

k·N+1=67→k·N=66

2)      следовательно, основание N – это делитель числа 66

3)      с другой стороны, запись числа содержит 4 цифры, то есть 1000N ≤ 67≤10000N N3 ≤67<N4

4)      выпишем кубы и четвертые степени первых натуральных чисел:

23=8, 33=27, 43=64, 53=125, ...

24=16, 34=81, ...

5)      видим, что из этого списка только для числа N = 3 выполняется условие N3 ≤67<N4

6)      таким образом, верный ответ – 3.

7)    можно сделать проверку, переведя число 67 в троичную систему 6710 = 21113

Еще пример задания:

Укажите наименьшее основание системы счисления, в которой запись числа 30 трехзначна.  

Решение:

1)      обозначим через  N  неизвестное основание системы счисления, тогда запись числа 30 в этой системе имеет вид

X Y ZN = 30

2)      вспомним алгоритм перевода числа из системы счисления с основанием N в десятичную систему: расставляем сверху номера разрядов и умножаем каждую цифру на основание в степени, равной разряду  

2  1  0

X Y ZN = X · N2 + Y · N + Z = 30

 3)      поскольку запись трехзначная, X≠0 , поэтому 30≥N2

4)      с другой стороны, четвертой цифры нет, то есть, в третьем разряде – ноль, поэтому 30<N3

5)      объединяя последние два условия, получаем, что искомое основание N  удовлетворяет двойному неравенству

N2≤30<N3

6)      учитывая, что N  – целое число, методом подбора находим целые решения этого неравенства; их два – 4 и 5:

42 = 16 ≤ 30 < 43 = 64 

52 = 25 ≤ 30 < 53 = 125

7)      минимальное из этих значений – 4

8)      таким образом, верный ответ – 4 .

Еще пример задания:

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 23 оканчивается на 2.

Общий подход:

·   основание системы счисления, мы обозначим  через N  

·   поскольку последняя цифра числа – 2, основание должно быть больше 2, то есть N>2

·   вспомним алгоритм перевода числа из десятичной системы в систему с основанием N , из него следует, что младшая цифра результата – это остаток от деления исходного числа на N

Решение:

1)      итак, нужно найти все целые числа N≥3 , такие что остаток от деления 23 на N  равен 2, или (что то же самое)

 23=k·N+2       (*)                                                                                   

где k  – целое неотрицательное число (0, 1, 2, …);

2)      сложность в том, что и k и N  неизвестны, однако здесь нужно «играть» на том, что это натуральные числа

3)      из формулы (*) получаем k·N=21 , так что задача сводится к тому, чтобы найти все делители числа 21, которые больше 2

4)      в этой задаче есть только три таких делителя: N=2, 7  и 21 

5)      таким образом, верный ответ – 3, 7, 21 .

Еще пример задания:

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке.

Вот начало списка:

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

Запишите слово, которое стоит на 240-м месте от начала списка.

Решение:

1)      подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв:

1

А

А

А

А

А

2

А

А

А

А

О

3

А

А

А

А

У

4

А

А

А

О

А

...

 

 

 

 

 

 

 

 

 

 

240

У

У

У

О

У

241

У

У

У

У

А

242

У

У

У

У

О

243

У

У

У

У

У

 35 = 243 слова; 240-ое место – четвертое с конца;

2)      так как слова стоят в алфавитном порядке, то первая треть (81 шт)  начинаются с «А», вторая треть (тоже 81) – с «О», а последняя треть – с «У», то есть первая буква меняется через 81 слово

3)      аналогично:

•     2-я буква меняется через 81/3 = 27 слов;

•     3-я буква – через 27/3 = 9 слов;

•     4-я буква – через 9/3 = 3 слова и

•     5-я буква меняется в каждой строке.

4)      из этой закономерности ясно, что

·   на первой позиции в искомом слове будет буква «У» (последние 81 букв);

·   на второй – тоже буква «У» (последние 27 букв);

·   на третьей – тоже буква «У» (последние 9 букв);

·   на четвертой – буква «О» (т.к. последние три буквы «У», а перед ними 3 буквы «О»)%

·   на пятой – буква «У» (т.к. последние 3 буквы чередуются «А», «О», «У», а перед ними такая же последовательность).

5)      Ответ:  УУУОУ.

Проверочные задания

  1. Как представлено число 8210 в двоичной системе счисления?

      10100102
      10100112
      1001012
      10001002


  2. Укажите наименьшее основание системы счисления, в которой запись числа 70 трехзначна

     2
    3
    4
    5

  3. В системе счисления с некоторым основанием десятичное число 129 записывается как 1004. Укажите это основание

    4
    5
    6
    7.

  4. В системе счисления с некоторым основанием десятичное число 129 записывается как 1004. Укажите это основание

    4
    5
    6
    7

      

  5.  Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:

    1. ААААА
    2. ААААО
    3. ААААУ
    4. АААОА
    ……
    Запишите слово, которое стоит на 101-м месте от начала списка.

    АУОУА
    ОУАОУ
     УОАОУ
    ОАУАО