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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

9
Пусть имеется шесть железнодорожных вагонов, пронумерованных
1, 2, 3, 4, 5 и 6. Установить, можно ли их переставить в порядке:
а) 325641;
б) 154623.
Если такие перестановки возможны, то покажите, как это сделать.
3. Некоторые последовательности из S и X, описывают бессмыс-
ленные операции, так как может не оказаться вагонов на указанных пу-
тях. Невозможно, например, реализовать последовательность
SXXSSXXS.
Будем называть последовательность из S и X, представляющую пе-
рестановку из n элементов, допустимой, если в ней содержится n симво-
лов S и n символов X, и если она задаёт операции, которые можно вы-
полнить.
Сформулируйте правило, которое позволит различать допустимые и
недопустимые последовательности.
Покажите, что никакие две различные допустимые последователь-
ности не приводят к одинаковой выходной перестановке.
4. Простая формула для a
n
– количества перестановок из n элемен-
тов, которые можно получить, используя стек так, как в упр. 2, имеет вид:
a
n
=
−
−
1
22
n
n
n
n
, где
n
n2
– общее число последовательностей, в ко-
торые S и X входят одинаковое число n раз;
−1
2
n
n
– число недопусти-
мых последовательностей, в которые S и X входят одинаковое число
n раз.
Вычислите значение a
n
и определите всевозможные, недопустимые
и допустимые последовательности из S и X, а также перестановки, кото-
рые будут получены в результате реализации допустимых последова-
тельностей для:
а) n = 2;
б) n = 3.
5. С использованием стека можно получить перестановку p
1
p
2
…
p
n
из 1, 2, …, n тогда и только тогда, когда нет таких индексов i, j и k, что
i < j < k и p
j
< p
k
< p
i
. Применив это условие, поясните, почему из
123456 перестановку 154623 получить нельзя, а перестановку 325641 –
можно.
6. Рассмотрите задачу, поставленную в упр. 2, заменив стек на
очередь. Какие перестановки из 1, 2, …, n можно получить, используя
очередь?

Страницы