4. Алгоритмы и структуры данных. Стандартные примитивные типы

Стандартные примитивные типы - это те, которые доступны в большинстве компьютеров "на ровне железа".
  • INTEGER
  • REAL
  • BOOLEAN
  • CHAR
  • SET

INTEGER

Если компьютер использует n битов для представления целых чисел в дополнительном коде, то допустимые значения x должны удовлетворять условию -2n-1 <= x < 2n-1.

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

Если мы определим частное q = m DIV n и остаток r = m MOD n, то должны выполняться следующие соотношения (предполагается, что n > 0):
q*n + r = m и 0 <= r < n
Примеры:
  • 31 DIV 10 = 3
  • 31 MOD 10 = 1
  • -31 DIV 10 = -4
  • -31 MOD 10 = 9
Деление на 10n может быть осуществлено сдвигом десятичных знаков на n позиций вправо с отбрасыванием избыточных цифр справа. Аналогичный метод применим и к двоичной нотации. Если используется дополнительный код (как это имеет место практически во всех современных компьютерах) то сдвиги обеспечивают целочисленное деление (как DIV выше). Поэтому в компиляторе нетрудно реализовать операцию вида m DIV 2n (или m MOD 2n) с помощью быстрой операции сдвига (или с помощью маски).

REAL

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

Стандартная функция преобразования ENTIER(x) дает целую часть величины x. Тогда округление величины x выполняется с помощью ENTIER(x + 0.5).

Алгоритм обеспечивает быстрое вычисление величины y = xn, где n - неотрицательное целое:
y := 1.0; i := n;
WHILE i > 0 DO (* x0n = xi * y *)
 IF ODD(i) THEN y := y*x END;
 x := x*x; i := i DIV 2
END

BOOLEAN

Булевские операции - это логические конъюнкция, дизъюнкция и отрицание. Например, для булевских переменных p и q и целых переменных x = 5, y = 8, z = 10 два присваивания
p := x = y
q := (x <= y) & (y < z)
дают p = FALSE и q = TRUE

В большинстве языков программирования булевские операции & (AND) и OR обладают дополнительным свойством, отличающим их от других бинарных операций. Например, сумма x+y не определена, если не определен любой из операндов x или y, однако конъюнкция p&q определена, даже если не определено значение q, при условии что p равно FALSE. Поэтому точное определение операций & и OR дается следующими равенствами:
p & q = если p, то q, иначе FALSE
p OR q = если p, то TRUE, иначе q

CHAR

Тип CHAR представляет литеры, которые можно напечатать.

Чаще всего используется множество литер, определенное Международной организацией по стандартизации (ISO), и, в частности, его американский вариант ASCII (American Standard Code for Information Interchange).

Функция ORD(ch) дает порядковый номер литеры ch в используемом множестве литер.
Функция CHR(i) дает литеру с порядковым номером i.
Функция CAP(ch) - ее значение заглавная буква, соответствующая ch, если ch - буква.

SET

VAR r, s, t: SET

r := {5}; s := {x, y .. z}; t := {}

Следующие элементарные операции определены для операндов типа SET:
  • * пересечение множеств
  • + объединение множеств
  • - разность множеств
  • / симметрическая разность множеств
  • IN принадлежность множеству
Приоритеты этих операций определяются так, что приоритет пересечения выше, чем у объединения и разности, а приоритеты последних выше, чем у операции принадлежности.

r * s + t = (r*s) + t
r - s * t = r - (s*t)
r - s + t = (r-s) + t
r + s / t = r + (s/t)
x IN s + t = x IN (s+t)

Теги: