Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





 

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

,

где:

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

A – мантисса;

p – порядок.

 

Например в десятичной системе счисления число 3,14 можно представить в виде:

3,14=0,314*101

Здесь мантисса равна 0,314, а порядок равен 1.

Такое представление чисел далеко не однозначно. Число 3,14 можно представить как:

3,14=3,14*100=0,314*101=0,0314*102=…

 

Порядок числа определяет положение запятой и записи мантиссы. При изменении порядка соответствующим образом меняется положение запятой. Запятая как бы «плавает». Это изменение запятой и дало название способу представления чисел.

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

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

3,14=0,314*101

 

Здесь A=0,314, p=1. Аналогично для числа -0,00062 имеем -0,00062=0,62*10-3 A=0,62, p=-3.

Точно также в любой системе счисления с основанием Q число a неравное нулю записывается в форме с плавающей точкой. Число a называется нормализованным, если выполняется условие:

Пример 1.

Пример 1.

Дано A(10)=43,97. Найти A(2).

Решение:

Сначала переводим целую часть B(10)=43

B(2)=101011

Затем дробную C(10)=97

C(2)= 1100001

 

Записываем результат

D(2)= 101011,1100001

Теперь приводим число к нормализованному виду. Для этого сдвигаем запятую на шесть разрядов 6(10)= 110(2).

Получили мантиссу равную 0,1010111100001 и порядок равный 110.



 

Ответ:

A(2)=0,1010111100001*10110

 

 

Арифметические операции в системах счисления используемых вычислительной техникой.

 

Все правила вычислений любой позиционной системы счисления совпадают с правилами десятичной системы счисления.

 

Арифметические операции с целыми числами в двоичной системе счисления.

 

Как и в десятичной системе счисления, все арифметические операции с целыми числами в двоичной системе счисления основаны на таблице сложения и умножения, приведенных в таблицах 6 и 7.

 

Таблица 6. Сложение двоичных чисел   Таблица 7. Умножение двоичных чисел
     
 
 

 

Пример 1.

Дано A(2)=1001101. B(2)=10101. Найти C(2)= A(2)+B(2).

+10101

 

Ответ C(2)=1100010

 

Пример 2.

Дано A(2)=1101. B(2)=1010. Найти C(2)= A(2)*B(2).

*1010
+1101 +0000 +1101

 

Ответ C(2)=1100010

 

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

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

 

Арифметические операции с целыми числами в восьмеричной и шестнадцатеричной системах счисления.

 

Как и в десятичной или двоичной системах счисления все арифметические операции с целыми числами в восьмеричной или шестнадцатеричной системах счисления основаны на таблицах сложения и умножения. Таблицы сложения и умножения в восьмеричной и шестнадцатеричной системах счисления приведены в таблицах 8, 9, 10 и 11.

Таблица 8.

Таблица сложения целых чисел в восьмеричной системе счисления.

 

 

Таблица 9.

Таблица умножения целых чисел в восьмеричной системе счисления.

 

 

Таблица 10.

Таблица сложения целых чисел в шестнадцатеричной системе счисления.

  A B C D E F
A B C D E F
A B C D E F
A B C D E F
A B C D E F
A B C D E F
A B C D E F
A B C D E F
A B C D E F
A B C D E F
A B C D E F
A A B C D E F
B B C D E F 1A
C C D E F 1A 1B
D D E F 1A 1B 1C
E E F 1A 1B 1C 1D
F F 1A 1B 1C 1D 1E

 


Таблица 11.

Таблица сложения целых чисел в шестнадцатеричной системе счисления.

  A B C D E F
