Контрольная работа по "Информатике"

25.Методы перевода  чисел

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

А_(S)=a_nSⁿ+ a_n-1S^n-1+…+ a₁S¹+ a₀S⁰ + a_-1S^-1 +…+ a_-mS^m=b_kR^k+ b_k-1R^k-1+…+b₁R¹+ b₀R⁰+ b_-1R^-1+…+ b_-lR^l=A_(R) Поэтому в общем виде задача перевода чисел из системы счисления с основаниеи S в систему счисления с основанием R представляет собой либо задачу определения коэффициентов b_i по правилам S-арифметики, либо задачу вычисления А_(R) по правилам R-арифметики, исходя из того, что известны a_j. и S^j . Правило перевода целых чисел на основании S-арифметикиИсходное число А_(S), разделить на R по правилам S-арифметики, Полученное частное принять за исходное число и вновь разделить на R. Процесс деления очередного частного продолжать до тех пор, пока не будет получено частное меньше R . Изображение числа а_(S) в R-системе счисления получают записью остатков от деления в порядке, обратном порядку их получения. Правило перевода целых чисел на основании R-арифметики Самую старшую цифру a_n в изображении числа а_(S) умножить на S по правилам R-арифметики. Добавить следующую цифру a_n-1 и вновь умножить на S. Умножение и сложение выполнять до тех пор, пока не будет добавлена самая младшая цифра a₀ . Полученное число будет представлять собой A_(R) .Правило перевода дробных чисел на основании S-арифметики Исходное число A(S) умножить на R по правилам S-арифметики. Целая часть полученного числа представляет собой цифру b_-1 числа А(R) . Затем, отбросив целую часть, умножить дробную часть на R . При этом получается число, целая часть которого есть цифра b_-2 . Повторять процесс умножения l раз, пока не будут найдены все l цифр числа A(R). Правило перевода дробных чисел на основании R –арифметики. Самую младшую цифру в a_m в изображении числа A_(S) разделить на S по правилам R-арифметики. Добавить следующую цифру a_-(m-1) вновь разделить на S. Сложение и деление выполнять до тех пор, пока не будет добавлена самая старшая цифра a_-1. Последнее число, полученное делением, представляет собой число A_(R)Табличные методы переводаПервый табличный метод заключается в том, что имеются таблицы эквивалентов в каждой системе счисления для цифр этих систем и степеней основания (весов разрядов); задача перевода сводится к тому, что в выражение

А_(S)=a_nSⁿ+ a_n-1S^n-1+…+ a₁S¹+ a₀S⁰ + a_-1S^-1 +…+ a_-mS^m

для исходной системы счисления  надо поставить эквиваленты из новой системы для всех цифр и степеней основания и произвести соответствующие действия по правилам R-арифметики. Полученный результат этих действий будет изображать число в новой системе счисления. Второй табличный метод позволяет осуществлять перевод чисел из R-системы счисления в S-систему, т.е. обратный перевод, используя эквиваленты S-системы и R -арифметику. Исходное число A_(R) сравнить с эквивалентами чисел Sⁿ, 2Sⁿ; 3Sⁿ,..., (S-1)Sⁿ . Если A_(R), меньше всех этих эквивалентов, то а_n = 0, и перейти к сравнению с эквивалентами чисел S^п-1,2 S^n-1, 3S^n-1, .... (S -1)S^n-1. Если gSⁿ<A(R)<(g+1) Sⁿ (где g = 1, 2,... S-2), то an = g, образовать разность r= A(R)-gSⁿ и перейти к сравнение остатка r. с очередными эквивалентами. Аналогично определяются все остальные коэффициенты a_j. Использование промежуточной системы счисления. Этот метод применяют при переводе из десятичной системы в двоичную и наоборот. В качестве промежуточной системы счисления используют систему с основанием 2^х ( К =• 2, 3...). При переводе из десятичной системы вначале осуществляют перевод в промежуточную систему, а затем вместо 2 -х цифр подставляют двоичные эквиваленты. Для перевода из двоичной в десятичную систему вначале разбивают двоичный код на группы по К разрядов и каждую группу заменяют соответствующей 2^k -й цифрой, затем переходят от промежуточной к десятичной системе счисления любым из методов. В качестве промежуточной широко используются восьмеричная и шестнадцатеричная системы.

