59. Нормализованное представление чисел, переполнение, модифицирванные коды
Нормализованное представление чисел – это когда мантисса от 1 до 10.
Арифметическое переполнение — специфичная для компьютерной арифметики ситуация, когда при арифметическом действии результат становится больше максимально возможного значения для переменной, использующейся для хранения результата.
Пример: сложение двух переменных размером 8 бит с записью результата в переменную того же размера:
{\displaystyle
210_{10}+61_{10}=11010010_{2}+00111101_{2}=?}
{\displaystyle {\begin{array}{c}{\begin{array}{cc}+&{\begin{array}{c}11010010_{2}\\00111101_{2}\end{array}}\\\end{array}}\\\hline {\begin{array}{cc}&{\color {Red}1}00001111_{2}\end{array}}\end{array}}}При этом в результат записывается не ожидаемое {\displaystyle 271_{10}={\color {Red}1}00001111_{2}}100001111, а {\displaystyle 15_{10}=00001111_{2}}00001111. Если не проверять, было ли переполнение, то может возникнуть логическая ошибка в программе, о чём в некоторых случаях во время исполнения не узнает ни платформа, ни операционная система.
Для выявления ошибок при выполнении арифметических операций используются также модифицированные коды: модифицированный прямой; модифицированный обратный; модифицированный дополнительный, для которых под код знака числа отводится два разряда, т.е. “+” = 00; ”-” = 11. Если в результате выполнения операции в знаковом разряде появляется комбинация 10 или 01, то для машины это признак ошибки, если 00 или 11, то результат верный.
60. Алгоритмы сложения и вычитания в дополнительных и обратных кодах
Сложение и вычитание чисел со знаком в дополнительном коде
Если
оба числа имеют n–разрядное представление,
то алгебраическая сумма будет получена
по правилам двоичного сложения (включая
знаковый разряд), если отбросить возможный
перенос из старшего разряда. Если числа
принадлежат диапазону представимых
данных и имеют разные знаки, то сумма
всегда будет лежать в этом диапазоне.
Переполнение может иметь место, если
оба cлагаемых имеют одинаковые
знаки.
Пример 1: 6 – 4 = ?
6
– положительное число с кодом 0110
–4
– отрицательное число с дополнительным
кодом 1100
(перенос
игнорируется): 6 – 4 = 2.
Пример 2: –5
+ 2 = ?
2 – положительное число с кодом
0010
–5 – отрицательное число с
дополнительным кодом 1011
Число с кодом 1101 является отрицательным, модуль этого числа имеет код 00112 = 310.
А в обратном лень писать, и вообще этот код не используется, нужно заговорить Козлова.
61. Алгоритмы умножения в дополнительных и обратных кодах
Реальные алгоритмы выполнения операций умножения и деления в современных ЭВМ достаточно громоздки и идут лесом.
62. Структуры рекурсивных алгоритмов
Алло, это же пункт 16.
63. Применение рекурсивных алгоритмов
Рекурсивный алгоритм всегда разбивает задачу на части, которые по своей структуре являются такими же как исходная задача, но более простыми. Для решения подзадач функция вызывается рекурсивно, а их результаты каким-либо образом объединяются. Разделение задачи происходит лишь тогда, когда ее не удается решить сразу (она является слишком сложной).
Например, задачу обработки массива нередко можно свести к обработке его частей. Деление на части выполняется до тех пор, пока они не станут элементарными, т.е. достаточно простыми чтобы получить результат без дальнейшего упрощения. (то же самое в пункте 16 тоже)
Пример 1. Двоичный поиск в массиве
Двоичный поиск выполняется над отсортированным массивом. На каждом шаге искомый элемент сравнивается со значением, находящимся посередине массива. В зависимости от результатов сравнения либо левая, либо правая части могут быть “отброшены”.
Пример 2. Быстрая сортировка (quick sort)
Алгоритм быстрой сортировки на каждом шаге выбирает один из элементов (опорный) и относительно него разделяет массив на две части, которые обрабатываются рекурсивно. В одну часть помещаются элементы меньше опорного, а в другую – остальные.