A B C D E F
A C E 1A 1C 1E
B F 1B 1E 2A 2D
B 1C 2C 3C
A F 1E 2D 3C 4B
C 1E 2A 3C 4E 5A
E 1C 2A 3F 4D 5B
1B 2D 3F 5` 5A 6C 7E
A A 1E 3C 5A 6E 8C
B B 2C 4D 6E 8F 9A A5
C C 3C 6C 9C A8 B4
D D 1A 4E 5B 8F 9C A9 B6 C3
E E 1C 2A 7E 8C 9A A8 B6 C4 D2
F F 1E 2D 3C 4B 5A A5 B4 C3 D2 E1

 

 

Арифметические операции с вещественными числами в двоичной системе счисления.

 

Арифметические операции с вещественными числами в двоичной системе счисления аналогичны операциям в десятичной системе счисления. Рассмотрим процесс выполнения действий на примерах.

 

Пример 1.

Дано A(2)=10011,01. B(2)=1,0101 представленные в форме записи с фиксированной запятой. Найти C(2)= A(2)+B(2).

Решение:

Выравниваем количество знаков после запятой: A(2)=10011,0100. B(2)=1,0101

Выполняем операцию сложения

10011,0100 +1,0101
10100,1001

 

Ответ C(2)=10100,1001

 

Пример 2.

Дано A(2)=0,1001101*10101. B(2)=0,10101*101 представленные в форме записи с плавающей запятой. Найти C(2)= A(2)+B(2).

Решение:

Выравниваем порядки чисел:

A(2)=0,1001101*10101.

B(2)=0,10101*101=0,000010101*10101.

Складываем мантиссы:

Для этого выравниваем количество знаков после запятой: A(2)=0,100110100, B(2)= 0,000010101

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

0,100110100 +0,000010101
0,101001001

В результате сложения мантисс получили результат: 0,101001001. Дописываем показатель и получаем ответ.

Ответ C(2)=0,101001001*10101.

 

Операции умножения вычитания и деления производятся по аналогичному алгоритму.

 

Логические операции.

 

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

Существует три основных закона логического сравнения величин это И(and), ИЛИ(or) и НЕ(not). Схематическое представление элементов выполняющих логические операции и соответствующие им таблицы истинности представлено в таблице 12.

 

Таблица 12. Описание логических элементов вычислительной техники.

Операция Элемент Таблица истинности
Логическое произведение (конъюнкция). Операция «И». Результат логической суммы совпадает с результатом арифметического произведения. Результат будет равен истина, только в случае, если оба аргумента равны единице. A B A И Б
Логическая сумма (дизъюнкция). Операция «ИЛИ». Результат логической суммы, отличается от результата суммы двух одноразрядных двоичных чисел. Результатом будет истина, если хотя бы один входной аргумент равен единице. A B A ИЛИ B
Логическое отрицание(инверсия). Операция «НЕ» Результатом логической операции отрицание будет изменение значения входного аргумента: истина на лож и обратно. A НЕ A
           

 

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

Под сдвигом понимается смещение разрядов двоичного числа в право или в лево, в зависимости от указанного направления. Освободившееся после сдвига место заполняется нулями. В любой позиционной системе счисления сдвиг в лево(<<) на один разряд означает умножение на основание системы счисления, а сдвиг в право(>>) на один разряд - деление на основание системы счисление.

 

Пример 1.

Дано A(10)=123. Умножить число с помощью операции сдвига на 100(10).

Решение:

100=102 следовательно для умножения заданного числа на 100 необходимо выполнить сдвиг на два разряда в лево

A(10)=123*100=123 << 2=12300

Ответ A(10)=12300.

 

Пример 2.

Дано A(10)=345. Разделить число с помощью операции сдвига на 1000(10).

Решение:

Для выполнения операции деления на 1000 необходимо умножить исходное число на 1/1000

1/1000=0,001=10-3 следовательно для деления заданного числа на 1000 необходимо выполнить сдвиг на три разряда в право

A(10)=345/1000=345 >> 3=0,345

Ответ A(10)=0,345.

 

Пример 3.

Дано A(2)=11010. Умножить число с помощью операции сдвига на 100(2).

Решение:

100=22 следовательно для умножения заданного числа на 100 необходимо выполнить сдвиг на два разряда в лево

A(10)= 11010*100=11010 << 2=1101000

Ответ A(2)= 1101000.

 

Пример 4.

Дано A(2)=11010. Разделить число с помощью операции сдвига на 10 (2).

Решение:

Для выполнения операции деления на 10 необходимо умножить исходное число на 1/10

1/10=0,1=10-1 следовательно для деления заданного числа на 10 необходимо выполнить сдвиг на один разряда в право

A(10)=11010/10=11010 >> 1=1101

Ответ A(2)=1101.

Поскольку двоичная система счисления состоит всего из двух чисел {0,1} принято считать, что 0(2) в логических функциях представляет собой лож, а 1(2) истину. Исходя из этого при помощи логических элементов можно организовать любой вычислительный процесс. Рассмотрим процесс сложения двоичных чисел на примере двухразрядного сумматора рисунок 9.

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

 

Таблица 13. Процессы происходящие в двухразрядном сумматоре.

X Y (не X) (не Y) (Y и 1) (X и 2) (XиY) (3или4) S P

 

На схеме приведенной на рисунке 10 на вход сумматора поступает два одноразрядных числа записанных в двоичной системе счисления. На выходу получаем одно двухразрядное число представляющее собой сумму одноразрядных чисел записанных на входе. Преобразуем таблицу 13 в таблицу истинности для сложения одноразрядных чисел, записанных в двоичной системе счислении, таблица 14.

 

Таблица 14.

Результат работы сумматора, основанного на выполнении логических операций.

X Y PS

 

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

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

 

Введение в алгоритмизацию.

 

Понятие алгоритма.

 

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

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

Первым свойством алгоритма, является то, что он носит пошаговый(дискретный) характер определяемого им процесса.

Вторым свойством алгоритма является массовость, то есть существует некоторое множество объектов, которые могут служить исходными данными для рассматриваемого алгоритма. Например, для алгоритмов выполнения арифметических операций – сложения, вычитания умножения и деления, такими данными являются все действительные числа.

Например, для того, чтобы сложить два числа 15 и 17 используется алгоритм сложения в столбик.

 

+17

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

  1. Текущий разряд - крайний правый;
  2. Складываем значения цифр текущего разряда;
  3. Если значение суммы больше 9, добавляем единицу при сложении значений следующего разряда;
  4. Записываем значение правого разряда суммы;
  5. Если текущий разряд является последним, то сложение завершено, если нет, то текущим разрядом становиться следующий слева;
  6. Если сложение не завершено, то повторяем начиная со второго пункта.

Попробуем проделать операцию сложения тех же чисел (15 и 17) по представленному алгоритму:

  1. Текущий разряд - крайний правый (будем складывать 5 и 7);
  2. Складываем значение цифр текущего разряда 5+7=12;
  3. Значение суммы больше 9? Да, больше, при сложении значений следующего разряда будим добавлять единицу;
  4. Записываем значение сумм правого разряда 2;
  5. Текущий разряд не последний, переходим к следующему разряду;
  6. Складываем значение цифр следующего разряда 1+1=2 и дописываем единицу, так как значение суммы чисел предыдущего разряда было больше 9: 2+1=3.
  7. Значение суммы не больше 9, записываем значение суммы чисел разряда 3;
  8. Этот разряд является последним, поэтому сложение завершено. Получили результат 32.

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

Аналогичным образом можно составить алгоритм умножения, деления, вычитания и так далее.

Третьим свойством алгоритма, является то, что алгоритм должен быть понятен для исполнителя, то есть исполнитель знает как его выполнять. При этом исполнитель алгоритма выполняет «механически». Очевидно, что формулировка алгоритма должна восприниматься однозначно, а следовательно должна быть на столько точна, чтобы полностью определять все действия исполнителя.

Если применять один и тот же алгоритм к одним и тем же исходным данным, то мы всегда должны получать один и тот же результат. Например сколько бы раз мы не складывали числа «15» и «17», всегда будем получать один и тот же результат «32». И если при этом сравнивать результаты на каждом шаге выполнения алгоритма, то они так же будут идентичны. Таким образом можно говорить об однозначности алгоритмов.

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

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

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

Существует три основных вида шагов алгоритмов это:

1. действие(процесс) – выполнение какой либо операции, например вычисление суммы a=15+17 или положить монету в телефон автомат или набрать номер телефона, эти операции называются шагами действия – требуется что либо сделать.

2. условие(развилка) – сравнение каких либо исходных данных и определение на основе результата сравнения дальнейших действий, например если после набора номера телефон, по которому вы звонили занят, то появляется шаг условия повторить или нет, если повторить, то следует повторно набрать номер, а если нет, то перестать звонить.

3. повтор(цикл) – повторение каких либо операций, до тех пор, пока не выполнится какое либо условие, например – набирать номер телефона до тех пор, пока не дозвонитесь.

 

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

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

 

Таблица 15.

Основные элементы графического изображения алгоритма.

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

 

 

Алгоритмические системы.

 

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

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

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

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

  1. множество типов объектов, которыми могут являться исходные данные, подлежащих обработки алгоритмами данной системой;
  2. свойства исполнителя алгоритмов, то есть набор инструментов(средств, действий), которыми может пользоваться исполнитель для выполнения алгоритмов;
  3. множество типов объектов, которыми могут являться результаты выполнения алгоритмов данной системы;
  4. язык, на котором определяются правила адресованные исполнителю.

 

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

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

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

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

Еще одним параметром алгоритмической системы является требуемая точность конечного результата. Например, в алгоритмической системе предназначенной для обработки числовой информации, при определенных исходных данных на каком либо шаге может появиться необходимость деления единицы на тройку. Из арифметики известно, что результатом выполнения этой операции будет 0,33333…. То есть операцию деления единицы на тройку не возможно выполнить за конечное число шагов, возникает неопределенной или зацикливание процесса. Для того, чтобы избежать этой ситуации необходимо ввести параметр, определяющий требуемую точность, в данном случае количество знаков после запятой.

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

Один алгоритм является эквивалентным другому, если:

1. Множество допустимых исходных данных одного алгоритма является множеством допустимых исходных данных другого алгоритма, из возможности применения к каким либо исходным данным одного алгоритма следует возможность применения к этим же исходным данным другого алгоритма;

2. Применение к одним и те же исходным данным одного алгоритма дает то же самый результат, что и применение к этим же исходным данным другого алгоритма.

 

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

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

 









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.