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

ОГЛАВЛЕНИЕ

1. Введение

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

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

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

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

6. Текст программы с комментариями

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

8. Как пользоваться программой

ВВЕДЕНИЕ

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

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

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

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

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

II. ПОСТАНОВКА ЗАДАЧИ

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

III. ТЕОРЕТИЧЕСКАЯ ОСНОВА РЕШЕНИЯ ЗАДАЧИ

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

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

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

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

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

Таким образом, мы получили четыре старших разряда и число примет вид 1000хххххх. Вычисляем 25=32 и видим, что 32 < 55, значит шестой разряд равен 1 (результат 10 001ххххх), остаток 55−32=23.24=16 < 23 — пятый разряд 1 => 100 011хххх. Остаток 23−16=7.23=8 > 7 => 1 000 110ххх. 22=4 < 7 => 10 001 101хх, остаток 3.21=2 < 3 => 100 011 011х, остаток 1.20=1 = 1 => 1 000 110 111. Мы получили конечный результат.

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

Определим максимальный разряд. Т. к. 162=256 < 567, а 163=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*162=55. Определим, что будет стоять во втором разряде. Так как 3*161=48 < 55, а 4*161=64 > 55, то во втором разряде будет стоять цифра 23 0. Остаток=55−3*161=7. Определяем первый разряд: т.к. 160=1 то цифра первого разряда равна остатку, т. е. 27 0. Таким образом, мы получили число 2237 0, но уже в шестнадцатеричной системе исчисления.

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

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

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

IV. МЕТОДОЛОГИЧЕСКИЙ ПОДХОД

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

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

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

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

VII. ПОДРОБНЫЕ РАЗЪЯСНЕНИЯ ПО ПРОГРАММЕ

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

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

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