15 Билет
Формат с фиксированной точкой
Модель действительных чисел с фиксированной точкой аналогична представлению целых чисел со знаком:
под хранение целой и дробной части отводится известное число битов, т. е. привязка номеров разрядов числа к разрядам сетки фиксирована и позиция разделяющей двоичной точки известна. Разряды отсутствующих цифр заполняются незначащими нулями слева в целой части и справа в дробной. Отрицательные числа могут храниться в дополнительном коде.
Погрешность представления в данной модели равномерна: ε = b–kд/2.Арифметические операции над числами с фиксированной точкой можно выполнять поразрядно, рассматривая их без точки, как знаковые целые. После умножения точка ставится перед 2kд-й цифрой результата справа, младшие kд разрядов отбрасываются, причем по старшему из них выполняется округление младшей цифры результата.
Диапазон представления чисел в формате с фиксированной точкой. k – количество разрядов под целую часть; µ – количество разрядов под дробную часть;N — число, которое можно представить в такой разрядной сетке:
2–µ ≤ |N| ≤ 2k –2–µ
16 Билет
Формат с плавающей точкой
Модель действительных чисел с плавающей точкой служит для представления чисел с максимальной относительной точностью, измеряемой количеством хранимых значащих цифр действительного числа.
Для этого используется запись числа в нормализованной форме:
R = ±m*bp, где 1 = b0 £ т < b1, p – целое.
m — число, полученное перенесением точки в позицию после первой значащей цифры числа R, называется мантиссой.
p — количество разрядов, на которое была перенесена точка, называется порядком.
p > 0, если точка была перенесена влево,
и p < 0, если точка была перенесена вправо.
Примеры:
123.456 (10) = 1.23456 * 102 (1.23456 — мантисса, 2 — порядок)
0.0001011(2) = 1.011*2–4 (1.011 — мантисса, –4 — порядок)
18 Билет
Перестановки Перестановкой порядка N называется расположение N различных объектов в ряд в некотором порядке.
Например, для трех объектов — а, b и с — существует шесть
перестановок:
аbс, acb, bac, bса. cab, cba.
Для множества из N элементов можно построить N! различных перестановок: первую позицию можно занять N способами, вторую — (N – 1) способом, так как один элемент уже занят, и т. д. На последнее место можно поставить только один оставшийся элемент.
Следовательно, общее количество вариантов расстановки равно
N × (N −1) × (N − 2) × ... × 1 = N!
Инверсии Пусть даны базовое множество из N элементов 1,2, 3,..., N и его перестановка
Пара называется инверсией (инверсионной парой) перестановки ,
если при i < j.
Например, перестановка 4, 1, 3, 2 имеет четыре инверсии:
(4,1), (3,2), (4,3) и (4,2).
Единственной перестановкой, не содержащей инверсий, является упорядоченная перестановка 1, 2, 3, ... , N.
Таким образом, каждая инверсия — это пара элементов
перестановки, нарушающих ее упорядоченность.
Таблицей инверсий перестановки a1,a2, ...,aN называется последовательность чисел b1, b2 …, bN , где bj есть число элементов перестановки, больших j и расположенных левее j
(т. е. количество инверсий вида (x, j), при x > j).
Например,
для перестановки 5 9 1 8 2 6 4 7 3
таблица инверсий: 2 3 6 4 0 2 2 1 0.