Действий в различных системах счисления

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

Обратный переход осуществляется по формуле:

 

x_n = a_{m -1} ^. n^{m -1}+ a_{m -2} ^. n^{m -2}+…+ a ₀ ^. n ⁰ (2.2)

 

Перевод из двоичной системы счисления в восьмиричную:

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

Перевод из двоичной в шестнадцатиричную осуществляется аналогично, но делится на группы по 4 цифры.

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

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

Перевод правильных дробей:

1. Необходимо отделить вертикальной чертой дробную часть

2. Умножить дробную часть на основание новой системы счисления

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

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

Перевод неправильных дробей: отдельно переводится целая часть, отдельно – дробная.

 

Операции с двоичными числами:

0+0=0 0-0=0 0*0=0

0+1=1 1-0=1 0*1=0

1+0=1 1-1=0 1*0=0

1+1=10 10-1=1 1*1=1

0-1=1

Сложение:

75+28 = 103 1001011

75₁₀ = 1001011₂ + 11100

28₁₀ = 11100₂ 1100111 = 103

Вычитание: 75 – 28 = 47

Отрицательное число 28 для проведения с ним арифметических действий должно быть переведено в дополнительный код.

11100 – Прямой код числа 28

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

Обратный код 00011

Дополнительный код 00100

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

 

+ 1100100

0101111=47

Алгоритмизация

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

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

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

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

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

• Дискретность

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

• Понятность

Каждая команда алгоритма должна быть понятна тому, кто исполняет алгоритм; в противном случае эта команда и, следовательно, весь алгоритм в целом не могут быть выполнены. Данное требование можно сформулировать более просто и конкретно. Составим полный список команд, который умеет делать испол­нитель алгоритма, и назовем его системой команд исполнителя (СКИ). Тогда понятными будут являться только те команды, которые попадают в этот список.

· Определенность (или детерминированность)

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

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

• Результативность

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

• Корректность

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

• Массовость

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

Таковы основные свойства алгоритмов. Если их внимательно проанализировать, то становится очевидным, что исполнитель алгоритма не нуждается в какой-либо фантазии и сообразительности. Более того, для выполнения алгоритма совсем не требуется его понимание, а правильный результат может быть получен путем формального и чисто механического следования содержанию алгоритма.

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

Основными способами записи алгоритмов являются:

§ словесный;

§ словесно-формульный;

§ на алгоритмическом языке;

§ графический (блок-схема);

§ на языке программирования высокого уровня.

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

Блок-схема – графическое представление алгоритма

начало

a, b	Начало и конец алгоритма
А=А+5	Блок ввода – вывода в общем виде
a < b	Блок присваивания или блок вычислений
	Блок условия
А	Соединительный блок, если блок – схема не помещается на лист
i=1…100,10	Блок цикла For. Используется для задания цикла со счетчиком.

Задача: «Рассчитать площадь и периметр прямоугольника по двум известным сторонам».

начало

a, b

S=a*b

P=(a+b)*2

P, S

конец

Рисунок 1 – Пример выполнения алгоритма

 

1. Начало.

2. Вводим стороны прямоугольника.

3. Вычисляем площадь прямоугольника по формуле S=a*b.

4. Вычисляем периметр прямоугольника по формуле P=(a+b)*2.

5. Выводим значения площади и периметра.

6. Конец.