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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

125
6. Только тривиальную перестановку 1, 2, …, n.
7. Если в деке с ограниченным входом первым на выходе появляет-
ся величина n, то это означает, что в дек были введены 1, 2, …, n в дан-
ном порядке. На выходе, пользуясь той свободой вывода, которой обла-
дает дек, получим некоторую перестановку вида n, … . Например, при
n = 4 получаем перестановки 4123, 4132, 4321, 4312. Если в деке с огра-
ниченным выходом первым на выходе появляется величина n, то это оз-
начает, что в дек была введена некоторая перестановка p
1
p
2
… p
n
, кото-
рую можно получить из 1, 2, …, n, пользуясь свободой входа, причём в
зависимости от ограничений, наложенных на выход, либо p
1
= n, либо
p
n
= n. Например, при n = 4 получаем перестановки 4321, 4312, 4213,
4123. Поэтому получаем: а) 4132; б) 4213; в) 4231.
8. Если, например, n = 4, то таких перестановок не существует. Ес-
ли же n = 5, то их четыре: 51324, 51342, 52314, 52341.
§ 2
1. Состояние памяти после переупаковки:
1 1 2 3 3 3 3 4 4
0 1 2 3 4 5 6 7 8 9 10
11
12
13
14
15
16
17
18
19
Базовые адреса стеков: BASE [1] = –1, BASE [2] = 1, BASE [3] = 5,
BASE [4] = 16 и адреса верхних элементов стеков: TOP [1] = 1, TOP [2] = 2,
TOP [3] = 10, TOP [4] = 18 получены в результате выполнения алгоритма G.
Исходными данными для этого алгоритма послужили: OLDTOP [1] = 1,
OLDTOP [2] = 2, OLDTOP [3] = 8, OLDTOP [4] = 11; номер переполнив-
шегося стека i = 3, BASE [1] = –1, BASE [2] = 2, BASE [3] = 5, BASE [4] = 9,
BASE [5] = 19, TOP [1] = 1, TOP [2] = 3, TOP [3] = 10, TOP [4] = 11,
NEWBASE [5] = 19, L
∞
= 19, L
0
= –1.
Приведём последовательность выполнения шагов алгоритма: G1,
G2, G3, G4, G5, G6, R1, R2, R3, R4, R5, Конец алгоритма R, Конец алго-
ритма G.
§ 3
1. Узлы будут выведены в порядке: 1, 9, 3, 2, 7, 4, 5, 8 и 6. Приведём
последовательность выполнения шагов алгоритма: T1, T2, T3, T2, T3, T2,
T3, T2, T3, T2, T3, T2, T3, T2, T3, T2, T3, T2, T3, T2, T3, T4, T5, T6, T6, T7,
T5, T6, T6, T6, T7, T5, T6, T6, T7, T5, T6, T6, T7, T5, T6, T6, T6, T7, T5, T6,
T6, T7, T5, T6, T6, T7, T5, T6, T6, T7, T5, T6, T7, T5, T8.
2. Прибавление многочлена xy + xz – x к многочлену – xz + 2x – 2y
влечёт последовательное выполнение шагов A1, A2, A5, A2, A3, A4, A2,
A3, A2, A2, A3 алгоритма и даёт итоговый многочлен xy + x – 2y.

Страницы