Я начала повторять структуры данных и наткнулась на серию любопытных задач. Суть их такова: имеется некий набор данных на входе (для простоты будем считать, что очередь - потому как порядок критичен), стек и набор данных на выходе (тоже очередь). Обозначим процедуру push как S, pop как X. Для примера предположим, что в первой очереди 4 элемента: 1, 2, 3, 4. И так, задачи...
1. Порядок действий со стеком не является константой, но подчиняется определённым законам. Так, например, SXXSSSXX невозможен, потому как невозможно вытащить из стека то, что в него ещё не положили. А порядок SXSXSXS не годится, потому что стек не освобождается до конца. Соответственно, можно сформулировать определённые правила правильного порядка действий со стекам. У меня получилось вот такое определение...
Мой вариант
Я не совсем уверена, что моё решение полное и всеобъемлющее. Э?
2. Различными последовательнастями действий можно добиться различных результатов. Так, например:
SSSSXXXX -> 4321
SSXSXXSX -> 2314
Но не каждую последовательность можно получить пользуясь лишь одним стеком. Так, например, последовательность 3412 получить не удаётся. Какова общая формула количества возможных перестановок с помощью одного стека для N элементов? Напоминаю, что каждый элемент обязан попасть в стек один раз ровно.
Вот эта задача мне не даётся никак. С какой стороны я к ней ни подбиралась, у меня упорно получается N!, а этого не может быть, потому как факториал - это формула всех возможных перестановок в принципе, а мы уже знаем, что не каждую возможно выполнить через стек. Или я ошибаюсь?
А ещё было бы интересно составить общий алгоритм по выходной последовательности определяющий возможна ли данная перестановка и если да, то выдающий последовательность действий к ней приводящую. У меня пока есть только догадки как определить саму возможность подобной перестановки...