26.Форматы представления  чисел с фиксированной и плавающей  запятой

Форма представления чисел с  фиксированной точкой упрощает аппаратную реализацию ЭВМ, уменьшает время  выполнения машинных операций, однако при решении задач на машине необходимо постоянно следить за тем, чтобы все исходные данные, промежуточные и окончательные результаты находились в допустимом диапазоне представления. Если этого не соблюдать, то возможно переполнение разрядной сетки, и результат вычислений будет неверным. От этих недостатков в значительной степени свободны ЭВМ, использующие форму представления чисел с плавающей точкой, или нормальную форму. В нормальной форме число представляется в виде произведения X=mq^p где т мантисса числа; q основание системы счисления; р порядок. Для задания числа в нормальной форме требуется задать знаки мантиссы и порядка, их модули в q-ичном коде, а также основание системы счисления. Нормальная форма представления чисел неоднозначна, ибо взаимное изменение т и р приводит к плаванию точки (запятой). Отсюда произошло название формы представления чисел. В конкретной ЭВМ диапазон представления чисел с плавающей точкой зависит от основания системы и числа разрядов для представления порядка. При этом у одинаковых по длине форматов чисел с плавающей точкой с увеличением основания системы счисления существенно расширяется диапазон представляемых чисел. Точность вычислений при использовании формата с плавающей точкой определяется числом разрядов мантиссы r. Она увеличивается с увеличением числа разрядов.

27.Двоичная арифметика

Сложение двоичных чисел осуществляется тем же способом, что и в обычной  десятичной арифметике. Таблица сложения в двоичной системе счисления имеет вид: Табл1:0+0=0; 0+1=1; 1+0=1; 1+1=10; При сложении осуществляется перенос избытка из одного столбца в другой. Из табл. 1 видно, что при сложении двоичных значений 1+1 необходимо перенести 1 в предыдущий разряд, что обеспечит результат равный 10. Пример 1: 01000001+ 00101010=01101011; Пример2: 01000001+00101010=01101011

В результате арифметической операции появляется новое число: С = A Ñ B, где Ñ – знак арифметического действия (сложение, вычитание, умножение, деление). Операнд – число, участвующее в арифметической операции, выполняемой цифровым автоматом. Так как цифровой автомат оперирует только машинными изображениями чисел, то последние выступают в качестве операндов. Поэтому запишем:[C] = [A] Ñ [B], где [   ] – обозначение машинных изображений операндов. Двоичный полусумматор – устройство, выполняющее арифметические действия. Появление единицы переноса при сложении двух разрядов несколько изменяет правила сложения двоичных цифр. можно сформулировать правила поразрядных действий при сложении операндов A и B: a_i + b_i + П_i-1 = c_i + П_i, где a_i, b_i – i-й разряд 1-го и 2-го операндов соответственно; c_i – i-й разряд суммы; П_i-1 – перенос из (i–1)-го разряда; П_i – перенос в (i+1)-й разряд (переносы принимают значения 0 или 1). Заем равносилен вычитанию единицы из старшего разряда.Если A – уменьшаемое (1-й операнд), B – вычитаемое (2-й операнд), то для поразрядных действий a_i – b_i + z_i = c_i + z_i+1, где a_i, b_i, c_i – соответственно i-е разряды уменьшаемого, вычитаемого и разности; z_i – заем из младшего i-го разряда; z_i+1 – заем в старшем (i+1)-м разряде.

28.Коды: прямой, обратный, допол-ный

