Система непересекающихся множеств

Напишите программу, которая будет содержать реализацию структуры данных для совокупности непересекающихся подмножеств (disjoint sets) и обрабатывать запросы таких видов:

RESET n — создать новую серию подмножеств: множество из одного только элемента 0, из одного только элемента 1, и так до множества из одного только элемента n–1 включительно. Если структура уже содержала какую-то другую совокупность непересекающихся подмножеств, вся соответствующая информация утрачивается. На стандартный выход (экран) при этом следует вывести два слова через пробел «RESET DONE».

JOIN j k — объединить подмножества, которым принадлежат элемент j и элемент k. Если элементы и так принадлежали одному подмножеству, вывести на стандартный выход (экран) слово «ALREADY», после него через пробелы те же числа j и k в том же порядке. Если элементы до сих пор принадлежали разным подмножествам, то действие происходит только с данными в памяти, на экран ничего не выводится.

CHECK j k — проверить, одному ли подмножеству принадлежат элемент j и элемент k; вывести на стандартный выход (экран) слово «YES» (если одному) или слово «NO» (если разным).

Входные данные

Во входных данных содержится последовательность запросов RESET, JOIN и CHECK — каждый в отдельной строке, согласно вышеописанному формату.

СНМ (наивные реализации)

Гарантированно, что первая строка содержит запрос RESET, а общее количество запросов RESET не превышает 5. Общее количество всех запросов не превышает 200000. Значение n в каждом запросе RESET не превышает 100000. В каждом запросе JOIN и в каждом запросе CHECK оба числа будут в диапазоне от 0 до n–1, где n — параметр последнего выполненного запроса RESET.

Выходные данные

Для запросов RESET, CHECK и тех запросов JOIN, где элементы и так принадлежат одному подмножеству, выводить на стандартный выход (экран) соответствующий результат (в отдельной строке).

Примечание

Ответы «NO» даются на запросы «CHECK 2 11» и «CHECK 9 1», ответ «ALREADY 4 1» — на второй из запросов «JOIN 4 1» (10-я строка), «YES» — на «CHECK 5 10».

black zorro
Member

Откуда:
Сообщений: 453

Суть в сабже и вопрос:
В литературе я нашел что это плохая рекурсивная функция, примеры кода рекурсивного и нерекурсивного в виде стека.

Интересно какой физический смысл и направления применения есть у этой функции.

Да кстати по поводу нерекурсивного решения.
Я подумал что тупая замена стеком не есть хорошо и думаю
создать массив размером N * M где будут храниться предвычисленные
значения функции. Прав ли я что данная функция повторяется в своих вычислениях наподобие того как повторются ветки вычислений для Фибоначчи чисел ?

Система непересекающихся множеств

S.G.
Member

Откуда: cartoon network
Сообщений: 29645

Если не ошибаюсь, при рекурсивном вычислении числа
Фибоначчи F(n), вычисляется «всего лишь» 2^n значений,
т.е кол-во вычислений нарастает экспоненциально,
а при A(m,n) — нарастание гораздо круче.
Почему ее придумали — вероятно чтобы показать,
что любой, самый быстрый компьютер, можно заставить
работать медленно

Реализация рекурсии через стек — стандартный подход,
показывающий, что любая рекурсия может быть преобразована
в итерационный процесс. Ест-венно, вычисления при этом
не ускоряются. Если при вычислении ф-и Аккермана получаются
повторяющиеся значения (а это наверняка так),
то их запоминание и повторное использование дадут существ. выигрыш.

Но… http://www.softcraft.ru/paradigm/dp/dp05-02.shtml

В конце написано:
2. Попытайтесь создать итерационный алгоритм вычисления этой функции и запишите его на любимом языке программирования. Ваша программа должна использовать только конечное число переменных и не должна реализовывать рекурсию, например, с использованием стека.
В случае удачного решения обязательно опубликуйте результат!

Что- то говорит мне что этого еще никто не сделал…

Если исходное уравнение состояния объекта отличается от управляемой канонической формы,то в случае управляемости объекта для определения вектора обратной связи по состоянию используют следующую трехэтапную процедуру.

1. Преобразуют исходную модель объекта в управляемую каноническую форму, используя матрицу преобразования

. (*)

2. Находят вектор обратной связи по преобразованному состоянию , применяя (18).

3. Преобразуют вектор в вектор обратной связи по исходному состоянию . используя

