supremum множеств на Prolog

      Комментарии к записи supremum множеств на Prolog отключены

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 1 месяц назад.

  • Автор
    Сообщения
  • #2500

    questioner
    Участник

    Необходимо вычислить супремумом подмножества X множества M называется элемент E множества M такой, что он меньше или равен всем другим элементам множества M, значения которых больше всех элементов множества X.

    Я пытался решить так – найти максимальный элемент множества X (т.к. супремум должен быть больше этого значения), затем выбрать из множества M все элементы, большие этого значения и среди них выбрать минимальный. Однако, мне кажется такое решение не совсем правильным, кроме того, если изначально множество X пустое – то супремумом должен быть минимальный элемент множества M, однако мой алгоритм не сработает, т.к. безуспешно будет пытаться выполнить поиск максимума в пустом списке.

    Как правильно решить задачу? Желательно на Visual Prolog 5.2.

    Вложения:
  • #2502

    Вам нужно сначала выбрать элементы множества M, большие всех элементов множества X, а затем выбрать среди них минимальный:

    supremum(ListA, ListB, Supremum):-
      greater_elements(ListB, ListA, ListABiggestMaxB),
      min_list(ListABiggestMaxB, Supremum).

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

    Функция greater_elements выбирает из первого списка элементы, большие по значению всех элементов второго списка:

    greater_elements([], _List, []):-!.
    greater_elements([HeadFrom|TailFrom], List, [HeadFrom|Tail]):-
      check_greater(HeadFrom, List), !,
      greater_elements(TailFrom, List, Tail).
    greater_elements([_HeadFrom|TailFrom], List, Tail):-
      greater_elements(TailFrom, List, Tail).

    Она завершает свою работу если первый список пуст – очевидно, в пустом списке нет элементов больших всех элементов второго списка. Во всех остальных случаях первый список разделяется на голову (HeadFrom) и хвост (TailFrom). Хвост обрабатывается рекурсивно и к результату такой обработки может быть либо добавлена голова, либо нет. Добавление головы должно происходить лишь в том случае, если ее значение превосходит все элементы второго списка – такую проверку осуществляет функция check_greater:

    check_greater(_Greater, []):-!.
    check_greater(Greater, [Head|Tail]):-
      Greater >= Head, check_greater(Greater, Tail).

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

    Вложения:

Для ответа в этой теме необходимо авторизоваться.