Перемешать два списка на Prolog

      Комментарии к записи Перемешать два списка на Prolog отключены

Помечено: , , ,

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

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

    Нужно перемещать элементы двух списков на Visual Prolog, т.е.:

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

    domains
    element = integer
    list = element*
    predicates
    nondeterm mix(list, list, list)
    clauses
    mix([], [], []):-!.
    mix([], _B, []):-!.
    mix(_A, [], []):-!.
    mix([AHead|ATail], [BHead|BTail], [AHead,BHead|Tail]):-
    mix(ATail, BTail, Tail).
    goal
    mix([1,2,3], [4,5,6], X).

    В первом правиле предиката mix записано, что если оба списка кончились одновременно — возвращается пустой список. Во втором и третьем правилах возвращается такой же результат если один список кончился раньше второго. Наконец, последнее правило выбирает из обоих списков первые элементы, а хвосты обрабатывает рекурсивно. К полученному результату дописывает первые элементы списков так, чтобы элемент первого списка был первым (нечетным), а второго — вторым.

    Трассировка стека приведена ниже:

    % mix([1,2], [4,5,6,7,8,9,0], X).
    % -> mix([1,2], [4,5,6,7,8,9,0], [1,1,1], [4,4,4], X).
    % -> (первое правило) A = [1,2], B = [4,5,6,7,8,9,0], AFirsts = [1,1,1], BFirsts = [4,4,4]
    % -> (второе правило) AHead = 1, ATail = [2], BHead = 4, BTail = [5,6,7,8,9,0], AFirsts = [1,1,1], BFirsts = [4,4,4]
    % -> -> mix(ATail, BTail, AFirsts, BFirsts, Result).
    % -> -> (первое правило) A = [2], B = [5,6,7,8,9,0], AFirsts = [1,1,1], BFirsts = [4,4,4]
    % -> -> (второе правило) AHead = 2, BHead = 5, ATail = [], BTail = [6,7,8,9,0], AFirsts = [1,1,1], BFirsts = [4,4,4]
    % -> -> -> mix(ATail, BTail, AFirsts, BFirsts, Result).
    % -> -> -> (первое правило) A = [], B = [6,7,8,9,0], AFirsts = [1,1,1], BFirsts = [4,4,4]
    % -> -> -> (второе правило) - безуспешно разбивает А на голову и хвост
    % -> -> -> (третеье правило) А = [], BHead = 6, BTail = [7,8,9,0], AFirst = 1, AFirstsTail = [1,1], BFirsts = [4,4,4]
    % -> -> -> -> mix([], BTail, AFirstsTail, BFirsts, Result).
    % -> -> -> -> (первое правило) A = [], B = [7,8,9,0], AFirsts = [1,1], BFirsts = [4,4,4]
    % -> -> -> -> (второе правило) - безуспешно разбивает А на голову и хвост
    % -> -> -> -> (третеье правило) А = [], BHead = 7, BTail = [8,9,0], AFirst = 1, AFirstsTail = [1], BFirsts = [4,4,4]
    % -> -> -> -> -> mix([], BTail, AFirstsTail, BFirsts, Result).
    % -> -> -> -> -> (первое правило) A = [], B = [8,9,0], AFirsts = [1], BFirsts = [4,4,4]
    % -> -> -> -> -> (второе правило) - безуспешно разбивает А на голову и хвост
    % -> -> -> -> -> (третеье правило) А = [], BHead = 8, BTail = [9,0], AFirst = 1, AFirstsTail = [], BFirsts = [4,4,4]
    % -> -> -> -> -> -> mix([], BTail, AFirstsTail, BFirsts, Result).
    % -> -> -> -> -> -> (первое правило) A = [], B = [9,0], AFirsts = [], BFirsts = [4,4,4] Result = []
    % -> -> -> -> -> Result = [] {возвращает  [AFirst, BHead|Result] = [1, 8|[]] = [1,8]}
    % -> -> -> -> Result = [1,8] {возвращает  [AFirst, BHead|Result] = [1, 7|[1,8]] = [1,7,1,8]}
    % -> -> -> Result = [1,7,1,8] {возвращает  [AFirst, BHead|Result] = [1, 6|[1,7,1,8]] = [1,6,1,7,1,8]}
    % -> -> Result = [1,6,1,7,1,8] {возвращает [AHead, BHead|Result] = [2,5|[1,6,1,7,1,8]] = [2,5,1,6,1,7,1,8]}
    % -> Result = [2,5,1,6,1,7,1,8] {возвращает [AHead, BHead|Result] = [1,4|[2,5, 1,6,1,7,1,8]] = [1,4,2,5,1,6,1,7,1,8]}
    % -> X = [1,4,2,5,1,6,1,7,1,8]
    % X = [1,4,2,5,1,6,1,7,1,8]

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