Для хранения чисел и выполнения различных операций над ними их представляют различными кодами: прямым, обратным и дополнительным. Код числа в форме с фиксированной точкой, состоящий из кода знака и q-ичного кода его модуля, называется прямым кодом. Разряд прямого кода числа, в котором располагается код знака, называется знаковым разрядом кода. Разряды прямого кода числа, в которых располагается q-ичный код модуля числа, называются цифровыми разрядами кода. При записи прямого кода знаковый разряд располагается левее старшего цифрового разряда и обычно отделяется от цифровых разрядов точкой. Правило представления Q-ичного кода числа в прямом коде имеет вид:

где х_i — значение цифры в i-м разряде исходного кода. При представлении чисел в прямом коде реализация арифметических операций в ЭВМ должна предусматривать различные действия с модулями чисел в зависимости от их знаков. Так, сложение в прямом коде чисел с одинаковыми знаками выполняется достаточно просто. Числа складываются и сумме присваивается код знака слагаемых. Более сложной является операция алгебраического сложения в прямом коде чисел с различными знаками. В этом случае приходится определять большее по модулю число, производить вычитание чисел и присваивать разности знак большего по модулю числа. Для упрощения выполнения операций алгебраического сложения в ЭВМ используются специальные коды, позволяющие свести эту операцию к операции арифметического сложения. В качестве специальных в ЭВМ применяются обратный и дополнительный коды. Они образуются из прямых кодов чисел, причем специальный код положительного числа равен его прямому коду.Для обозначения обратного кода числа Х_(q) используется запись вида [Х_(q)]_обр.Правило представления q-ичного кода числа в обратном коде имеет вид:

Для преобразования прямого кода двоичного  отрицательного числа в обратный код и наоборот необходимо знаковый разряд оставить без изменения, а в остальных разрядах нули заменить на единицы, а единицы на нули. Для обозначения дополнительного кода числа Х_(q) используется запись вида [X_(q)]_доп . Правило представления q-ичного кода числа в дополнительном коде имеет вид:

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

29.Сложение чисел в  форматах с фикс-ой и плав-ей  запятой

Реализация операций в арифметике с плавающей запятой требует  необходимости выравнивания порядков при сложении и вычитании и  нормализации результатов. Если диапазоны чисел, представимых в арифметике с фиксированной запятой и с плавающей запятой, соизмеримы, то числа с фиксированной запятой могут более точно представлять (кодировать) величины, так как свободны от часто необходимой для чисел с плавающей запятой операции округления. При машинной реализации такая операция обычно выполняется в устройстве-предшественнике (например, сумматор) с высокой точностью (большой разрядностью), а затем отсылается в устройство-приемник (например, регистр) с учётом заданной (например, декларированной в описаниях типов и структур данных) точности или с сохранением всех значащих разрядов. Таким образом, копирование непосредственного результата операции происходит либо с помощью операции округления, либо с помощью операции усечения. Эти две основные операции (кроме арифметических операций) вводятся следующим образом: усечение, отбрасывание цифр числа до определённого разряда, например, до ближайшего, меньшего целого числа и т.п.; округление, усечение с коррекцией числа по определённым правилам, например, до числа кратного заданному числу, до ближайшего целого и т.п. Двоичный сумматор прямого кода(ДСПК)-сумматор, в котором отсутствует цепь поразрядного переноса между старшим цифровым и знаковым разрядами, поэтому на ДСПК складываются числа, имеющие одинаковые знаки; сумма чисел имеет знак любого из слагаемых. При сложении чисел одинакового знака, представленных в формате с фиксированной запятой, может возникнуть переполнение разрядной сетки. Признаком переполнения разрядной сетки ДСПК является появление единицы переноса из старшего разряда цифровой части числа. Пример выполнения. сложить числа А= -0.1010111 и В= -0.0011001:Решение[A]_пр=1.1010111+[B]_пр=1.0011001=[C]_пр=1.111000; С=-0.1110000

30.Умнож. чисел в  форматах с фикс-ой и плав-ей запятой

