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

 

Основные темы параграфа:

■ перевод двоичного числа в десятичную систему счисления;

■ перевод десятичного числа в двоичную систему счисления.

 

В§ 18 учебника для 8 класса рассказано о двоичной системе счисления, которая используется в компьютере для представления чисел и выполнения вычислений с ними. Там же описаны правила, по которым можно вручную выполнить перевод двоичных чисел в десятичную систему счисления и обратный перевод — десятичных чисел в двоичные. Рассмотрим программы на Паскале для автоматического перевода чисел из одной системы счисления в другую. Ограничимся переводом целых чисел.

 

Программа перевода двоичного числа в десятичную систему счисления

 

Рассмотрим программу на Паскале, по которой происходит перевод целого двоичного числа в десятичную систему.

 

Program Numbers_2_l0;

var N10,N2,k: longint;

Begin

write('N2='); readln(N2);

{ввод исходного двоичного числа}

k:=1; N10:=0;

while (N2<>0) do

{цикл выполняется, пока N2 не равно нулю}

Begin

N10:=N10 + (N2 mod 10)*k;

{суммирование развернутой формы}

к:=к*2;

{вычисление степеней двойки: 2, 2², 2³...}

N2:=N2 div 10

{отбрасывание младшей цифры}

end;

writeln('N10=', N10) {вывод десятичного числа}

End.

 

В программе использованы следующие переменные:

N2 — целое двоичное число — исходное данное;

N10 — десятичное число — результат;

 

Тип longint — длинный целый тип. Значения величин этого типа лежат в диапазоне от -2147483648 до 2147483647. Значит, данная программа может работать с числами, не более чем 9-значными.

В этой программе используются две незнакомые вам операции с целыми числами. Операция div — целочисленное деление. Делимое и делитель являются целыми числами, а результат — целая часть частного. Например: 7 div 2 =3. Для отбрасывания младшего разряда целого числа используется целочисленное деление на 10. Например: 1234 div 10 = 123 — отбрасывается младший разряд.

Операция mod дает остаток от целочисленного деления. Например: 7 mod 2 = 1. Для получения младшего разряда целого числа вычисляется остаток от целочисленного деления на 10. Например: 1234 mod 10 = 4 — выделяется разряд единиц.

 

Пример. При переводе по данной программе двоичного числа 1101₂ в десятичную систему на экране увидим:

N2=1101

N10=13

Следовательно, в итоге получили: 1101₂=13.

 

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

 

Шаг алгоритма	Команды алгоритма	N2	k	N10	Проверка условия
	Ввод N2, k:=1, N10:=0
	N200				1101≠0, да
	N10:=N10 + (N2 mod 10)*k
	k:=k*2
	N2:=N2 div 10
	N200				110≠0,да
	N10:=N10 + (N2 mod 10)*k
	k:=k*2
	N2:=N2 div 10
	N200				11≠0,да
	N10:=N10 + (N2 mod 10)*k
	k:=k*2
	N2:=N2 div 10
	N2<>0				1≠0,да
	N10:=N10 + (N2 mod 10)*k
	k:=k*2
	N2:=N2 div 10
	N200				0≠0, нет
	Вывод N10

 

Программа перевода десятичного числа в двоичную систему счисления

 

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

 

Program Numbers_10_2;

var N10, N2, k: longint;

Begin

write('N10='); readln(N10);

{Ввод исходного десятичного числа}

k:=1; N2:=0;

Repeat

N2:=N2 + (N10 mod 2)*k;

{Суммирование развернутой формы}

k:=k*10; {Вычисление базиса: 10, 100, 1000,...}

N10:=N10 div 2 {Целочисленное деление на 2}

until (N10=0);

{Цикл заканчивает выполнение при N10=0}

writeln('N2=', N2) {Вывод двоичного числа}

End.

 

Здесь использованы те же обозначения, что и в предыдущей программе. Исходными данными являются: N10 — десятичное число. Результат получается в переменной N2 — число в системе с основанием 2.

В алгоритме используется цикл с постусловием (repeat... until). Цикл повторяется до выполнения условия: N10 = 0.

Пример использования программы. Переведем число 25 в двоичную систему счисления. Работа программы на экране компьютера отразится следующим образом:

N10=25

N2=11001

Следовательно, в результате получили: 25 =11001₂.

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

 

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

 

Программирование перевода 10 → 2 и 2 → 10 основано на использовании операций над целыми числами: div — целочисленное деление, mod — остаток от целочисленного деления.

 

Вопросы и задания

 

1. Введите в компьютер и отладьте программу Number S_2_l 0. Переведите с ее помощью в десятичную систему счисления следующие двоичные числа: 111110; 1111111; 100000. Проверьте правильность результатов.

2. Введите в компьютер и отладьте программу Number s_l 0_2. Переведите с ее помощью в двоичную систему счисления следующие десятичные числа: 255; 512; 1023. Проверьте правильность результатов.

 

Сложность алгоритмов

 

Основные темы параграфа:

■ объемная сложность алгоритма;

■ временная сложность алгоритма;

■ алгоритмы перебора;

■ сложность алгоритмов перебора.

 

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

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

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

S:=0; for i:=l to N do S:=S + X[i];

В теле цикла выполняется две операции: сложение и присваивание. Число повторений цикла равно N. Следовательно, суммарное число выполняемых операций равно N • 2.Значит, время выполнения всего цикла будет пропорционально N • 2: Т - N • 2. В таком случае говорят, что временная сложность алгоритма зависит линейно от объема данных. Во сколько раз возрастет N, во столько же раз возрастет время выполнения программы.

Если вернуться к алгоритму поиска наибольшего и наименьшего значений массива, то в нем также имеется один цикл, хотя тело цикла содержит большее число операций. Но с увеличением размера массива (N) время выполнения программы будет также увеличиваться линейно, т. е. пропорционально N. Следовательно, временная сложность алгоритмов суммирования массива и поиска в массиве максимального (минимального) элемента одинаковая — линейная.

Теперь оценим временную сложность алгоритма сортировки массива методом пузырька. По-прежнему обозначим через N размер массива. Алгоритм содержит два вложенных цикла. Внешний цикл имеет длину N - 1. Внутренний цикл с каждым повторением изменяет свою длину по убыванию: N - 1 ,N - 2, N - 3,..., 2, 1.Суммарное число повторений цикла можно посчитать так:

• вычислим среднюю длину внутреннего цикла:

[(N - 1) + 1]/2 = N/2;

• умножим эту величину на число повторений внешнего цикла:

( N - 1) • N /2 = (N ² - N)/2.

Временная сложность алгоритма определяется слагаемым с наибольшей степенью: Т ~ N ². В таком случае говорят, что временная сложность алгоритма сортировки методом пузырька имеет второй порядок по объему данных, т. е. пропорциональна квадрату N. Например, если размер массива увеличить в 10 раз, то время сортировки возрастет в 100 раз.