. (19)

Формула Аккермана объединяет эти шаги в одну формулу

, (20)

где матричный многочлен составлен с помощью коэффициентов характеристического уравнения желаемой системы.

Пример.

Пусть объект описывается уравнением состояния

,

а желаемый характеристический многочлен имеет вид .

Так как

,

то передаточная функция объекта имеет вид , т.е. объект представляет собой двойной интегратор. Отсюда, . Следовательно, n=2, иматрица управляемости

.

В соответствии с ( ** ) обратная матрица

.

Легко показать, что

, ,

так что согласно (*)

.

Используя (18) , ,…,, находим

, .

Согласно (19)

,

что совпадает с выражением, полученным ранее другим путем.

 

Команда MATLAB: acker (A,B, Рр).

Пример. Пусть в условиях предыдущего примера коэффициенты , , так что полюсы желаемой системы , k = 1. Тогда применяя команду

l = acker(A,B, [-4+j*4 -4-j*4]),

можно найти .

Сделаем несколько замечаний, касающихся рассмотренного метода размещения полюсов.

1. Матрица T может быть найдена только в том случае, когда существует обратная матрица управляемости . Следовательно, любое расположение полюсов проектируемой системы с помощью обратной связи по состоянию можно обеспечить, если объект управления полностью управляем, т.е. если матрица управляемости объекта является невырожденной, так что .

2. Спроектированная в соответствии с формулами (7), (18) и (19) система не удовлетворяет условию астатизма, т.е. ее передаточная функция

не равна единице при p=0, другими словами, спроектированная система является статической.

Здесь K(p) числитель ПФ объекта.

Если выбрать закон управления в виде

,

то передаточная функция проектируемой системы

.

Так как , то, как видим, введение наряду с обратной связью по состоянию прямой связи по задающему воздействию

Рис.3

(рис. 3) обеспечивает астатизм проектируемой системы.


Дата добавления: 2014-01-04; Просмотров: 1522; Нарушение авторских прав?;




Читайте также:



Для просмотра файлов Вам могут потребоваться

Аннотация: Речь пойдет о некоторых совершенно элементарных по формулировке комбинаторных задачах, которые приводят к вычислимым функциям, имеющим невообразимо большой рост.

О роли такого рода функций в математической логике будет упомянуто, но основное содержание — знакомство слушателей с примерами и сопутствующими понятиями.

Примерный план:

  • Примитивно рекурсивные функции и функция Аккермана.
  • «Долгие игры»: Геракл-Гидра, последовательность Гудстейна.
  • Теорема Крускала о вложениях деревьев и функция Фридмана.
  • Busy beaver: функция, превосходящая по росту любую вычислимую.

    (В пункте 4 полезно предварительное знакомство слушателей с машинами Тьюринга.)

Материалы:ldb_problems.pdf (71.9 Kb), ldb_presentation.pdf (1.6 Mb)
Цикл лекций

  • Быстрорастущие функции («быстрее, выше, сильнее»). Вводная лекция
    Л. Д. Беклемишев, 21 июля 2012 г. 11:15
  • Быстрорастущие функции («быстрее, выше, сильнее»). Лекция 1
    Л. Д. Беклемишев, 22 июля 2012 г. 17:00
  • Быстрорастущие функции («быстрее, выше, сильнее»). Лекция 2
    Л. Д. Беклемишев, 24 июля 2012 г. 11:15
  • Быстрорастущие функции («быстрее, выше, сильнее»). Лекция 3
    Л. Д. Беклемишев, 25 июля 2012 г. 15:30
  • Быстрорастущие функции («быстрее, выше, сильнее»). Лекция 4
    Л. Д. Беклемишев, 26 июля 2012 г.

    15:30

 

Как известно, функция Аккермана играет важную роль в теоретической информатике. Однако, с другой стороны, её быстрый рост вызывает трудности при вычислении.

Функция Аккермана может быть определена рекурсивно для неотрицательных целых чисел m и n следующим образом:

По заданным m и n вычислите значение A(m, n).

Входные данные

В каждой строке находятся два неотрицательных целых числа m и n, где 0m3. Для всех m < 3 значение n не превышает , если же m = 3, то значение n не превышает 24.

Выходные данные

Для каждой заданной пары чисел выведите в отдельной строке значение функции Аккермана A(m, n).

Добавить комментарий

Закрыть меню