Существует несколько методов  получения произведения двух чисел; все они дают результаты одинаковой точности, но требуют различных аппаратных затрат. Наиболее распространен метод, по которому произведение получается по следующей схеме: А=0.а₁а_{2 ……} а_n – множимое, а В=0.b₁b₂…b_n=(…(((b_n*2^-1+b_n-1)2^-1+b_n-2)2^-1+…+b₂)2^-1+b₁)2^-1 – множитель, произведение равно С=А*В=(…((b_n*0.а₁а_{2 ……} а_n)2^-1+b_n-1*0.а₁а_{2 ……} а_n) 2^-1 + …+b₁ *0.а₁а_{2 ……} а_n)2^-1, что означает, что умножение начинается с младших разрядов множителя и на каждом шаге сдвигается вправо сумма частных произведений. При умножении чисел, представленных в прямом коде, знак произведения определяется отдельно от цифровой части как SgC=SgA Å SgB, а цифровая часть формируется на двоичном сумматоре прямого кода. Произведение получается в прямом коде. При умножении чисел в прямом коде результат имеет 2n разрядов, где n – число разрядов операндов, и может содержаться соответственно старшая часть произведения – в сумматоре и младшая часть – в освобождающихся разрядах регистра множителя. Для реализации умножения необходимы регистры (Рг) для хранения множимого А и множителя В, сумматор (СМ) и схема анализа разрядов множителя В. содержимое регистра В и сумматора представляется в соответствующей таблице. При умножении чисел, представленных в формате с плавающей запятой, мантиссы сомножителей перемножаются как числа с фиксированной запятой на двоичном сумматоре прямого кода, порядки чисел складываются на двоичных сумматорах обратного или дополнительного кодов. Результат умножения мантисс может иметь нарушение нормализации слева на один разряд; его следует нормализовать путем сдвига мантиссы на один разряд влево и понижения порядка результата на единицу. Необходима проверка сумматора порядков на переполнение и исчезновение порядка.

31. Деление чисел, пред-ых  в форматах с фикс-ой и плав-ей  запятой

Деление двоичных чисел, представленных в формате с фиксированной  запятой, осуществляется двумя методами:с восстановлением остатков; без восстановления остатков, и представляет последовательные операции алгебраического сложения делимого и делителя, а затем остатков и сдвига. Деление выполняется на двоичных сумматорах дополнительного и обратного кодов. Результат получается в прямом коде. Знаковую и цифровую часть частного получают раздельно. Знак частного Sg C образуется по следующему правилу: SgC=SgA Å SgB Для определения цифр частного С_i используют следующие правила.

Правило 1. если делимое А и делитель В представлены в соответствии с таблицей

Где В- изменение знака операнда на противоположный, то необходимо сравнивать на каждом шаге знаки делимого А и остатков А_i и принимать С_i=1, если знаки совпали, и С_i=0 – при несовпадении знаков А и А_i.

Правило 2. если делимое А и делитель В представлены в соответствии с таблицей 5, то в очередной разряд частного С_i переписывается содержимое знакового разряда сумматора на каждом шаге.

Необходимым условием выполнения операции деления чисел с фиксированной запятой является ½А½<½B½, В¹0, в противном случае – переполнение разрядной сетки сумматора. Для нахождения результата с точностью n разрядов надо найти (n+1)-й разряд частного, а затем округлить результат. Признаки окончания операции деления: достижение заданной точности; получение очередного остатка, равного нулю. Деление чисел в формате с плавающей запятой, имеет следующие особенности: ½m_A½<½m_B½; деление производится путем деления мантисс как чисел с фиксированной запятой на двоичных сумматорах обратного и дополнительного кодов и вычитания порядков в тех же кодах, после чего оценивается переполнение разрядной сетки сумматора порядков; ½m_A½³½m_B½; деление производится путем формального деления мантисс и вычитания порядков, после чего осуществляется нормализация результата сдвигом мантиссы вправо на один разряд и увеличением порядка на единицу, затем оценивается переполнение разрядной сетки сумматора порядков.

32.Понятие и свойства  алгоритмов

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

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