Задача 1.
Предположим, что имеется некоторый кусок ленты, разделенный на кадры. Кадры занумерованы с двух сторон. Полоска ленты склеена в лист Мебиуса. Необходимо составить алгоритм упорядочения этой последовательности, предположив, что соседние кадры можно переставлять, (естественно, в упорядоченной последовательности будет один "скачок" от минимального элемента к максимальному). Следует учесть, что при перестановки кадров переставляются числа с обеих сторон кадров. Пример:
Есть 2 кадра
А1, В1 - одна сторона кадров,
А2, В2 - другая.
Пусть А1=1, А2=2, В1=7, В2=3. Тогда после перестановки содержащего А< В будет А1=7, А2=3, В1=1, В2=2).
Всегда ли такое упорядочение возможно?
|
Решение задачи 1.
Если мы будем переставлять кадр A с соседним с ним справа, пока A не пройдет всю ленту Мебиуса и не вернется на свое место, то окажется, что стороны кадра поменяются - то, что раньше было A1 станет B1, и наоборот.
Разрежем ленту. Из замечания выше следует, что мы можем полагать, что на одной стороне ленты в каждом кадре написано минимальное из чисел, находящихся на сторонах кадра. Упорядочиваем элементы этой стороны ленты по неубыванию, Если и на другой стороне элементы выстроились по неубыванию, и при этом последний элемент первой стороны не превышает первого элемента второй стороны, то поставленная задача решена, иначе упорядочение невозможно.
|
