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

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

Введение

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

Рассмотрим подробнее, как это осуществляется. Пусть нам надо умножить число 1101 на 101 (оба числа в двоичной системе исчисления). Машина делает это следующим образом: она берет число 1101, и если первый элемент второго множителя равен 1 то она заносит его в сумму.

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

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

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

Постановка задачи

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

Теоретическая основа решения задачи

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

Допустим, нам нужно перевести число 567 десятеричной системы в двоичную систему. Делается это следующим образом: отыскивается максимальная степень двойки, чтобы два в этой степени было меньше или равно исходному числу. В нашем случае это 9, т. к. 2^9=512, а 2^10=1024, что больше нашего начального числа. Таким образом, мы получили число разрядов результата. Оно равно 9+1=10.

Значит, результат будет иметь вид 1 ххххххххх, где вместо х может стоять 1 или 0. Найдем вторую цифру результата.

Возведем двойку в степень 9 и вычтем из исходного числа: 567-2^9=55. Затем сравниваем с числом 2^8=256.

Так как 55 меньше 256 то девятый разряд будет нулем, т.е. результат уже примет вид 10 хххххххх. Рассмотрим восьмой разряд: 2^7=128 > 55, значит, и восьмой разряд будет нулем. Т. к. 2^6=64 то седьмой разряд равен нулю.

Таким образом, мы получили четыре старших разряда и число примет вид 1000 хххххх. Вычисляем 2^5=32 и видим, что 32 < 55, значит шестой разряд равен 1 (результат 10001 ххххх), остаток 55-32=23.2^4=16 < 23 - пятый разряд 1 => 100011 хххх. Остаток 23-16=7.2^3=8 > 7 => 1000110 ххх. 2^2=4 < 7 => 10001101 хх, остаток 3.2^1=2 < 3 => 100011011х, остаток 1.2^0=1 = 1 => 1000110111. Мы получили конечный результат.

Теперь попробуем перевести тоже число 567, но уже в шестнадцатеричную систему. Подход примерно такой же.

Определим максимальный разряд. Т. к. 16^2=256 < 567, а 16^3=4096 > 567, то максимальный разряд 2+1=3. Определим число, которое будет стоять в третьем разряде.

Ищется максимальный множитель в пределах от 1 до 15, чтобы текущая степень шестнадцати умноженная на этот множитель была меньше или равнялась исходному числу (а в дальнейшем - остатку). В нашем примере этот множитель 2, т. к. 256*2=512 < 567, а 256*3=768 > 567. Значит, старший разряд нашего результата будет равен 22 0, и результат примет вид 2 хх, где вместо х могут стоять любые цифры или буквы из ниже перечисленных: 0,1,2,3,4,5,6,7,8,9, A, B, C, D, E, F. Вычисляем остаток: 567-2*16^2=55. Определим, что будет стоять во втором разряде. Так как 3*16^1=48 < 55, а 4*16^1=64 > 55, то во втором разряде будет стоять цифра 23 0. Остаток=55-3*16^1=7. Определяем первый разряд: т. к. 16^0=1 то цифра первого разряда равна остатку, т.е. 27 0. Таким образом, мы получили число 2237 0, но уже в шестнадцатеричной системе исчисления.

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

Допустим нам нужно перевести число 24A3F 0в десятеричную систему. Берем старший (4-ый) разряд и возводим 16 в степень 4-1=3, получаем 16^3=4096. Полученный результат умножаем на значение четвертого разряда, т.е. 4.

Получается 4096*4=16384. Этот результат мы заносим в сумму. Переходим к следующему разряду: 16^2=256.256 нужно умножить на значение третьего разряда т.е. A. Как известно в шестнадцатеричной системе исчисления буквы от A до F символизируют числа от 10 до 15 (A=10, B=11, C=12, D=13, E=14, F=15). Умножив 256 на 10, получим 2560 и этот результат добавляем к сумме, в которой у нас пока было 16384. В сумму у нас получилось 18944. Переходим ко второму разряду: 3*16^1=48, добавив это в сумму, получим 18992. И последний разряд: 15*16^0=15. Конечная сумма равна 219007 0. Мы получили результат в десятеричной системе исчисления.

Методологический подход

