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

 

Выучить разделы дисциплины, связанные с системами счисления, классификацией систем счисления [1,2,3].

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

Кратко число записывается следующим образом:

 

, (1.1)

 

где - количественный эквивалент числа ( );

- цифры из множества, с помощью которых можно представить число ( );

- целая часть числа;

- дробная часть числа.

 

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

В техническом аспекте длина числа интерпретируется как длина разрядной сетки.

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

Количественный эквивалент числа - ( ) - ( ), заданного в определенной системе счисления, является некоторой функцией числовых эквивалентов всех его цифр, т.е.:

 

, (1.2)

где - количественный эквивалент числа ( );

– максимальный количественный (числовой) эквивалент цифры числа ( ), находящийся в крайнем левом разряде;

– минимальный количественный (числовой) эквивалент цифры числа ( ), находящийся в крайнем правом разряде;

 

Тогда при любой конечной разрядной сетке ( ) будет принимать в зависимости от количественных эквивалентов отдельных разрядов значения от до .

Диапазон представления ( ) чисел в данной системе счисления - это интервал числовой оси, заключенный между максимальными и минимальными числами, представленными заданной разрядностью ( длинной разрядной сетки):

 

, (1.3)

 

где - диапазон представимых чисел в определенной системе счисления;

- максимальный количественный эквивалент числа по основанию ;

- минимальный количественный эквивалент числа по основанию .

 

Исходя из вышесказанного графически число можно представить как показано на рис. 1.1.

 

Рисунок 1.1 - Графическое представление числа

 

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

Задача перевода чисел из одной позиционной системы счисления в другую позиционную систему счисления является одной из главных при изучении дисциплины “Основы компьютерных вычислений”. Ее можно сформулировать следующим образом: требуется перевести некоторое число ( ), записанное в позиционной системе счисления с основанием ( ), в такую же позиционную систему счисления, имеющую основание ( ).

Другими словами: по изображению операнда ( ) в системе счисления с основанием ( ) найти изображение ( ) того же операнда в системе с основанием ( ).

 

, (1.4)

 

, (1.5)

 

Существуют 2 группы методов перевода: табличные и расчетные.

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

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

 

, (1.6)

 

где - цифры из - го множества системы счисления;

- основание - системы счисления.

, (1.7)

 

где - цифры из - го множества системы счисления;

- основание - системы счисления.

 

Для перевода операнда ( ) в систему с основанием ( ) необходимо записать ( ) в форме для вычисления количественного эквивалента, далее заменить цифры ( ) и основания ( ) их эквивалентами ( ) в системе с основанием ( ), а потом вычислить полученное выражение по правилам арифметики в системе счисления с основанием ( ). Этот алгоритм удобно использовать в случае, когда ( ), причем ( ) соответствует системе счисления, где просто и "привычно" выполняются операции сложения и умножения (например, десятичной системе). Для упрощения вычислений используют схему Горнера (1.8), в соответствии с которой формула для преобразуется путем многократного вынесения за скобки:

 

, (1.8)

 

где - цифра в целой части числа;

- цифра в дробной части числа;

- основание системы счисления.

 

Отсюда видно, что для получения целой части числа необходимо выполнить ( ) шагов вычислений, а для получения дробной - ( ) шагов вычислений. Таким образом вышеописанный алгоритм, состоит из двух алгоритмов, а именно: перевода целого числа, выполняемого в соответствии с рекуррентной формулой (1.9):

 

, (1.9)

 

где - целая часть исходного числа в системе счисления с основанием ( );

 

И перевода дробей по рекуррентной формуле (1.10):

 

, (1.10)

 

где - дробная часть исходного числа в системе с основанием ( ).

 

Рассмотренный алгоритм не имеет каких-либо теоретических ограничений на область своего применения. Однако при переводе целых чисел в системы с "непривычными" основаниями, особенно в случае ( ), использование этого алгоритма связано с весьма громоздкими вычислениями.

Поэтому на практике применяется следующий алгоритм перевода целых чисел и правильных дробей (например из десятичной системы счисления в недесятичную систему счисления) при условии когда (исключением является перевод в 16-и ричную систему счисления). Целое число ( ) запишем в системе с основанием ( ) с использованием схемы Горнера (1.8):

 

