Методы программирования. Громов Ю.Ю - 131 стр.

UptoLike

131
определяет разбиение множества M на два класса эквивалентности:
K
1
= {1, 2, 5, 6, 8, 9} и K
2
= {3, 4, 7}.
2. а) Независимые величины E
0
, E
11
, E
12
,
13
E
, E
14
и выражения для
зависимых величин:
E
1
= E
0
, E
5
= E
0
E
11
E
12
+ E
14
,
E
9
= E
12
,
E
2
= E
0
+
13
E
+ E
14
,
E
6
= E
0
,
E
10
= E
11
,
E
3
= E
0
+ E
14
, E
7
= E
0
,
13
E
=
13
E
;
E
4
= E
0
E
11
E
12
+ E
14
, E
8
= E
11
+ E
12
,
б) если E
0
= 1, E
11
= 2, E
12
= 3,
13
E
= 2 и E
14
= 6, то E
1
= 1, E
2
= 9, E
3
= 7,
E
4
= 2, E
5
= 2, E
6
= 1, E
7
= 1, E
8
= 5, E
9
= 3, E
10
= 2 и
13
E
= 2;
в) A = 9, B = 9, C = 7, D = 2, F = 5, K = 3, L = 2, M = 7 и N = 1.
§ 9
1. Минимальное время 32 u, максимальное время 48 u, среднее вре-
мя 37
15
2
u.
§ 10
1. N = 16, а записи в памяти размещены так, что образуют последо-
вательность ключей:
K
5 0 5 0 9 1 8 2 6 4 1 5 6 6 7 7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
По окончании работы алгоритма C вспомогательная таблица COUNT
будет иметь следующий вид:
COUNT
6 0 7 1 15
2 14
4 9 5 3 8 10
11
12
13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Сортировка является устойчивой, поскольку если K
i
= K
j
и j > i, то
COUNT[j] > COUNT[i].
2. N = 16, а записи в памяти размещены так, что образуют последо-
вательность:
R
5 T
0 C
5 U
0 O
9 .
1 N
8 S
2 R
6 A
4 A
1 G
5 L
6 T
6 I
7 O
7 N
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
По окончании работы алгоритма D в области вывода записи будут
размещены следующим образом:
S
0 C
0 O
1 N
1 G
2 R
4 A
5 T
5 U
5 L
6 A
6 T
6 I
7 O
7 N
8 S
9 .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16