Рассматривая перевод из десятеричной системы исчисления в двоичную и шестнадцатеричную, можно найти много общего. В обоих случаях мы ищем максимальную степень, затем в обоих случаях сравниваем остаток с числом возведенным в степень разряда. Единственная разница заключается в том, что при переводе в двоичную систему основанием степени служит двойка, а при переводе в шестнадцатеричную систему основанием служит число шестнадцать. Возникает вопрос: а нельзя ли объединить оба этих перевода в одну процедуру, в которую в качестве параметров передавать основание степени? При более подробном рассмотрении перевода в двоичную систему можно заметить, что, сравнивая остаток со степенью двойки мы отмечаем только как бы два состояния: да или нет, т.е. 1 или 0, а при переводе в шестнадцатеричную систему мы рассматриваем не просто степень числа шестнадцати, а произведение этой степени на величину будущего разряда.

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

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

В результате такого подхода к решению задачи алгоритм значительно упрощается, т. к. в нем нет ветвлений.

Подробные разъяснения по программе

Программа начинается стандартной строкой: Program Perevod; Далее следует описательная часть программы. Она состоит из нескольких разделов:

- Uses: указывает какие внешние TPU файлы будет использовать программа (это специфика Turbo Pascal).

- Const: описывает используемые в программе константы. S - массив констант строк символов состоящих из пятидесяти символов. Им присваиваются значения, которые будут использоваться для составления меню.

- Var: описывает переменные.

Longint - целочисленный тип, значение которого может изменяться от -2147483648 до 2147483647 и занимает в памяти 32 бита.

Integer - целочисленный тип, может принимать значение от -32768 до 32767 и занимает объем памяти в 16 бит.

Char - символьный тип, может принимать значение любого символа.

Byte - целочисленный тип, может принимать значения от 0 до 255 и занимает объем памяти в 8 бит.

Set of '0'. 'F' - тип множество, элементы которого могут быть любые символы находящиеся в промежутке от '0' до 'F'.

Array [1. 255] of Char - массив символов размером в 255 знаков.

String - строка символов переменной длины (длина может изменяться от 1 до 255 символов).

Далее в программе идет описание процедуры Zast. Эта процедура выводит на экран в столбик пункты меню, в которых указывается из какой и в какую систему исчисления пользователь хочет перевести число. Структура процедуры линейная. Она состоит из нескольких операторов:

Window (1,1,80,24) - отводит окно доступное для вывода.

ClrScr - очищает экран.

TextColor (15) - устанавливает цвет последующего вывода (ярко белый).

GoToXY (x, y) - переводит курсор в строку с номером y и столбец с номером x.

Write () - выводит на экран от позиции курсора выражение, указанное в скобках.

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

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

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

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

После выполнения процедуры Zast следует оператор организации цикла с пост-условием Repeat. Внутри этого цикла осуществляется выполнение всей дальнейшей программы.

Внутри него последовательно идет установка цвета на малиновый, перемещение курсора в позицию 13,2 и вывод символа метки текущего положения курсора в меню (2> 0).

Далее идет оператор ожидания ввода клавиши ReadKey.

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

После этого идет блок условных операторов If, которые обрабатывают нажатую клавишу и выполняют определенные действия в соответствии с нажатой клавишей.

Первый оператор If обрабатывает ситуацию, если была нажата клавиша «ВВЕРХ». В результате его выполнения значение переменной Y уменьшается на единицу, а если она была равна 1, то ее значение становится равным 7.

Аналогично действует второй условный оператор, только он обрабатывает клавишу «ВНИЗ».

Третий условный оператор принимает значение True если была нажата клавиша ESC (выход). В этом случае пе - 13 ременной Y присваивается значение 7, а переменной Klav значение клавиши ВВОД. Оба эти значения переменных символизируют выход из внешнего цикла с пост-условием, а значит и выход из программы.

Четвертый условный оператор обрабатывает клавишу ВВОД, но при условии, что Y<7, т.е. курсор в меню не подведен к последней строке со значением выхода из программы. Если значение выражения этого условного оператора примет значение True, то начинается выполнение основной части программы, которая осуществляет непосредственно перевод из одной системы исчисления в другую.

Сначала очищается экран. Затем малиновым цветом в первой строке выводится из какой и в какую систему исчисления программа будет переводить числа. После этого, в нижней строке зеленым цветом выводится фраза «ESC - ВЫХОД В МЕНЮ». Затем устанавливается цвет вывода на экран белый и выделяется окно для вывода исключающее первую и последнюю строки экрана. Переменной Stroka (переменная указывает строку положения курсора) присваивается значение 2.

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