.

 

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

 

.

 

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

Алгоритм перевода целых чисел из одной позиционной системы счисления (десятичной) в другую позиционную систему счисления (недесятичную) можно сформулировать следующим образом: операнд ( ) необходимо делить на ( ) по правилам целочисленного деления в исходной системе с основанием ( ) до получения остатка. Если частное от такого деления не нуль, то далее частное рассматривается как делимое и процесс деления на ( ) продолжают. Как только очередное частное станет равным нулю, процесс деления прекращают.

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

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

В этом случае для преобразования чисел необходимо воспользоваться формулой (1.11):

, (1.11)

 

где - количественный эквивалент числа ( );

- цифра, ;

- основание системы счисления;

- количество разрядов в целой части числа слева от запятой;

- количество разрядов в дробной части числа справа от запятой;

- позиция цифры в числе.

 

Тогда можно сказать, что - это весовой коэффициент т.е. (основание системы счисления возведенное в степень позиции цифры в числе).

Перевод чисел из не десятичной системы счисления в недесятичную систему счисления и основания систем счисления кратны степени двойки.

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

Алгоритм перевода состоит из двух шагов:

- шаг 1 - из восьмеричной системы счисления перевести в двоичную систему счисления. Каждая цифра восьмиричного числа переводится отдельно в двоичную систему счисления. Достаточно объединить цифры двоичного числа в группы по столько цифр, каков показатель степени, т.к. перевод осуществляется из восьмеричной системы счисления, то группы будут содержать три цифры ( ), такая группа называется триадой;

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

В целой части числа группировка производится справа налево, в дробной части числа – слева направо. Если в последней группе (тетраде) недостает цифр, то дописываются нули: в целой части числа – слева, в дробной части числа – справа. Затем каждая группа заменяется соответствующей цифрой новой системы счисления.

Перевод чисел из недесятичной системы счисления в недесятичную систему счисления и основания систем счисления не кратны степени двойки.

Если необходимо перевести число из пятиричной системы счисления в троичную систему счисления, необходим промежуточный перевод через десятичную систему счисления.

Алгоритм перевода состоит из двух шагов:

- шаг 1 - из пятиричной системы счисления перевести в десятичную систему счисления. Перевод осуществляется согласно формулы (1.11);

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

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

Двоично-десятичное число разбивается на группы которые содержат четыре цифры ( ). Такая группа называется тетрадой. В целой части числа группировка производится справа налево, в дробной части числа – слева направо. Если в последней группе (тетраде) недостает цифр, то дописываются нули: в целой части числа – слева, в дробной части числа – справа.

Затем каждая группа заменяется соответствующей цифрой новой системы счисления.

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

Пусть исходное число ( ), записанное в системе счисления с помощью цифр ( ) с основанием ( ), имеет вид:

 

, (1.12)

 

Тогда число ( ) в новой системе счисления с основанием ( ), будет иметь вид:

 

, (1.13)

 

Переписав по схеме Горнера, получим:

 

, (1.14)

 

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

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

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

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

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

Эти операции повторяют либо до получения нулевой дробной части произведения, либо до получения необходимого количества разрядов числа ( ). Старшая цифра результата перевода (то есть, первая после запятой) совпадает с первой отделенной целой частью, вторая цифра результата - со второй отделенной целой частью и т.д.

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

Для перевода неправильной десятичной дроби в двоичную систему счисления необходимо отдельно перевести целую часть числа и отдельно дробную часть числа.

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

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

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

Контрольные вопросы

 

1. Опишите алгоритм перевода целых чисел из десятичной системы счисления в недесятичную систему счисления.

2. Опишите алгоритм перевода целых чисел из недесятичной системы счисления в десятичную систему счисления.

3. Опишите алгоритм перевода целых чисел из недесятичной системы счисления в недесятичную систему счисления при условии, что основания систем счисления кратны степени двойки.

4. Опишите алгоритм перевода чисел из недесятичной системы счисления в недесятичную систему счисления при условии, что основания систем счисления не кратны степени двойки.

5. Опишите алгоритм перевода чисел из десятичной системы счисления в двоично-десятичную систему счисления.

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

7. Опишите алгоритм перевода неправильной десятичной дроби в двоичную систему счисления.

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

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