Изучение методов перевода чисел из одних систем исчисления в другие (Лабораторная работа № 7)

Лабораторная работа №7.

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

Цель работы:  Изучить методы перевода чисел из одних систем исчисления в другие.

Краткие теоретические сведения.

      1. Представление чисел и других значений в компьютере

1.1. Позиционные системы счисления

1.1.1. Запись натуральных чисел

Система счисления – это система записи, или обозначения, чисел. Самыми совершенными системами счисления оказались позиционные. В этих системах число, обозначенное цифрой, зависит от ее места (позиции) в записи числа. Например, обычные записи 13 и 31 в десятичной системе состоят из одинаковых цифр (символов “1” и “3”), но обозначают разные числа: 1 • 10+3 и 3 • 10+1.

Позиционная система счисления с основой Р (Р-ичная) имеет Р цифр С₀, С₁,..., С_p-1, обычно обозначающих натуральные числа от до Р-1. Эти записи и обозначенные ими числа – значения этих записей – называются одноразрядными Р-ичными. Цифры десятичной системы О, 1, 2,..., 9 называются арабскими, и были заимствованы арабами у индусов.

В программировании широко применяется шестнадцатеричная система, в которой первые 10 цифр арабские, а следующие шесть –буквы А, В, С, D, Е, F. Они обозначают числа, десятичная запись которых 10, 11, 12, 13, 14, 15 соответственно.

Число Р в Р-ичной системе обозначается двухразрядной записью С₁С₀, число Р+1 – записью C₁С₁, и т.д. до Р•Р-1. Например: 10, 11,..., 99 в десятичной системе; 10, 11 в двоичной; 10, 11,...,1F, 20,..., FF в 16-ричной. Число ЕРобозначается уже тремя цифрами С₁С₀С₀, далее идет С₁С₀С₁ и т.д. Например: 100, 101,..., 999 в десятичной системе; 100, 101, 11О, 111 в двоичной 100, 101,..., FFF в 16-ричной. И вообще, запись вида:

(a_ka_k-1…a₁a₀)_p

означает в Р-ичной системе число, которое является значением полинома:

a_k•P^k+a_k-1•P^k-1+...+a1•P+a₀

Например, двоичная запись (10011)₂, обозначает число, которое в  десятичной записи имеет вид 1 • 2⁴+0 • 2³+0 • 2²+1 • 2¹+1 • 2°=19. Шестнадцатеричная запись (1ВС)₁₆ — это десятичное 1 • 16²+11 • 16+12=444.

Самая правая цифра в записи числа обозначает количество единиц и называется младшей, а самая левая — количество чисел p^kи называется старшей.

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

По Р-ичной записи (a_ka_k-1...a_la₀)_Pнатурального числа N можно построить его десятичное представление, вычислив значения полинома с помощью операций умножения и сложения в десятичной системе. Именно этим мы занимались двумя абзацами выше.

Рассмотрим, как получить по натуральному числу N цифры Р-ичного представления. Пусть N=(a_ka_k-1...a₁a₀)_p, и количество цифр k+1 неизвестно. Запишем представление в таком виде:

N = a_k•P^k+a_k-l • P^k-1+…+a₁•P+a₀= (...(a_k-• P+a_k-1) • P+…+a₁)•P+a₀

Отсюда очевидно, что значением а₀ является N mod Р, а₁ – (NdivP)modР и т.д. Таким образом, если поделить N на Р в столбик, то остаток от деления будет значением младшей цифры. Потом можно так же поделить на Р частное от первого деления – остаток будет выражать количество Р-ичных десятков и т.д., пока последнее частное не окажется меньше Р. Оно и будет значением старшей цифры.  При Р>10 еще нужно превратить числа, большие 9, в цифры.   Например:   получим   цифры   16-ричного   представления  десятичного числа 1022:

1022  16               63 16

  96                       48   3

     62                    15

     48

     14

Выделенные полужирным 14, 15 и 3 – это количества 16-ричных единиц, десятков и сотен соответственно. Обозначим их 16-ричными цифрами Е, F и 3 соответственно и получим запись 3FE.

Если натуральное N представлено в базовом типе целых integer,  то получить его Р-ичные цифры можно по следующему алгоритму (последняя цифра получается как остаток от деления на Р частного, меньшего Р):

while N > 0 do begin

d := NmodP;

no значению d построить Р-ичную цифру;

N := N divP

end

Если обозначить буквами А, В,..., Z числа от 10 до 35, то по этому алгоритму можно образовать представление чисел вплоть до 36-ричной системы. Для использования еще больших основ систем счисления нужно дополнительно расширить алфавит.

1.1.2. Дробные числа

Р-ичное представление чисел, меньших 1, имеет вид 0.a_-1a_-2…,где a_-j – Р-ичные цифры. Эта запись обозначает действительное число – значение выражения:

a_-1•P^-1+a_-2•P^-2…

Например, 0.1101)_{2 –}  это десятичное 1•2^-1+1•2^-2+0•2^-3+1•2^-4=0.5+0.25 +0.0625 = =0.8125 ; (0.21)₃ –десятичное 2 • З^-1+1 • 3^-2=0.777...=0.(7); (О.ВС)₁₆ - десятичное 11 • 16^-1+12• 16^-2=0.734375.

По Р-ичному представлению, в котором заданы r старших цифр, десятичная запись числа получается вычислением значения многочлена:

a_-1•P^-1+a_-2•P^-2…a_-r•P^-r

Напомним, что если основа Р имеет простые делители, отлич­ные от 2 и 5, то число с конечной Р-ичной записью изображается бесконечной, но периодической десятичной дробью. Если же про­стыми делителями Р являются только 2 и 5, то и десятичная дробь конечна.

Рассмотрим, как по действительному значению V получить цифры его Р-ичного представления. Пусть V=(0.a_-1a_-2…)_P.  Запишем пред­ставление в таком виде:

V= P^-1•(a_-1+P^-1•(a_-2+…))