Далее в программе следует оператор цикла с пост-условием Repeat, внутри которого осуществляется ввод исходного числа. Сначала идет ожидание нажатия клавиши, и если клавиша будет нажата, то значение этой клавиши запишется в переменную Klav. Стандартная функция UpCase переводит символ из нижнего регистра в верхний. Условный оператор If определяет, является ли нажатая клавиша допустимой, и если это так, то переменная Kol (количество символов во введенном числе) увеличивается на единицу, значение клавиши записывается в массив A (массив символов с исходным числом) и введенная клавиша отображается на экране.

Следующий условный оператор определяет, не была ли нажата клавиша ЗАБОЙ. В этом случае Kol уменьшается на единицу, курсор перемещается на одну позицию влево и стирается последний введенный символ.

Оператор Until осуществляет выход из цикла с пост-условием в том случае, если была нажата клавиша ВВОД или клавиша ESC.

Далее следует условный оператор, который обрабатывает условие нажатия клавиши ВВОД. Если это так, то это означает, что исходное число введено и пользователь хочет получить результат, и необходимо приступить к непосредственному переводу.

Внутри этого условного оператора выполняется цикл от 1 до Kol (количество символов в исходном числе). Внутри этого цикла условным оператором If определяется в зависимости от символа его числовой эквивалент для дальнейшего умножения, а затем переменная Promeg увеличивается на число равное произведению полученного числового эквивалента на основание исходной системы исчисления в степени Kol-1. В результате выполнения этого цикла мы из исходного числа в виде набора символов получили его значение в десятеричной системе исчисления. Таким образом половину перевода мы осуществили. Теперь нам нужно это значение перевести в необходимую систему исчисления.

Далее следует обнуление переменной I, а после этого циклом с пост-условием определяется максимальный порядок результата (см. п. III. Теоретические основы решения задачи).

После того как мы определили этот порядок и записали его в переменную I, организуется цикл от I до 0. Внутри этого цикла проводятся следующие преобразования для получения необходимого результата:

- переменной Help присваивается числовое значение Jтого элемента в исходном результате;

- условным оператором If из этого значения получает символ, который будет стоять в результате;

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

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

Все эти действия были описаны в теоретической части настоящего реферата, а их практическое осуществление не требует никакого труда.

После выполнения этих операций, программа переходит к получению следующего символа, пока не получит последний символ искомого результата. Как только результат получен, он выводится на экран оператором WriteLn.

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

Условие выхода из этого цикла - это нажатие клавиши ВВОД, если курсор меню стоял на строке «ESC - ВЫХОД В DOS».

Если это условие выполнилось, то осуществляется очищение экрана и выполнение программы завершается.

Если Вы ошиблись при вводе исходного числа, то можно нажать клавишу ЗАБОЙ, и последний введенный символ сотрется.

Чтобы завершить выполнение программы или осуществить перевод из другой системы исчисления, нужно нажать клавишу ESC (о чем указано в нижней строке экрана). В этом случае Вы окажетесь в начальном меню. Если Вы хотите продолжить перевод, то опять клавишами ВВЕРХ и ВНИЗ подведите курсор к нужной строке меню и нажмите ВВОД.

Если же Вы хотите завершить выполнение программы, то это можно сделать двумя вышеописанными способами.

