Сортировка И Последовательности

Тема в разделе "Другие", создана пользователем nick-martel, 16 дек 2011.

  1. nick-martel

    nick-martel Гость

    Доброго времени суток! Нужно решить задачу на языке программирования R. Задача такая:

    Предположим, что имеется некоторый кусок ленты, разделенный на кадры. Кадры занумерованы с двух сторон. Полоска ленты склеена в лист Мебиуса. Необходимо составить алгоритм упорядочения этой последовательности, предположив, что соседние кадры можно переставлять, (естественно, в упорядоченной последовательности будет один "скачок" от минимального элемента к максимальному). Следует учесть, что при перестановки кадров переставляются числа с обеих сторон кадров. Пример:

    Есть 2 кадра

    А1, В1 - одна сторона кадров,

    А2, В2 - другая.

    Пусть А1=1, А2=2, В1=7, В2=3. Тогда после перестановки содержащего А« В будет А1=7, А2=3, В1=1, В2=2).

    Всегда ли такое упорядочение возможно?
    --------------
    Решение её в текстовом виде такое:
    Если мы будем переставлять кадр A с соседним с ним справа, пока A не пройдет всю ленту Мебиуса и не вернется на свое место, то окажется, что стороны кадра поменяются - то, что раньше было A1 станет B1, и наоборот.

    Разрежем ленту. Из замечания выше следует, что мы можем полагать, что на одной стороне ленты в каждом кадре написано минимальное из чисел, находящихся на сторонах кадра. Упорядочиваем элементы этой стороны ленты по неубыванию, Если и на другой стороне элементы выстроились по неубыванию, и при этом последний элемент первой стороны не превышает первого элемента второй стороны, то поставленная задача решена, иначе упорядочение невозможно.

    ----

    Очень хотелось бы получить хотя бы помощь в написании кода для R.
     
Загрузка...
Похожие Темы - Сортировка Последовательности
  1. vera2014
    Ответов:
    0
    Просмотров:
    1.071
  2. Liori
    Ответов:
    2
    Просмотров:
    1.005
  3. FCDK
    Ответов:
    0
    Просмотров:
    1.264
  4. ленарано
    Ответов:
    1
    Просмотров:
    1.103
  5. Creder
    Ответов:
    0
    Просмотров:
    1.346

Поделиться этой страницей