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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

124
ОТВЕТЫ К УПРАЖНЕНИЯМ
§ 1
1. Да, если всегда включать все элементы в один из двух концов.
2. а) Да, если выполнить последовательность операций
SSSXXSSXSXXX; б) Нет (может получиться только 154632), поскольку 2
может предшествовать 3 тогда и только тогда, когда 2 удаляется из стека
до занесения в него 3.
3. Допустимой последовательностью из S и X является та, в кото-
рой при просмотре её слева направо текущее число вхождений X никогда
не превышает текущего числа вхождений S.
Две различные допустимые последовательности должны дать раз-
ный результат по следующей причине. Если две последовательности сов-
падают до некоторого момента, а затем в одной из них встречается S и в
другой – X, то вторая последовательность выведет символ, который нельзя
будет вывести раньше символа, посланного в стек операцией S в первой
последовательности. Например, SSSSXXXX → 4321, SSSXSXXX → 3421.
4. а) a
2
=
⋅
2
22
−
−
⋅
12
22
=
2
4
−
1
4
=
!2!2
!4
−
!3!1
!4
=
2
1
2
1
4321
⋅⋅⋅
⋅⋅⋅
−
–
3
2
1
1
4321
⋅⋅⋅
⋅
⋅
⋅
= 3 ⋅ 2 − 4 = 6 − 4 = 2.
Всевозможные последовательности: SSXX, XXSS, SXSX, XSXS,
SXXS, XSSX.
Недопустимые последовательности: XXSS, XSXS, SXXS, XSSX.
Допустимые последовательности: SSXX, SXSX.
В результате реализации этих последовательностей будут получены
перестановки: 21, 12;
б) a
3
=
⋅
3
32
−
−
⋅
13
32
=
3
6
−
2
6
=
!3!3
!6
−
!4!2
!6
=
−
⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅
321321
654321
−
4
3
2
1
2
1
654321
⋅⋅⋅⋅⋅
⋅
⋅
⋅
⋅
⋅
= 20 − 15 = 5.
Допустимые последовательности SSSXXX, SSXSXX, SSXXSX,
SXSSXX, SXSXSX.
В результате реализации этих последовательностей будут получены
перестановки: 321, 231, 213, 132, 123.
5. Перестановку 154623 получить нельзя, так как существуют ин-
дексы i = 2, j = 5 и k = 6, при которых p
j
= 2 < p
k
= 3 < p
i
= 5. Перестановку
325641 получить можно, поскольку не существует таких индексов i, j и k,
при которых i < j < k и p
j
< p
k
< p
i
.

Страницы