Program Perevod; Uses Crt; Const P1='Перевод из '; {константы для начального меню} s: array [1. 7] of string[50]=(p1+'десятеричного кода в двоичный. ', p1+'двоичного кода в десятеричный. ', p1+'десятеричного кода в шестнадцатиричный. ', p1+'шестнадцатиричного кода в десятеричный. ', p1+'двоичного кода в шестнадцатиричный. ', p1+'шестнадцатиричного кода в двоичный. ', ' ESC - ВЫХОД В DOS'); Var Promeg, Chast: Longint; Znach, j: Integer; Klav: Char; i, Stroka, Isx, Kon, y, Kol, Help: Byte; Keys: Set of '0'. 'F'; a: Array [1. 255] of Char; Otv, Pom: string; Procedure Zast; {процедура вывода меню} begin Window (1,1,80,24); {выделить окно 80х24} ClrScr; {очистить окно} TextColor(15); {установить цвет - белый} FOR I: =1 TO 7 do begin {цикл по строкам} GoToXY (15, I*2); Write (s[i]); {формирование меню} end; end {zast}; {конец процедуры меню} Function Stepen (Chis, St: Byte): Longint; {функция возведения в степень} var c: Byte; Res: longint; begin Res: =1; For c: =1 to st do Res: =Res*chis; Stepen: =Res; {присвоение функции значения} End {Stepen}; {конец функции возведения в сепень} Begin {НАЧАЛО ОСНОВНОЙ ПРОГРАММЫ} y: =1; {y - текущая строка в меню} Zast; {вывести меню} Repeat {цикл для перемещения в меню} TextColor(13); GoToXY (13, y*2); Write (Chr(16)); {вывести метку текущей строки меню} klav: =ReadKey; {считывание клавиши в klav} GoToXY (13, y*2); Write (' '); {стирание старой метки текущей строки} if Ord(Klav) =72 then if y > 1 then y: =y-1 else y: = 7; {если клавиша ВВЕРХ} if Ord(Klav) =80 then if y < 7 then y: =y+1 else y: = 1; {если клавиша ВНИЗ} if Ord(Klav) =27 then begin y: =7; klav: =Chr(13) end; {если клавиша ESC} if (Ord(Klav) =13) and (y<7) then begin {если клавиша ВВОД не на выходе} ClrScr; {очистить экран} TextCOLOR (13); GoToXY (20,1); Write (s[y]); {вывести название перевода} TextCOLOR (10); GoToXY (31,24); Write ('ESC - ВЫХОД В МЕНЮ'); {вывести клавишу для выхода} TextColor(15); {поменять цвет - белый} Window (1,2,80,23); {установить окно со 2 по 23 строки} Stroka: =2; {текущая строка} - 9 Case y of {определение клавиш которые можно будет нажимать} 1,3: begin {если перевод из десятиричного кода} Isx: =10; Keys: =['0'. '9']; {возможные клавиши} If y=1 Then Kon: =2 else Kon: =16; {присвоение системы исчисления результата} end; 2,5: begin Isx: = 2; Keys: =['0', '1']; {определение клавиш которые можно будет нажимать} If y=2 Then Kon: =10 else Kon: =16; {присвоение системы исчисления результата} end; 4,6: begin isx: =16; keys: =['0'. '9', 'A'. 'F']; {определение клавиш которые можно будет нажимать} if y=4 then kon: =10 else kon: =2; {присвоение системы исчисления результата} end; end; Repeat {основной цикл для перевода} Write ('? '); Promeg: =0; Kol: =0; Otv: =''; {подготовительные действия} Repeat {цикл для ввода числа} klav: =ReadKey; {чтение клавиши} if UpCase(Klav) in Keys then begin {если клавиша допустимая} kol: =kol+1; {количество символов в исходном числе} a[kol]: =UpCase(Klav); {запоминание введенного символа} Write (a[kol]); {вывод нажатого символа} end; if (Ord(Klav) =8) and (Kol>0) then begin {если клавиша ЗАБОЙ} kol: =kol-1; GoToXY (WhereX-1, WhereY); ClrEol; end; Until (Ord(klav) =13) or (Ord(klav) =27); {пока не нажата ВВОД или ESC} if Ord(klav) =13 then begin {если клавиша ВВОД - начало обработки результата} for i: =1 to kol do begin {перевода введенного числа в десятеричную систему} if a[i]<'A' then Znach: =Ord (a[i]) -48 else Znach: =Ord (a[i]) -55; promeg: =promeg+Znach*Stepen (isx, kol-i); end; i: =0; Repeat {определение максимального порядка результата} i: =i+1; Chast: =Trunc (Promeg/Stepen (Kon, i)); Until Chast<Kon; For j: =i downto 0 do begin {перевод в нужную систему исчисления} Help: =Trunc (Promeg/Stepen (Kon, j)); If Help>9 Then Pom: =Chr (55+Help) Else Str (Help, Pom); Otv: =Otv+Pom; Promeg: =Promeg-Help*Stepen (Kon, j); end; WriteLn (' = ', Otv); {вывод результата} end; {конец обработки результата} Until Ord(Klav) =27; {если нажата ESC то выход в основное меню} Zast; {вывод заставки} end; Until (Ord(Klav) =13) and (y=7); {если в меню нажали ESC или ВВОД на выходе} ClrScr {очистить экран} end.